数据结构线性表.ppt

《数据结构线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表.ppt（80页珍藏版）》请在优知文库上搜索。

1、2023-3-21 第第2章章 线性表线性表 2.1 2.1 线性表的概念及运算线性表的概念及运算 2.2 2.2 线性表的顺序存储线性表的顺序存储 2.3 2.3 线性表的链式存储线性表的链式存储 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加2.5 2.5 顺序表和链表的综合比较顺序表和链表的综合比较 2.6 2.6 总结总结2023-3-222.1 2.1 线性表的概念及运算线性表的概念及运算一、线性表的定义一、线性表的定义线性表线性表(Linear List)(Linear List)是由是由n(nn(n0)0)个类型个类型相同的数据元素组成的有限序列，记做：相同的数据元

2、素组成的有限序列，记做：（a a1 1,a,a2 2, ,，a ai-1i-1，a ai i，a ai+1i+1， ，a an n）2.1.1 2.1.1 线性表的逻辑结构线性表的逻辑结构 2023-3-23线性表的形式定义为：线性表的形式定义为： 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-24二、线性表的特点二、线性表的特点同一性：同一性

3、：线性表由同类数据元素组成，每一线性表由同类数据元素组成，每一 个个a ai i必须属于同一数据对象。必须属于同一数据对象。有穷性：有穷性：线性表由有限个数据元素组成，表线性表由有限个数据元素组成，表 长度就是表中数据元素的个数。长度就是表中数据元素的个数。有序性：有序性：线性表中相邻数据元素之间存在着线性表中相邻数据元素之间存在着 序偶关系序偶关系a ：表中必存在唯一的一个表中必存在唯一的一个“第一元素第一元素”；表中必存在唯一的一个表中必存在唯一的一个“最后元素最后元素”；除最后元素之外，均有除最后元素之外，均有 唯一的后继唯一的后继；除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯

4、一的前驱。2023-3-252.1.22.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)

5、操作前提：线性表操作前提：线性表L已存在已存在 。 操作结果：将表操作结果：将表L置为空表。置为空表。 判空表、求表长、查找、插入、删除判空表、求表长、查找、插入、删除 ADT LinearList2023-3-262.2 2.2 线性表的顺序存储线性表的顺序存储 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 线性表线性表的最简单的顺序存储方法是：的最简单的顺序存储方法是： 一、顺序表一、顺序表: 顺序存储顺序存储是以元素在存储器中的相对位置是以元素在存储器中的相对位置表示元素间的逻辑关系。表示元素间的逻辑关系。 用一组地址连续的存储单元，依次存放用一组地址连续的存储单元，依次存放线性

6、表中的数据元素线性表中的数据元素（顺序表）（顺序表）: a1 a2 ai-1 ai an2023-3-27LOC(ai) = LOC(a1) + (i-1)k 第一个数据元素第一个数据元素a1的存储位置称线的存储位置称线性表的性表的起始地址起始地址(基地址基地址)，所有数据元素所有数据元素的存储位置均取决于的存储位置均取决于a1的存储位置。的存储位置。 LOC(ai) = LOC(ai-1) + k若每个数据元素所占存储长度为若每个数据元素所占存储长度为k，则有：，则有：2023-3-28二、顺序表结构示意图二、顺序表结构示意图存储地址 内存空间状态 逻辑地址 Loc(a1) a11 Loc(

7、a1)+(2-1)k a2 2 loc(a1)+(i-1)k ai i loc(a1)+(n-1)k an n . loc(a1)+(maxlen-1)k 空闲2023-3-29三、顺序表结构的三、顺序表结构的C语言定义语言定义#define maxsize=线性表可能达到的最大长度；线性表可能达到的最大长度；typedef struct ElemType elemmaxsize/* 线性表占用的数组空间线性表占用的数组空间*/ int last； /*记录线性表最后一个元素在数组记录线性表最后一个元素在数组elem 中的位置（下标值），空表置为中的位置（下标值），空表置为-1*/ SeqLi

8、st； 注意区分元素的序号和数组的下标，如注意区分元素的序号和数组的下标，如a a1 1的序号为的序号为1 1，而其对应的数组下标为，而其对应的数组下标为0 0。 2023-3-2102.2.2 线性表顺序存储结构的基本运算线性表顺序存储结构的基本运算 线性表的基本运算线性表的基本运算： 查找操作查找操作 插入操作插入操作 删除操作删除操作 顺序表合并运算顺序表合并运算 顺序表的优缺点分析顺序表的优缺点分析2023-3-211一、查找操作一、查找操作 线性表的两种基本查找运算：线性表的两种基本查找运算：按序号查找按序号查找 GetData(L,i)GetData(L,i)：要求查找线性要求查找

