数据结构单链表.ppt

《数据结构单链表.ppt》由会员分享，可在线阅读，更多相关《数据结构单链表.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 线性表链表单链表定义定义特点特点C C描述描述基本形态基本形态基本操作实现基本操作实现一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即指针指针）。1.数据元素在“逻辑逻辑关系上的相邻相邻”用“指针指针”来表示。2.单链表 中访问数据元素时需从头开始“顺序访问顺序访问”。3.比顺序表的优势在于，提供高效地重排重排数据项的能力。a1a2a3a4anL单链表的C描述 typedef struct LNode ElemType data;/数据域 struct LNode *next;/指针域 LNode,*LinkList;LinkList L；/

2、L/L 为单链表的头指针为单链表的头指针头指针指向单链表中的第一个结点第一个结点用指针表示链接，用结构体表示结点，结点是由数据项和用指针表示链接，用结构体表示结点，结点是由数据项和链接组成的，链接是指向下一结点的指针。链接组成的，链接是指向下一结点的指针。单链表的基本形态空表空表非空表非空表为了操作方便，在第一个结点之前虚加一个为了操作方便，在第一个结点之前虚加一个“头结点头结点”哑元结点哑元结点LL-next=NULL;不允许删除操作不允许删除操作a1a2a3anL可以进行插入、删除操作可以进行插入、删除操作单链表基本操作1、初始化（动态分配）Stutas InitList(LinkList

3、&L)L=(LinkList)malloc(sizeof(LNode);if(!L)exit(overflow);L-next=NULL;return OK;L头结点头结点L211830754256pppj1 2 3单链表基本操作2、取单链表中指定位序的数据元素演示例子：取单链表中第3个元素值取元素的基本操作单链表是一种单链表是一种“顺序访问顺序访问”的结构，为找第的结构，为找第 i i 个数据个数据元素，必须先找到第元素，必须先找到第(i-1 i-1)个数据元素。个数据元素。1.1.指针指针p p始终指向单链表中第始终指向单链表中第j j个结点；个结点；2.2.移动指针，比较移动指针，比较

4、j j 和和 i i，相等则找到。，相等则找到。Status GetElem_L(LinkList L,int i,ElemType&e)/L是是带头结点的点的链表的表的头指指针，以，以 e 返回第返回第 i 个元素个元素/GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p=L-next;j=1;/p p指向第一个指向第一个结点，点，j j为计数器数器while(p&jnext;j+;/顺指指针向后向后查找，直到找，直到pp指向第指向第ii个元素个元素/或或pp为空空if(p&j=i)e=p-data;return OK;/取得第 i 个元素else/第 i

5、个元素不存在 return ERROR;与顺序表相比，链表不适合与顺序表相比，链表不适合于查找第于查找第i i个元素的操作。个元素的操作。单链表基本操作3、插入（在第i个元素前插入e）单链表中：ai-1 有序对有序对 改变为改变为 和和 eaiai-1在单链表中在单链表中插入结点插入结点只需要只需要修改指针修改指针。若要在第。若要在第 i i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第(i-1)(i-1)个结点的指针。个结点的指针。Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的点的单链表的表的头指指针，本算法

6、，本算法 /在在链表中第表中第i 个个结点之前插入新的元素点之前插入新的元素 e /LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)else return ERROR;p=L;j=0;while(p&j next;+j;/寻找第寻找第(i-1)个结点个结点if(p&j=i-1)s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;eai-1aiai-1sp有序有序对 和和改改变为 ai-1aiai+1ai-1单链表基本操作4、删除（第i个

7、元素）在单链表中在单链表中删除第删除第 i i 个结点个结点时，要找到单链表中第时，要找到单链表中第(i-1i-1)个结点，个结点，修改其指向后继的指针。修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq Status ListDelete_L(LinkList&L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&j next;+j;

8、/寻找第 i-1 个结点，并令 p 指向它。if (p-next&j=i-1)q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;else return ERROR;/删除位置不合理对比单链表和顺序表的基本操作插入和删除的简单性是链表存在的理由插入和删除的简单性是链表存在的理由只修改相关结点的指向保持链表特性单链表的访问方式是顺序访问单链表的访问方式是顺序访问查找第i个数据项的代价，沿着链表，一个一个结点地访问，直到找的这个数据项算法时间复杂度：O(ListLength(L)单链表基本操作5、清空while(L-next)p=L-

9、next;L-next=p-next;free(p);算法时间复杂度：O(ListLength(L)单链表基本操作6、销毁while(L)p=L-next;free(L);L=p;单链表基本操作7、判空if(L-next=NULL)return TRUE;else return FALSE;8、求表长int ListLength(LinkList L)p=L-next;i=0;while(p)i+;p=p-next;return i;单链表基本操作9、搜索（查找元素）p=L-next;i=1;while(p&p-data!=e)p=p-next;i+;if(p)return i;else re

10、turn 0;从第一个结第一个结点点开始搜索搜索成功，返回搜索成功，返回位序位序；否则，返回否则，返回0 0单链表的应用1.建立单链表链表是一个动态结构，它不需要预分配空间，因此生成链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是链表的过程是一个结点一个结点“逐个插入逐个插入”的过程。的过程。逆序建立单链表逆序建立单链表顺序建立单链表顺序建立单链表新结点新结点插入在头插入在头结点的结点的后面，作为重排链表后后面，作为重排链表后的的第一个结点第一个结点新结点新结点插入在尾插入在尾结点的结点的后面，作为重排链表后后面，作为重排链表后的的最后一个结点最后一个结点逆序建立单链表操作步骤操作

11、步骤建立一个带头结点的空单链表；建立一个带头结点的空单链表；输入数据元素输入数据元素ai，建立新结点，建立新结点p，并把，并把p插插入在头结点之后成为第一个结点。入在头结点之后成为第一个结点。重复执行重复执行步，直到完成单链表的建立。步，直到完成单链表的建立。a1a1a2void CreateList_N(LinkList&L,int n)/逆序输入n个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表fo

12、r(i=1;i data);/输入元素值 p-next=L-next;L-next=p;/插入顺序建立单链表操作步骤操作步骤建立一个带头结点的空单链表；建立一个带头结点的空单链表；输入数据元素输入数据元素ai，建立新结点，并把其插入，建立新结点，并把其插入在尾结点在尾结点p之后成为最后一个结点。之后成为最后一个结点。重复执行重复执行步，直到完成单链表的建立。步，直到完成单链表的建立。a1pa1ppa2pa3pppan顺序建立单链表：即新元素插入表尾L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表时间复杂度为O(n)p=L;f

13、or(i=1;idata);q-next=p-next;p-next=q;p=q;单链表的应用2.归并有序链表归并有序单链表归并有序单链表LaLa和有序单链表和有序单链表LbLb得到有序单链表得到有序单链表LcLc。链表结点之间的关系是通过指针指向建立起来的，链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程可以直接利用原来两个表的存储空间，合并过程中只需要把中只需要把La和和Lb两个链表中的结点重新进行链两个链表中的结点重新进行链接即可。接即可。单链表的应用归并思想：需要设

14、立需要设立3个指针个指针pa、pb、pc，其中，其中pa和和pb分别指分别指向向La和和Lb中当前待比较插入的结点，而中当前待比较插入的结点，而pc指向指向Lc中当前最后一个结点（中当前最后一个结点（Lc的表头结点设为的表头结点设为La的表头的表头结点）。指针的初值为：结点）。指针的初值为：pa和和pb分别指向分别指向La和和Lb表中的第一个结点，表中的第一个结点，pc指向空表指向空表Lc中的头结点。通中的头结点。通过比较指针过比较指针pa和和pb所指向的元素的值，依次从所指向的元素的值，依次从La或或Lb中中“摘取摘取”元素值较小的结点插入到元素值较小的结点插入到Lc的最后，的最后，当其中一

15、个表变空时，只要将另一个表的剩余段链当其中一个表变空时，只要将另一个表的剩余段链接在接在pc所指结点之后即可。所指结点之后即可。归并有序单链表void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;/pa和pb初值指向第一个结点Lc=La;/用La的头作为Lc的头结点pc=Lc;/pc初值指向Lc的头结点while(pa&pb)/La和Lb均未到达表尾，依次“摘取”两表中值较小的结点插入到Lc的最后if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-ne

16、xt=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);算法时间复杂度：O(m+n)算法空间复杂度：O(1)单链表的应用3.稀疏多项式的运算稀疏多项式可以抽象成一个线性表。稀疏多项式的相加稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为合并过程空

17、间复杂度为O(1)O(1)。多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x87 05 17A3 19 88 1B22 7-9 8单链表的应用稀疏多项式的相加规则：对于两个多项式中所有指数相同的项，对应系数规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为相加，若其和不为零，则作为“和多项式和多项式”中的一项插中的一项插入到入到“和多项式和多项式”链表中去；对于两个多项式中指数不链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到相同的项，则将指数值较小的项插入到“和多项式和多项式”链链表中去。表中去。“和多项式和多项式”链

18、表中的结点无需生成，而应该链表中的结点无需生成，而应该从两个多项式链表中摘取。从两个多项式链表中摘取。7 05 1711 122 7A稀疏多项式相加typedef struct PNodefloat coef;int expn;struct PNode*next;PNode,*Polynomial;用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。稀疏多项式相加假设头指针假设头指针papa和和pbpb的单链表分别为多项式的单链表分别为多项式A A和和B B的存储结的存储结构，指针构，指针p1p1和和p2p2分

19、别指向分别指向A A和和B B中当前进行比较的某个结中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到项，对应系数相加，若其和不为零，则将插入到“和多和多项式项式”链表中去；对于指数不相同的项，则通过比较将链表中去；对于指数不相同的项，则通过比较将指数较小的项插入到指数较小的项插入到“和多项式和多项式”链表中去。链表中去。稀疏多项式相加void AddPolyn(Polynomial&pa,Polynomial&pb)p1=pa-next;p2=pb-next;p3=pa;while(

20、p1&p2)if(p1-expn=p2-expn)sum=p1-coef+p2-coef;if(sum!=0)p1-coef=sum;p3-next=p1;p3=p1;p1=p1-next;r=p2;p2=p2-next;free(r);else稀疏多项式相加 r=p1;p1=p1-next;free(r);r=p2;p2=p2-next;free(r);else if(p1-expnexpn)p3-next=p1;p3=p1;p1=p1-next;elsep3-next=p2;p3=p2;p2=p2-next;p3-next=p1?p1:p2;free(pb);单链表的应用稀疏多项式的创建多

21、项式的创建方法类似于链表的创建方法，区别在于多多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插入到此项的前面，这样即可保证多项式项，将输入项插入到此项的前面，这样即可保证多项式链表的有序性。链表的有序性。稀疏多项式的创建void CreatePolyn(Polynomial&p,int n)p=(Polynomial)malloc(sizeof(PNode);p-next=NULL;for(i=1;icoef,&s-expn);pre=p;q=p-next;while(q&q-expnexpn)pre=q;q=q-next;s-next=q;pre-next=s;