数据结构(第二版)课件 包振宇 第二章 线性表.ppt

《数据结构(第二版)课件 包振宇 第二章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4典型例题第二章线性表线性表的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素；（2）存在唯一的一个被称为“最后一个”的数据元素；（3）除第一个以外，集合中的每一个数据元素均有且只有一个前驱；（4）除最后一个以外，集合中每一个数据元素均有且只有一个后继。2.1线性表的逻辑结构线性表是最简单的一种数据结构。简单地说，一个线性表是n(n≥０)个具有相同属性的数据元素的有限序列，其中各个数据元素有着依次相邻（串接）的逻辑关系。线性表中数据元素的个数n称为线性表的长度。n=0时，该线性表为空

2、表。n>0时该线性表可记为：（A0,A1,┅Ai,┅An-1）其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）和终点(An-1)外，每个数据元素都有且只有一个直接前趋和一个直接后继。Ai+1是Ai的直接前驱，Ai+1是Ai的直接后继。线性表中的数据元素可以是各式各样的，但同一线性表中的元素必定有相同的特性，即属同数据对象，相邻数据元素辶间存在着有序关系。线性表是一个相当灵活的数据结构，其表长可根据不同的操作增长或缩短。对线性表进行的基本操作有：存取、插入、删除、合并、分解、查找、排序、求线性表的长度等。2.2线性表的顺序

3、存储结构2.2.1顺序分配线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置，则第i+1个数据元素的存储位置为：loc(Ai)=Loc(A0)+i*L.因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用Ｃ语言的一维数组实现，数组的类型随数据元素的属性而定。2.2.2线性表的操作线性表结构简单、易于实现，但插入或删除一个元素时需对其后继的全部元素逐个进行移动

4、（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。所以，这种结构仅适用于数据元素个数不经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。(一)线性表插入操作(1)1、在数组中下标为i的元素前插入一个新元素。例2.1某Ｃ语言程序中，整型数组Ｖ的９９个元数Ｖ［０］～Ｖ［９８］组成一个线性表。为了在Ｖ［i］位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右：举例（续）分析：①初

5、始条件V,i,b②执行条件：0≤i≤98③执行结果：1成功0不成功④N-S流程图如右：图举例（续）用函数实现算法如下：intins1(intV[],inti,intb){intj；if((i<0

6、

7、i>98){printf(“Thevalueofiisoutofrange”)；return0;/*插入失败*/}for(j=99；j>i；j--)v[j]=v[j-1];/*后移*/v[i]=b；/*插入*/return1；/*插入成功*/｝线性表的插入操作（2）2、在有序表中插入一个新元素例2.2设有一个有序线性表，用数组结构实现，最大元素个数为n。设当前元素个数是m。要求在该有序表中插入

8、一个值为x的元素。当x=63时，插入前后的有序表的示意图如右：举例（续）分析：①初始条件：a,n,m,x②插入条件：m=n){printf(“插入失败”);return0;}/*插入失败*/for(i=m-1;i>=0&&a[i]>x;i--)a[i+1]=a[i];/*后移*/a[i+1]=x;m++;/*插入*/return1;/*插入成功*/}（二）线性表的删除(1)1﹑删除下标为i的数据元素例2.3为在V[0]到V[

9、99]中删除一个元素V[i],引用del1函数。删除前后的线性表的示意图如右举例（续）分析：①初始条件：数组V，删除下标i②删除条件：0≤i≤99③执行结果：1成功,0不成功④N-S流程图如右:举例（续）Del1函数定义如下：intdel1(intv[],inti){intj;if(i<0

10、

11、i>99){printf(“thevalueofIisoutofrange”);return0;/*删除失败*/}