《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-2》由会员分享，可在线阅读，更多相关《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-2（25页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,1.,2.,3.,本章讲述内容：,4.,线性表的基本知识 ；,线性表的顺序存储实现 ；,线性表的链式存储实现（单链表、双链表、循环链表） ；,线性表的具体应用举例 。,2.1 线性表的基本知识,线性表的定义,1.,一组数据的逻辑结构呈线性关系时，称其为线性表。即所谓“线性表”，是由具有相同类型的有限多个数据元素组成的一个有序序列。,若把一个线性表取名为L，里面有n（n0）个元素，每个元素用ai（1in）表示，下标代表该元素在线性表中的位置，那么可以把线性表L记为： L = (a1 , a2, , ai, ai+1, , an1, an ),.,.,线性表的若干概念,2.,.,线
2、性表中数据元素的个数n，称为线性表的“长度”。当n=0时，表示线性表中不包含任何元素，称其为“空表”。若线性表L为空，则记为L =（）或L = 。,.,在线性表中，对任意一对相邻结点ai和ai+1（1in1），称ai为ai+1的“直接前驱”，称ai+1为ai的“直接后继”。,ai,ai+1,ai+1的直接前驱,ai的直接后继,.,若线性表中元素的值与它的位置间存在联系，比如其元素的值是按递增顺序排列的，那么称这种线性表为“有序线性表”；若线性表中元素的值与它的位置之间没有特殊的联系，那么称这种线性表为“无序线性表”。,2.2 线性表的顺序存储实现,2.2.1 顺序表,线性表的特点,3.,.,.
3、,有且仅有一个起始结点a1，它没有直接前驱，只有一个直接后继a2 。,.,有且仅有一个终端结点an，它没有直接后继，只有一个直接前驱an1 。,其余结点ai（2in1）都有且仅有一个直接前驱ai1和一个直接后继ai+1。,线性表上的常见处理,4.,.,创建一个新的线性表，或删除一个已经存在的线性表 。,.,使线性表增长（即插入一个元素）、使线性表缩短（删除一个元素），增长或缩短后元素间仍将保持线性关系 。,.,得到当前线性表里拥有的元素个数（测试出线性表的长度）。,.,查找到所需要的线性表元素的值，读出这个值，或者对这个值进行修改 。,.,从一个元素出发，得到它的前驱结点和后继结点 。,顺序表
4、的定义,1.,采用顺序式存储结构存放线性表时，是把表中的数据结点按其逻辑次序依次存储在内存中的一块连续存储区里。这时，线性表中逻辑上邻接的两个数据结点，其存储结点在物理位置上也是相邻接的。以这种顺序存储结构实现的线性表，被称为“顺序表”。,由于顺序表中任一个存储结点的位置可通过计算得到，所以对顺序表中的任一数据元素的访问，都可在相同的时间内实现，即可方便地实现随机访问。,由于顺序表要占用内存中的连续存储区，因此为其分配一块存储区域之后，在该区域里能够容纳的数据元素的个数是有限的。,顺序表所占存储区大小,2.,在顺序式存储中，存储结点里不需要存放结点间的邻接关系，数据的存储结点大小与其数据结点大
5、小相同。因此，顺序表所占的连续存储区，应该由数据结点所需的存储量以及数据结点的个数来决定。,求顺序表任一存储结点地址的公式,3.,LOC ( ai ) = LOC ( a1 ) + size x ( i - 1),第i个存储 结点的地址,第1个存储 结点的地址,存储结点尺寸,前面已有 的结点个数,a1,1,a2,2,a3,3,ai,i,ai+1,i+1,an-1,n-1,an,n,位置序号：,结点内容：,存储地址：,LOC(a1),size,LOC(a1)+size,LOC(a1)+sizex(i-1),空闲,设存储结点的数据类型为elemtype，每个存储结点所需存储量为 size，顺 序表
6、Sq 第1个存储结点a1的起 址为 LOC(a1)。那么，顺序表 Sq 第 i 个存储结点 ai 的起址 LOC(ai) 可通过公式得到 。,顺序表的几个特点,4.,.,.,.,由于顺序表中元素之间是一种线性的逻辑关系，因此在往顺序表里插入或删除一个数据元素时，势必要对原有数据元素进行移动，以求维持这种线性关系。,2.2.2 顺序表的基本算法描述,创建顺序表的算法,算法2-1,算法描述,(1),Create_Sq (Sq，Sq_num，Sq_max) elemtype SqMAX*size ; Sq_num = 0; Sq_max = MAX ; return Ok; ,算法分析,(2),算法
7、讨论,(3),算法说明一个类型为elemtype、名为Sq的数组，获得顺序表所需存储空间，分配的存储区尺寸为MAX*size。,.,.,Sq_max的作用，是为了在顺序表Sq上进行操作时，能与Sq_num比较，确保顺序表不发生越界行为。,.,Sq_num的作用，用来随时记录顺序表中当前存放的数据元素的个数 。,注意，Sq_max是顺序表的最大长度，表创建后，它是保持不变的常量；Sq_num是顺序表内当前拥有的数据元素个数，随着数据元素的插入与删除，Sq_num将会不断地发生变化，但不能让它越过 Sq_max。,.,.,顺序表里已有元素的下标是1Sq_num。也就是说，通常顺序表里的元素可以表示
8、成：Sq 1 Sq_num。注意，若是用C语言里的数组来实现线性表，就要注意C语言的数组下标规定则是从0开始的。,在顺序表指定位置后插入元素的算法,算法2-2,33,1,12,2,25,3,61,4,77,5,24,6,38,7,51,8,9,10,顺序表Sq：,插入22,空闲,33,1,12,2,25,3,61,4,77,5,24,6,38,7,51,8,9,10,顺序表Sq：,移动元素次序：,空闲,33,1,12,2,25,3,61,4,77,5,24,6,38,7,51,8,9,10,顺序表Sq：,空闲,腾空位置5,33,1,12,2,25,3,61,4,77,5,24,6,38,7,5
9、1,8,9,10,顺序表Sq：,空闲,完成插入,22,说明：在顺序表Sq的第i个位置之后插入新数据元素x，算法名称为Insert_Sq ()，参数为Sq、i、x。算法约定：当iSq_num时，新数据结点插入在表尾。,.,.,比如，Sq里已有8个数据元素：Sq1=33，Sq2=12，Sq8=51。希望在位置4的后面插入数据元素22。,最后，将数据元素22写入到腾出的位置5处，完成对顺序表的插入操作。,那么应将原先位于位置58的4个元素都后移一个表位，将位置5腾空。要注意，移动应该由后往前一个个地进行，即先将第8个数据元素移到位置9处，再将第7个数据元素移到位置8处，如此等等。,移动完成后，位置5
10、被腾空。,.,.,.,插入也可在指定位置i之前进行。这时，新插入的元素就是顺序表中的第i个元素。编写算法时，必须依照具体要求做，不能一概而论。,算法分析,(2),.,算法讨论,(3),.,算法描述,(1),Insert_Sq (Sq, i, x) if (Sq_num = Sq_max) printf (“The sequential list is full !“); if (iSq_num) i = Sq_num; for ( j=Sq_num+1; ji; j- ) Sqj = Sqj-1 ; Sqj = x ; Sq_num+ ; ,算法中最实质的部分是腾空指定的插入位置，它由一个fo
11、r循环来实现。循环前，须先考察插入位置参数是否合适。根据约定，若iSq_num，就把新结点插入在表尾。,.,移动从当前最后一个元素开始，到第i+1个元素为止，每次都是把元素往后移动一个表位。具体实施移动的操作是： Sqj = Sqj1,插入算法的执行主要耗费在for循环上。影响时间的因素有二：一是顺序表当前的长度（Sq_num）；另一是插入操作的位置（i）。,.,.,在设计算法时，要特别注意边界位置的处理。对于顺序表来说，边界是指第1个数据元素的位置，是指当前表中最后一个元素的位置，或是指整个表的最后一个位置。,算法通过for循环，从第i+1个元素开始往前移动一个表位，直到第Sq_num个元素
12、为止。每一次移时做的操作是： Sqj1 = Sqj,算法分析,(2),算法描述,(1),删除顺序表指定位置处元素的算法,算法2-3,说明：删除Sq中第i个位置处的数据元素，将其值存入变量x。,Delete_Sq (Sq，i，x) if (iSq_num) return ERROR ; x = Sqi ; for ( j=i+1; j=Sq_num; j+ ) Sqj-1 = Sqj ; Sq_num=Sq_num-1; ,算法讨论,(3),移动元素次序：,33,1,12,2,25,3,61,4,77,5,24,6,38,7,51,8,9,10,顺序表Sq：,空闲,删除位置i,22,43,当前最
13、后一个元素,33,1,12,2,25,3,61,4,24,5,38,6,51,7,43,8,9,新腾空的表位,顺序表Sq：,空闲,完成插入,77,删除算法的执行时间主要耗费在for循环上，影响时间的因素是顺序表当前的长度（Sq_num）和删除操作的位置（i）。,.,.,对于顺序表，如果删除操作对位置i的选取是等概率的，那么删除第i个元素平均需要移动的元素个数是Sq_num / 2。,算法分析,(2),算法描述,(1),查找顺序表中第1个与给定数据相等的元素的算法,算法2-4,说明：给定数据x，在顺序表Sq 中查找第一个与它相等的元素。查找成功时，返回元素位置；若失败，返回0。,Locate_S
14、q (Sq, Sq_num, x) for (i=1; i=Sq_num ; i+) if (Sqi = x) return (i) ; if (i = Sq_num) return (0) ; ,算法通过for循环实现查找，循环由条件“i = Sq_num”控制。在顺序表中还没有找到第一个与x相同的数据元素时，循环就会继续下去。,.,.,循环只在两种情况下停止：一是找到等于x的元素，就通过“return (i)”返回i，结束循环；一是查到表尾也没有等于x的元素，于是通过“return (0)”返回0，结束循环。,算法讨论,(3),“查找”是在任何数据结构上定义的最基本的操作处理，因为插入、删
15、除等都需要先进行查找，以确定操作执行的位置。任何查找，只可能有两个结果：找到或没有找到。因此在设计查找算法时，必须解决好这样的两种问题。,.,打印顺序表各结点值的算法,算法2-5,Print_Sq(Sq, Sq_num) if (Sq_num = 0) printf (“The sequential list is empty !“); else for (i=1; i=Sq_num; i+) printf (“%d“, Sqi); ,求顺序表现有元素个数的算法,算法2-6,往顺序表尾添加新元素的算法,算法2-7,Length_Sq(Sq_num) printf (“The Length of sequential list is =%d“, Sq_num); ,Append_Sq(Sq, Sq_num, Sq_max, x) if (Sq_num = Sq_max) printf (“The sequential list is full !“); else SqSq_num+1 = x ; Sq_num = Sq_num+1 ; ,算法描述,(1),算法分析,(2),这个算法与算法2-2不
