《计算机软件基础课件PPT第2章-1-线性表》由会员分享，可在线阅读，更多相关《计算机软件基础课件PPT第2章-1-线性表（73页珍藏版）》请在金锄头文库上搜索。
1、线性数据结构线性数据结构：指相邻的前后数据元素之：指相邻的前后数据元素之 间是一对一的线性关系。间是一对一的线性关系。一一.线性表线性表 二二.栈和队列栈和队列 三三.串和数组串和数组1线性表的类型定义线性表的类型定义线性表的顺序表示和实现线性表的顺序表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的应用线性表的应用2一一.线性表线性表3(1)(1)线性表线性表 是一种最简单最常见的是一种最简单最常见的线性数据结构线性数据结构。定义：定义：线性表是线性表是n(n=0)n(n=0)个数据元素的有限序列。个数据元素的有限序列。n n是线性表的长度，是线性表的长度，n=0n=0时为空表时
2、为空表表示：表示：(a(a1 1,a,a2 2,a,ai i,a,an n)线性表中所有元素的性质是相同的线性表中所有元素的性质是相同的相邻的元素之间存在着序偶关系相邻的元素之间存在着序偶关系a 2.12.1 线性表的类型定义线性表的类型定义4（2 2）线性表的特点）线性表的特点线性结构线性结构都具有以上都具有以上4 4个特点。个特点。1 1存在唯一的一个存在唯一的一个“第一元素第一元素”2 2存在唯一的一个存在唯一的一个“最后元素最后元素”4 4除最后元素在外，均有除最后元素在外，均有唯一的后继唯一的后继3 3除第一元素之外，均有除第一元素之外，均有唯一的前驱唯一的前驱a1a2a3a4a5a
3、65（2 2）线性表的特点）线性表的特点例：例：线性数据结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继（）。6(3)(3)线性表的抽象数据类型定义线性表的抽象数据类型定义ADTList 数据对象数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n设线性表为设线性表为(a1，a2,.，ai，.，an),称称i为为ai在线性表中的位序。在线性表中的位序。ADTList基本操作：基本操作：7(4)(4)线性表的基本操作：线性表的基本操作：表2-1 线性表的基本操作 8引用引用对一个数据可以建立一个“引用”，它的作用是为
4、一个变量起一个别名。int a;/定义a是整型变量int&b=a;/声明b是a的“引用”，即b是a的别名，代表同一变量，通过b可以引用a。9假设假设:有两个集合有两个集合 A 和和 B 分别用两个线性表分别用两个线性表 La和和Lb 表表示，即：线性表中的数据元素即为集合中的成员。现要求示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合一个新的集合AAB。例例2-12-1:求集合的并集求集合的并集 上述问题可演绎为：上述问题可演绎为：扩大线性表扩大线性表La，将存在于，将存在于线性表线性表Lb 中而不存在于线性表中而不存在于线性表La中的数据元中的数据元素插入到线性表素插入到线性表
5、La中去。中去。101从线性表从线性表Lb中依次察看每个数据元素中依次察看每个数据元素2依值在线性表依值在线性表LA中进行查找中进行查找3若不存在，则插入之若不存在，则插入之GetElem(Lb,i,e)LocateElem(La,e)ListInsert(La,+La_len,e)操作步骤操作步骤:11 GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e)ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之for(i=1;iLb.elemjLa.elemiLb.elemj，则将，则将Lb.elem
6、jLb.elemj插入到表插入到表LcLc中；中；若若La.elemiLb.elemj La.elemiLb.elemj，则将，则将La.elemiLa.elemi插入到表插入到表LcLc中；中；如此进行下去如此进行下去，直到其中一个表被扫描完毕；，直到其中一个表被扫描完毕；然后再将未扫描完的表中剩余的所有元素放到表然后再将未扫描完的表中剩余的所有元素放到表LcLc中。中。14void MergeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lc /merge_listwhile(i=La_len)&(j=Lb_len)/将La和L
7、b当前较小元素插入Lc中 while(i=La_len)/若 La 不空,将La剩余插入Lc中while(j=Lb_len)/若 Lb 不空,将Lb剩余插入Lc中InitList(Lc);/构造空的线性表 Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);15while(i=La_len)&(j=Lb_len)/La 和 Lb 均非空，i=j=1,k=0 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将 ai 插入到 Lc 中 ListInsert(Lc,+k,ai);+i;else /将
8、bj 插入到 Lc 中 ListInsert(Lc,+k,bj);+j;16 while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入 La 表中剩余元素 while(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入 Lb 表中剩余元素17特点：特点：1 1.逻辑上相邻的元素，逻辑上相邻的元素，物理上也相邻物理上也相邻;2 2.支持支持随机存取。随机存取。顺序表顺序表：用一组：用一组地址连续地址连续的存储单元的存储单元依次存放依次存放线性表中的数据元素
9、。线性表中的数据元素。2.22.2 线性表的顺序存储和实现线性表的顺序存储和实现所有数据元素的存储位置均取决于第一个数据元素所有数据元素的存储位置均取决于第一个数据元素的存储位置（随机存取）的存储位置（随机存取）LOC(ai)=LOC(a1)+(i-1)d1in基地址基地址18线性表的起始地址线性表的起始地址称作线性表的基地址称作线性表的基地址LOC(a1)地址公式：地址公式：a1a2ai-1aian19顺序顺序存储的存储的C语言描述语言描述typedefstructSqList;/俗称俗称顺序表顺序表#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量线性表存储空间的
10、初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量线性表存储空间的分配增量ElemType*elem;/存储空间基址存储空间基址intlength;/当前长度当前长度intlistsize;/当前分配的存储容量当前分配的存储容量/以以sizeof(ElemType)为单位为单位20基本操作在顺序表中的实现基本操作在顺序表中的实现1.InitList(&L)/结构初始化结构初始化2.LocateElem(L,e)/查找查找3.ListInsert(&L,i,e)/插入元素插入元素4.ListDelete(&L,i)/删除元素删除元素5.ListAgainMalloc
11、(&L)/存储空间再分配存储空间再分配6.ListEmpty(L)/判空判空7.ListLength(L)/求表长求表长8.ListTraverse(L)/遍历遍历21StatusInitList_Sq(SqList&L)/构造一个空的线性表构造一个空的线性表/InitList_SqL.elem=(ElemType*)malloc(LIST_INIT_SIZE sizeof(ElemType);L.length=0;/空表长度为空表长度为0L.listsize=LIST_INIT_SIZE/初始存储容量初始存储容量returnOK;1。InitList(&L)的实现的实现:22图示：顺序表图示
12、：顺序表LocateElem_Sq23754138546217L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见，基本操作是：可见，基本操作是：将顺序表中的元素将顺序表中的元素逐个和给定值逐个和给定值 e e 相比较。相比较。2。LocateElem(L,e)的实现的实现intLocateElem_Sq(SqListL,ElemTypee)/在顺序表中查找第一个值与在顺序表中查找第一个值与e e相等的元素，相等的元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回0 0/LocateElem_Sqi=1;/i i 的初值为
13、第的初值为第1 1元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第1 1元素的存储位置元素的存储位置while(i=L.length&*p+!=e)+i;if(i=L.length)return i;elsereturn0;2324(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 aiean,表的长度增加3。ListInsert(&L,i,e)的实现的实现分析：分析：插入元素时，线性表的逻辑结构发生什么变化？插入元素时，线性表的逻辑结构发生什么变化？25StatusListInsert_Sq(SqL
14、ist&L,inti,ElemTypee)/在顺序表在顺序表L L的第的第 i i 个元素之前插入新的元素个元素之前插入新的元素e,e,/i /i 的合法范围为的合法范围为 1iL.length+11iL.length+1/ListInsert_Sqq=&(L.elemi);/q/q 指示插入位置指示插入位置for(p=&(L.elemL.length);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移插入位置及之后的元素右移*q=e;/插入插入e e+L.length;/表长增表长增1 1returnOK;262118307542568721183075例 ListInsert_
15、Sq(L,5,66)L.length0pppq87564266q=&(L.elemi);/q指示插入位置指示插入位置for(p=&(L.elemL.length);p=q;-p)*(p+1)=*p;p*q=e;/插入插入e27(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 4。ListDelete(&L,i,&e)的实现的实现分析：删除元素时，线性表的逻辑结构发生什么变化？分析：删除元素时，线性表的逻辑结构发生什么变化？09 十一月十一月 202328StatusLis
16、tDelete_Sq(SqList&L,inti,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1returnOK;p=&(L.elemi);/p/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给e eq=L.elem+L.length;/表尾元素的位置表尾元素的位置if(iL.length)returnERROR;/删除位置不合法删除位置不合法292118307542568721183075L.length-10pppq8756p=&(L.elemi);/p为被删除元素的位置为被删除元素的位置q=L.elem+L.length;/表尾元素的位置表尾元素的位置for(+p;pdatap-data表示结点数据域表示结点数据域p-nextp-next表示结点指针域表示结点指针域p37二、单链表操作的实现二、单链表操作的实现GetElem(L,i,e)/取第取第i i个数据元素个数据元素ListInsert(&L,
