第二章线性表.ppt

第二章 线性表 2.1 线性表的定义与运算 2.1.1 线性表的定义 2.1.2 线性表的基本操作 2.2 线性表的顺序存储 2.2.1 顺序表 2.2.2 顺序表上基本运算的实现 2.3 线性表的链式存储 2.3.1 线性链表 2.3.2 线性链表上基本运算的实现 2.3.3 循环链表 2.3.4 双向链表 2.1 线性表的定义与运算 2.1.1 线性表的定义 1.线性表是一种线性的数据结构，其特点是数据元素之间存在“一对一”的关系。即线性表是由同一类型的数据元素构成的线性结构。 2.线性表是n(n≥０)个具有相同属性的数据元素的有限序列，线性表中数据元素的个数n称为线性表的长度。n=0 时，该线性表为空表。n0时该线性表可记为：（A0,A1,┅Ai,┅An-1） 其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）和终点(An-1)外，每个数据元素都有且只有一个直接前驱和一个直接后继。Ai-1是Ai的直接前驱，Ai+1是Ai的直接后继。 3.线性表的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素；（2）存在唯一的一个被称为“最后一个”的数据元素；（3）除第一个以外，集合中的每一个数据元素均有且只有一个前驱；（4）除最后一个以外，集合中每一个数据元素均有且只有一个后继。 2.1.2 线性表的基本操作 1.创建线性表 GreateList(L) 2.求线性表的长度 int LengthList(L) 3.按值查找 SearchList(L,x) 4.插入操作InsertList(L,i,x) 5.删除操作 DeleteList(L,i) 6.显示操作 ShowList(L) 2.2 线性表的顺序存储 2.2.1 顺序表 线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置，则第i+1个数据元素的存储位置为： loc(Ai)=Loc(A0)+i*L. 因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用Ｃ语言的一维数组实现，数组的类型随数据元素的属性而定。 2.2.2 顺序表上基本运算的实现 线性表结构简单、易于实现，但插入或删除一个元素时需对其后继的全部元素逐个进行移动（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。 所以，这种结构仅适用于数据元素个数不经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。 (一)线性表插入操作(1) 1、在数组中下标为i的元 素前插入一个新元素。 例2.1 某Ｃ++语言程序中，整型数组Ｖ的９９个元数Ｖ［０］～Ｖ［９８］组成一个线性表。为了在Ｖ［i］位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右： 举例（续） 分析： ①初始条件V,i,b ②执行条件：0≤i≤98 ③执行结果：1 成功 0 不成功 ④N-S流程图如右: 图 举例（续） 用函数实现算法如下： int ins1( int V[ ], int i, int b) { int j； if((i0 ||i98) { printf(“The value of i is out of range\n”)； return 0; /*插入失败*/ } for (j=98；ji；j--) v[j]=v[j-1];/*后移*/ v[i]=b； /*插入*/ return 1； /*插入成功 */ ｝ 线性表的插入操作（2） 2、在有序表中插入一个新元素 例2.2 设有一个有序线性表，用数组结构实现，最大元素个数为n。设当前元素个数是m。要求在该有序表中插入一个值为x的元素。当x=63时，插入前后的有序表的示意图如右： 举例（续） 分析： ①初始条件：a,n,m,x ②插入条件：mn ③执行结果：1 成功 0 不成功 ④N-S