《数据结构第2章线性表ppt》由会员分享，可在线阅读，更多相关《数据结构第2章线性表ppt（64页珍藏版）》请在金锄头文库上搜索。
1、,第二章线性表学习导读 线性表（ Linear list ）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；其他的每一个数据元素均有一个唯一的直接前驱和一个唯一的直接后继数据元素。通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。1. 线性表的逻辑结构2. 线性表的顺序存储结构 3. 线性表的链式存储结构4. 一元多项式的表示及相加6学时,2.1 线性表的逻辑结构,线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英
2、文字母表（A，B，C，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；再如，某公司2003年每月产值表（400，420，500，600，650）(单位：万元)是一个长度为12(个月)的线性表，其中的每一个月的数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，图2-1的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项：职工号、姓名、基本工资。,职工编号,姓名,图2-1 职工工资表,矩阵也是一个线性表，但它是
3、一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。 综上所述，一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。,抽象
4、数据类型线性表的定义如下：(见严蔚敏书P19 ADT List) ADT List数据对象: D= ai| aiElemSet,i=0,1,2, ，n-1 n1数据关系: R=| ai-1，aiD, i=1,2, ，n-1Elemset为某一数据对象集；n为线性表的长度。,线性表的基本操作： 1 InitList(&L) 初始化：构造一个空的线性表L。 2. DestroyList(&L) 销毁：销毁一个业已存在的线性表L。 3. ClearList(&L) 清空：将一业已存在的线性表L重置为空表。 4. ListEmpty(L) 判表空：若L为空表，则返回TRUE；否则返回FALSE 。 5
5、 ListLength(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 6 GetElem(L,i,&e) 对给定的线性表L，取第i个数据元素。0iLength(L)-1），用e返回L中第i个数据元素的值。 或 GetElem(L,I) ， 1iLength(L)，正确返回值，否则出错。 LocateElem(L,e) e为线性表中的同型元素，定位 返回L中第一个与e满足相等关系数据元素的位序, 若这种数据元素不存在, 则返回0 。 PriorElem(L,cur_e,&pre_e) 求前驱：若cur_e是L的数据元素, 且不是第一个, 则用pre_e返回它的前驱, 否则操作失
6、败, pre_e无定义。或PriorElem(L，e) 求前驱： e是L表中同质元素，求出e的前驱元素并用e返回其值。若有值，函数返回真，否则返回假。,9. NextElem(L,cur_e,&next_e)求后继 若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败, next_e无定义。 或用NextElem(L，e) 求后继 ： e是L表中同质元素求出e的后继元素并用e返回其值。若有值，函数返回真，否则返回假。 10. ListInsert(&L,i,e) 插入 在L中第i个位置之前插入新的数据元素e,L的长度加1 。 11. ListDelete(&L
7、,i,&e) 删除 删除L的第i个数据元素,并用e返回其值,L的长度减1 。（i的选择要合法） 12. ListTraverse(L,visit() 遍历 对给定的线性表L，依次输出L的每一个数据元素。（不允许重复） 13. Copy(L,C) 复制 将给定的线性表L复制到线性表C中。 14. Merge(A,B,C) 合并 将给定的线性表A和B合并为线性表C。 ADT List,更复杂的运算:一表拆成二表、求两表的共同元素等。 算法2-1 将所有在线性表Lb中但不在La表中的数据元素插入到La中。即A=AB（见125个算法） void union(List ,时间复杂性为：O（La表长*Lb
8、表长）,算法2-2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。 （见125个算法） Void MargeList(List La,List Lb,List /该算法将LA，LB中有重复数据的元素全部加到LC 表中。,时间复杂性为： O（LA表长+LB表长）,在计算机内，线性表有两种基本的存储结构： 顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法。,2.2 线性表的顺序存储结构,在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序
9、存储结构。,2.2.1 线性表的顺序存储结构,在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d个字节，则线性表中第i个下表元素ai在计算机存储空间中的存储地址为： Loc(ai)= Loc(a0)+i*d,在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点： （1）数组中的元素间的地址是连续的； （2）数组中所有
10、元素的数据类型是相同的。而这与线性表的顺序存储的空间结构是类似的。,若定义数组An= a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。其结构如图2-2所示。 1.一维数组 逻辑地址 数据元素 存储地址 名称0 a0 Loc(A0) A01 a1 Loc(A0) +d A1i ai Loc(A0)+i*d Ain -1 a n-1 Loc(An-1) An-1空闲空间MAXNUM-1图2-2 一维数组存储示意图,由于线性表的长度可变，且所需最大存储
11、空间随问题不同而不同，则在C语言中可用动态分配的一维数组，如下描述： /-线性表的动态分配顺序存储结构- #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 /*这里的LIST_INIT_SIZE与书中的maxsize等价 */ #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位） SeqList;,如下描述： /-线性表的动态分配顺序存储
12、结构- #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef structElemType dataLIST_INIT_SIZE; /存储空间基址int length; /当前长度 SeqList; /但本书里这种定义方式不常用,若定义数组Anm，表示此数组有n行m列，如下图2-3所示。,0 1 2 j m-10 a00 a01 a02 a0j a0 m-11 a10 a11 a12 a1j a1 m-12 a20 a21 a22 a2j a2 m-1i ai 0 ai1
13、 ai2 ai j 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 二维数组存储示意图,2.2.2 线性表在顺序存储结构下的运算,可用C语言描述顺序存储结构下的线性表（顺序表）如下： #define TRUE 1 #define FALSE 0 #define MAXNUM Elemtype ListMAXNUM ; /*定义顺序表List*/ int num= -1; /*定义当前数据元素的下标，并初始化*/ 我们还可将数组和表长封装在一个结构体中： struct Linear_list Elemtype ListMAXNUM; /*定义数组域*/int length; /*定义表长域*/ ,1线性表的初始化,Int Initlist(Seqlist *L) L-elem （ElemType )malloc(maxszie*sizeof(ElemType);if(! L-elem ) exit(fail);L-length = 0;L - Listsize = maxsize;return OK; ,