9、线性表表L L中第中第i i个数据元素，其结果是个数据元素，其结果是L.elemi-1L.elemi-1或或L-elemi-1L-elemi-1。按内容查找按内容查找 LocateLocate（L,e):L,e): 要求查找线性要求查找线性表表L L中与给定值中与给定值e e相等的数据元素，其结相等的数据元素，其结果是：若在表果是：若在表L L中找到与中找到与e e相等的元素，相等的元素，则返回该元素在表中的序号；若找不到，则返回该元素在表中的序号；若找不到，则返回一个则返回一个“空序号空序号”，如，如-1-1。2023-3-212成功成功查找操作示意图查找操作示意图查找操作查找操作: Loc

10、ate(L, e ) 23 75 41 38 54 62 17L.elemL. lastmaxlene =38ppp ppP 0 1 2 3 0 7p 50失败失败基本操作是:将顺序表中的元素逐个和给定值e相比较。2023-3-213线性表的查找算法线性表的查找算法 int Locate(SeqList L，ElemType e) p=0 ; /*p为扫描计数器，初值为为扫描计数器，初值为0，即从第一，即从第一 个元素开始比较个元素开始比较*/while (p=L.last)&(L.elemp!=e) ) p+; /*顺序扫描表，直到找到值为顺序扫描表，直到找到值为e的元素的元素, 或扫描到表

11、尾而没找到或扫描到表尾而没找到*/ if (p=L.last) return(p+1);/*若找到值为若找到值为e的元素的元素,则返回其序号则返回其序号*/else return(-1); /*若没找到，则返回空序号若没找到，则返回空序号*/时间复杂度：时间复杂度：O(n)2023-3-214二、插入操作二、插入操作 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i(1in+1)i(1in+1)个位置，插入一个新元素个位置，插入一个新元素e e，使长度为，使长度为n n的线性表的线性表: :(a(a1 1,a,a2 2, , ，a ai-1i-1，a ai i，a an n) ) 变

12、成长度为变成长度为n+1n+1的线性表的线性表: : （a a1 1，,a,ai-1i-1，e e，a ai i，a an n）。）。2023-3-215插入插入操作示意图操作示意图a1 a2 ai-1 ai ana1 a2 ai-1 eaian操作过程如下：操作过程如下：2023-3-216例：例：线性表线性表 (4,9,15,28,30,30,42,51,62)，需，需在第在第4 4个元素之前插入一个元素个元素之前插入一个元素“21”。则需要将。则需要将第第9 9个位置到第个位置到第4 4个位置的元素依次后移一个位置，个位置的元素依次后移一个位置，然后将然后将“21”插入到第插入到第4 4

13、个位置，个位置，序号序号移动元素移动元素插入元素插入元素12345678109491528303042516249152830304262514915212830304262512023-3-217插入算法插入算法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

14、=L-elemk; L-elemi-1=e; L-last+; return(OK); 时间复杂度：时间复杂度：O(n)2023-3-218三、删除操作三、删除操作 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i (1in)个元素删去，使长度为个元素删去，使长度为n的线的线性表性表 (a1，,ai-1，ai，ai+1，an)，变成长度为变成长度为n-1的线性表的线性表: : (a1，,ai-1， ai+1，an)。 2023-3-219删除删除操作示意操作示意操作过程如下：操作过程如下：ai+1 ana1 a2 ai-1 ai ai+1 ana1 a2 ai-1 2023-3-22

15、0 删除删除算法算法 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-221四、合并运算四、合并运算 已知已知 ：有两个顺序表有两个顺序表LA和和LB，其元，其元素均为非递减有序排列，要求编写算法，素均为非递减有序排列，要求编写算法，将将LA和和LB合

16、并成一个顺序表合并成一个顺序表LC，并使，并使LC也是非递减有序排列。也是非递减有序排列。 顺序表顺序表合并算法：合并算法：void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0; j=0; k=0;2023-3-222while(ilast&jlast) if(LA-elemielemj) LC-elemk=LA-elemi; i+; k+; else LC-elemk=LB-elemj; j+; k+; while(ilast) LC-elemk=LA-elemi; i+; k+; while(jlast) LC-elemk=LB-elemj; j+; k+; LC-last=LA-last+LB-last+1; 时间复杂度：时间复杂度：O(n+m)2023-3-223五、顺序存储结构的优点和缺点五、顺序存储结构的优点和缺点 优点：优点：1.1.无需为表示结点间的逻辑关系而增加额外的存储空间；无需为表示结点间的逻辑关系而增加额外的存储空间； 2.2.可方便地随机存取表中的任一元素。可方便地随机存取表中的任一元素。 缺点：缺点：1.