资源描述：
《数据结构-02线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构（DataStructure）主讲：李耀国第二章线性表（LinearList）第二章线性表2.1线性表的类型定义2.1.1线性表的定义2.1.2线性表的基本操作2.2线性表的顺序表示和实现2.2.1顺序表-线性表的顺序存储表示2.2.2顺序表中基本操作的实现2.2.3顺序表其他算法举例2.3线性表的链式表示和实现2.3.1单链表和指针2.3.2单链表的基本操作2.3.3单链表的其他操作举例2.3.4循环链表2.3.5双向链表2.4有序表2.5顺序表和链表的综合比较2.1线性表的类型定义线性结构的特点：在数据元素的非空有限集中，①存在唯一的一个被称做“第一个”的
2、数据元素；②存在唯一的一个被称做“最后一个”的数据元素；③除第一个之外，集合中的每个元素均只有一个前驱；④除最后一个之外，集合中的每个元素均只有一个后继。线性表(Linear_List)是最简单，也是最基本的一种线性数据结构。它有两种存储表示：顺序表和链表，它主要的操作是插入、删除和查找等。2.1线性表的类型定义2.1.1线性表的定义线性表的实例：1）(3,8,5,7,10)是一个线性表，其中的数据元素是整数,按上述顺序排列，表中共有5个数据元素。2）(A,B,C,D,…,X,Y,Z)是一个线性表,其中的数据元素是英文字母,按字母顺序排列，共有26个数据元素。3）按字
3、母顺序排列的学生姓名表。4）按字母顺序排列的商品列表。5）(1分、2分、5分、1角、2角、5角)2.1.1线性表的定义6）下图的学生学籍档案表，是稍复杂的线性表，表中元素可以由多个数据项组成，在这里每个学生档案是一个线性表，它由学号、姓名、和各项成绩组成。（和绪论中介绍的图书目录表类似）学生学籍档案表学号姓名入学分数分……0101赵前进60190……0102华罗庚64098……0103李龙58080……∶∶∶∶∶2.1.1线性表的定义线性表(Linear_List)是n(n≥0)个数据元素的有限序列，表中各个数据元素具有相同的特性，既属于同一数据对象，表中相邻的数据元
4、素之间存在“序偶”关系。通常将线性表记做(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)(2-1)则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。n是表的长度。当n=0时，表为空。a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，其中i为数据元素ai在线性表中的位序。除了这种优先关系之外，在线性表中不再有其他的结构。2.1.2线性表的基本操作线性表的抽象数据类型定义：ADTList{数据对象:D={ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={
6、
7、ai-1,ai∈D,i=2,...,n}基本操作：InitList(&L):构造一个空线性表LDestroyList(&L):在线性表L存在的条件下，摧毁线性表LClearList(&L):在线性表L存在的条件下，将L重置为空表ListEmpty(L):若L为空，返回TRUE，否则返回FALSEListLength(L):在线性表L存在的条件下，返回表中元素的个数GetElem(L,i,&e):在1≤i≤ListLength(L)条件下，用e返回L中第i个元素LocateElem(L,e):返回L中第一个与e满足相等关系的元素的位序，如不存在，返回
8、0more2.1.2线性表的基本操作PriorElem(L,cur_e,&pre_e):如果cur_e是L中的元素，并且不是第一个，则用pre_e返回它的前驱。否则失败。NextElem(L,cur_e,&next_e):如果cur_e是L中的元素，并且不是最后一个，则用next_e返回它的后继。否则失败。ListInsert(&L,i,e):在1≤i≤ListLength(L)+1条件下，在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e):在1≤i≤ListLength(L)条件下，删除L的第i个数据元素，并用e返回其值，L
9、的长度减1。ListTraverse(L):依次输出L中的每个数据元素。}ADTList2.1.2线性表的基本操作前面各个操作的定义仅对抽象的线性表而言，定义中尚未涉及线性表的存储结构以及实现这些操作所用的编程语言。但利用这些操作可以完成例如研究算法、求解算法及分析算法等重要工作。在这一层次研究问题可以避开技术细节，面向应用，深入讨论问题。下面我们可以通过例子来看如何设计应用。例2.1合并两个线性表：La和Lb是分别表示两个集合A、B，现求一个新的集合A=A∪B2.1.2线性表的基本操作10从线性表Lb中删除一个数据元素（同时获取该元素）20按该元素
