《数据结构（C语言描述）教学课件斯庆巴拉第2章线性表》由会员分享，可在线阅读，更多相关《数据结构（C语言描述）教学课件斯庆巴拉第2章线性表（73页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,学习重点： 线性表的概念及表示方法 线性表的顺序存储方式及操作的实现算法 线性表的链式存储方式及操作的实现算法,第2章 线性表,2.1 实例：学生信息的存储 2.2 线性表的逻辑结构 2.3 线性表的顺序存储 2.4 线性表的链式存储 2.5 动态存储管理 2.6 应用举例：线性表的建立、合并 本章总结,2.1 实例：学生信息的存储,2.1.1 问题描述 2.1.2 问题的分析 2.1.3 实现算法,2.1.1 问题描述,对在校生信息的管理是一项庞大的工程,它要求能够完成新、老学生信息的输入、修改、插入和删除工作等等。下面就给出一张学生基本情况登记表如表2-1所示：,2.1.2
2、 问题的分析,学生基本情况登记表中包含每个学生的基本情况，如学号、姓名、性别等等。在此表中学生的基本信息的排列是以学号为依据，从小到大排列。 从数据结构的定义来讲，可将表看成是以学生记录为元素，以学号的升序排列为关系，经常进行插入、删除和查找等操作的数据结构（线性结构）。 要用计算机解决此问题需要做以下工作： 第一，信息以什么形式表示并存储到计算机中；第二，各种操作的具体实现方法（算法）。,三个方面,学生情况登记表是一个由多条记录组成的表格，可用编程语言的结构体类型表示，此时记录中的每个数据项对应结构体中的一个成员，多条记录可定义成一个结构体数组。 定义如下： struct student i
3、nt num; / 表示学号 char name12; / 表示姓名 / 其余省略 ；,对信息进行存储时，元素以数组形式存放在连续的存储空间中，以物理位置来体现关系。但随时存在退学、转学等情况，所以分配时应多分配一些存储空间，并用一个整型变量给出元素个数。 定义如下： #define size maxsize /分配的存储单元个数 struct List student stu size ; /保存学生记录 int len ; /学生人数 ,顺序存储方式,2.1.3 实现算法,以删除操作为例，则实现步骤为： 第一步，在数组中查找给定学号的学生记录。 第二步，对数组元素进行删除。因给数组分配的单
4、元是连续的，所以删除一个元素需要把删除元素后面的所有元素都往前移一位。,实现算法：删除学号为num的学生记录，并保存到t中。 void DeleteList(List ,结论： 1 给定的学生登记表中的记录以学号的从小到大排列，记录间是一对一的关系 线性结构。 2 除了第一条记录和最后一条记录以外，所以记录都只有唯一的前驱记录和后继记录。,2.2 线性表的逻辑结构,2.2.1 线性表的逻辑结构 2.2.2 线性表的基本操作,线性表是一种线性结构，它具有以下特点： l 构成线性表的数据元素之间的关系是一对一的关系 l 有且仅有一个第一个元素和一个最后一个元素 l 除第一个元素外，所有元素有且仅有
5、一个前驱元素 l 除最后一个元素外，所有元素有且仅有一个后继元素,2.2.1 线性表的逻辑结构,线性表是相互间存在一对一关系的相同类型元素的有限集。（元素个数是确定的） 线性表表示为：（a1,a2,a3,ai-1,ai,an） 其中，aiElemtype代表线性表的元素类型,n为线性表的元素个数，通常称n为线性表的长度(n0)，n=0线性表是空表，否则为非空表。a1为线性表的第一个元素，an为线性表的最后一个元素。它是一个由n个元素组成的以逻辑顺序表示元素间关系的线性结构。,例： 线性表2=（A，B，C，D） 分析： 线性表2是一个元素类型为字符型的由4个元素组成的有限集。 A是线性表的第一个
6、元素，D是线性表的最后一个元素。元素之间的关系：B的前一个元素是A，后面元素是C，所以称A是B的前驱元素，而C是B的后继元素。除了A以外所有元素都有唯一的前驱，除了D以外所有元素都有唯一的后继。,2.2.2 线性表的基本操作,线性表的常用操作有以下几种： InitList(L) 初始化。（建立一个空表L） LengthList(L) 求长度。求线性表L中的元素个数。 GetList(L,i,elem) 取元素。 EmptyList(L) 判空表。 LocateList(L,elem) 查找元素。 InsertList(L,i,elem) 插入元素。 DeleteList(L,i) 删除元素。
7、PriorElem(L,elem) 取前驱元素。 NextElem(L,elem) 取后继元素。,注意： 1 各个基本操作的初始条件（参数及类型）和最终结果（有无返回值）。 2 操作的定义依赖线性表的逻辑结构，而操作的实现却依赖于线性表的存储结构。,2.3 线性表的顺序存储,2.3.1 顺序存储方式 2.3.2 各种操作的实现,2.3.1 顺序存储方式,顺序存储方式是指在内存中开辟连续的存储单元，用来存放线性表的元素，并以元素的物理位置来体现元素之间的线性关系。,图 2-1 顺序存储结构示意图,在顺序存储方式中，对线性表分配了连续的maxsize个存储单元用来存放元素，设存储空间的起始地址为b
8、，每个元素所占的字节数为d，则a1的地址为b，a2的地址为b+d,依次类推，ai的地址为 b+(i-1)*d，an的地址为b+(n-1)*d。可得计算线性表元素存储地址的公式： LOC（ai）=LOC(a1)+(i-1)*元素在内存中所占字节数,线性表顺序存储数据类型定义： # define maxlen maxsize / maxsize为分配的存储单元个数 struct ListSq Elemtype e maxlen ; / 存放元素 int len ; / 线性表长度 注意：在C语言中数组的下标是从0开始的，与线性表中元素的序号不一致，下标的取值范围0下标maxsize=1。,2.3.
9、2 各种操作的实现,操作一：InitList(L) 初始化。 操作二：LocateList(L,elem) 查找元素。 操作三：InsertList(L,i,elem) 插入元素。 操作四：DeleteList(L,i) 删除元素。 操作五：PriorElem(L,elem) ，取前驱元素。,操作一：InitList(L) 初始化。 分析：初始化就是创建空线性表（空线性表是一个不含任何元素的长度为0的线性表） 实现算法： void InitList(ListSq 时间复杂度为O(1) 结论：线性表进行求长度或判断是否为空表等操作时，直接读线性表的长度L.len或判断L.len是否等于0就可以实
10、现相应操作。,操作二：LocateList(L,elem) 查找元素。 分析：前一节的学生信息表中如果需要某个学生的地址邮寄成绩单，常用的方法是从第一个学生起进行比较，如果不是所要找的学生就继续，直到找到所要找的学生的记录或无此学生为止。 线性表的查找操作也可按此方法来完成。从第一个元素开始与elem进行比较，不相等就继续，直到找到相等的元素返回该元素的序号，或没有找到相应元素返回0值为止。,实现算法： int LocateList(ListSq L,Elemtype elem ) int i=0; while (iL.len) ,不满足表示：查找不成功！,不满足表示：查找成功,平均情况下，时
11、间复杂度为O（n）。,时间复杂度取决于算法中的循环语句的循环次数，即查找元素过程中的比较次数。 最好情况是查找第一个元素：时间复杂度为O（1） 最坏情况是查找元素不存在：时间复杂度为O（n）。 （n是线性表中元素的个数） 设查找每个元素的概率是相等的，则依次查找各个元素的过程中比较次数分别为1、2、，n次，则等概率情况下平均比较次数为：,操作三：InsertList(L,i,elem) 插入元素。 分析：在学生情况登记表中增加一条记录的具体实现方法是给增加的记录找到合适的位置进行插入，后续记录都往后移一位。同样，在第i个位置处插入元素，需要线性表的第i+1个元素开始到最后一个元素都往后移了一位
12、，空出第i+1个位置存储元素elem，线性表的长度加1。如图2-2所示： 需要考虑的问题： 1 存储空间的分配采用了静态分配，存储空间大小是固定的。所以，有可能出现 “溢出”现象。（需判断） 2 插入位置i代表元素的序号， i的取值范围为： 0 = i = LengthList(L) 。（需判断）,实现算法： Void InsertList(ListSq ,图2-2 顺序表的第i个元素位置插入元素,平均情况下，时间复杂度为O(n)。,插入操作的时间复杂度主要取决于算法中需要向后移动的元素个数。 最好情况是插入在最后面，时间复杂度为O（1）。 最坏情况是插入在最前面，时间复杂度为O（n）。 等概
13、念的情况下，元素的移动次数为：,操作四：DeleteList(L,i) 删除元素。 分析：在本章第一节的实例中，提到过学生信息的删除操作。通常采取的方法是先找学生记录，找到后将它从表中删除。线性表进行删除操作也一样，先找删除位置，后进行删除，后续元素都向前移一位。删除元素ai，则从ai+1到an所有元素都往前移一位，线性表的长度减1。如图2-3所示： 考虑的问题： 1 进行删除时先找删除位置，初始条件中的i是元素序号，i的取值范围为： 1 = i =LengthList(L) 。（需判断） 2 对空表无法进行删除操作。 （需判断）,图2-3 从顺序表中删除第i个元素,实现算法： void De
14、leteList( ListSq ,删除操作的时间复杂度主要取决于算法中需要向前移动的元素个数。 最好情况：删除最后一个元素，时间复杂度为O（1）。 最坏情况：删除第一个元素，时间复杂度为O（n）。 等概念的情况：时间复杂度为O（n）。,操作五：PriorElem(L,elem) ，取前驱元素。 考虑的问题：（存在前驱的条件） 1 需要判断元素elem是否是线性表L的元素。 2 需要判断元素elem是不是线性表的第一个元素。 步骤： 只有元素elem是线性表L的元素，并且不是第一个元素时，才存在前驱，返回该元素的前驱（下标减一）；否则返回空值，并给出提示信息。,实现算法： Elemtype P
15、riorElem(ListSq L , Elemtype elem ) int i; i=LocateList(L,elem ) ; /条件一 if ( i=0 ) printf(“%d不是线性表中的元素！“,elem ); else if ( i= 1) /条件二 printf(“是线性表第一个元素，不存在前驱！”); else return L.e i-2 ; return NULL; /没有前驱 ,时间复杂度取决于元素是否是线性表中元素判断过程，算法中调用了LocateList ( L , elem ) 查找函数，时间复杂度为O(n)。 读取后继元素的操作NextElem(L,elem)
16、与取前驱一样，先判断元素elem是否是线性表L的元素，如果是继续判断元素elem不是线性表的最后一个元素，只有两个条件都满足时，才存在后继元素。,结论： 1 线性表顺序存储时，开辟的内存空间必须是连续的，需要以元素在内存中的物理位置来体现元素间的逻辑关系。 2 在第i个元素的后面进行插入或删除第i个元素时，从第i+1个元素到最后一个元素都往后移一位或往前移一位，都涉及到元素的移动。所以算法的时间复杂度都为O（n）。（该存储方式下不适宜做插入和删除操作） 3 读取顺序表中的元素时，可利用元素的序号任意读取线性表是的元素。（随机访问，该存储方式下适宜做读取操作）,2.4 线性表的链式存储,2.4.1 链式存储方式 2.4.2 各种操作的实现 2.4.3 循环单链表 2.4.4 双向链表,引入： 线性表
