第2章线性表
第
2
章
线性表
线性表是最简单、最基本,也是最常用的数据结构。
幼儿园小朋友人数众多,有的幼儿园为便于管理,会给每个班级排一个固定顺序的队伍,如班级里有30个小朋友,会按照顺序给小朋友排学号1,2,330,不管是平时放学排队还是外出参加活动,小朋友都按照学号排队,让每个小朋友记住自己前后的小朋友,若发现前后小朋友不在马上报告老师,而老师只要记住第1个小朋友就可以了。班级中,只有1号前面没有小朋友,只有30号后面没有小朋友,其他每个学号都是前面只有一个小朋友,后面只有一个小朋友,这就是一个典型的线性表。
本章我们就要来学习线性表。
2.1线性表的逻辑结构
2.1.1线性表的定义
线性表L是nn0个具有相同属性的数据元素a1,a2,a3,,an组成的有限序列。其中，序列中元素的个数n称为线性表的长度。
当n=0时称为空表,即不含有任何元素。
常常将非空的线性表Ln0记为：L=a1,a2,，ai-1,ai,ai 1,，an。
其中，ai-1为ai的直接前驱,ai＋1为ai的直接后继。a1为表头元素,an为表尾元素。线性表有以下特点。
1 在非空的线性表中,存在唯一的一个被称为第一个的数据元素,又称为表头元素；存在唯一的一个被称为最后一个的元素,又称为表尾元素。
2 线性表中数据的位置先后是有序的。除表头元素外,线性表中的每一个元素有且仅有一个前驱；除表尾元素外,线性表中的每一个元素有且仅有一个后继。表头元素只有一个后继而没有前驱,表尾元素只有一个前驱而没有后继。
3 线性表中的数据的类型是相同的。表的长度n的取值是有限数,最小为0。
在日常生活中,线性表的例子很多。例如，26个英文字母组成的字母表A,B,C,,Y,Z就是一个典型的线性表,该表长度是26,每个字母是表中的一个元素。表21所示的学生信息表也构成了一个线性表。
表21学生信息表
学号姓名班级年龄宿舍
160210001崔雨计科160118星苑305
160210002丁洁计科160119星苑305
160210003樊辰计科160118松苑207
160210004冯波计科160119松苑207
160210005郭力计科160120松苑207
160210006胡志计科160120松苑207
该线性表表长为6,表中每个学生的信息为一个数据元素,包括学号、姓名、班级、年龄和宿舍等数据项信息。
2.1.2线性表的基本运算
数据结构的基本运算是定义在逻辑结构层次上的,而这些运算的具体实现是需要建立在存储结构上的,因此下面定义的线性表的基本运算作为逻辑结构的一部分,其具体实现却要在线性表的存储结构确定之后才能够完成。
线性表的基本操作有以下几项。
1 线性表L的初始化，其语句如下。
InitListL
构造一个空的线性表L，即表的初始化。
2 创建线性表L，其语句如下。
CreatListL
3 求线性表L的长度，其语句如下。
GetLengthL
求表中结点的个数,即求表的长度。
4 按序号取线性表L中的元素，其语句如下。
GetNodeL,i
取线性表L中的第i个元素,这里1iLengthL。
5 在线性表L中查找元素e，其语句如下。
LocateListL,e
在L中查找值为e 的结点,并返回该结点在L中的位置。若L中有多个结点的值和e 相同,则返回首次找到的结点位置；若L中没有结点的值为e,则返回一个特殊值如-1,表示查找失败。
6 在线性表L中插入新元素，其语句如下。
InsertListL,i,e
在线性表L的第i个位置上插入一个值为x 的新结点,使得原编号为i,i 1,,n的结点变为编号为i 1,i 2,,n 1的结点。这里1in 1,而n是原表L的长度。插入后,表L的长度加1。
7 在线性表L中删除元素，其语句如下。
DeleteListL,i
删除线性表L的第i个结点,使得原编号为i 1,i 2,,n的结点变成编号为i,i 1,,n-1的结点。这里1in n是原表L的长度,删除后表L的长度减1,为n-1。
8 将线性表中元素输出，其语句如下。
PrintListL
将线性表L中的元素打印输出,若对线性表进行了一些操作,如插入、删除等,需要将其打印输出查看操作结果。
2.2线性表的顺序存储及运算实现
线性表有两种基本的存储结构：顺序存储结构和链式存储结构。
2.2.1线性表的顺序存储结构
线性表的顺序存储是最简单、最直接的一种存储方式,即把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。这样的存储方式使线性表逻辑上相邻的元素存储在物理地址相邻的存储单元里,即以计算机内物理位置相邻来反映数据元素之间逻辑上的相邻关系,采用这种存储方式的线性表又称为顺序表。
顺序表有以下特征。
1 线性表的所有元素所占的空间是连续的。
2 线性表中各个数据元素在存储空间中是按照逻辑顺序依次存放的。
由于线性表中的所有数据元素都是同一数据类型,所以每个元素在存储器中占用的空间字节数相同。只要知道了第1个数据元素a1的存储地址和它所占有的存储单元个数,即可求得第i个数据元素ai的地址。假定第一个元素a1的地址为LOCa1,每个数据元素占k个字节,则第i个数据元素ai的地址是：
LOCai=LOCa1 i－1k1in
例如：第2个数据元素a3的地址是LOCa2=LOCa1 k
第3个数据元素a3的地址是LOCa3=LOCa1 2k
第i个数据元素ai的地址是LOCai=LOCa1 i－1k
顺序表的顺序存储结构如图21所示。
图21顺序表的顺序存储示意图
由于线性表中的数据元素都是按照逻辑关系进行存储的，所以只要确定了顺序表的起始位置，线性表中的任一数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机存取的存储结构。
顺序表在具体实现时,一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxSize个元素,在C语言中可用数组data\[MaxSize\]来存储数据元素,为保存线性表的长度需定义一个整型变量length。线性表的第l,2,,n个元素分别存放在此数组下标为0,1,,length-1数组元素中,如图21所示。
在C语言中,可用下述类型定义来描述线性表。
#defineMaxSize100*顺序表的容量*
typedefintDataType;*在应用中,将实际数据类型定义成DataType *
typedefstruct{
DataTypedata\[MaxSize\];*定义存储表元素的数组*
intlength;*顺序表的实际长度*
}SeqList; *顺序表数据类型说明*
SeqList *L;*定义一个顺序表类型的指针变量L*
在使用一维数组存放线性表时,通常定义的数组的空间要比实际表稍长大一些,以便对线性表进行各种运算,特别是对线性表的插入运算。一般情况下,应该尽可能考虑到使用的线性表可能达到的最大长度,如果定义的存储空间过小,则在线性表动态增长时可能会出现存储空间不够而无法插入新的元素的情况；如果存储空间过大,而实际又没有用到那么大的存储空间,则会造成存储空间的浪费。在实际应用中,可以根据线性表动态变化过程中的一般规模来决定开辟存储空间量,设置足够的数组长度,以备扩展。
2.2.2顺序表上基本运算的实现
1. 顺序表L的初始化
顺序表的初始化即构造一个空表,顺序表是否为空取决于其数据元素个数是否为0,因此,只要将表L的长度设置为0即可构造出一个空表。
算法21顺序表的初始化。
void InitListSeqList *L*顺序表的初始化即将表的长度置为0*
{
L-＞length=0;
}
该算法的时间复杂度为O1。
2. 创建一个顺序表L
算法22创建一个元素为整型数的顺序表,元素不包括0,遇到0时表示输入结束。顺序表长度由用户输入的数据来决定。
void CreatListSeqList *L
{
int k=0;*计数*
DataType x;
scanf"%d",&x;
whilex!=0*依次从键盘输入顺序表元素,遇到0结束。*
{
L-data\[k\]=x;
k;
scanf"%d",&x;
}
L-length=k;
}
该算法的时间复杂度为On,其中n为该顺序表中元素个数的规模。
思考：
若顺序表长度为固定值,如何创建顺序表？
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
