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

1,2.3 线性表的链式存储结构,线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 l 在做插入或删除元素的操作时，会产生大量的数据元素移动； l 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； l 线性表的容量难以扩充。,2,线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2所示的形式存储：,3,线性表链式存储结构示意图,4,术语 表示每个数据元素的两部分信息组合在一起被称为结点； 其中表示数据元素内容的部分被称为数据域（data）； 表示直接后继元素存储地址的部分被称为指针或指针域（next）。 单链表简化为下图描述形式,单链表结构示意图,5,其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。 带头结点的单链表 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。（头结点中数据域根据需要存放一些便于操作的信息，如元素个数等；或不存放任何信息。其引入使得所有链表（即使是空表）的值都不为NULL。）如下图所示：,带头结点的单链表结构示意图,6,链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,7,在C语言中，实现线性表的链式存储结构的类型定义 typedef strcut LNode /结点类型 ElemType data; struct LNode *next; LNode; typedef struct /链表类型 LNode *head; LinkList;,8,2.3.2 典型操作的算法实现 1. 初始化链表L：创建带头结点的空链表。 int InitList(LinkList *L) L-head=(*LNode)malloc(sizeof(LNode); /为头结点分配存储单元 if (L-head) L-head-next=NULL; return OK; else return ERROR ; ,9,2. 销毁链表L：删除链表中包括头结点在内所有结点。 void DestoryList(LinkList *L) LNode *p; while (L-head) /依次删除链表中的所有结点 p=L-head; L-head=L-head-next; free(p); /从头结点开始删，直到删完为止。,10,3. 清空链表L ：删除链表中除头结点外的所有结点。 void ClearList(LinkList *L) LNode *p; while (L-head-next) p=L-head-next; /p指向链表中头结点后面的第一个结点 L-head-next=p-next; /删除p结点 free(p); /释放p结点占据的存储空间 /从头结点后的第一个结点开始删，直到删完为止。,11,4. 求链表L的长度 int ListLength(LinkList L) LNode *p; int len; for(p=L.head, len=0;p-next=NULL; p=p-next,len+); return(len); 循环条件表达式 重复执行的语句 ,12,5. 判断链表L是否为空。 int ListEmpty(LinkList L) if (L.head-next=NULL) return TRUE; else return FALSE; ,13,6. 通过e返回链表L中第i个数据元素的内容 void GetElem(LinkList L,int i,EntryType *e) LNode *p; int j; /j为计数器，记载所经过的结点数目 if (iListLength(L) exit ERROR; /检测i值的合理性 for (p=L.head,j=0; j!=i;p=p-next,j+); /找到第i个结点 *e=p-data; /将第i个结点的内容赋给e指针所指向的存储单元中 ,14,7. 在链表L中检索值为e的数据元素 LNode *LocateELem(LinkList L,EntryType e) LNode *p; for (p=L.head-next;p ,15,8. 返回链表L中结点e的直接前驱结点 LNode *PriorElem(LinkList L,LNode* e) LNode *p; if (L.head-next=e) return NULL; /检测第一个结点 for (p=L.head;p-next ,16,9. 返回链表L中结点e的直接后继结点 LNode *NextElem(LinkList L,LNode* e) LNode *p; for(p=L.head-next;p ,17,10. 在链表L中第i个数据元素之前插入数据元素e int ListInsert(LinkList *L,int i,EntryType e) LNode *p,*s; int j; if (iListLength(L)+1) return ERROR; s=(LNode*)malloc(sizeof(LNode);/s为存放e的结点 if (s=NULL) return ERROR; s-data=e; for (p=L-head,j=0;p /P25图2-9。,18,11. 将链表L中第i个数据元素删除，并将其内容保存在e中。 int ListDelete(LinkList *L,int i,EntryType *e) LNode *p*s; int j; if (iListLength(L) return ERROR; /检查i值的合理性 for(p=L-head, j=0;jnext,j+); /寻找第i-1个结点 s=p-next; /用s指向将要删除的结点 *e=s-data; p-next=s-next; /删除s指针所指向的结点 free(s); return OK; /P26图2-10。,19,2.3.3 循环链表 若将链表中最后一个结点的next域指向头结点，如下图： 实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。,带头结点的循环链表示意图,20,1. 初始化链表CL：即只有一个头结点，并且头结点的next域指向它自身。 int InitList(LinkList *CL) CL-head=(*LNode)malloc(sizeof(LNode); if (CL-head) CL-head-next=CL-head; return OK; /让next域指向它自身 else return ERROR ; ,21,2. 在循环链表CL中检索值为e的数据元素 LNode *LocateELem(LinkList CL,EntryType e) /如果所有结点都没有满足条件，则P停在头结点；而单链表中，P停在最末一个结点。 LNode *p; for (p=CL.head-next;(p!=CL.head) ,22,*与单链表对比其他操作如下：,1、关于销毁链表、清空链表、求链表长度、返回第i个元素的值、插入元素、删除元素等操作，与单链表基本相似。 2、判断链表是否为空： if (cl.head-next=cl.head) return TRUE; else return FALSE; 3、返回结点e的直接前驱结点与直接后继结点： 只是判断循环结束的条件不同：如果找不到结点e，循环链表结束在头结点，而单链表结束在最后一个结点。 *思考题。有的时候，若在循环链表中设立尾指针而不设立头指针，可使某些操作简化。如合并两个循环链表时。图示表达：P28图2.13。,23,2.3.4 双向循环链表 在循环链表中，访问结点的特点： 访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。 结论：循环链表并不适用于经常访问前驱结点的情况。 解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。 双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,24,(a),(b),25,用C语言实现双向循环链表的类型定义 typedef strcut DuLNode /双向链表的结点类型 EntryType data; struct DuLNode *prior,*next; DuLNODE; typedef struct /双向链表类型 DuLNode *head; DuLinkList;,26,（1）初始化双向循环链表DL int InitDuList(DuLinkList *DL) DL-head=(DuLNode*)malloc(sizeof(DuLNode); /为头结点分配存储单元 if (DL-head=NULL) return ERROR; DL-head-next=DL-head; /让头结点的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-next=s;/p的前驱结点的next域指向s p-prior=s;/ p-prior域指向s,28,图 2-9,29,完整的算法： int DuListInsert(DuLinkList *L,int i,EntryType e) DuLNode *p,*s; int j; if (iListLength(DL)+1) return ERROR; /检测i值的合理性 s=(DuLNode*)malloc(sizeof(DuLNode); /为新结点分配存储单元 if (s=NULL) return ERROR; s-data=e; for (p=L-head,j=0;p ,30,（3）创建双向循环链表DL。 void Create_DuLinkList(DuLinkList *DL) /从键盘输入数据元素，直到输入0为止 if (InitDulist(DL)=ERROR) exit ERROR; scanf(“%d”, ,31,本节小结与作业,链式存储结构特点：1、碎片可以得到充分利用。2、只能顺序存取数据元素，不能随机存取。 但是克服了顺序存储的缺点：1、插入与删除数据元素时不用移动大量的数据元素。2、空间浪费解决了。3、可以随意扩充线性表的容量。 P37： 2.4 2.5 2.6,32,2.4 线性表的两种存储结构比较,看书。 作业：P37习题：2.1,2.2,2.3,33,2.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，5，4，7，6，1。 数据结构的分析 这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。,36,37,顺序存储结构 算法描述 让n个人围坐在一张圆桌旁； for (i=1;i=n;i+) 从1开始报数，报到m停止； 报到m的人离开桌子； 最终的算法实现 #define LIST_MAX_LENGTH 7 #define n LIST_MAX_LENGTH typedef int ElemType; /将ElemType定义为int类型 void Joseph(int code ,int n),38,/通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数 sqList people;/定义顺序表people int temp,m; /m是报数的上限值 scanf(“%d”, /记录当前报数人的编号,39,for (i=1;i0) count+; while (count!=m); printf(“%d”,position); /输出当前离开桌旁人的编号 GetElem(people,position, /并将其密码变为负值，即删除了此人 ,40,链式存储结构 使用一个不带头结点的循环单链表结构。结点结构为：,41,用C语言定义 typedef struct /循环链表中每个结点的数据域部分的类型 int No; /编号 int code; /密码 INFO; typedef INFO ElemType;,42,算法 void Joseph(int code,int n) LinkList people;/定义单向循环链表people LNode *position,*pre; /position指向当前报数的结点，pre指向其前驱结点 if (InitList(,43,position=people.head; /（已设尾指针） /让position指向最后一个结点，以便报数从第一个开始 while (position-next!=people.head) /不是空链表的话 position= NextElem(people,position); /取后继结点，即第一个结点 scanf(“%d”,44,printf(“%d”,position-elem.No); /离开桌子处理，输出其编号 m=position-elem.code; /将离开者密码给m pre=PriorElem(people,position);/取其前驱结点给pre pre-next=position-next; free(position);/ 这三步是删除该离开者 position= pre;/将前驱结点指针赋值给position printf(“%d”,position-elem.No); /处理最后一个人，即输出最后一个人的编号 free(position);/并释放其空间