《数据结构之链式顺序线性表》由会员分享，可在线阅读，更多相关《数据结构之链式顺序线性表（120页珍藏版）》请在金锄头文库上搜索。
1、退 出主目录 下一页第二章 线性表2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 顺序表与链表的比较主目录下一页上一页退 出本章要点n线性表(Linear List) ：由n(n)个数据元素 (结点)a1，a2， an组成的有限序列。其中数 据元素的个数n定义为表的长度。当n=0时称为 空表，常常将非空的线性表(n0)。记作： (a1，a2，an)n这里的数据元素ai(1i n)只是一个抽象 的符号，其具体含义在不同的情况下可以不同 。2.1 线性表的类型定义主目录下一页上一页退 出本章要点例1、26个英文字母组成的字母表（A，B，C,Z）例2
2、、某校从1978年到1983年各种型号的计 算机拥有量的变化情况。（6，17，28，50，92，188）2.1 线性表的类型定义主目录下一页上一页退 出本章要点例3、学生健康情况登记表如下：2.1 线性表的类型定义姓 名学 号性 别 年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . .主目录下一页上一页退 出本章要点例4、一副扑克的点数 （2，3，4，J，Q，K，A）2.1 线性表的类型定义从以上例子可看出线性表的逻辑特征是：在非空的线性表中，有且仅有一个开始结点a1，它没 有直接前趋
3、，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有 一个直接前趋an-1；其余的内部结点ai(2i n-1)都有且仅有一个直 接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体 实现则是在存储结构上进行的。主目录下一页上一页退 出本章要点n线性表的特点n同一性：线性表中所有元素的性质相同n有序性：除第一个和最后一个数据元素 之外，其它数据元素有且仅有一个前驱和一 个后继。第一个数据元素无前驱，最后一个 数据元素无后继n有穷性：数据元素在表中的位置只取决 于它自身的序号，序号不可能无穷，故元素 个数不可能无穷2
4、.1 线性表的类型定义主目录下一页上一页退 出本章要点抽象数据类型（ADT）的表示 ADT 数据对象：结构关系：基本操作： ADT /（参数表）操作前提：操作结果：2.1 线性表的类型定义主目录下一页上一页退 出本章要点线性表的抽象数据类型定义ADT LinearList数据元素:D=ai|aiD0,i=1,2,n,n0,D0为某一数据对象结构关系:S=| ai, ai+1 D0,I=1,2,n-1基本操作:(1)InitList(L) /初始化操作前提:L为未初始化线性表操作结果:将L初始化为空表(2)DestroyList(L) /删除表 操作前提:线性表L已存在操作结果:将L销毁(3)C
5、learList(L) /内容清空操作前提:线性表L已存在操作结果:将表L置为空表主目录下一页上一页退 出本章要点(4)EmptyList(L) /判空操作前提:线性表L已存在操作结果:如果L为空表则返回真,否则返回假(5)ListLength(L) /求长度操作前提:线性表L已存在操作结果:如果L为空表则返回0,否则返回表中的元素个数(6)Locate(L,e) /检索操作前提:表L已存在,e为合法元素值操作结果:如果L中存在元素e,则将“当前指针”指向e所在位置并返回真,否则返回假(7)GetData(L,i) /取元素操作前提:表L已存在,且i值合法,即1iListLength(L)操作
6、结果:返回线性表L中第i个元素的值线性表的抽象数据类型定义主目录下一页上一页退 出本章要点(8)InsList(L,i,e) /插入(前插)操作前提:表L已存在,e为合法元素值且1iListLength(L)+1操作结果:将表L中第i个位置插入新的数据元素e,L的长度加1(9)DelList(L,i, /*V是数组的名字，假设数组中 的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*mVVViVm-12.2.1 顺序表的存储结构主目录下一页上一页退 出本章要点若定义数组Anm，表示此数组有n行m列，如下图2-3所示。0 1 2 j m-1 0 a00 a
7、01 a02 a0j a0 m-11a10 a11 a12 a1j a1 m-12a20 a21 a22 a2j a2 m-1i ai0 ai1 ai2 aij ai m-1n-1 an-1 ,0 an-1,1 an-1,2 an-1,j an-1,m-1图2-3 二维数组二维数组主目录下一页上一页退 出本章要点在C语言中，二维数组的保存是按照行方式存储的，先将第一行元素 排好，接着排第二行元素，直至所有行的元素排完。如图2-4所示。图2-4 二维数组存 储示意图主目录下一页上一页退 出本章要点n 由于C语言中的一维数组也是采用顺序 存储表示，故可以用数组类型来描述顺序 表。又因为除了用数组来
8、存储线性表的元 素之外，顺序表还应该用一个变量来表示 线性表的长度属性，所以我们用结构类型 来定义顺序表类型。2.2.1 顺序表的存储结构主目录下一页上一页退 出本章要点# define MAXSIZE 100/* 线性表可能达到的最大长度为100 */typedef int elemtype;typedef structelemtype elemMAXSIZE;/*线性表占用的数组空间*/int len; /* 线性表实际长度，这里记录线性表中最 后一个元素在数组elem 中的位置（下标值 ），空表置1 */ Sqlist;2.2.1 顺序表的存储结构主目录下一页上一页退 出本章要点# de
9、fine MAXSIZE 100 typedef struct elemtype elemMAXSIZE;int len; Sqlist;2.2.1 顺序表的存储结构主目录下一页上一页退 出本章要点在顺序表存储结构中，很容易实现线 性表的一些操作，如线性表的构造、第i 个元素的访问。注意：C语言中的数组下标从“0” 开始，因此，若L是Sqlist类型的顺序表 ，则表中第i个元素是L.elemi-1。2.2.2 顺序表上实现的基本操作主目录下一页上一页退 出本章要点n顺序表的初始化顺序表的初始化即构造一个空表， 这对表是一个加工型的运算，因此，将L 设为指针参数，首先动态分配存储空间 ，然后，将
10、表中 len 指针置为0，表示 表中没有数据元素。算法如下：2.2.2 顺序表上实现的基本操作主目录下一页上一页退 出本章要点Sqlist *init_Sqlist( ) Sqlist *L; L=(Sqlist * )malloc(sizeof(Sqlist);L-len=0; return L;n设调用函数为主函数，主函数对初始化函数的 调用如下：main()Sqlist *L;L=Init_Seqlist(); 顺序表的初始化主目录下一页上一页退 出本章要点n按序号查找n注意：元素标号与数组的下标之间 的关系元素an元素ai元素a2元素a1Elem0Elem1Elemi- 1Elemn-
11、 12.2.2 顺序表上实现的基本操作主目录下一页上一页退 出本章要点nLocate（L，x）：查找顺序表中是否含 有与x值相同的元素ai-1a2a1alenai+1aix按内容查找主目录下一页上一页退 出本章要点ai-1a2a1alenai+1aix按内容查找主目录下一页上一页退 出本章要点ai-1a2a1alenai+1aix如果x和ai-1相同， 则找到并停止查找； 否则按照前面的步骤 继续下去按内容查找主目录下一页上一页退 出本章要点ai-1a2a1alenai+1aix如果此时仍然 没有找到，返 回错误并停止n有关算法及程序在“查找”一章中介绍按内容查找主目录下一页上一页退 出本章要
12、点nint Location_Sqlist(Sqlist *L, elemtype x) int i=0;while(ilen if (i=L-len) return -1;else return i; /*返回的是存储位置*/按内容查找主目录下一页上一页退 出本章要点以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第 i(1in+1)个位置上，插入一个新结点x， 使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，x，ai，an)2.2.2 顺序表上实现的基本操作主目录下一页上一页退 出本章要点a2a1anai+1ai01i-1
13、iai-1a2a1alenai+1aixai-1a2 a1 ai ai+1alength alen ai+1 ai xn-1插入运算主目录下一页上一页退 出本章要点n顺序表上完成这一运算通过以下步骤进 行：(1) 将aian 顺序向下移动，为新 元素让出位置；(2) 将 x 置入空出的第i个位置；(3) 修改表长。插入运算主目录下一页上一页退 出本章要点int InsList(Sqlist *L,int i,int x) /*在线性表V中第i 个元素之前插入x，i 的合法值为 1 i L-len +1*/int k;if(iL-len+1)printf(“Locate Error!”);ret
14、urn 0; /*位置i值不合法 */if(L-len=MAXSIZE)printf(“Filled!“);return(ERROR);for(k=L-len-1;k=i-1;k - -)L-elemk+1=L-elemk; /*插入位置后的元素依次右移*/L-elemi-1=x; /* 插入x */L-len+; /* 表长加1*/return 1;注意数组元 素从0开始插入运算主目录下一页上一页退 出本章要点本算法中注意以下问题： n (1) 顺序表中数据区域有MAXSIZE个存 储单元，所以在向顺序表中做插入时先 检查表空间是否满了，在表满的情况下 不能再做插入，否则产生溢出错误。n (
15、2) 要检验插入位置的有效性，这里 i的有效范围是：1=n+1时，由于循环变量的终值大于初值 ，结点后移语句将不进行；这是最好情况，其时间 复杂度O（1）； n 当i=1时，结点后移语句将循环执行n次，需 移动表中所有结点，这是最坏情况，其时间复杂度 为O（n）。插入运算主目录下一页上一页退 出本章要点由于插入可能在表中任何位置上进行，因此需 分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个 结点，令Eis(n)表示移动结点的期望值（即移动的 平均次数），则在第i个位置上插入一个结点的移动 次数为n-i+1。故Eis(n)=pi(n-i+1)不失一般性，假设在表中任何位置 (1in+1)上插入结点的机会是均等的，则p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)= (n-i+1)/(n+1)=n/2 插入运算主目录下一页上一页退 出本章要点也就是说，在顺序表上做插入运算，平 均要移动表上一半结点。当表长 n较大时， 算法的效率相当低。虽然Eis(n)中n的的系数 较小，但就数量级而言，它仍然是线性阶的 。因此算法的平均时间复杂度为O(n)。 插入运算主目录下一页上一页退 出本章
