数据结构单链表.pptx

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

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

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

3、表中指定位序的数据元素演示例子：取单链表中第3个元素值第5页/共35页取元素的基本操作单链表是一种“顺序访问”的结构，为找第 i 个数据元素，必须先找到第(i-1)个数据元素。1.指针p始终指向单链表中第j个结点；2.移动指针，比较 j 和 i，相等则找到。第6页/共35页 Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的链表的头指针，以 e 返回第 i 个元素/GetElem_L算法时间复杂度为:O(ListLength(L)p=L-next;j=1;/p指向第一个结点，j为计数器while(p&jnext;j+;/顺指针向后查找，直

4、到 p 指向第 i 个元素 /或 p 为空if(p&j=i)e=p-data;return OK;/取得第 i 个元素else/第 i 个元素不存在 return ERROR;与顺序表相比，链表不适合于查找第i个元素的操作。第7页/共35页单链表基本操作3、插入（在第i个元素前插入e）单链表中：ai-1 有序对 改变为 和 eaiai-1在单链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第(i-1)个结点的指针。第8页/共35页 Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法 /

5、在链表中第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)第9页/共35页s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;eai-1aiai-1sp第10页/共35页有序对 和 改变为 ai-1aiai+1ai-1单链表基本操作4、删除（第i个元素）在单链表中删除第 i 个结点时，要

6、找到单链表中第(i-1)个结点，修改其指向后继的指针。第11页/共35页 ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq第12页/共35页 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;/寻找第 i-1 个结点，并令 p 指向它。if (p-next&j=i-1)q=p-next;p-

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

8、基本操作6、销毁while(L)p=L-next;free(L);L=p;第16页/共35页单链表基本操作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;第17页/共35页单链表基本操作9、搜索（查找元素）p=L-next;i=1;while(p&p-data!=e)p=p-next;i+;if(p)return i;else return 0;从第一个结点开始搜索搜索成功，返回位序；否则，返回0第1

9、8页/共35页单链表的应用1.建立单链表链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。逆序建立单链表顺序建立单链表新结点插入在头结点的后面，作为重排链表后的第一个结点新结点插入在尾结点的后面，作为重排链表后的最后一个结点第19页/共35页逆序建立单链表操作步骤建立一个带头结点的空单链表；输入数据元素ai，建立新结点p，并把p插入在头结点之后成为第一个结点。重复执行步，直到完成单链表的建立。a1a1a2第20页/共35页void CreateList_N(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateLi

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

11、-next=NULL;/先建立一个带头结点的单链表时间复杂度为O(n)p=L;for(i=1;idata);q-next=p-next;p-next=q;p=q;第23页/共35页单链表的应用2.归并有序链表归并有序单链表La和有序单链表Lb得到有序单链表Lc。链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可。第24页/共35页单链表的应用归并思想：需要设立3个指针pa、pb、pc，其中pa和pb分别指向La和Lb中当前待比较插入的结点，而pc指向Lc中当前最后一

12、个结点（Lc的表头结点设为La的表头结点）。指针的初值为：pa和pb分别指向La和Lb表中的第一个结点，pc指向空表Lc中的头结点。通过比较指针pa和pb所指向的元素的值，依次从La或Lb中“摘取”元素值较小的结点插入到Lc的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。第25页/共35页归并有序单链表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的头结点whil

13、e(pa&pb)/La和Lb均未到达表尾，依次“摘取”两表中值较小的结点插入到Lc的最后if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);算法时间复杂度：O(m+n)算法空间复杂度：O(1)第26页/共35页单链表的应用3.稀疏多项式的运算稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复

14、杂度为O(1)。多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x87 05 17A3 19 88 1B22 7-9 8第27页/共35页单链表的应用稀疏多项式的相加规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。7 05 1711 122 7A第28页/共35页稀疏多项式相加typedef struct PNodefloat coef;int exp

15、n;struct PNode*next;PNode,*Polynomial;用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。第29页/共35页稀疏多项式相加假设头指针pa和pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数较小的项插入到“和多项式”链表中去。第30页/共35页稀疏多项式相加void AddPolyn(Po

16、lynomial&pa,Polynomial&pb)p1=pa-next;p2=pb-next;p3=pa;while(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第31页/共35页稀疏多项式相加 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;else

17、p3-next=p2;p3=p2;p2=p2-next;p3-next=p1?p1:p2;free(pb);第32页/共35页单链表的应用稀疏多项式的创建多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插入到此项的前面，这样即可保证多项式链表的有序性。第33页/共35页稀疏多项式的创建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;第34页/共35页谢谢您的观看！第35页/共35页