数据结构线性表.ppt

2023/3/2,1,第2章 线性表,2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加2.5 顺序表和链表的综合比较 2.6 总结,2023/3/2,2,2.1 线性表的概念及运算,一、线性表的定义线性表(Linear List)是由n(n0)个类型相同的数据元素组成的有限序列，记做：（a1,a2,，ai-1，ai，ai+1，an）,2.1.1 线性表的逻辑结构,2023/3/2,3,线性表的形式定义为：Linear-list=(D,R),其中:D=ai|aiD0,i=1,2,n,n0 R=N N=|ai-1,aiD0,i=2,3n D0为某个数据对象；n为表的长度。,线性表是一种最简单、最常用的数据结构,2023/3/2,4,二、线性表的特点,同一性：线性表由同类数据元素组成，每一 个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表 长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着 序偶关系：,表中必存在唯一的一个“第一元素”；表中必存在唯一的一个“最后元素”；除最后元素之外，均有 唯一的后继；除第一元素之外，均有 唯一的前驱。,2023/3/2,5,2.1.2线性表的抽象数据类型定义,ADT LinearList数据元素：D=ai|aiD0,i=1,2,n n0,D0为某数据对象关系：|ai,ai+1D0，i=1,2,n-1基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。判空表、求表长、查找、插入、删除 ADT LinearList,2023/3/2,6,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储结构,线性表的最简单的顺序存储方法是：,一、顺序表:,顺序存储是以元素在存储器中的相对位置表示元素间的逻辑关系。,用一组地址连续的存储单元，依次存放线性表中的数据元素（顺序表）:,2023/3/2,7,LOC(ai)=LOC(a1)+(i-1)k,第一个数据元素a1的存储位置称线性表的起始地址(基地址)，所有数据元素的存储位置均取决于a1的存储位置。,LOC(ai)=LOC(ai-1)+k,若每个数据元素所占存储长度为k，则有：,2023/3/2,8,二、顺序表结构示意图,2023/3/2,9,三、顺序表结构的C语言定义,#definemaxsize=线性表可能达到的最大长度；typedef struct ElemType elemmaxsize/*线性表占用的数组空间*/int last；/*记录线性表最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList；,注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。,2023/3/2,10,2.2.2 线性表顺序存储结构的基本运算,线性表的基本运算：查找操作 插入操作 删除操作 顺序表合并运算 顺序表的优缺点分析,2023/3/2,11,一、查找操作,线性表的两种基本查找运算：按序号查找 GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。按内容查找 Locate（L,e):要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。,2023/3/2,12,成功,查找操作示意图,查找操作:Locate(L,e),e=,38,P,0,1,2,3,0,7,50,失败,基本操作是:将顺序表中的元素逐个和给定值e相比较。,2023/3/2,13,线性表的查找算法,int Locate(SeqList L，ElemType e)p=0;/*p为扫描计数器，初值为0，即从第一 个元素开始比较*/while(p=L.last)/*若没找到，则返回空序号*/,时间复杂度：O(n),2023/3/2,14,二、插入操作,线性表的插入运算是指在表的第i(1in+1)个位置，插入一个新元素e，使长度为n的线性表:(a1,a2,，ai-1，ai，an)变成长度为n+1的线性表:（a1，,ai-1，e，ai，an）。,2023/3/2,15,插入操作示意图,e,ai,an,操作过程如下：,2023/3/2,16,例：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，,2023/3/2,17,插入算法,int InsList(SeqList*L,int i,ElemType e)int k;if(iL-last+2)printf(“i值不合法”)；return(ERROR);if(L-last=maxsize-1)printf(“表已满无法插入”)；turn(ERROR);for(k=L-last;k=i-1;k-)L-elemk+1=L-elemk;L-elemi-1=e;L-last+;return(OK);,时间复杂度：O(n),2023/3/2,18,三、删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(a1，,ai-1，ai，ai+1，an)，变成长度为n-1的线性表:(a1，,ai-1，ai+1，an)。,2023/3/2,19,删除操作示意,操作过程如下：,ai+1,an,2023/3/2,20,删除算法,int DelList(SeqList*L,int i,ElemType*e)int k;if(iL-last+1)printf(“位置不合法！”)；return(ERROR);*e=L-elemi-1;for(k=i;ilast;k+)L-elemk-1=L-elemk;L-last-;return(OK);,时间复杂度：O(n),2023/3/2,21,四、合并运算,已知：有两个顺序表LA和LB，其元素均为非递减有序排列，要求编写算法，将LA和LB合并成一个顺序表LC，并使LC也是非递减有序排列。,顺序表合并算法：,void merge(SeqList*LA,SeqList*LB,SeqList*LC)i=0;j=0;k=0;,2023/3/2,22,while(ilast,时间复杂度：O(n+m),2023/3/2,23,五、顺序存储结构的优点和缺点,优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。,缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其 它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续的存储空间，存储分配只能 预先进行静态分配。因此当表长变化较大时，难以确 定合适的存储规模。,2023/3/2,24,2.3 线性表的链式存储,链表定义：,我们从两个角度来讨论链表：1.从实现角度:链表可分为动态链表和静态链表；2.从链接方式的角度:链表可分为单链表、循环链表和双链表。,采用链式存储结构的线性表称为链表。,2023/3/2,25,2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表*2.3.5 静态链表,链表,2023/3/2,26,2.3.1 单链表,头指针：指向链表首结点的指针。,用一组地址任意的存储单元存储线性表中的数据元素，对每一数据元素附加指针信息，以便表述元素间的逻辑关系。,因每个结点仅有一个指针域，故称作单链表。,指针：指示后继元素存储地址。,2023/3/2,27,一、单链表的示例图,2023/3/2,28,二、带头结点的单链表示意图,为了操作的方便，一般在单链表的第一个结点之前附设一个头结点。,带头结点的单链表：,带头结点的空单链表：,2023/3/2,29,三、单链表的存储结构描述,typedef struct Node/*结点类型定义*/ElemType data；struct Node*next；Node,*LinkList；/*LinkList为结构指针类型*/,2023/3/2,30,2.3.2 单链表上的基本运算,线性表的基本运算：建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例：求单链表的长度 求两个集合的差,2023/3/2,31,一、建立单链表,1、头插法建表,操作步骤：,1、建立一个“空表”；,2、输入数据元素an，建立结点并插入；,3、输入数据元素an-1，建立结点并插入；,an-1,4、依次类推,直至输入完a1结束。,2023/3/2,32,2、头插法建表算法,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;L=(Linklist)malloc(sizeof(Node)；L-next=NULL;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag=0;,2023/3/2,33,3、尾插法建表,操作步骤：,1、建立一个“空表”；,2、输入数据元素a1，建立结点并插入；,3、输入数据元素a2，建立结点并插入；,a2,4、依次类推,直至输 入完an结束。,2023/3/2,34,4、尾插法建表算法,Linklist CreateFromTail()LinkList L;Node*r,*s;int flag=1;L=(Node*)malloc(sizeof(Node);L-next=NULL;r=L;while(flag)c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s else r-next=NULL;flag=0;,2023/3/2,35,二、单链表查找,1、按序号查找,单链表是一种顺序存取结构,为找第 i 个数据元素,必须从头顺序扫描前 i-1 个数据元素，需要计数器 j 与指针 p 协调处理。,其中要求指针p始终指向线性表中第j个数据元素。,2023/3/2,36,0,j,1,2,3,Pdata=30,例i=3时,按序号查找的实现过程:,2、按序号查找示例图,2023/3/2,37,3、按序号查找算法,Node*Get(LinkList L,int i)Node*p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULL)&(jnext；j+；if（i=j）return p；/*找到了第i个结点*/else return NULL；/*找不到,i0或in*/,2023/3/2,38,4、按值查找算法,/*在带头结点的单链表L中查找其值等于key的结点,若找到则返回该结点的指针p,否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/*从表中第一个结点比较*/while(p!=NULL)if(p-data!=key)p=p-next;else break;/*找到结点key，退出循环*/return p;,2023/3/2,39,三、单链表插入操作,s,在单链表中第 i 个结点之前插入结点e 的操作即为:,将有序对,可见,在链表中第 i 个结点之前插入结点需要找到并修改第 i-1 个结点的指针。,改变为 和,2023/3/2,40,单链表插入算法,void InsList(LinkList L,int i,ElemType e)Node*pre,*s;int k=0;pre=L;while(pre!=NULL,2023/3/2,41,四、单链表删除,在单链表中删除第 i 个结点的操作即为:,将有序对 和 改变为,可见,在链表中删除第 i 个结点同样需要找到并修改第 i-1 个结点的指针。,2023/3/2,42,单链表删除算法,void DelList(LinkList L,int i,ElemType*e)Node*p,*r;int k=0;p=L;while(p-next!=NULL/*释放被删除结点的空间*/,2023/3/2,43,五、求单链表的长度,int ListLength(LinkList L)/*L为带头结点的单链表*/Node*p;p=L-next;j=0;while(p!=NULL)p=p-next;j+;return j;,2023/3/2,44,六、求两个集合的差,已知：以单链表表示集合,假设集合A用单链表LA表示,集合B用单链表LB表示,设计算法求两个集合的差，即求A-B。,算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于链表LA中的每个元素e，在链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。,2023/3/2,45,求两个集合差的算法,void Difference(LinkList LA,LinkList LB)Node*pre;*p,*r;pre=LA;p=LA-next;/*p指向LA表中某结点,pre始终指向p 的前驱*/while(p!=NULL)q=LB-next;while(q!=NULL,2023/3/2,46,2.3.3循环链表(Circular Linked List),首尾相接的链表称为循环链表。将最后一个结点的指针又指回头结点即得循环链表。,循环单链表与单链表的差别在于：判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,2023/3/2,47,循环单链表的合并,已知:两个带头结点的循环单链表LA、LB，编写算法，将两个循环单链表首尾相接合并为一个循环单链表，其头指针为LA。,算法思想:先找到两个链表的尾，并分别由指针p、q指向它们，然后将LA链表的尾与LB链表的第一个结点链接起来，并将LB链表的尾与LA链表的头结点链接起来即可。,2023/3/2,48,循环单链表合并算法实现,LinkList merge_1(LinkList LA,LinkList LB)/*将两个链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;while(q-next!=LB)q=q-next;p-next=LB-next;q-next=LA;free(LB);return(LA);,2023/3/2,49,2.3.4 双向链表,一、双向链表的结构定义：typedef struct Dnode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；,链表中每结点不仅有指向后继的指针，还有指向前趋的指针，这种链表称为双向链表。,2023/3/2,50,二、双向链表的操作特点：,“查找”和单链表相同，并可增加一种从后向前的“查找”方式。,“插入”和“删除”操作时可直接定位于i号结点，但需要同时修改两个方向上的指针。,p-next-prior=p-prior-next=p,2023/3/2,51,三、双向链表插入示意图,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,P定位于ai?,2023/3/2,52,四、双向链表删除示意图,q=p-next;p-next=q-next;p-next-prior=p;free(q);,双向链表删除操作是否可不用工作指针q?,q,2023/3/2,53,p-next=p-next-next;free(p-next-prior);p-next-prior=p;,P定位于ai?,2023/3/2,54,五、双向循环链表示意图,非空表,he,空表,he,2023/3/2,55,六、双向链表应用举例,已知：设一个循环双链表L=（a,b,c,d）编写一个算法将链表转换为L=（b,a,c,d）。算法思想：实际上是交换表中前两个元素的次序。算法实现：voidswap(DLinkList L)DNode*p,*q,*h;h=L-next;p=h-next;q=h-prior;h-next=p-next;p-next-prior=h;p-prior=q;p-next=h;L-next=p;h-prior=p;,2023/3/2,56,*2.3.5 静态链表(Static Linked List),在没有“指针”数据类型的高级语言中，可用“结构体”数组描述线性链表。,一、静态链表的结构定义,#define Maxsize=链表可能达到的最大长度 typedef struct ElemType data;int cur;Component,StaticListMaxsize;,2023/3/2,57,数组中cur域的内容为后继元素的下标(位置),其作用相当于指针，称其为游标。,该数组中元素的逻辑关系，取决于cur的值，而不取决于元素在数组中的相对位置。0号元素为头结点，cur值为0表示链表结束。,这种由数组描述的链表称为静态链表,2023/3/2,58,二、静态链表插入和删除示例,线性表:(a,b,c,d,f,g,h,i）,Maxsize=11,2023/3/2,59,三、静态链表初始化,初始化操作是指将静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：,void initial(StaticList space,int*av)int k;space0.cur=0;/*设置静态单链表的头指针指向位置0*/for(k=0;kMaxsize-1;k+)spacek.cur=k+1;/*连链*/spaceMaxsize-1.cur=0;/*标记链尾*/*av=1;/*设置备用链表头指针初值*/,2023/3/2,60,四、静态链表结点的分配与回收,分配结点int getnode(int*av)/*从备用链表中取一个结点,分配给待插入的静态链表*/int i=*av;*av=space*av.cur;return i;,结点回收void freenode(int*av,int k)/*将下标为 k的空闲结点插入到备用链表*/spacek.cur=*av;*av=k;,2023/3/2,61,五、静态链表插入操作,1、先从备用单链表上取一个可用的结点；2、将其插入到已用静态单链表第i个元素之前。void insbefore(StaticList space,int i,int*av)j=*av;/*从备用表中取到可用结点空间的下标*/*av=space*av.cur;/*修改备用表的头指针*/spacej.data=x;k=space0.cur;for(m=1;mi-1;m+)/*找第i-1个元素的位置k*/k=spacek.cur;spacej.cur=spacek.cur;spacek.cur=j;,2023/3/2,62,六、静态链表删除,首先寻找第i-1个元素的位置，之后通过修改相应的游标域进行删除，并实现回收。void delete(StaticList space;int i;int*av)k=space0.cur;for(m=1,mi-1;m+)k=spacek.cur;j=spacek.cur;spacek.cur=spacej.cur;spacej.cur=*av;*av=j;/*回收*/,2023/3/2,63,它由n+1个系数唯一确定,故可用线性表来表示:P=(p0,p1,，pn)每项的指数隐含在序号里,一.一元多项式的表示,但对于形如 S(x)=1+3x10234 2x29456的稀疏多项式，上述表示方法却不合适！,2.4 一元多项式的表示及相加,2023/3/2,64,一般情况下的一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n,故可用如下线性表表示一元稀疏多项式：(p1,e1),(p2,e2),(pm,em)其每个元素有两个数据项(系数和指数),2023/3/2,65,typedef struct Polynode int coef;int exp;Polynode*next;Polynode,*Polylist;,二、一元稀疏多项式结点结构定义,例如:P999(x)=7x3-2x12-8x999,可用表示为：(7,3),(-2,12),(-8,999),2023/3/2,66,输入多项式的系数和指数，用尾插法建立链表。Polylist polycreate()Polynode*head,*rear,*s;int c,e;rear=head=(Polynode*)malloc(sizeof(Polynode);/*建立多项式的头结点，rear 始终指向单链表的尾*/scanf(“%d,%d”,三、建立多项式链表,2023/3/2,67,四、两个多项式相加,运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项复抄到“和多项式”中。,2023/3/2,68,五、两个多项式相加算法,void polyadd(Polylist la;Polylist lb)a=la-next;b=lb-next;/*a和b分别指向la和lb链表*/c=la;/*c指向和多项式链表中的尾结点*/while(a!=NULL b=b-next/*将b结点加入到和多项式中*/*将多项式la或lb中剩余的结点加入到和多项式中*/,2023/3/2,69,sum=a-coef+b-coef;if(sum!=0)a-coef=sum;c-next=a;c=a;a=a-next;temp=b;b=b-next;free(temp);else temp=a;a=a-next;free(temp);temp=b;b=b-next;free(temp);,指数相等系数相加,2023/3/2,70,la或lb中剩余结点加入到和多项式,if(a!=NULL)c-next=a;else c-next=b;,2023/3/2,71,2.5 顺序表和链表的比较,一、顺序表与链表的比较 基于空间的考虑 基于时间的考虑 基于语言的考虑,二、线性表链式存储方式的比较 见P64 表2-1,2023/3/2,72,1基于空间的考虑,顺序表为静态分配的存储结构,故有如下问题：1.要按最大可能的表长分配存储空间；2.必要时难于扩充存储空间。,动态链表可根据需要动态生成结点,因其需用指针表示元素间的逻辑关系，故其存储密度较低。存储密度=元素本身占用存储量/结点占用存储量,静态链表的兼具顺序表与动态链表的特点。,2023/3/2,73,2基于时间的考虑,顺序表的特点在于可随机存取表中元素,但插入、删除操作时是要大量移动元素；,动态链表的特点在于插入、删除操作时只改指针步移动元素，但不能随机存取表中元素，需顺链找；,2023/3/2,74,3基于语言的考虑,对于没有“指针”类型的高级语言，若线性表有大量的插入、删除操作时，可选用静态链表。,对于有“指针”类型的高级语言，若线性表的长度不变，且有大量的插入、删除操作时，也可选用静态链表，因静态链表比动态链表更方便。,2023/3/2,75,2.6 总结与提高,主要知识点：一、线性表的特征；二、线性表的存储方式；三、链表的操作技术：1、从“头”顺链查找技术；2、指针保留技术；3、表尾判断技术；,2023/3/2,76,典型例题,例1、整数顺序表奇偶数分离问题,方法二：使用原顺序表空间，空间复杂 度降为O(1)。,方法一：额外申请一个顺序表，时、空 复杂度均为O(n)。,2023/3/2,77,AdjustSqlist(Seqlist*L)int i=0,j=L-last;while(ielemi%2!=0)i+;/*检测表的左半部分,若为奇数,则i加1,直到找到偶数为止*/while(L-elemj%2=0)j-;/*检测表的右半部分,若为偶数,则j减1,直到找到奇数为止*/if(ielemi;L-elemi=L-elemj;L-elemj=t;/*交换*/,2023/3/2,78,例2、单链表就地逆置,void reverselist(linklist L)p=L-next;L-next=NULL;while(p!=NULL)q=p-next;p-next=L-next;L-next=p;p=q,2023/3/2,79,例3、链表表示的二进制数加1算法,算法思想：从高位向低位找到最后一个0，将其变为1，并将此后的各位置0。若未找到0，则表头插入一个结点，置为1，其余结点置0。,自己设计算法！,2023/3/2,80,第二章结束,