数据结构第2章_线性表

《数据结构第2章_线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表●本章要点●线性表的逻辑结构●线性表的顺序存储●线性表的链式存储●顺序表和链表的比较●本章难点●顺序存储结构、链式存储结构及基本运算的实现●2.1线性表的逻辑结构●2.1.1线性表的类型定义线性表是一种线性结构，线性结构的数据元素之间是一种线性关系，线性关系的特点如下：●在一个线性表中的数据元素的类型是相同的，数据元素一个接一个地排列。●存在一个惟一的被称作“第一个”的数据元素。●存在惟一的一个被称作“最后一个”的数据元素。●除第一个之外，每个数据元素均只有一个前驱；除最后一个之外，每个数据元素均只要一个后继。一个线性表是n(n≥0)个同类型数据元素a1,

2、a2,a3,…，an的有限序列。记作：（a1,a2,a3,…,an）从定义可以看出，线性表强调两个特性：（1）任何数据元素ai(i=1,…，n)必须是同类型的数据。（2）数据元素的有序性，数据元素在表中的位置决定了它的序号。表中数据元素的个数n称为线性表的长度。长度为0的线性表称为空表。●2.1.1线性表的类型定义数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。对于线性表，常用的运算有如下几种：(1))置空表（结构初始化）init_seqlist(L)；操作结果：构造一个空的线性表L。⑵求线性表的长度。list_length(L);初始条

3、件：线性表L已存在。操作结果：返回L中元素个数。●2.1.2线性表的基本操作⑶定位:访问线性表的第i个元素。get_node(L,i);初始条件：线性表L已存在。操作结果：返回L中第i个元素的值或地址。⑷查找:在线性表中查找满足某种条件的数据元素。location_list(L,x);初始条件：线性表L已存在。操作结果：返回L中值为给定值x的数据元素。●2.1.2线性表的基本操作⑸插入:在线性表的第i个元素之前，插入一个同类型的元素。insert_list(L,i,x);初始条件：线性表L已存在。操作结果：在L的第i个位置插入一个值为x的新元素。⑹删除:删除线性表中第

4、i个元素。delete_list(L,i);初始条件：线性表L已存在。操作结果：在L中删除序号为i的数据元素。⑺清除表:将已有线性表变为空表，即删除表中所有元素。●2.1.2线性表的基本操作线性表的顺序存储表示称为顺序表。2.2.1顺序表用一组地址连续的存储单元依次存储线性表的数据元素，这种存储方式称为线性表的顺序存储结构。即逻辑相邻,物理相邻。线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有数据元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间上是按逻辑顺序依次存放的。●2.2线性表的顺序存储a1a2…ai-1aiai+1…an…01…i-2

5、i-1i…n-1MAXSIZE-1data数组下标length-1线性表的顺序存储设a1的存储地址为Loc(a1)，每个数据元素占d个存储单元，则第i个数据元素的地址为：Loc(ai)＝Loc(a1)+(i-1)*d１≤i≤n已知顺序表的首地址和每个元素所占地址单元的个数，就可求出第i个数据元素的地址。(随机访问速度快,不受规模影响)●2.2.1顺序表#defineMAXSIZE线性表可能达到的最大长度typedefstruct{Elemtypedata[MAXSIZE];intlength;}SeqList;SeqList*pslist;/*定义一个顺序表*/存储实

6、现●2.2.1顺序表pslist是一个指针变量，存放的是顺序表的地址。表长pslist->length；表空标志pslist->length=0；表满标志pslist->length=MAXSIZE；数据元素pslist->data[0]～pslist->data[pslist->length-1]a1a2…ai-1aiai+1…an…01…i-2i-1i…n-1MAXSIZE-1a1a2…ai-1aiai+1…an…pslist->datapslist->length-1●2.2.1顺序表aipslist->data[i-1]ai?●2.2.2顺序表的基本运算⒈顺序

7、表的初始化初始化即构造一个空表。算法分析将pslist设为指针参数，动态分配存储空间，将表中length指针设置为0，表示表中没有元素。初始化算法实现：SeqList*init_list(){SeqList*list;list=(SeqList*)malloc(sizeof(SeqList));list->length=0;return(list);}main(){SeqList*pslist;pslist=init_list();}●2.2.2顺序表的基本运算⒉插入算法顺序表的插入是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据