线性表的链式存储结构.ppt

1、1，2.3线性表的链记忆结构、线性表顺序记忆结构的特征是简单方便的记忆方式。 必须将线性表的数据要素依次存储在连续的存储器单元中，以数据要素的存储顺序来表现对应的逻辑顺序，该存储方式为静态存储形式。 曝露的问题l在进行插入或删除元素的操作时，会移动大量的数据元素。对于l长度变化较大的线性表，必须一次分配足够的存储空间，但这些空间往往不能充分利用。l线式时间修正的容量很难扩展。 另外，线性表的链式存储结构线性表的链式存储结构是指在任意存储器单元的集合(可以是连续的或者不连续的)中存储线性表中的数据元素。 为了反映数据元素之间的逻辑关系，给每个数据元素添加指示其直接后续元素的存储位置的信息，以及其

2、具体内容。 假设存在线性列表(a、b、c、d )，则以在图2中示出的形式存储直接的后续元素，该直接的后续元素表示数据元素的内容，可以通过将、3、线性列表链接存储结构的图像、4、表示各数据元素的两种信息组合来称为节点单链接表简化如下图所示。 单链表的结构图，5。 其中head是指单链表中的第一个节点。 这是单链接表操作的入口点。 因为最后一个节点没有直接后续节点，所以指针字段包含一个特殊值NULL。 NULL值由图标中常用的()符号表示。 开头节点的单链表，为了使链表的操作简单，在链表的最初的节点前附加节点，多称为开头节点。 这消除了对链表中第一个节点的特殊处理。 (必要时，标头节点内的数据字段

3、中存储有元素数等易于操作的信息，或者不保存任何信息。 引入了即使是空表，所有链表的值也不为空。 如下图所示，开头节点的单链表结构图像、6、链存储器结构的特征(1)线性表中的数据要素向存储单元的存储顺序和逻辑顺序不一定一致(2)在操作线性列表时，以开头指针进入链表， 仅通过在各节点的指针字段中向后方扫描该佗节点，将具有搜索最初的节点所花费的时间与搜索最后的节点所花费的时间不同这一特征的访问方式称为逐次访问方式。 7、在c语言中，实现线性表的链内存结构的类型定义typedef strcut LNode /节点型ElemType data； 结构节点*下一个； LNode； typedef stru

4、ct /链接表类型LNode *head； 链接列表； 8、8、8,2.3.2典型操作的算法是1 .初始化链接表l :创建起始节点的空链接表。 英特尔列表(链接列表* l ) l-head=(* lnode )大小(长度(长度) )。 /向标题节点分配存储单元if (L-head) L-head-next=NULL。 回复正常； 激活恢复错误； 9、2 .放弃链表l :删除链表中包含标题节点的所有节点。 voiddestorylist (链接列表* l )节点* p。 依次删除while (L-head) /链表中的所有节点p=L-head。 l-head=l-head -下一个； 自由(p

5、)； /从第一个节点删除，直到删除完成。10、3 .空链表l :删除链表开头节点以外的所有节点。 voidclearlist (链接列表* l )节点* p。 前方下一个(l-head-next ) p=前方下一个(l-head-next )。 /p指向链表中第一个节点后面的第一个节点L-head-next=p-next。 /p节点自由(p )； 释放/p节点占用的内存空间/从起始节点之后的第一个节点开始删除，直到删除完成。 11、4 .求出链接表l的长度intlist length (链接列表l ) lnode * p。 英特兰； 前方(p=l .头部，len=0； p-next=空值； p

6、=p -下一个，len )； 返回(长度)； 循环条件式反复执行的语句12、5 .判断链表l是否为空。英特尔列表实例if (l .头下一个=空)返回真。 激活返回失败；13、6 .以e返回链接表l中第I个数据元素的内容void get elem (链接列表l、入口I、入口类型* e ) lnode * p。 英特尔； /j是计数器，记载所经过的节点数if (iListLength(L) exit ERROR。 检测/i值的合理性for (p=L.head，j=0； j！=i； p=下一个，j )；/找到第I个节点*e=p-data；/将第I个节点的内容分配给e指针指向的存储单元，14，7 .链

7、接表l中值为e的数据要素lnode * locate elem (链接列表l，输入类型e ) lnode * p； 下一个(p=l .头部)； p、15、8 .链接表l中结点e的直接前驱结点lnode * prior elem (链接列表l、LNode* e) LNode *p 返回空值(l .头下一个=e )。 /第一个节点for (p=l .头； p-next，16，9 .返回链接表l中紧接节点e之后的节点lnode * Nextel em (链接列表l，链接节点* e ) lnode * p。 下一个(p=l .头部)； p，17，10 .在链接表l中的第I个数据元素之前插入数据元素e

8、int list insert (链接列表l，int i，进入类型e ) lnode * p，*s。 英特尔； if (列表长度(l )1)返回错误。 其中s=(lnode * ) malloc (尺寸(lnode ) )/s是存储e的节点if (s=空)返回错误。 s数据=e； 前方(p=l前头，j=0； p /P25图2-9。18、11 .删除链表l中第I个数据元素，将其内容保存在e中。 列表删除(链接列表* l、英特尔、进入类型* e )节点* p * s。 英特尔； if (列表长度(l ) )返回错误。 /检查I值的合理性for(p=L-head，j=0； j下一个，j )； /i-

9、1查找第一个节点s=p-next。 /用s指示要删除的节点*e=s-data； p下一个=s下一个； /s删除指针指向的节点free(s )； 回复正常； /P26图2-10。19、2.3.3循环链接表将链接表最后一个节点的next域指向报头节点时，如下图所示实现循环链接表的类型定义与单链接表完全相同，其全部操作也与单链接表相似只是判断链表结束的条件不同而已。 接下来，列举两个循环链表操作的算法示例。开头节点的循环链接表示意图、20、1 .初始化链接表CL :即开头节点仅1个，开头节点的next域指向其本身。 intinitlist (链接列表* cl ) cl-head=(* lnode )

10、大小(大小(节点) )。 接下来，接下来，接下来，接下来。 回复正常； 确保next域指向其自身的else return ERROR。 另外，2-1、2-2 .在循环链接表CL中，如果值为e的数据元素的所有节点都不满足条件，则p终止于报头节点。 在单链表中，p停止在最后一个节点。 LNode *p； 下一个(p=cl .头部)； (p！=CL.head )，22，*与单链表相比的其他操作，1 .对于单链表的废弃，使链表为空，求链表的长度，返回第I个元素的值，插入元素，删除元素等的操作，以及2、判断链接表是否为空： if (cl.head-next=cl.head )返回真； 激活返回失败； 3

11、 .转移至节点e的直接前驱节点和直接后续节点：判断循环结束的条件只不同：如果没有发现节点e，则循环链路表在开头节点结束，单链路表在最后的节点结束。 *思考题。 在某些情况下，在循环链表中不设置标头指针而设置尾指针可以简化某些操作。 例如，在结合两个循环链表的情况下。 图示的表现： P28图2.13。23、2.3.4双向循环链表在循环链表中，接入节点的特征：仅接入后续节点后退一步，接入前驱节点需要进行一圈。 结论循环链表不适用于经常访问前驱节点。 解决方案：如果需要频繁同时访问前驱节点和后续节点，请使用双向链接表。 所谓的双向链表。 双向链接表是指每个节点都有两个指针域。 一个指后续节点，另一个

12、指前驱节点。用、24、(a )、(b )、25、c语言实现的双向环路链接表的类型定义typedef strcut DuLNode /双向链接表的节点类型EntryType data； 强制双节点*上一级，*下一级； 杜洛德； 类型结构/双向链接表类型DuLNode *head； 杜林基斯特； (1)对双向循环链路表dlintinitdulist (dulin klist * dl ) dl-head=(du lnode * ) malloc (sizeof (dulnoof )进行初始化/在报头节点中对存储单元if (dl-head )进行初始化dl-head -下一个=dl-head； /头

13、节点的next域指向自己的DL-head-prior=DL-head； /使标头节点的prior域指向自己的return OK。27、(2)在双向循环链路表DL中，在第I个数据元素之前插入数据元素e的节点之前插入新节点的过程。 要在双向循环链路表的p节点前插入s节点，请使用以下语句序列： P30图2.16 s-next=p； /s的next域指向p节点s-prior=p-prior。 /p-prior被分配给s-prior p-prior -下一个=s。 /p的前驱结点的面向next域的s p-prior=s； /p-prior域点s、28、图2-9、29、完整算法：双列表* l、入口I、入口

14、类型磁盘int i； 清单长度(dl ) 1回复器。 检测/i值的合理性s=(du lnode * ) malloc (sizeof (du lnode ) )； /向新节点分配存储单元if (s=null )返回错误。 s数据=e； 前方(p=l前头，j=0； (3)创建双向循环链接表dl.void create _ dulin klist (dulin klist * dl )/从键盘输入数据元素，直到输入0为止2 .只能依次访问数据要素，不能随机访问。 但是，顺序存储的缺点是： 1、插入和删除数据元素时不需要移动大量数据元素。 2 .解决了空间的浪费。 3、可自由扩展线性时间修正的容量。

15、 p37:2.42.52.6、32、2.4线性表两种内存结构进行比较，读书。 作业： P37练习题：2.1、2.2、2.3、33、2.5线性表的应用例，教材上的5个例子的分析。 下节课向同学说明分析。 你必须做到让大家都能听懂。 讨论。34，2.5线性时间校正的应用实例，约瑟夫(Joseph )问题：编号1，2， n的n人按时间校正坐在圆桌旁，每个人都有一个密码(正整数)。 首先，输入正整数作为计数上限值m，然后，从第一个人开始顺时针方向从1开始顺序计数，报告m的人离开桌子旁边，他的手的密码作为新的m值，顺时针方向从下一个坐在桌子旁边的人开始顺时针方向从1开始重新计数，全员离开桌子旁边35，假设7人，号码从1到7，他们手中的暗号分别是3，1，7，2，4，8，4，前m=2，根据报纸，这7人离开桌子旁边的顺序应该是2，3，分析数据结构这个问题的主角是n人，谁假设有7个人，他们的信息可以表示如下。36、37、顺序存储结构算法的描述是，使n个人坐在圆桌旁for (i=1； i=n； I )从1开始报告，报告m停止。 报告m的人离开表的最终的修正算法实现# define list _ max _ length7# definenlist _ max _ lengthtypedefintelemtype。 将ElemType定义为通过int型void Joseph(int code，int