《一章线性表.ppt》由会员分享，可在线阅读，更多相关《一章线性表.ppt（112页珍藏版）》请在三一办公上搜索。
1、第2章 线性表,概述,线性表是最很简单也是最重要的数据结构，它是线性结构。所以我们学习数据结构从线性表开始。从本章开始到第四章都是讨论线性。是整个数据结构的基础按逻辑结构、存储结构、算法设计这三个顺序进行分析。,2.1线性表的逻辑结构,线性表（Linear List）是由n（n0）个数据元素（结点）a1，a2，an组成的有限序列。数据元素的个数n定义为表的长度（n=0时称为空表）。将非空的线性表（n0）记作：（a1，a2，an）数据元素ai（1in）只是个抽象符号，其具体含义在不同情况下可以不同。,线性表的逻辑结构图示,a1,ai,an,线性表的例子,【例1】英文字母表（A，B，Z）是线性表，
2、表中每个字母是一个数据元素（结点）【例2】一副扑克牌的点数（2，3，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数和花色【例3】学生成绩表（见概论中表1.1）中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。,线性表的特征,有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1。,常见的线性表的基本运算,常见的基本运算有：初始化，求表长，求第i个结点，查找，插入和删除等操作。为
3、了尽可能地比较准确地描述些运算过程，我们采用类似于函数的形式对它进行描述。这些基本运算并不是凭空想出来，而是根据实际应用总结出来的。,线性表的ADT表示,ADT LinearList 数据元素:D=ai|aiD0,i=1,2,3n,n0,D0某一数据对象逻辑结构:R=,ai,ai+1 D0,i=1,2,n-1基本操作:,1 InitList（L）,操作前提：L为一个未初始化的线性表。操作结果：将L初始化为空表。构造一个空的线性表L，即表的初始化。,2.DestroyList(L),操作前提：线性表L已存在。操作结果：将L销毁。,3.ClearList(L),操作前提：线性表L已存在。操作结果：
4、将L置空,4.IsEmptyList(L),判断L是否为空表。如为空返回true，否则返回faslse前提：L已存在，,5.ListLength(L),求线性表L中的结点个数，即求表长。,6.Locate(L,e),确定元素e在线性表L中的位置。（与书上不同）在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x，则返回一个特殊值表示查找失败,7.GetData(L,i),操作前提：表L已存在，且i值 合法，返回线性表L中第i个元素的值。,8.InsList(L,i,e),在线性表L的第i个位置上插入一个元素e，i+
5、1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。,9.DeleteList（L,i,e）,删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。并且用e返回这个删除元素的值。长度减1.ADT LinearList,说明,这些操作只是从逻辑结构的角度来讨论的，主要用来说明这些运算的功能，是“做什么”,至于如何实现，则要等到讨论存储结构后才考虑。,2.2 线性表的顺序存储结构,概述顺序表顺序表的算法实现,2.2.1.概述,简单来说了，本节
6、就是讨论一维数组的使用。这在C语言中已经详细讨论过。,2.2.2.顺序表,1.定义2.存储地址公式3.特点,2.2.1顺序表,顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法(2)顺序表（Sequential List）用顺序存储方法存储的线性表简称为顺序表（Sequential List）。,内存表示,a1,a2,a3,.,ai,.,an每个结点占C个存储单元。,2.结点ai 的存储地址,设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址
7、（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：LOC（ai）=LOC（a1）+（i-1）*c（1in）,思考题,int a10,a2=a3+a5;为什么我们在程序中引用数组元素时，没有应用此地址公式？,顺序表的特点,在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。,4.存储结构,#define MaxSize 100/表空间的大小
8、可根据实际需要而定，这里假设为100typedef struct StudInfo STUDINFO;typedef int ElemType;/DataType的类型可根据实际情况而定，这里假设为int typedef struct ElemType elemMaxSize；/向量data用于存放表结点 int last；/最后一个元素的下标 SeqList;,ElemType是什么？,根据实际需要，把某个数据类型定义为ElemType，而且针对不同的数据类型，在程序上机测试，要对程序做相应的修改。,序号与下标(index)关系,第1个元素的下标为0第2个元素的下标为1.第last+1个元素
9、的下标为last,表的长度与last的关系,表的长度=last+1,2.2.3算法实现,定义了存储结构后，就可以讨论运算实现。插入操作删除操作查找操作,1.插入操作,插入运算的逻辑描述线性表的插入运算是指在表的第i（1in+1）个位置上，插入一个新结点x，使长度为n的线性表：（a1，ai-1，ai，an）变成长度为n+1的线性表：（a1，ai-1，e，ai，an）要考虑两种极端情况：当线性表已满时，怎么办？当插入位置不正确怎么办？,插入过程说明,在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置
10、，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将e插入表的末尾。,插入算法,#define OK 1#define ERROR 0void InsertList(SeqList*L，ElemType e，int i)/将新结点x插入L所指的顺序表的第i个结点的位置 int j;if(iL-last+2)printf(“position error”);/非法位置，退出运行 return ERROR;if(L-last=MaxSize)printf(“Over flown”);return ERROR;,for(k=L-last;k=i-1;k-)L-elemk+1
11、=L-elemk;/结点后移L-elemi-1=e;/插入xL-last+;/表长加1return OK;/插入算法结束,算法性能分析,最好情况，插入到表的最后，不需要移动元素，可以直接插入e。最坏情况，插入到第1个位置，需要移动n次。一般情况，移动次数与插入位置i有关。,平均情况,设n+1种等几率情况。,插入示例,假设在i=3位置插入一个35,算法分析,现把一个数x插入到第i个位置。假设表里已有n个结点。,分析,移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1
12、)。当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n)。那么平均来说时间复杂度为多少呢？,时间复杂度的推导过程,插入位置有1到n+1，假设机率均等，每个位置的可能性为1/(n+1)。,平均时间复杂度,EIS(n)=n/2表长的一半。所以算法的平均时间复度为O(n)。即与表中已有元素的个数 成正比。,2.删除操作,删除操作的逻辑说明删除操作的算法实现删除操作的性能分析,删除运算的逻辑描述,线性表的删除运算是指将表的第i（1in）个结点删去，使长度为n的线性表（a1，ai-1，ai，ai+1，an）变成长度为n-1的线性表（a1，ai-1，ai+1，an）注意：当要删除元素的位置i
13、不在表长范围（即i1或iL-length）时，为非法位置，不能做正常的删除操作,顺序表删除操作过程,后面的元素向前移动过程,删除算法,int DelList(SeqList*L,int i,ElemType*e)/从L所指的顺序表中删除第i个结点aiint k;if(iL-last+1)printf(“删除位置不存在!”);return ERROR;*e=L-elemi-1;for(k=i;klast;j+)L-elemk-1=L-elemk;/结点前移 L-last-;/表长减小 return OK;,时间复杂度,Ede(n)=(n-1)/2所以平均时间复杂度为O(n),3.查找操作,按序号
14、查找 GetData(L,i)return L.elemi-1;按内容查找 Locate(L,e),Locate(L,e),int Locate(SeqList L,ElemType e)int i=0;while(i=L.last),时间复杂度,O(n),例子 两个有序表的合并,LA和LB是两个顺序表，且按非递减有序排列。把它们合并成一个非递减有序排列。例如LA=(2,2,3),LB=(1,3,3,4)，合并后为LC=(1,2,2,3,3,3,4)。,void merge(SeqList*La,SeqList*Lb,SeqList*Lc)int i=0,j=0,k=0;while(ilast
15、,while(ilast)Lc-elemk+=La-elemi;while(jlast)Lc-elemk+=Lb-elemj+;Lc-last=La-last+Lb-last+1;,时间复杂度,O(La-last+Lb-last),顺序表的优点,存储效率高，存储结构本身已表示数据的逻辑结构，无需额外的存储空间表示逻辑结构。随机访问某个元素。,顺序表的缺点,插入和删除操作需要移动大量的结点。存储空间分配是静态分配。表的大小要事先确定，这样会造成程序不能适应 实际情况的变化。如果事先把表长确定太大，可能会浪费存储空间。如果把表长确定得太小，可能造成数据溢出。,2.3 线性表的链式存储结构,顺序表的
16、优点：随机存取结构，简单（用数组）方便。顺序表的缺点：插入和删除需要移动大量的元素(n/2).这了避免大量结点移动，我们采用了线性表的另一种结构：链式存储结构,链式存储结构,简称为链表，它不仅可以用来表示线性结构，也可以表示非线性结构。是最常见的存储结构之一。链式存储结构的具体形式有多种：单链表，双链表，循环链表等。我们主要讨论单链表。,2.3.1单链表,链表的结构示意图。现在一个元素包括二部分内容：一部分是数据本身，另一部分是下一个元素的地址。,链表结点的存储结构,data是数据域，存放数据信息本身next是指针域（又称链域）存放下一个结构的地址。线性表的每个结点就是通过指针域把n个逻辑上相
17、邻的结点链接起来。由于每个结点只有一个指针域，所以称单链表。,结点定义举例,Typedef struct Node ElemType data;struct Node*next;Node,*LinkList;Node*,LinkList本质上是一样的，但是一般来说用LinkList表示整个链表，用Node*表示某个结点。,链表的表头结点,在链表操作时，经常需要判断第一个结点是否存在。这种判断既浪费运行时间，也增加编程的复杂性。为此，在建立链表时，先建立一个结点，放在链表最前面，这个结点不代表实际元素。在后续的链表处理过程中，这个表头结点永远存，给其他操作带来许多便利。,2.3.2单链表的基本操
18、作,初始化链表建立链表往链表中插入一个结点在链表删除一个结点遍历链表,1.初始化单链表,void InitList(LinkList*L)*L=(LinkList)malloc(sizeof(Node);*L-next=NULL;,2.建立单链表,头插入法尾插入法,void CreateFromHead(LinkList L)Node*s;char c;int flag=1;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag=0;,尾插入法,新
19、建立的结点插入到链表的末尾,void CreateFromTail(LinkList L)Node*r,*s;int flag=1;r=L;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;else flag=0;r-next=NULL;,3.查找,按序号查找按值查找,求序号查找,/L是链表，i是元素的序号，1i n,如果找到，返回该位置的结点，仔细分析，如果i=0，会怎么样？Node*GetNode(LinkList L,int i)int j;Node*p;if(inext!=
20、NULL),按值查找,Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;while(p!=NULL)if(p-data!=key)p=p-next;else break;return p;/思考题，找不到时，p为什么值？,4.求单链表的长度,int ListLength(LinkList L)Node*p;p=L-next;j=0;while(p)p=p-next;j+;return j;,单链表插入操作,问题说明：在单链表中第i个位置插入一个数据元素e。操作的三个步骤：找到i-1元素的指针；申请新结点；插入链表。,算法,int InsLi
21、st(LinkList L,int i,ElemType e)Node*pre,*s;int k;if(inext;k+;/这里最好使用前面的GetNode函数,同学们练习,if(!pre)printf(“cant find the position”);return ERROR;s=(Node*)malloc(sizeof(Node);s-data=e;s-next=pre-next;pre-next=s;return OK;,单链表的删除操作,pre,p,int DelList(LinkList L,int i,ElemType*e)Node*pre,*r;int k;pre=L;k=0;
22、while(pre-next!=NULL,if(pre-next=NULL)printf(“the node to be delete doesnt exist”);return ERROR;r=pre-next;pre-next=r-nxt;e=r-data;free(r);return OK;,练习，用链表重做两个有序表的合并,LinkList MergeLinkList(LinkList La,LinkList Lb)Node*pa,*pb;LinkList Lc;pa=La-next;pb=Lb-next;Lc=La;Lc-next=NULL;r=Lc;while(pa!=NULL,i
23、f(pa)r-next=pa;if(pb)r-nex=pb;free(Lb);return Lc;,循环链表,循环链表是指头尾相连的链表，其实现算法与单链表类似，但是判断当前结点p是否为尾结点不一样，p!=NULL，或 p-next!=NULL对于循环链表 p!=head,或p-next!=head,循环链表的尾指针,经常在尾结点设置链表指针。请大家讨论,把两个循环链表合并成一个,LinkList merge_l(LinkList La,LinkList Lb)Node*p,*q;p=La;q=Lb;while(p-next!=La)p=p-next;while(q-next!=Lb)q=q-
24、next;q-next=La;p-next=Lb-next;free(Lb);return Lb;,在尾结点设置指针,一般循环链表在尾结点设立一个指针，重做上面的这个例子。,例2-3 循环链表的合并,有两个带表头的循环链表La,Lb，将它们合并为一个循环链表，其头指针为La。,LinkList merge_2(LinkList Ra,LinkList Rb)Node*p;p=Ra-next;Ra-next=Rb-next-next;free(Rb-next);Rb-next=p;return Rb;,LinkList merge_1(LinkList La,LinkList Lb)Node*p
25、,*q;p=La;q=Lb;while(p-next!=La)p=p-next;while(q-next!=Lb)q=q-next;q-next=La;p-next=Lb-next;free(Lb);Return La;,双向链表,双向链表,typedef struct DNode ElemType data;struct DNode*prior,*next;DNode,*DoubleList;,带表头的双向链表,双向链表的优点,既可以向前找，又可以向后找，因此查找前驱结点非常方便。某个结点为pp-prior-next=p;p-next-prior=p;,双向链表的插入操作,在p结点之前插入一
26、个结点s s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-next=s;,双向链表的删除操作,删除p结点p-prior-next=p-next;p-next-prior=p-prior;free(p);,静态链表,线性表的应用,一元多项式的运算,逻辑结构,存储结构,struct Polynode double coef;int exp;PolyNode*next;PolyNode,*PolyList;,1.多项式链表的建立,Polylist Polycreate()Polynode*head,*rear,*s;head=(Polynode*
27、)malloc(sizeof(Polynode);rear=head;scanf(“%d,%d”,两个多项式相加,void Polyadd(Polylist pa,PolyList pb)Polynode*p,*q,*tail,*temp;int sum;p=pa-next;q=pb-next;tail=pa;,while(p!=NULL,else temp=p;p=p-next;free(temp);temp=q;q=q-next;free(temp);else tail-next=q;tail=q;q=q-next;,if(p!=NULL)tail-next=p;else tail-nex
28、t=q;,多项式相加,分配一个结点,ListNode*p;/悬挂状态p=(ListNode*)malloc(sizeof(ListNode);,例2：链表置逆,分析,链表置逆,void ReverseLink(LinkList L)p=L-next;L-next=NULL;while(p)q=p-next;p-next=L-next;L-next=p;p=q;,二进制加1,二进制用链表表示，每一个结点代表一位，第一个结点代表最高位，依次存放，最后一个结点。,二进制加1,void BinAdd(LinkList L)Node*q,*r,*temp,*s;q=L-next;r=L;while(q!=NULL)if(q-data=0)r=q;q=q-next;,If(r!=L)r-data=1;Else temp=r-next;s=(Node*)malloc(sizeof(Node);s-data=1;s-next=temp;r-next=s;r=s;r=r-next;,while(r!=NULL)r-data=0;r=r-next;,
