《第三章 线性表的链式存储结构教案.doc》由会员分享，可在线阅读，更多相关《第三章 线性表的链式存储结构教案.doc（9页珍藏版）》请在三一文库上搜索。
1、第3章 线性表的链式存储结构l 线性表的链式存储结构l 线性表的应用举例线性表顺序存储结构的特点它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题l 在做插入或删除元素的操作时，会产生大量的数据元素移动；l 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；l 线性表的容量难以扩充。第一节 线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每
2、个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储：存储地址内容直接后继存储地址100b120.首元素位置120c160.144a100.160dNULL.术语表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。单链表简化的图形描述形式headd cba其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值N
3、ULL。NULL值在图示中常用（）符号表示。带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：headd cba链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。在C语言中，实现线性表的链式存储结构的类型定义typedef strcut node /结点类型 EntryTy
4、pe item; struct node *next;NODE;typedef struct /链表类型 NODE *head;LINK_LIST;典型操作的算法实现（1）初始化链表Lint InitList(LINK_LIST *L) L-head=(*NODE)malloc(sizeof(NODE); /为头结点分配存储单元 if (L-head) L-head-next=NULL; return OK; else return ERROR ;（2）销毁链表L void DestoryList(LINK_LIST *L) NODE *p; while (L-head) /依次删除链表中的所
5、有结点 p=L-head; L-head=L-head-next; free(p); （3）清空链表L void ClearList(LINK_LIST *L) NODE *p; while (L-head-next) p=L-head-next; /p指向链表中头结点后面的第一个结点 L-head-next=p-next; /删除p结点 free(p); /释放p结点占据的存储空间 （4）求链表L的长度int ListLength(LINK_LIST L) NODE *p; int len; for(p=L.head, len=0;p-next=NULL; p=p-next,len+); r
6、eturn(len);（5）判链表L空否。 int IsEmpty(LINK_LIST L) if (L.head-next=NULL) return TRUE; else return FALSE; （6）通过e返回链表L中第i个数据元素的内容void GetElem(LINK_LIST L,int i,EntryType *e) NODE *p; int j; if (iListLength(L) exit ERROR; /检测i值的合理性 for (p=L.head,j=0; j!=i;p=p-next,j+); /找到第i个结点 *e=p-item; /将第i个结点的内容赋给e指针所指
7、向的存储单元中（7）在链表L中检索值为e的数据元素NODE *LocateELem(LINK_LIST L,EntryType e) NODE *p; for (p=L.head-next;p&p-item!=e;p=p-next); /寻找满足条件的结点 return(p);（8）返回链表L中结点e的直接前驱结点NODE *PriorElem(LINK_LIST L,NODE* e) NODE *p; if (L.head-next=e) return NULL; /检测第一个结点 for (p=L.head;p-next&p-next!=e;p=p-next); if (p-next=e)
8、 return p; esle return NULL; （9）返回链表L中结点e的直接后继结点NODE *NextElem(LINK_LIST L,NODE* e) NODE *p; for(p=L.head-next;p&p!=e;p=p-next); if (p) p=p-next; return p;（10）在链表L中第i个数据元素之前插入数据元素e int ListInsert(LINK_LIST *L,int i,EntryType e) NODE *p,*s; int j; if (iListLength(L)+1) return ERROR; s=(NODE*)malloc(s
9、izeof(NODE); if (s=NULL) return ERROR; s-item=e; for (p=L-head,j=0;p&jnext;j+); /寻找第i-1个结点 s-next=p-next; p-next=s; /将s结点插入 return OK;（11）将链表L中第i个数据元素删除，并将其内容保存在e中。int ListDelete(LINK_LIST *L,int i,EntryType *e) NODE *p*s; int j; if (iListLength(L) return ERROR; /检查i值的合理性 for(p=L-head, j=0;jnext,j+)
10、; /寻找第i-1个结点 s=p-next; /用s指向将要删除的结点 *e=s-item; p-next=s-next; /删除s指针所指向的结点 free(s); return OK;循环链表若将链表中最后一个结点的next域指向head图2-7 带头结点的循环链表示意图实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。（1）初始化链表CLint InitList(LINK_LIST *CL) CL-head=(*NODE)malloc(sizeof(NODE); if (CL-head) CL-
11、head-next=CL-head; return OK; /让next域指向它自身 else return ERROR ;（2）在循环链表CL中检索值为e的数据元素NODE *LocateELem(LINK_LIST CL,EntryType e) NODE *p; for (p=CL.head-next;(p!=CL.head)&(p-item!=e);p=p-next); if (p!=CL.head) return p; else return NULL ;双向循环链表在循环链表中，访问结点的特点访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。结论：循环链表并不适用于经常
12、访问前驱结点的情况。解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。head用C语言实现双向循环链表的类型定义typedef strcut du_node /双向链表的结点类型 EntryType item; struct du_node *prior,*next;DU_NODE;typedef struct /双向链表类型 DU_NODE *head;prioritemnextDU_LINK_LIST;（1）初始化双向循环链表DLint InitDuList(DU_LINK_LIST *D
13、L) DL-head=(DU_NODE*)malloc(sizeof(DU_NODE); /为头结点分配存储单元 if (DL-head=NULL) return ERROR; DL-head-next=DL-head; /让头结点的next域指向自身 DL-head-prior=DL-head; /让头结点的prior域指向自身 return OK;（2）在双向循环链表DL中，第i个数据元素之前插入数据元素eps在一个结点之前插入一个新结点的过程。在双向循环链表中的p结点之前插入s结点应使用下列语句序列：s-next=p;s-prior=p-prior;p-prior-next=s;p-pr
14、ior=s;完整的算法：int DuListInsert(DU_LINK_LIST *L,int i,EntryType e) DU_NODE *p,*s; int j; if (iListLength(DL)+1) return ERROR; /检测i值的合理性 s=(DU_NODE*)malloc(sizeof(DU_NODE); /为新结点分配存储单元 if (s=NULL) return ERROR; s-item=e; for (p=L-head,j=0;p&jnext;j+); /寻找第i 个结点 s-next=p; s-prior=p-prior; /将新结点插入 p-prior
15、-next=s; p-prior=s; return OK;（3）创建双向循环链表DL。void Create_Du_Link_List(DU_LINK_LIST *DL) if (InitDulist(DL)=ERROR) exit ERROR; scanf(“%d”,&data); for (int i=1;data;i+) DuListInsert(DL,i,data); scanf(“%d”,&data); 第二节 线性表的顺序与链式存储结构的比较顺序存储结构特点：用数组实现，操作简便，但如果在操作时插入，删除元素过多，则需要移动大量元素，会降低程序的效率。链式存储结构特点：用链表实现
16、，操作相对复杂，但对于移动大量元素的情况，可有效地利用空间。第三节 线性表的应用举例约瑟夫（Joseph）问题：编号为1，2，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。数据结构的分析
17、这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。编号密码是否在桌旁的状态131211371421541681741顺序存储结构算法描述让n个人围坐在一张圆桌旁；for (i=1;i=n;i+) 从1开始报数，报到m停止； 报到m的人离开桌子；最终的算法实现#define LIST_MAX_LENGTH 7#define n LIST_MAX_LENGTHtypedef int EntryType; /将EntryType定义为int类型void Joseph(int code,int n)/通过一维数组code带入n个
18、人手中的密码，n是开始就坐在桌旁的人数 SQ_LIST people; int temp,m; /m是报数的上限值 scanf(“%d”,&m); /输入最初的m if (InitList(&people)=ERROR) exit ERROR; for (i=1;i=n;i+) if (ListInsert(&people,i,codei-1)=ERROR) exit ERROR; position=0; /记录当前报数人的编号 for (i=1;i0) count+; while (count!=m); printf(“%d”,position); /输出当前离开桌旁人的编号 GetElem
19、(people,position,&m); people.itemposition-1=-people.itemposition-1; /将密码变为负值 链式存储结构使用一个不带头结点的循环单链表结构。结点结构为：No code next用C语言定义typedef struct /循环链表中每个结点的数据域部分的类型 int No; /编号 int code; /密码INFO;typedef INFO EntryType;算法void Joseph(int code,int n) LINK_LIST people; NODE *position,*pre; /position指向当前报数的结点
20、 if (InitList(&people)=ERROR) exit ERROR; /初始化链表people for (i=1;inext!=people.head) position= NextElem(people,position); scanf(“%d”,&m); /输入最初的m for (i=1;iitem.No); /离开桌子处理 m=position-item.code; pre=PriorElem(people,position); pre-next=position-next; free(position); position= pre; printf(“%d”,position-item.No); /处理最后一个人 free(position);