《数据结构：第2章 线性表》由会员分享，可在线阅读，更多相关《数据结构：第2章 线性表（83页珍藏版）》请在金锄头文库上搜索。
1、第第2章章线性表线性表2.1线性表的概念及运算线性表的概念及运算2.2线性表的顺序存储线性表的顺序存储2.3线性表的链式存储线性表的链式存储2.4一元多项式的表示及相加一元多项式的表示及相加2.1线性表的概念及运算线性表的概念及运算4.线性表的逻辑结构线性表的逻辑结构1.线性表的定义线性表的定义一个线性表是具有一个线性表是具有n个数据元素的有限序列。个数据元素的有限序列。记为记为(a1,ai-1,ai,ai+1,an)2.线性表的长度线性表的长度线性表中元素的个数线性表中元素的个数n(n=0),n=0时时,称为空表。称为空表。3.位序位序ai是第是第i个元素，称个元素，称i为数据元素为数据元素
2、ai在线性表中的位序在线性表中的位序。例子：例子：l英文字母表英文字母表(A,B,Z)；l车辆登记表车辆登记表。5.线性表的特点线性表的特点l同同一一性性：线线性性表表由由同同类类数数据据元元素素组组成成，每每一一个个ai必须属于同一数据对象。必须属于同一数据对象。l有有穷穷性性：线线性性表表由由有有限限个个数数据据元元素素组组成成，表表长度就是表中数据元素的个数。长度就是表中数据元素的个数。l有有序序性性：线线性性表表中中相相邻邻数数据据元元素素之之间间存存在在着着序偶关系序偶关系。6.线性表的基本运算线性表的基本运算l初始化初始化InitList（&L）建立一个空表。建立一个空表。l求表长
3、求表长ListLength（L）返回线性表的长度。返回线性表的长度。l读表元素读表元素GetElem（L,i,&e)用用e返回返回L中第中第i个数据元素的个数据元素的值。值。l定位定位LocateElem（L,e,compare()）返回满足关系的数据元返回满足关系的数据元素的位序。素的位序。l插入插入ListInsert（&L,i,e）在在L中第中第i个位置之前插入新的数个位置之前插入新的数据元素据元素e，线性表的长度增，线性表的长度增1。l删除删除ListDelete（&L,i,&e）删除删除L的第的第i个位置上的数据元个位置上的数据元素素e，线性表的长度减，线性表的长度减1。l输出输出L
4、istDisplay（L）按前后次序输出线性表的所有元素。按前后次序输出线性表的所有元素。练习练习1：两个线性表：两个线性表LA和和LB分别表示两个集合分别表示两个集合A和和B，现求一个新的集合现求一个新的集合A=AB。voidunion(List&La,ListLb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);O(ListLength(La)ListLength(Lb)练习练习
5、2：两个线性表两个线性表LA和和LB中的数据元素按值非递中的数据元素按值非递减有序排列，现将减有序排列，现将LA和和LB归并为一个新的线性归并为一个新的线性表，表，LC中的数据元素仍按值非递减有序排列。中的数据元素仍按值非递减有序排列。LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)voidMergeList(ListLa,ListLb,List&Lc)InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);i=j=1;k=0;while(i=La_len)
6、&(j=Lb_len)GetElem(La,i,a);GetElem(Lb,j,b);if(a=b)ListInsert(Lc,+k,a);+i;elseListInsert(Lc,+k,b);+j;while(i=La_len)GetElem(La,i+,a);ListInsert(Lc,+k,a);while(j=Lb_len)GetElem(Lb,j+,b);ListInsert(Lc,+k,b);O(ListLength(La)+ListLength(Lb)例，例，La=(3,5,8)Lb=(2,6,8,9,15)构造构造Lc=(2,3,5,6,8,8,9,15)358La268Lb9
7、15Lcij2首先，首先，La_len=3；Lb_len=5；3ijij5ij6ij88jij9j15j算法结束算法结束！2.2线性表的顺序表示和实现线性表的顺序表示和实现1.顺序表：顺序表：按顺序存按顺序存储方式构储方式构造的线性造的线性表。表。假假设设线线性性表表中中有有n个个元元素素，每每个个元元素素占占k个个单单元元，第第一一个个元元素素的的地地址址为为loc(a1)，则则可可以以通通过过如如下下公公式式计计算算出出第第i个个元元素素的的地地址址loc(ai)：loc(ai)=loc(a1)+(i-1)k其中其中loc(a1)称为基地址。称为基地址。2.顺序表的特点：顺序表的特点：l逻
8、辑结构中相邻的数据元素在存储结构中逻辑结构中相邻的数据元素在存储结构中仍然相邻。仍然相邻。l线性表的顺序存储结构是一种随机存取线性表的顺序存储结构是一种随机存取的存储结构。的存储结构。3.顺序表的描述：顺序表的描述：typedefstructElemType*elem；intlength;/当前长度当前长度intlistsize;/分配的存储容量分配的存储容量SqList；/ElemTypeelemMAXSIZE;typedef#ElemType;#为根据具体问题确定的数据类型为根据具体问题确定的数据类型typedefintStatus;4.顺序表上基本运算的实现顺序表上基本运算的实现l初始化
9、初始化StatusInitList_Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;L.elem=newElemTypeLIST_INIT_SIZE;顺序表的插入顺序表的插入：在表中第：在表中第4个元素之前插入个元素之前插入“21”。顺序表中插入元素顺序表中插入元素l插入插入StatusListInsert_Sq(SqList&L,inti,ElemTypee)i
10、f(iL.length+1)returnERROR;if(L.length=L.listsize)realloc();.;/越界处理越界处理 ；q=&(L.elemi-1);for(p=&(L.elemL.length-1;p=q;-p)*(p+1)=*p;*q=e;+L.length;returnOK;/越界处理越界处理newbase=(ElemType*)realloc(L.elem，(L.listsize+LISTINCREMENT)*sizeof(ElemType)；if(!newbase)exit(OVERFLOW)；L.elem=newbase；L.listsize+=LISTIN
11、CREMENT；if(L.length=L.listsize)算法时间复杂度算法时间复杂度:时间主要花在移动元素上，而移动元素的个数取决时间主要花在移动元素上，而移动元素的个数取决于插入元素位置。于插入元素位置。i=1，需移动，需移动n个元素；个元素；i=i，需移动，需移动ni+1个元素；个元素；i=n+1，需移动，需移动0个元素；个元素；假设假设pi是在第是在第i个元素之前插入一个新元素的概率个元素之前插入一个新元素的概率则长度为则长度为n的线性表中插入一个元素所需移动元的线性表中插入一个元素所需移动元素次数的素次数的期望值期望值为为:Eis=pi(ni+1)n+1i=1设在任何位置插入元素
12、设在任何位置插入元素等概率等概率，pi=n+11Eis=(ni+1)=n+11i=1n+12nO(n)图图顺序表中删除元素顺序表中删除元素顺序表的删除顺序表的删除：删除第：删除第5个元素，个元素，l删除删除StatusListDelete_Sq(SqList&L,inti,ElemType&e)if(iL.length)returnERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;returnOK;算法时间复杂度算法时间复杂度:时间主要花在移动元素上，而移动元素的个数取决时间主要花在移
13、动元素上，而移动元素的个数取决于删除元素位置。于删除元素位置。i=1，需移动，需移动n- -1 1个元素；个元素；i=i，需移动，需移动ni个元素；个元素；i=n，需移动，需移动0个元素；个元素；假设假设qi是删除第是删除第i个元素的概率个元素的概率则长度为则长度为n的线性表中删除一个元素所需移动元的线性表中删除一个元素所需移动元素次数的素次数的期望值期望值为为:Edl=qi(ni)ni=1设删除任何位置的元素设删除任何位置的元素等概率等概率，qi=n1Edl=(ni)=n1i=1n2n- -1 1O(n)l顺序表的归并，表中元素非递减排列。顺序表的归并，表中元素非递减排列。voidMerge
14、List_Sq(SqListLa,SqListLb,SqList&Lc)pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc();if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last)&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=
15、*pa+;while(pbnext=NULL;(2)销毁线性表销毁线性表DestroyList(L)释释放放单单链链表表L占占用用的的内内存存空空间间。即即逐逐一一释释放放全全部部结结点点的空间。的空间。voidDestroyList(LinkListL)LinkListp=L,q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);(3)判线性表是否为空表判线性表是否为空表ListEmpty(L)若单链表若单链表L没有数据结点没有数据结点,则返回真则返回真,否则返回假。否则返回假。intListEmpty(LinkListL)return(L-
16、next=NULL);(4)求线性表的长度求线性表的长度ListLength(L)返回单链表返回单链表L中数据结点的个数。中数据结点的个数。intListLength(LinkListL)LinkListp=L;inti=0;while(p-next!=NULL)i+;p=p-next;return(i);(5)输出线性表输出线性表DispList(L)逐逐一一扫扫描描单单链链表表L的的每每个个数数据据结结点点,并并显显示示各各结结点点的的data域值。域值。voidDispList(LinkListL)LinkListp=L-next;while(p!=NULL)printf(%c,p-da
17、ta);p=p-next;printf(n);StatusGetElem(LinkListL,inti,ElemType&e)p=L-next;j=1;while(p&jnext;+j;if(!p|ji)returnERROR;e=p-data;returnOK;(6)取表元素取表元素l从头指针从头指针L出发，出发，从头结点（从头结点（L-next）开始顺着链域扫描；开始顺着链域扫描；l用用j做计数器，累做计数器，累计当前扫描过的结计当前扫描过的结点数，当点数，当j=i时，时，指针指针p所指的结点就所指的结点就是要找的第是要找的第i个结点。个结点。例，例，取第取第i=3个元素。个元素。Zhao
18、Qian0LiLSunp=L- -nextj=1p=p- -nextj=2p=p- -nextj=3e=p- -data=Sun时间复杂度时间复杂度:O(n)l在单链表第在单链表第i个结点前插入一个结点的过程个结点前插入一个结点的过程(7)插入插入StatusListInsert(LinkList&L,inti,ElemTypee)p=L;j=0;while(p&jnext;+jif(!p|ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;returnOK;l删除单链表的第删除单链
19、表的第i个结点的过程个结点的过程(8)删除删除StatusListDelete(LinkList&L,inti,ElemType&e)p=L;j=0;while(p-next&jnext;+jif(!(p-next)|ji-1)returnERROR;r=p-next;e=r-data;p-next=p-next-next;/(p-next=r-next;)free(r);returnOK;l动态建立单链表的过程动态建立单链表的过程头插法建立单链表头插法建立单链表(9)头插法建表头插法建表CreateList_H(LinkList&L,intn)L=(LinkList)malloc(sizeo
20、f(LNode);L-next=NULL;for(i=n;i0;-i)s=(LinkList)malloc(sizeof(LNode);scanf(&s-data);s-next=L-next;L-next=s;l尾插法建表尾插法建表(10)尾插法建表尾插法建表CreateList_T(LinkList&L,intn)tail=L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)s=(LinkList)malloc(sizeof(LNode);scanf(&s-data);s-next=NULL;tail-next=s;tail
21、=s;(11)按元素值查找按元素值查找LocateElem(L,e)思思路路：在在单单链链表表L中中从从头头开开始始找找第第1个个值值域域与与e相相等等的的结点结点,若存在这样的结点若存在这样的结点,则返回位置则返回位置,否则返回否则返回0。intLocateElem(LinkListL,ElemTypee)LinkListp=L-next;intn=1;while(p!=NULL&p-data!=e)p=p-next;n+;if(p=NULL)return(0);elsereturn(n);练习：已知练习：已知L是带头结点的非空单链表，指针是带头结点的非空单链表，指针p所指的所指的结点既不是
22、第一个结点，也不是最后一个结点结点既不是第一个结点，也不是最后一个结点l删除删除*p结点的直接后继结点的语句序列结点的直接后继结点的语句序列q=p-next;p-next=q-next;free(q);l删除删除*p结点的直接前驱结点的语句序列结点的直接前驱结点的语句序列q=L;while(q-next-next!=p)q=q-next;s=q-next;q-next=p;free(s);l删除删除*p结点的语句序列结点的语句序列q=L;while(q-next!=p)q=q-next;q-next=p-next;free(p);l删除首元结点的语句序列删除首元结点的语句序列q=L-next;
23、L-next=q-next;free(q);l删除最后一个结点的语句序列删除最后一个结点的语句序列while(p-next-next!=NULL)p=p-next;q=p-next;p-next=NULL;free(q);链式结构的特点非随机存贮结构，所以取表元素要慢于顺非随机存贮结构，所以取表元素要慢于顺序表。序表。节约了大块内存适合于插入和删除操作适合于插入和删除操作实际上用空间换取了时间，结点中加入了指针，使得这两种操作转换为指针操作;线性表实现方法的比较 实现不同实现不同顺序表方法简单，各种高级语言中都有数组类型，容顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是基于
24、指针的，相对来讲复杂些。易实现；链表的操作是基于指针的，相对来讲复杂些。存储空间的占用和分配不同存储空间的占用和分配不同从存储的角度考虑，顺序表的存储空间是静态分配的，从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是在程序执行之前必须明确规定它的存储规模，也就是说事先对说事先对“MAXSIZE”要有合适的设定，过大造成浪要有合适的设定，过大造成浪费，过小造成溢出。而链表是动态分配存储空间的，费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表的长度或存储不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链
25、表。规模难以估计时，采用链表。线性表运算的实现不同线性表运算的实现不同按序号访问数据元素，使用顺序表优于链表。按序号访问数据元素，使用顺序表优于链表。插入删除操作插入删除操作 ，使用链表优于顺序表。，使用链表优于顺序表。l作业：作业：2.42.193.静态链表静态链表有些高级程序设计语言并没有指针类型，如有些高级程序设计语言并没有指针类型，如FORTRAN和和JAVA。我们可以用数组来表示。我们可以用数组来表示和实现一个链表，称为和实现一个链表，称为静态链表静态链表。可定义如下：可定义如下：#defineMAXSIZE1000/最多元素个数最多元素个数typedefstructElemType
26、data;intcur;/游标，指示器游标，指示器component,SLinkListMAXSIZE;li=si.cur;指针后移操作指针后移操作lMalloc:i=s0.cur;第一个可用结点位置第一个可用结点位置if(s0.cur)s0.cur=si.cur;lFree:/释放释放k结点结点sk.cur=s0.cur;s0.cur=k;lInsert:/将将i插在插在r之后之后si.cur=sr.cur;sr.cur=i;lDelete:;/p为为k的直接前驱，释放的直接前驱，释放ksp.cur=sk.curFree(k);单链表基础要点单链表基础要点l在单链表中，不能从当前结点出发访问
27、到任一结点。在单链表中，不能从当前结点出发访问到任一结点。l在单链表中，删除某一指定结点时，必须找到该结在单链表中，删除某一指定结点时，必须找到该结点的前驱结点。点的前驱结点。l线性表的链式存储结构是一种顺序存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构，不具有随机访问任一元素的特点。不具有随机访问任一元素的特点。l设置头结点的作用：使在链表的第一个位置上的操设置头结点的作用：使在链表的第一个位置上的操作和表中其它位置上的操作一致，无需进行特殊处作和表中其它位置上的操作一致，无需进行特殊处理，对空表和非空表的处理统一。理，对空表和非空表的处理统一。练习：练习：2.22写一算法，对
28、单链表实现就地逆置。写一算法，对单链表实现就地逆置。voidReverse_L(LinkList&L)p=L-next;L-next=NULL;while(p!=NULL)q=p;p=p-next;q-next=L-next;L-next=q;循环链表循环链表l循环链表是另一种形式的链式存储结构；循环链表是另一种形式的链式存储结构；l可从当前结点出发，访问到任一结点；可从当前结点出发，访问到任一结点；l循环单链表；循环单链表；l多重循环链表。多重循环链表。l单循环链表单循环链表设置尾指针设置尾指针rear,比设头指针更好。比设头指针更好。连接两个只设尾指针的单循环链表L1和L2 操作如下：操作
29、如下：p= R1 next; /保存保存L1 的头结点指针的头结点指针R1-next=R2-next-next; /头尾连接头尾连接free(R2-next); /释放第二个表的头结点释放第二个表的头结点 R2-next=p;R2b1bna1anR1p例，取循环链表第例，取循环链表第i个元素。个元素。p=L- -next；j=1 1；while(p!=L&jnext；+j；if(p=L|ji)returnERROR；e=p- -data；returnOK；StatusGetElem_L(LinkListL，inti，ElemType&e)操作与线性单链表基本一致，差别只是在于算法中的操作与线性
30、单链表基本一致，差别只是在于算法中的循环结束条件不是循环结束条件不是p是否为空是否为空，而是，而是p是否等于头指针是否等于头指针。双链表 希望查找前驱的时间复杂度达到希望查找前驱的时间复杂度达到O(1)，我，我们可以用空间换时间们可以用空间换时间, ,每个结点再加一个指向每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。前驱的指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为用这种结点结构组成的链表称为双向链表双向链表。 结点的结构结点的结构图图:priornextdata双向链表的逻辑表示priordatanextLL2.双向链表双向链表(DoubleLinkedLis
31、t)l类型描述类型描述typedefstructDuLNodeElemTypedata;structDuLNode*prior;structDuLNode*next;DuLNode,*DuLinkList;l双向循环链表双向循环链表p-next-prior=p-prior-next;pl双向链表的前双向链表的前(后后)插入操作插入操作s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;qs-next=q-next;q-next-prior=s;s-prior=q;q-next=s;l双向链表的删除操作双向链表的删除操作p-prior-next=p
32、-next;p-next-prior=p-prior;l删除删除*p的直接后继结点的语句序列的直接后继结点的语句序列q=p-next;p-next=p-next-next;p-next-prior=p;free(q);l删除删除*p的直接前驱结点的语句序列的直接前驱结点的语句序列q=p-prior;p-prior=p-prior-prior;p-prior-next=p;free(q);l作业：作业：2.82.9循环链表算法举例循环链表算法举例 （1 1） 假设一个单循环链表，其结点含有三个域假设一个单循环链表，其结点含有三个域pre、data、link。其中。其中data为数据域；为数据域；
33、pre为指针域，它的值为空指针为指针域，它的值为空指针（null）；）；link为指针域，它指向后继结点。请设计算法，将此为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。表改成双向循环链表。void SToDouble（DuLinkList la）/ la是结点含有是结点含有pre，data，link三个域的单循环链表。其中三个域的单循环链表。其中data为数据域；为数据域； pre为空指针域，为空指针域，link是指向后继的指针域。是指向后继的指针域。本算法将其改造成双向循环链表。本算法将其改造成双向循环链表。while（la-link-pre=null） la-link-pr
34、e=la/将结点将结点la后继的后继的pre指针指向指针指向la la=la-link； /la指针后移指针后移 /算法结束算法结束循环链表算法举例循环链表算法举例（2）已知一双向循环链表，从第二个结点至表尾递增有序，已知一双向循环链表，从第二个结点至表尾递增有序，（设（设a1xan）如下图。试编写程序，将第一个结点删除）如下图。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序并插入表中适当位置，使整个链表递增有序 x a1 a2 anLvoid DInsert（DuLinkList &L） L是无头结点的双向循环链表，自第二结点起递增有序。本算法是无头结点的双向循环链表，自
35、第二结点起递增有序。本算法将第一结点（将第一结点（a1xprior; / t暂存尾结点指针 p=L-next； 将第一结点从链表上摘下将第一结点从链表上摘下 p-prior=L-prior；p-prior-next=p； x=s-data; while（p-datanext； 查插入位置查插入位置 s-next=p；s-prior=p-prior；插入原第一结点插入原第一结点s p-prior-next=s；p-prior=s；L=t-next; 算法结束算法结束例例编编写写出出判判断断带带头头结结点点的的双双向向循循环环链链表表L是是否否对对称相等的算法。称相等的算法。解解:p从从左左向向右
36、右扫扫描描L,q从从右右向向左左扫扫描描L,若若对对应应数数据据结结点点的的data域域不不相相等等,则则退退出出循循环环,否否则则继继续续比比较较,直直到到p与与q相相等等或或p的的下下一一个个结结点点为为*q为为止止。对对应应算算法如下法如下:循环链表算法举例循环链表算法举例（3）intEqual(DuLinkListL)intsame=1;DuLinkListp=L-next;/*p指向第一个数据结点指向第一个数据结点*/DuLinkListq=L-prior;/*q指向最后数据结点指向最后数据结点*/while(same=1)if(p-data!=q-data)same=0;elsei
37、f(p=q)break; /*数据结点为奇数的情况数据结点为奇数的情况*/q=q-prior;if(p=q)break; /*数据结点为偶数的情况数据结点为偶数的情况*/p=p-next;returnsame;顺序表和链表的比较顺序表和链表的比较l基于空间的考虑基于空间的考虑 存储密度存储密度=元素本身所占的存储量元素本身所占的存储量/实际分配实际分配的存储总量的存储总量l基于时间的考虑基于时间的考虑 顺序表：随机存取结构，顺序表：随机存取结构，O(1)。链表：链表：顺序存取结构，顺序存取结构，O(n)。l基于语言的考虑基于语言的考虑2.4一元多项式的表示及相加一元多项式的表示及相加用一个线性表用一个线性表P来表示：来表示：假设假设mnext;while(p-data!=x&p!=L)p=p-next;if(p=L)returnNULL;/没找到没找到p-freq+;s=p-pre;while(s!=L&s-freqfreq)s=s-pre;/查找插入位置查找插入位置if(s!=p-pre)returnp;if(s!=p-pre)p-pre-next=p-next;p-next-pre=p-pre;p-next=s-next;s-next-pre=p;s-next=p;p-pre=s;spp
