《[理学]数据结构课件2》由会员分享，可在线阅读，更多相关《[理学]数据结构课件2（100页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,1教学目的：通过线性表的学习，熟悉本书对每种数据结构的描述方法，掌握线性表的定义、特点、典型算法及实际中的实用。 2教学要求：了解线性表的逻辑结构特性。熟练掌握线性表的两种存储结构的描述方法。熟练掌握线性表在顺序存储结构上基本操作的实现；查找、插入和删除等。熟练掌握在各种链式结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。能够从时间和空间复杂度的角度比较线性表两种存储结构的特点及应用场合。,3教学重点：线性表顺序存储结构的特点及基本操作。线性表链式存储结构的特点及基本操作。 4教学难点：链表的概念。链式存储结构上算法的实现。,线性表 是n个类型相同数据元素的有
2、限序列。记作： （a1, a2, ，ai-1，ai，ai+1， ，an） （1）数据元素ai(1in)是一个抽象符号，具体含义在不同情况下可以不同。（2）相邻数据元素之间存在着序偶关系。表中ai-1领先于ai ai-1是ai的直接前驱ai是ai-1的直接后继（3）元素的个数n被定义为线性表的长度，n=0为空表。,2.1 线性表的逻辑结构,2.1.1 线性表的定义,例1、26个英文字母组成的字母表（A，B，C、Z） 例2、某校从1978年到1983年各种型号计算机拥有量的变化情况。（6，17，28，50，92，188） 例3、学生信息检索系统 例4、一副扑克的点数（2，3，4，J，Q，K，A）,
3、线性表的逻辑特征： 在数据元素的非空有限集中 存在唯一的一个称为“第一个”的数据元素； 存在唯一的一个称为“最后一个”数据元素; 3. 除第一个外，每个数据元素有且只有一个直接前驱元素； 4. 除最后一个外，每个数据元素有且只有一个直接后继元素。两种存储方法：顺序存储和链式存储；主要操作：插入、删除和检索。,线性表的特点： 同一性：每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成。有序性：相邻数据元素之间存在着序偶关系。 线性表是一种最常见的数据结构，矩阵、数组、字符串、堆栈、 队列等都符合线性条件。,线性表形式定义为：,说明：ai通常将它的数据类型抽象表述为datatype
4、， datatype根据具体问题而定.,含有n个元素的线性表是一个数据结构Linear_list=(D, R)其中：D=ai |aiD, i=1,2,n, n0R=N , N=| ai-1 , aiD, i=2,3,nD为某个数据对象,数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。,2.1.2 线性表的基本操作, 线性表初始化：InitList(L)初始条件：线性表L不存在。操作结果：构造一个空的线性表。 求线性表的长度：LengthList(L)初始条件：线性表L存在。操作结果：返回线性表中所含元素的个数。 取元素函数：GetList(L,i)初始条件：线性表
5、L存在，1iLengthList(L)。操作结果：返回线性表L中第个元素的值或地址。, 按值查找：LocatList(L,x) 初始条件：线性表L存在，是给定的一个数据元素。 操作结果：在L中查找值为的数据元素，其结果返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功; 否则，返回一特殊值表示查找失败。 插入操作：InsertList(L,i,x)初始条件：线性表L存在，插入位置 i 正确 (1in+1)。操作结果：在L的第i个位置上插入一个值为x的新元素，插入后线性表长=原线性表长+1。 删除操作：DeleteList(L,i)初始条件：线性表L存在，1in。操作结果：删除序号为i
6、的数据元素，新表长原表长。,2.2 线性表的顺序存储及运算实现,2.2.1 线性表的顺序存储结构,是指用一组地址连续的存储单元依次存储线性表中的各个元素。采用顺序存储结构的线性表通常称为顺序表。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素的地址loc(ai)： Loc(ai)=Loc(a1)+(i-1)*k 1in 其中loc(a1)称为基地址。,图2.2 顺序表存储示意图,线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中， 即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。,顺序存储结构可以借助于高级程序设计语言中的
7、一维数组来表示。线性表的顺序存储结构可用C语言定义如下：,可用C语言描述顺序存储结构下的线性表（顺序表）如下：typedef struct Linear_list datatype elemMAXSIZE; /*定义数组域*/int last; /*线性表中最后一个元素在数组中的位置*/ SeqList;,定义：SeqList L ;如图2.2（a)所示,表长L.last+1线性表中的数据元素a1至an分别存放在 L.elem0 L.elemL.last中。,或定义：SeqList *L ; 如图2.2（b）所示。表长表示为（*L）.last+1或 L-last+1， 数据元素的存储空间为：L
8、-elem0 L-elemL-last,2.2.2 线性表顺序存储结构上的基本运算,1 顺序表的初始化SeqList *InitList( ) SeqList *L;L=( SeqList *)malloc(sizeof(SeqList);或L=new(SeqList)L-last=-1; return L; 设调用函数为主函数，主函数对初始化函数的调用如下：main()SeqList *L;L= InitList(); ,2 按值查找 算法如下：int LocatList(SeqList *L, datatype x) int i=0;while(ilast /*返回的是存储位置*/ 本算法
9、的主要运算是比较。平均比较次数为（n+1）/2，时间复杂度为O(n)。,3 插入运算线性表的插入是指在表的第i个位置上插入一个值为x的新元素，如图2.3所示。i的取值范围为1in+1 。 步骤： 将aian 顺序向下移动，为新元素让出位置； 将x 置入空出的第i个位置； 修改last指针（相当于修改表长），使之仍指向最后一个元素。,算法设计时请注意： 在表满的情况下不能再做插入，否则产生溢出错误。 检验插入位置的有效性：1in+1，其中n为原表长。 注意数据的移动方向。,算法实现：,int InsertList(SeqList *L，int i，datatype x) int j;if (L-
10、last=MAXSIZE-1) printf（“表满”）; return（-1）; /*表空间已满，不能插入*/if (iL-last+2) /*检查插入位置的正确性*/ printf（位置错）; return（0）; for (j=L-last; j=i-1; j-)L-elemj+1=L-elemj; /*结点移动 */L-elemi-1=x; /*新元素插入*/L-last+; /*last仍指向最后元素*/return (1); /*插入成功，返回*/ ,4. 删除操作指将表中第i个元素从线性表中去掉，如图2.4所示。i 的取值范围为：1in 。 步骤： 将ai+1an 顺序向上移动。
11、 修改last指针使之仍指向最后一个元素。,注意： 当表空时不能做删除 ，否则产生下溢错误。 要检查删除位置的有效性1in。 删除ai 之后，该数据已不存在，如果需要，先取出ai ，再做删除。 注意数据的移动方向。,算法如下：int DeleteList(SeqList *L; int i) int j;if (iL-last+1) /*检查空表及删除位置的合法性*/ printf (不存在第i个元素); return(0); for (j=i; jlast; j+)L-elemj-1=L-elemj; /*向上移动*/L-last-; return(1); /*删除成功*/,性能分析： 在顺
12、序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率Pi=1/(n+1), i=1, 2, ，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数， 则,时间复杂度为：O（n）,又设：pi 为删除第i个元素的概率并假设在任何位置上删除的概率相等即pi=1/n, i=1, 2, ，n。 删除一个元素所需移动元素的平均次数Edel为,时间复杂度为：O（n）,2.2.3 顺序表应用举例例 2.1 将顺序表(a1，a2，. ，an) 重新排列为以a1 为界的两部分：a1前面的值均比a1小，a1后面的值均比a1大（这里假
13、设数据元素的类型具有可比性，不妨设为整型），操作前后如图2.5所示。这一操作称为划分，a1 也称为基准。,基本思路：从第二个元素开始到最后一个元素，逐一向后扫描： 当前数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。 当前结点若比a1小，说明它应该在a1的前面，此时将它前面的元素都依次向后移动一个位置，然后将它置入a1前。,存储结构即为第2节中的SeqList；其中datatype定义为int。算法如下void part(SeqList *L) int i, j ;datatype x, y ; x=L-elem0; /* 将基准置入 x 中*/fo
14、r(i=1; ilast; i+)if (L-elemielemi;for(j=i-1; j=0; j-) /*移动*/Lelemj+1=L-elemj;L-elem0=y; ,最坏情况下移动数据时间性能为(2),例2.2 利用两个线性表la和lb分别表示两个集合A和B，现要求一个新的集合A=AB。假设集合中的数据元素属于整型数据。 算法思路：扩大线性表la，将存在于线性表lb中而不在la中的数据元素加入到线性表la中。逐一取出lb中的元素，判断是否在la中，若不在，则插入。 存储结构与例2.1相同。 A=(23, 45, 78, 91, 55) B=(47, 23, 8, 55) AB=(2
15、3, 45, 78,91, 55,47,8)SeqList *la, SeqList lb 初始化la, lb:la-elem0 la-elem4: 23, 45, 78, 91, 55lb.elem0 lb.elem3: 47, 23, 8, 55,算法如下： void unin(SeqList *la, SeqList *lb) int i, j, La_len, Lb_len; datatype e;La_len=La-last; Lb_len=Lb-last;for (i=0; ielemj) j+; /*在la中查找e元素*/if (jLa_len) /*la 中不存在和e 相同的元素，则插入之*/ if (La_lenelem+(La-elem)=e; union 时间复杂度：O（ListLength(la) ListLength(lb)）,
