数据结构单链表.ppt
- 文档编号:18854131
- 上传时间:2024-01-30
- 格式:PPT
- 页数:35
- 大小:657KB
数据结构单链表.ppt
《数据结构单链表.ppt》由会员分享,可在线阅读,更多相关《数据结构单链表.ppt(35页珍藏版)》请在冰点文库上搜索。
第二章线性表链表单链表定义定义特点特点CC描述描述基本形态基本形态基本操作实现基本操作实现一组数据项的集合,其中每个数据项都是一个结点的一部分,每个结点都包含指向下一个结点的链接(即指针指针)。
1.数据元素在“逻辑逻辑关系上的相邻相邻”用“指针指针”来表示。
2.单链表中访问数据元素时需从头开始“顺序访问顺序访问”。
3.比顺序表的优势在于,提供高效地重排重排数据项的能力。
a1a2a3a4anL单链表的C描述typedefstructLNodeElemTypedata;/数据域structLNode*next;/指针域LNode,*LinkList;LinkListL;/L/L为单链表的头指针为单链表的头指针头指针指向单链表中的第一个结点第一个结点用指针表示链接,用结构体表示结点,结点是由数据项和用指针表示链接,用结构体表示结点,结点是由数据项和链接组成的,链接是指向下一结点的指针。
链接组成的,链接是指向下一结点的指针。
单链表的基本形态空表空表非空表非空表为了操作方便,在第一个结点之前虚加一个为了操作方便,在第一个结点之前虚加一个“头结点头结点”哑元结点哑元结点LL-next=NULL;不允许删除操作不允许删除操作a1a2a3anL可以进行插入、删除操作可以进行插入、删除操作单链表基本操作1、初始化(动态分配)StutasInitList(LinkList&L)L=(LinkList)malloc(sizeof(LNode);if(!
L)exit(overflow);L-next=NULL;returnOK;L头结点头结点L211830754256pppj123单链表基本操作2、取单链表中指定位序的数据元素演示例子:
取单链表中第3个元素值取元素的基本操作单链表是一种单链表是一种“顺序访问顺序访问”的结构,为找第的结构,为找第ii个数据个数据元素,必须先找到第元素,必须先找到第(i-1i-1)个数据元素。
个数据元素。
1.1.指针指针pp始终指向单链表中第始终指向单链表中第jj个结点;个结点;2.2.移动指针,比较移动指针,比较jj和和ii,相等则找到。
,相等则找到。
StatusGetElem_L(LinkListL,inti,ElemType&e)/L是带头结点的链表的头指针,以是带头结点的链表的头指针,以e返回第返回第i个元素个元素/GetElem_L算法算法时间复杂度时间复杂度为为:
O(ListLength(L)p=L-next;j=1;/pp指向第一个结点,指向第一个结点,jj为计数器为计数器while(p&jnext;j+;/顺指针向后查找,直到顺指针向后查找,直到pp指向第指向第ii个元素个元素/或或pp为空为空if(p&j=i)e=p-data;returnOK;/取得第i个元素else/第i个元素不存在returnERROR;与顺序表相比,链表不适合与顺序表相比,链表不适合于查找第于查找第ii个元素的操作。
个元素的操作。
单链表基本操作3、插入(在第i个元素前插入e)单链表中:
ai-1有序对有序对改变为改变为和和eaiai-1在单链表中在单链表中插入结点插入结点只需要只需要修改指针修改指针。
若要在第。
若要在第ii个结点之前个结点之前插入元素,修改的是第插入元素,修改的是第(i-1)(i-1)个结点的指针。
个结点的指针。
StatusListInsert_L(LinkList&L,inti,ElemTypee)/L为带头结点的单链表的头指针,本算法为带头结点的单链表的头指针,本算法/在链表中第在链表中第i个结点之前插入新的元素个结点之前插入新的元素e/LinstInsert_L算法的算法的时间复杂度时间复杂度为:
O(ListLength(L)elsereturnERROR;p=L;j=0;while(p&jnext;+j;/寻找第寻找第(i-1)个结点个结点if(p&j=i-1)s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入returnOK;eai-1aiai-1sp有序对有序对和和改变为改变为ai-1aiai+1ai-1单链表基本操作4、删除(第i个元素)在单链表中在单链表中删除第删除第ii个结点个结点时,要找到单链表中第时,要找到单链表中第(i-1i-1)个结点,个结点,修改其指向后继的指针。
修改其指向后继的指针。
ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pqStatusListDelete_L(LinkList&L,inti,ElemType&e)/删除以L为头指针(带头结点)的单链表中第i个结点/ListDelete_L算法的算法的时间复杂度时间复杂度为:
O(ListLength(L)p=L;j=0;while(p-next&jnext;+j;/寻找第i-1个结点,并令p指向它。
if(p-next&j=i-1)q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);returnOK;elsereturnERROR;/删除位置不合理对比单链表和顺序表的基本操作插入和删除的简单性是链表存在的理由插入和删除的简单性是链表存在的理由只修改相关结点的指向保持链表特性单链表的访问方式是顺序访问单链表的访问方式是顺序访问查找第i个数据项的代价,沿着链表,一个一个结点地访问,直到找的这个数据项算法时间复杂度:
O(ListLength(L)单链表基本操作5、清空while(L-next)p=L-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)returnTRUE;elsereturnFALSE;8、求表长intListLength(LinkListL)p=L-next;i=0;while(p)i+;p=p-next;returni;单链表基本操作9、搜索(查找元素)p=L-next;i=1;while(p&p-data!
=e)p=p-next;i+;if(p)returni;elsereturn0;从第一个结第一个结点点开始搜索搜索成功,返回搜索成功,返回位序位序;否则,返回否则,返回00单链表的应用1.建立单链表链表是一个动态结构,它不需要预分配空间,因此生成链表是一个动态结构,它不需要预分配空间,因此生成链表的过程是链表的过程是一个结点一个结点“逐个插入逐个插入”的过程。
的过程。
逆序建立单链表逆序建立单链表顺序建立单链表顺序建立单链表新结点新结点插入在头插入在头结点的结点的后面,作为重排链表后后面,作为重排链表后的的第一个结点第一个结点新结点新结点插入在尾插入在尾结点的结点的后面,作为重排链表后后面,作为重排链表后的的最后一个结点最后一个结点逆序建立单链表操作步骤操作步骤建立一个带头结点的空单链表;建立一个带头结点的空单链表;输入数据元素输入数据元素ai,建立新结点,建立新结点p,并把,并把p插插入在头结点之后成为第一个结点。
入在头结点之后成为第一个结点。
重复执行重复执行步,直到完成单链表的建立。
步,直到完成单链表的建立。
a1a1a2voidCreateList_N(LinkList&L,intn)/逆序输入n个数据元素,建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:
O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=1;idata);/输入元素值p-next=L-next;L-next=p;/插入顺序建立单链表操作步骤操作步骤建立一个带头结点的空单链表;建立一个带头结点的空单链表;输入数据元素输入数据元素ai,建立新结点,并把其插入,建立新结点,并把其插入在尾结点在尾结点p之后成为最后一个结点。
之后成为最后一个结点。
重复执行重复执行步,直到完成单链表的建立。
步,直到完成单链表的建立。
a1pa1ppa2pa3pppan顺序建立单链表:
即新元素插入表尾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;单链表的应用2.归并有序链表归并有序单链表归并有序单链表LaLa和有序单链表和有序单链表LbLb得到有序单链表得到有序单链表LcLc。
链表结点之间的关系是通过指针指向建立起来的,链表结点之间的关系是通过指针指向建立起来的,所以用链表进行合并不需要另外开辟存储空间,所以用链表进行合并不需要另外开辟存储空间,可以直接利用原来两个表的存储空间,合并过程可以直接利用原来两个表的存储空间,合并过程中只需要把中只需要把La和和Lb两个链表中的结点重新进行链两个链表中的结点重新进行链接即可。
接即可。
单链表的应用归并思想:
需要设立需要设立3个指针个指针pa、pb、pc,其中,其中pa和和pb分别指分别指向向La和和Lb中当前待比较插入的结点,而中当前待比较插入的结点,而pc指向指向Lc中当前最后一个结点(中当前最后一个结点(Lc的表头结点设为的表头结点设为La的表头的表头结点)。
指针的初值为:
结点)。
指针的初值为:
pa和和pb分别指向分别指向La和和Lb表中的第一个结点,表中的第一个结点,pc指向空表指向空表Lc中的头结点。
通中的头结点。
通过比较指针过比较指针pa和和pb所指向的元素的值,依次从所指向的元素的值,依次从La或或Lb中中“摘取摘取”元素值较小的结点插入到元素值较小的结点插入到Lc的最后,的最后,当其中一个表变空时,只要将另一个表的剩余段链当其中一个表变空时,只要将另一个表的剩余段链接在接在pc所指结点之后即可。
所指结点之后即可。
归并有序单链表voidMergeList_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-next=pb;pc=pb;pb=pb-next;pc-next=pa?
pa:
pb;free(Lb);算法时间复杂度:
O(m+n)算法空间复杂度:
O
(1)单链表的应用3.稀疏多项式的运算稀疏多项式可以抽象成一个线性表。
稀疏多项式的相加稀疏多项式可以抽象成一个线性表。
稀疏多项式的相加过程和归并两个有序表的过程极其类似。
不同之处在于,过程和归并两个有序表的过程极其类似。
不同之处在于,多项式的相加过程在比较两个多项式指数时要考虑三种多项式的相加过程在比较两个多项式指数时要考虑三种情况(等于、小于、大于)。
链式存储结构更加灵活,情况(等于、小于、大于)。
链式存储结构更加灵活,合并过程空间复杂度为合并过程空间复杂度为O
(1)O
(1)。
多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x870517A319881B227-98单链表的应用稀疏多项式的相加规则:
对于两个多项式中所有指数相同的项,对应系数规则:
对于两个多项式中所有指数相同的项,对应系数相加,若其和不为零,则作为相加,若其和不为零,则作为“和多项式和多项式”中的一项插中的一项插入到入到“和多项式和多项式”链表中去;对于两个多项式中指数不链表中去;对于两个多项式中指数不相同的项,则将指数值较小的项插入到相同的项,则将指数值较小的项插入到“和多项式和多项式”链链表中去。
表中去。
“和多项式和多项式”链表中的结点无需生成,而应该链表中的结点无需生成,而应该从两个多项式链表中摘取。
从两个多项式链表中摘取。
70517111227A稀疏多项式相加typedefstructPNodefloatcoef;intexpn;structPNode*next;PNode,*Polynomial;用单链表表示多项式时,每个链表结点存储多项式中的一个非零项,包括系数(coef)和指数(expn)两个数据域以及一个指针域(next)。
稀疏多项式相加假设头指针假设头指针papa和和pbpb的单链表分别为多项式的单链表分别为多项式AA和和BB的存储结的存储结构,指针构,指针p1p1和和p2p2分别指向分别指向AA和和BB中当前进行比较的某个结中当前进行比较的某个结点,则逐一比较两个结点中的指数项,对于指数相同的点,则逐一比较两个结点中的指数项,对于指数相同的项,对应系数相加,若其和不为零,则将插入到项,对应系数相加,若其和不为零,则将插入到“和多和多项式项式”链表中去;对于指数不相同的项,则通过比较将链表中去;对于指数不相同的项,则通过比较将指数较小的项插入到指数较小的项插入到“和多项式和多项式”链表中去。
链表中去。
稀疏多项式相加voidAddPolyn(Polynomial&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稀疏多项式相加r=p1;p1=p1-next;free(r);r=p2;p2=p2-next;free(r);elseif(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);单链表的应用稀疏多项式的创建多项式的创建方法类似于链表的创建方法,区别在于多多项式的创建方法类似于链表的创建方法,区别在于多项式链表是一个有序表,每项的位置要经过比较才能确项式链表是一个有序表,每项的位置要经过比较才能确定。
首先初始化一个空链表用来表示多项式,然后逐个定。
首先初始化一个空链表用来表示多项式,然后逐个输入各项,通过比较,找到第一个大于该输入项指数的输入各项,通过比较,找到第一个大于该输入项指数的项,将输入项插入到此项的前面,这样即可保证多项式项,将输入项插入到此项的前面,这样即可保证多项式链表的有序性。
链表的有序性。
稀疏多项式的创建voidCreatePolyn(Polynomial&p,intn)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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 单链表