分享
 
 
 

数据结构拾遗---线性表

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

二 线性表

这一次,我们就来看一看线性表。

我们先给出一个线性表的知识图,它或许并不非常准确,但可以帮助您回忆您在您看过的数据结构教材中所学的大部分内容。事实上,在阅读以下的内容之前,我也鼓励您停下来想一想,想一想线性表那些在您封存的记忆中依然闪光的部分。

我无意和您对此图的细节划分标准进行辩论,也无意于全部讨论它们,既然是“拾遗”,我以对您有所启发为乐,希望能提出些容易让人忽视的问题,促使您更好、更主动的去学习和思考。

1,数据组织内在的逻辑联系

一个小蚂蚁,急奔在一望无际的沙滩上。它有一个棘手的任务,就是,它需要考察这沙地上所有的沙子。万里平沙呵,我所走之处,都是千差万别的沙粒,让我如何开始考察呀!风儿建议它,以某点为中心,给所有的沙子建立一个“序”:若半径为r,同在此圆周上的为等,其内的为小,其外的为大,借r去考察沙子们,断不会无处下手了。

如果沙子可比喻数据,那么建立一种序,亦即建立一种模型,是我们组织数据的第一步,否则我们也要面临“万里平沙”的局面了。在所有的序中,“线性”当是最简单的一种。我们今日所要谈的线性表,就基本上是基于这种关系建立的一类数据结构。

对于数据的集合A={…,x,y,z,…},|A|=n,我们映射其为An={a0,a1,…,an-1},且对于元素

ai,1<=i<=n-2,

和它有关系的只有ai-1,ai+1,前者称其为前驱,后者称其为后继,都是唯一的。这是线性表的基本逻辑特征。

抽象出一种序(或关系)出来,往往是计算机解决问题的一种基本方法。数据结构的发展与演化,也就是从数据存储与组织的角度,深刻发展、展示这一思想的。

我们看线性表。可以图示说明。对于基本部分,如下图:

如果对存取加以限制,就是我们计算机科学中使用非常广泛的两种数据结构:

线性表检索某个数据的时候,一般是顺序搜索下一个,直到搜索到该数据为止。换句话,一次检索或一次更新的时候需要的时间是线性的,为了解决这个问题,可以扩张为一个基于概率的数据结构,跳跃表。而对于线性表的元素,如果亦允许之满足一定的结构,则可以扩张为广义表,这个数据结构定义满足很好的递归性。见下图:

图形的背后的不变的概念,表明它们是由同一个模型变化而来。抽象的魅力,还远不止于此。我们以后有机会,再在计算机科学的经典例子中说明。对于串和矩阵,稀疏矩阵,有些算法,值得大家注意。

对于这些基本内容不熟悉的读者,请您查阅有关数据结构书。

2,线性表实现时要注意的地方

我们不会详细谈线性表的实现。诸如链表实现的时候,您是使用c语言,还是使用c++语言进行封装,诸如链表的插入节点的时候,您应注意指针的顺序,诸如线性表,您是否要加一个头节点以统一操作;并非它们不是重点,它们恰恰是基础部分,但我想这是您首先要熟悉的。

(1)实现的时候,我想给您总结一下,接着图1的知识结构,线性表所有可常见的形式。

链表的实现。链表的形式,有A={单链表、双向链表}, B={循环,不循环}之分。则前后组合,类别为:B×A,共有四种。是否加头节点,是一个技巧。

栈与队列。栈与队列,可用顺序表实现,也可用链表实现。另外,循环队列与优先级队列,是大家所熟悉的。但有意思的,循环栈,大家是少见的;想一想,如下棋等活动,只允许连续后退n步,那么保存刚经历的活动n步,就可以如此实现了。建议大家写程序试试。

跳跃表与广义表。它们的实现,大家可见于《数据结构与算法分析》(张铭等译)和《数据结构(用面向对象方法与C++描述)》(殷人昆等编著)。

(2)指针的意义,在于存储地址。所以实现上,不仅指针变量可以为之,诸如整型变量也可以作为指针之用。所以链表等,也可以使用复杂的顺序存储方式实现。

(3)如下图,一个执行了一段时间后的链表:

对于c语言或c++语言实现的链表等数据结构,申请了内存资源,当内存资源回收时,问题就出来了。即使经过了细心的设计,没有出现错误;但因为节点(一个小的内存单元)是经过多次申请的,当回收时需要一个一个的回收,速度就会特别慢。如果节点数目巨大,则速度通常是难以忍受的。

这个问题的解决,通常是申请内存资源时,一次性申请一个较大的单元,然后作为节点分配的缓存区,当使用完毕后,再一次申请同样一个较大的单元。对这些较大的单元进行管理,回收时不再以一个节点为单位,而以该较大的单元为单位。速度就可以提升。

(4) 只有当必要的时候,否则就不要使用复杂的数据结构。解决问题以方便为准。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有