《数据结构-第二章线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构-第二章线性表.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 页第 2 页线性表是最简单常用的数据结构，顺序存储结构 链式存储结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。第二章第二章线性表线性表第 3 页 第二章第二章 线性表线性表2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.3线性表的链式存储和实现2.3.1线性链表2.3.2循环链表2.3.
2、3双向链表2.4一元多项式的表示及相加第 4 页第二章第二章线性表线性表在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。第 5 页线性表是线性表是n个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，通常记作（通常记作（a1,a2,a3,an）。）。姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555.2.1线性表的类型定义线性表的类型定义例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电
3、话号码簿。一一线性表的逻辑结构线性表的逻辑结构第 6 页2.1线性表的类型定线性表的类型定义义说明：说明：设设A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；是同一类型的；2）在表中在表中ai-1领先于领先于ai，ai领先于领先于ai+1，称称ai-1是是ai的直接前驱，的直接前驱，ai+1是是ai的直接后继；的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且在线性表中，除第一个元素和最后一个元素之外，其他元素都
4、有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数线性表中元素的个数n称为线性表的长度，称为线性表的长度，n=0时称为空表；时称为空表；5）ai是线性表的第是线性表的第i个元素，称个元素，称i为数据元素为数据元素ai的序号，每一个元素在的序号，每一个元素在线性表中的位置，仅取决于它的序号；线性表中的位置，仅取决于它的序号；第 7 页2.1线性表的类型定义线性表的类型定义线性表的其他表示方式二元组表示L=，其中
5、D=a1,a2,a3,.anS=RR=,图示表示a ai i+1a a1a ai-i-1a a2 2a ai ia an n顶点：表示数据边：表示是数据间的顺序结构关系第 8 页2.1线性表的线性表的类型定义类型定义二二ADTList三三数据对象数据对象:D=ai|aiElemSeti=1,2,3.,n,n0四四数据关系数据关系:R1=|ai-1,aiD,i=1,2,3.,n,n0五五基本操作基本操作:1初始化操作初始化操作:InitList(&L),构造一个空的线性表构造一个空的线性表L;2销毁操作销毁操作:DestroyList(&L),销毁一个线性表销毁一个线性表L;3清空操作清空操作:
6、ClearList(&L),将将L重置为空表重置为空表;4返回空表返回空表:ListEmpty(L),若若L为空为空表表,返回返回TRUE,否则否则FALSE5元素计数元素计数:ListLength(L),返回返回L中元素个数中元素个数6返回位序返回位序:LocateElem(L,e,compare(),返回返回L中第中第1个与个与e满满足足compare()的数据元素的位序的数据元素的位序.若这样的数据元素不存在若这样的数据元素不存在,返返回回07GetElem(L,i,&e):用用e返回返回L中第中第i个数据元素的值个数据元素的值8ListInsert(&L,i,e):在在L中第中第I个位
7、置之前插入新的数据元素个位置之前插入新的数据元素e,L的长度加；的长度加；第 9 页2.1线性表的类型定义线性表的类型定义说明1上面列出的操作，只是线性表的一些常用的基本操作；2不同的应用，基本操作可能是不同的；3线性表的复杂操作可通过基本操作实现；第 10 页为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系课堂讨论：算法课堂讨论：算法.1,2.2如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？第 11 页 2.2 2.2线性表的线性表的顺序存储顺序存储和实现和实现一线性表的顺序存储结构顺序表二顺序表的基本操作算法三效率分析第 12 页线
8、性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n线性表（a1,a2,a3,.an）的顺序存储结构用顺序存储结构存储的线性表称为顺序表2.2线性表的顺序存储和实现线性表的顺序存储和实现一一线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表线性表的顺序存储结构第 13 页2.2线性表的顺序存储和实现线性表的顺序存储和实现说明：说明：在顺序存储结构下，线性表元素之间在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映的逻辑关系，通过元素的存储顺序反映（表示）出来；（表示）出来；假
9、设线性表中每个数据元素占用假设线性表中每个数据元素占用t个个存储单元，那么，在顺序存储结构中，线存储单元，那么，在顺序存储结构中，线性表的第性表的第i个元素的存储位置与第个元素的存储位置与第1个元素个元素的存储位置的关系是：的存储位置的关系是：Loc(ai)=Loc(a1)+(i1)ta a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nt t个单元个单元Loc(a1)Loc(ai)第 14 页2.2线性表的顺序存储和实现线性表的顺序存储和实现怎样在计算机上实现线性表的顺序存储结构？可用C语言中的一维数组来表示,但数组不是线性表,数组存放的是线性表,数组的类型由线
10、性表中的数据元素的性质决定.如:#define MAX 100 int vMAX;第 15 页2.2线性表的顺序存储和实现线性表的顺序存储和实现顺序表的类型定义顺序表的类型定义#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量线性表存储空间的分配增量typedefstructElemType*elem;/线性表存储空间基址线性表存储空间基址intlength;/当前线性表长度当前线性表长度intlistsize;/当前分配的线性表存储空间大小当前分配的线性表存储空间大小/（
11、以（以sizeof(ElemType)为单位）为单位）SqList;SqList：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；length：存放线性表的表长；listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。第 16 页2.2线性表的顺序存储和实现线性表的顺序存储和实现存放线性表元素的一维数组设设A=（a1,a2,a3,.an）是一线性表，是一线性表，L是是SqList类型的结构变量，类型的结构变量，用于存放线性表用于存放线性表A，则则L在内存中的状态如图所示：在内存中的状
12、态如图所示：顺序表通过顺序表通过元素的存储顺序元素的存储顺序反映线性表元素间的逻辑关系反映线性表元素间的逻辑关系 a1a1 a2 a2ai-1ai-1 aiaiai+1ai+1 an an0 01 1i-2i-2i-1i-1i in-1n-19999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n9999第 17 页2.2线性表的顺序存储和实现线性表的顺序存储和实现二、顺序表的基本操作算法二、顺序表的基本操作算法1.插入插入insert(v,x,i)功能：功能：在顺序表在顺序表v中的第中的第i(1=i=n+1)个数据元素之个数据元素之前插入
13、一个新元素前插入一个新元素x,插入前线性表为插入前线性表为(a1,a2,a3,ai-1,ai,an)插入后插入后,线性表长度为线性表长度为n+1,线性表为线性表为(a1,a2,a3,ai-1,x,ai,an)第 18 页2.2线性表的顺序存储和实现线性表的顺序存储和实现插入前插入后插入操作示意图：插入操作示意图：a1a1 a2 a2ai-1ai-1 aiaiai+1ai+1 an an01i-2i-1in-1MAX-1n nP_lenP_len a1a1 a2 a2 ai-1 ai-1 x x aiai an an01i-2i-1n-2n-1nMAX-1n+1n+1P_lenP_len第 19
14、 页2.2线性表的顺序存储和实现线性表的顺序存储和实现intinsert(intv,inti,intx,int*p_len)intj;if(i*p_len)return(0);/*i值不合法值不合法for(j=*p_len,j=i;j-)vj=vj-1;vi-1=x;*p_len+;/*插入插入x,表长增表长增1return(1);插入操作算法插入操作算法第 20 页删除算法的主要步骤删除算法的主要步骤1）若）若i不合法或表不合法或表L空，算法结束，并返回空，算法结束，并返回0；否则转否则转2）2）将第将第i个元素之后的元素（不包括第个元素之后的元素（不包括第i个元素）依次向前移动一个个元素）
15、依次向前移动一个位置位置;3）表长）表长-12.2线性表的顺序存储和实现线性表的顺序存储和实现第 21 页2.2线性表的顺序存储和实现线性表的顺序存储和实现intdelete(intv,inti,int*p_len)intj;if(i*p_len)return(0);/*i值不合法值不合法for(j=i,jlink=null;Return(head);1）初始化操作功能：建空线性链表参数：head为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给head；第 37 页建立链表建立链表lNODE*create_link(n)/*建立有建立有n个结点的线性单链表的算
16、法个结点的线性单链表的算法 NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=p;for(i=I;Idata=i;q-link=NULL;p-link=q;p=q;return(head);第 38 页 插入结点插入结点lq=(NODE*)malloc(sizeof(NODE);q-data=a;q-link=p-link;p-link=q;headheadzyxp pyxzp pheadheada第 39 页13插入操作Insert_link(NODE*head,intx,inti)功能：在线性链表的第i个元素结点之前插入一个新元
17、素结点x；插入操作图示：2.3.1 线性链表线性链表插入前插入后ai-1aia2a1ai+1nanheadheadai-1aia2a1ai+1nanxheadhead第 40 页2.3.1 线性链表线性链表插入操作主要步骤：1）查找链表L的第i-1个元素结点；2）为新元素建立结点；3）修改第i-1个元素结点的指针和新元素结点指针完成插入；第 41 页lInt insert_link(NODE*head,int x,int i)NODE*p,*s;int j;p=head;j=0;while(p!=NULL)&(jlink;j+;if(p=NULL)return(0);s=(NODE*(mall
18、oc(sizcof(NODE);s-data=x;s-link=p-link;p-link=s;return(1);第 42 页 删除结点删除结点lq=p-link;p-link=q-link;free(q);headheadzyxq qyxzq qheadheadp pp p第 43 页2.3.1 线性链表线性链表删除操作主要步骤：1）查找链表的第i-1个元素结点,使指针p指向它,将指针q指向第i个结点；2）修改第i-1个元素结点指针，使其指向第i个元素结点的后继；3)回收q指针所指的第i个结点空间；第 44 页2.3.1 线性链表线性链表删除前删除后ai-1aia2a1ai+1nanhea
19、dheadai-1aia2a1ai+1nanheadp pp pq qq q第 45 页l在线性链表中删除第在线性链表中删除第i个结点个结点lInt delete_link(NODE*head,int i)NODE*p,*q;int j;p=head;j=0;while(p!=NULL)&(jlink;j+;if(p=NULL)return(0);q=p-link;p-link=q-link;free(q);return(1);第 46 页2.3.1线性链表线性链表三三线性链表的其他操作的实现线性链表的其他操作的实现例：将两个递增有序线性链表归并成一个递减有序表。例：将两个递增有序线性链表归并
20、成一个递减有序表。设线性表设线性表A、B分别用头指针为分别用头指针为head_a、head_b的两个的两个带头结点的线性链表存储带头结点的线性链表存储,归并后的递减有序表头指针为归并后的递减有序表头指针为head,将两表数据较小的结点依次取出插入到新表将两表数据较小的结点依次取出插入到新表利用基本操作直接对链表进行操作第 47 页2.3.1线性链表线性链表线性链表归并操作图示73n952n7head_ahead_b79n2head38785第 48 页NODE*merge_link(NODE*head_a,NODE*head_b)NODE*p,*q,*head;head=(NODE*)mall
21、oc(sizeof(NODE);head-link=NULL;p=head_a-link;q=head_b-link;while(p!=NULL)&(q!=NULL)If(p-datadata)head_a-link=p-link;p-link=head-link;head-link=p;p=head_a-link;elsehead_b-link=q-link;q-link=head-link;head-link=q;q=head_b-link;第 49 页while(p!=NULL)head_a-link=p-link;p-link=head-link;head-link=p;p=head_
22、a-link;while(q!=NULL)head_b-link=q-link;q-link=head-link;head-link=q;q=head_b-link;free(head_a);free(head_b);return(head);第 50 页2.3.1 线性链表小结线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入删除操作通过修改结点的指针实现；3不能随机存取元素；第 51 页1循环链表的概念循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是循环链表是线性表的另一种链式存储结构，它的特点是将
23、线性链表的最后一个结点的指针指向链表的第一个结点将线性链表的最后一个结点的指针指向链表的第一个结点2循环链表图示循环链表图示2.3.2单向循环链表单向循环链表(a)非空表 （b）空表headheadheadheada1an第 52 页2.3.2单向单向循环链表循环链表说明在在解决某些实际问题时循环链表可能要比线性链表方便些。解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；如将一个链表链在另一个链表的后面；循循环链表与线性链表操作的主要差别是算法中循环结束的条环链表与线性链表操作的主要差别是算法中循环结束的条件不是件不是p或或p-link是否为是否为NULL,
24、而是它们是否等于首指针；而是它们是否等于首指针；对对循环链表，有时不给出头指针，而是给出尾指针循环链表，有时不给出头指针，而是给出尾指针a aa1an给出尾指针的循环链表第 53 页2.3.2单向单向循环链表循环链表b ba aa1anb bb1bna aa1anb1bnq qq qp pp pp=a-link;q=b-link;a-link=q-link;b-link=p;free(q);第 54 页约瑟夫回环问题约瑟夫回环问题Voidlead(NODE*head,intm)NODE*p,*q;inti;p=head;q=NULL;i=1;while(p-link!=p)while(ilin
25、k!=p)i+;q=p;p=p-link;if(p-link!=p)i=1;printf(“%d”,p-data);q-link=p-link;q=p;p=p-link;free(q);elseprintf(“%d”,p-data);第 55 页1双向链表的概念双向链表的概念2.3.3双向链表双向链表(a)a)结点图示结点图示数据域指针域指针域结点结点存储数据元素存储数据元素存储后继结点存储后继结点 的地址的地址存储前趋结点存储前趋结点 的地址的地址双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。第 56 页2.3.3双向链表双向链表2双向链表图示双向链
26、表图示headhead(b)空的双向循环链表（c）非空的双向循环链表headheadabStructnodeintdatastructnode*llink,*rlink;第 57 页在双向链表中删除结点时指针变在双向链表中删除结点时指针变化情况化情况在双向链表中插入一个在双向链表中插入一个结点时指针的变化情况结点时指针的变化情况pai-1xaipaiai+1ai-12.3.3双向链表双向链表3、双向链表的基本操作算法第 58 页2.3.3双向链表双向链表1）插入操作算法）插入操作算法(在在p所指结点之后插入所指结点之后插入q结点的过程结点的过程)q=(NODE*)malloc(sizeof(N
27、ODE);q-data=x;q-rlink=p-rlink;q-llink=p;p-rlink=q;(q-rlink)-llink=q;第 59 页2.3.3双向链表双向链表2）删除操作算法）删除操作算法(p-llink)-rlink=p-rlink;(p-rlink)-llink=p-llink;free(p);aiai+1pai-1第 60 页2.4一元多项式的表示及相加一元多项式的表示及相加计算机计算机领域：领域：P=(p0,p1,p2,pn)Q=(q0,q1,q2,qm)R=(p0+q0,p1+q1,pm+qm,pm+1,pn)P(x)=p0+p1x+p2x2+p pn n x xn
28、nQ(x)=q0+q1x+q2x2+q qm m x xm m 不失一般性，设不失一般性，设mindexindex：p所指结点应为和多项式中的结点所指结点应为和多项式中的结点p-index=q-index：将将p所指结点的系数所指结点的系数“加加”到到q所指所指结结点的系数上相加；点的系数上相加；p-indexq-index：从表从表bh中删除中删除q所指结点，并将其所指结点，并将其插入到插入到ah表表p所指结点之前；所指结点之前；第 68 页一元多项式的相加算法一元多项式的相加算法（算法（算法2.8）voidpolyadd(NODE*ah,NODE*bh)NODE*pre_p,*p,*q,*
29、temp;charcomp;pre_p=ah;p=ah-next;q=bh-next;while(p!=NULL)&(q!=NULL)comp=compare(p-index,q-index)switch(comp)（接下页）第 69 页续续casenext;break;case=:/两者的指数值相等两者的指数值相等p-coef+=q-coef;if(p-coef=0.0)/合并后系数为合并后系数为0pre_p-next=p-next;free(p);elsepre_p=p;p=pre_p-next;temp=q;q=q-next;free(temp);break;case:/多项式多项式A中
30、当前结点的指数值大中当前结点的指数值大temp=q-next;q-next=p;pre_p-next=q;pre_p=q;q=temp;第 70 页续续if(q!=NULL)pre_p-next=q;free(bh);charcompare(intn1,intn2)if(n1n2)return();第 71 页第二章第二章线性表小结线性表小结本章学习了线性表的顺序存储结构顺序表，链式存储结构,线性链表,循环链表,双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。