第02章线性表.

第2章线性表主要知识点线性表抽象数据类型顺序表单链表循环单链表循环双向链表静态链表设计举例2.1线性表抽象数据类型1.线性表的定义线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。线性结构:2.线性表抽象数据类型数据:｛a0,a1,…,an-1｝,ai的数据类型为DataType操作:(1)ListInitiate(L)初始化线性表(2)ListLength(L)求当前数据元素个数(3)ListInsert(L,i,x)插入数据元素(4)ListDelete(L,i,x)删除数据元素(5)ListGet(L,i,x)取数据元素｛a0,a1,…,an-1｝表示数据元素有次序关系,简称序列。2.2线性表的顺序表示和实现1.顺序表的存储结构实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。顺序表的存储结构如图所示顺序存储结构的线性表称作顺序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;2.顺序表操作的实现（1）初始化ListInitiate(L)voidListInitiate(SeqList*L){L-size=0;/*定义初始数据元素个数*/}（2）求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}（3）插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L-size;ji;j--)L-list[j]=L-list[j-1];/*依次后移*/L-list[i]=x;/*插入x*/L-size++;/*元素个数加1*/return1;}101112141516listlistMaxSize-10123456i=3Size=6size=713待插数据x710111213141516MaxSize-101234567i=3size=6......（4）删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x){intj;*x=L-list[i];/*保存删除的元素到x中*/for(j=i+1;j=L-size-1;j++)L-list[j-1]=L-list[j];/*依次前移*/L-size--;/*数据元素个数减1*/return1;}10111213141516list删除前101112141516list删除后MaxSize-10123456MaxSize-10123456i=3size=7size=6要删的数据x13......（5）取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i0||iL.size-1){printf(参数i不合法!\n);return0;}else{*x=L.list[i];return1;}}3.顺序表操作的效率分析时间效率分析:算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作(最深层语句频度)T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置i.若i=size，则根本无需移动（特别快）；若i=0，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则插入时的平均移动次数为:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可证:顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)001()()12nnisiiinEpninin110011()()2nndliiinEqninin顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1)主要优点是算法简单，空间单元利用率高；主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。主要优缺点4.顺序表应用举例例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过100个。实现方法：1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中，通过#include“SeqList.h”）程序设计如下：#includestdio.h#defineMaxSize100typedefintDataType;#includeSeqList.hvoidmain(void){SeqListmyList;inti,x;ListInitiate(&myList);for(i=0;i10;i++)ListInsert(&myList,i,i+1);ListDelete(&myList,4,&x);for(i=0;iListLength(myList);i++)ListGet(myList,i,&x);}程序运行结果：12346789102.3线性表的链式表示和实现1.单链表的结构(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。结点结构如图示：指针域数据域nextdata或数据域：存储元素数值数据指针域：存储直接后继的存储位置(2)头指针、头结点和首元结点的区别头指针头结点首元结点a0heada1…an^示意图如下：头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a０的结点。(3)带头结点单链表和不带头结点单链表的比较pa0a1an-1∧…headdatanextx∧s(a)插入前pa0a1an-1∧…headdatanextx∧s(b)插入后1).在带头结点单链表第一个数据元素前插入结点2).删除带头结点单链表第一个数据元素结点pa0a1an-1∧…headdatanext3).在不带头结点单链表第一个数据元素前插入结点a0a1an-1∧…headx∧s(a)插入前a0a1an-1∧…headxs(b)插入后4).在不带头结点单链表其他数据元素前插入结点pai-1a0aian-1∧…headdatanextxs…×5).删除不带头结点单链表第一个数据元素结点a0a1an-1∧…headdatanext×6).删除不带头结点单链表其他数据元素结点pai-1a0aian-1∧…headdatanext…×ai+1结论：（1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数（4）因此，带头结点单链表的算法设计简单结点定义：typedefstructNode{DataTypedata;structNode*next;}SLNode2.单链表的操作实现（1）初始化ListInitiate(head)voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)-next=NULL;}（2）求当前数据元素个数ListLength(head)intListLength(SLNode*head){SLNode*p=head;intsize=0;while(p-next!=NULL){p=p-next;size++;}returnsize;}head...0a1a1na∧size=0(a)...0a1a1na∧size=n(b)pphead（3）插入ListInsert(head,i,x)intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;j=-1;while(p-next!=NULL&&ji-1){p=p-next;j++;}if(j!=i-1){printf(“插入位置参数错！”);return0;}q=(SLNode*)malloc(sizeof(SLNode));q-data=x;q-next=p-next;p-next=q;return1;}0a...ia1na∧qx...1ia0a...ia1na∧...1iaxq(a)(c)(b)ppheadhead①②说明：①要在带头结点的单链表第i（0≤i≤size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q-data=x），最后修改新结点的指针域指向ai结点（即q-next=p-next），并修改ai-1结点的指针域指向新结点q（即p-next=q）。②循环条件由两个子条件逻辑与组成，其中子条件p-next!=NULL保证指针所指结点存在，子条件ji-1保证最终让指针p指向ai-1结点。（4）删除ListDelete(head,i,x)intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;j=-1;while(p-next!=NULL&&p-next-next!=NULL&&ji-1){p=p-next;j++;}if(j!=i-1){printf(“插入位置参数错！”);return0;}s=p-next;*x=s-data;p-next=p-next-next;free(s);return1;}0a...ia1na∧...1ia(a)0a...1na∧...1ia(b)iaiasheadheadp①1ia1iap说明：要在带头结点的单链表中删除第i（0≤i≤size-1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s=p-next），并把数据元素ai的值赋予x（即*x=s-data），最后把ai结点脱链（即p-next=p-next-next），并动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的①对应算法中的删除语句。（5）取数据元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;p=head;j=-1;while(p-next!=NULL&&ji){p=p-next;j++;}if(j!=i){printf(“取元素位置参数错！”);