《数据结构单链表》PPT课件.ppt

《《数据结构单链表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构单链表》PPT课件.ppt（35页珍藏版）》请在三一办公上搜索。

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

2、用结构体表示结点，结点是由数据项和链接组成的，链接是指向下一结点的指针。,单链表的基本形态,空表非空表,为了操作方便，在第一个结点之前虚加一个“头结点”,哑元结点,L,L-next=NULL;,不允许删除操作,L,可以进行插入、删除操作,单链表基本操作,1、初始化（动态分配）,Stutas InitList(LinkList,j,1,2,3,单链表基本操作,2、取单链表中指定位序的数据元素,演示例子：取单链表中第3个元素值,取元素的基本操作,单链表是一种“顺序访问”的结构，为找第 i 个数据元素，必须先找到第(i-1)个数据元素。,1.指针p始终指向单链表中第j个结点；2.移动指针，比较 j

3、和 i，相等则找到。,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/顺指针向后查找，直到 p 指向第 i 个元素/或 p 为空,if(p,与顺序表相比，链表不适合于查找第i个元素的操作。,单链表基本操作,3、插入（在第i个元素前插入e）,单链表中：,有序对 改变为 和,在单链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第(i

4、-1)个结点的指针。,Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,算法的时间复杂度为:,O(ListLength(L),else return ERROR;,p=L;j=0;while(p/寻找第(i-1)个结点if(p&j=i-1),s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;,s,p,有序对 和 改变为,单

5、链表基本操作,4、删除（第i个元素）,在单链表中删除第 i 个结点时，要找到单链表中第(i-1)个结点，修改其指向后继的指针。,q=p-next;p-next=q-next;e=q-data;free(q);,p,q,Status ListDelete_L(LinkList&L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点/ListDelete_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p-next/寻找第 i-1 个结点，并令 p 指向它。if(p-next&j=i-1),q=p-next;p-nex

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

7、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,从第一个结点开始搜索,搜索成功，返回位序；否则，返回0,单链表的应用,1.建立单链表,链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。,逆序建立单链表,顺序建立单链表,新结

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

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

10、,单链表的应用,2.归并有序链表,归并有序单链表La和有序单链表Lb得到有序单链表Lc。,链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可。,单链表的应用,归并思想：,需要设立3个指针pa、pb、pc，其中pa和pb分别指向La和Lb中当前待比较插入的结点，而pc指向Lc中当前最后一个结点（Lc的表头结点设为La的表头结点）。指针的初值为：pa和pb分别指向La和Lb表中的第一个结点，pc指向空表Lc中的头结点。通过比较指针pa和pb所指向的元素的值，依次从La或

11、Lb中“摘取”元素值较小的结点插入到Lc的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。,归并有序单链表,void MergeList_L(LinkList,算法时间复杂度：,O(m+n),算法空间复杂度：,O(1),单链表的应用,3.稀疏多项式的运算,稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为O(1)。,多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8,单链表

12、的应用,稀疏多项式的相加,规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。,11 1,22 7,A,稀疏多项式相加,typedef struct PNodefloat coef;int expn;struct PNode*next;PNode,*Polynomial;,用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一

13、个指针域（next）。,稀疏多项式相加,假设头指针pa和pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数较小的项插入到“和多项式”链表中去。,稀疏多项式相加,void AddPolyn(Polynomial 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);,单链表的应用,稀疏多项式的创建,多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插入到此项的前面，这样即可保证多项式链表的有序性。,稀疏多项式的创建,void CreatePolyn(Polynomial,