数据结构考研课件-大连海事大学ky0-绪论

《数据结构考研课件-大连海事大学ky0-绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表2.1线性表的定义和抽象数据类型2.2线性表的顺序存储结构2.4线性表的链式存储结构第二章线性表2.3线性表应用举例2.5线性表操作在单链表上的实现第二章线性表2.1线性表的定义和抽象数据类型2.1.1线性表的定义2.1.2线性表的抽象数据类型2.1.3操作举例第二章线性表线性结构非线性结构顺序存储结构链式存储结构索引结构散列结构逻辑结构存储结构数据结构线性表广义表堆栈和队列树图2.1.1线性表的定义1.相关知识回顾A=(a1，a2，a3，......,an)(1)当1

2、最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。2.线性关系除了第一个数据元素与最后那个数据元素外，其余每个元素有且仅有一个直接前驱元素，有且仅有一个直接后继元素，数据元素之间存在着一对一的关系，我们将这种逻辑关系称为线性关系。第二章线性表数据元素之间具有的逻辑关系为线性关系的数据元素集合称为线性表。线性表(LinearList)是具有相同特性的数据元素的一个有限序列。3.线性表的定义第二章线性表线性表的长度：表中元素的个数，用n表示空表：n=0的线性表线性表一般表示为：(a1,a2,…,ai,ai+1,…,an)a1：表头元素；

3、an：表尾元素ai是第i个数据元素，i是在表中的位序;直接前驱元素是ai-1；直接后继元素ai+1一个线性表可以用一个标识符来命名，如用A命名线性表，则：A=(a1,a2,…,ai,ai+1,…,an)第二章线性表4.线性表的形式化定义二元组：linear_list=(A,R)元素类型ElemType是一种通用数据类型标识符，可以通过typedef语句在使用前将其定义为任一具体类型。如，整数typedeftypedefintElemType;有序表：存在按值的升序或降序排列的字段（有序字段）；不存在则为无序表A=(a1，a2，a3，......,an)数列：(25，

4、12，78，34，100，88)99001张华女17……99002李军男18……99003王小明男17……99050刘末女19…………学号姓名性别年龄其他…………a1a2a3··a50a1a2a3a4a5a6字母表：(‘A’，‘B’，‘C’，……,‘X’,‘Y’,‘Z’)a1a2a3……a24a25a26数据文件：一个数据元素是一个整数一个数据元素是一个英文字母一个数据元素是一个数据记录第二章线性表2.1.2线性表的抽象数据类型由一组数据结构和在该组数据结构上的一组操作所组成抽象数据类型(AbstractDataType简称ADT)第二章线性

5、表数据部分：用标识符L表示一个线性表，可采用顺序、链接、散列等任一方式存储到计算机中，其存储类型用标识符ListType表示操作部分：对线性表所作的各种操作运算，如插入、删除、求表的长度、判断表是否为空等第二章线性表抽象数据类型线性表的定义如下：ADTLinearListisData：一个线性表L＝(a1,a2,…,ai,ai+1,…,an)当L=()时为空表endLinearListOperation：操作描述请见后续页第二章线性表voidInitList(ListType&L)；操作结果：构造一个空的线性表L。初始化操作第二章线性表清除操作voidClearLi

6、st(ListType&L)；操作结果：清除线性表L中的所有元素，使之成为一个空表。第二章线性表intLenthList(ListType&L);初始条件：操作结果：线性表L已存在。返回L中元素个数，若空则返回0。求长度操作第二章线性表boolEmptyList(ListType&L);初始条件：操作结果：线性表L已存在。若L为空表，则返回真(true)，否则返回假(false)。线性表判空操作第二章线性表ElemTypeGetList(ListType&L,intpos);初始条件：操作结果：线性表L已存在，返回L中第pos个元素的值。若pos出界，则打印出错信息

7、（求线性表中某个数据元素）且1≤pos≤LengthSize(L)第二章线性表voidTraverseList(ListType&L);初始条件：操作结果：线性表L已存在。按照L中元素的逻辑顺序访问每个元素，且每个元素仅被访问一次（遍历线性表）第二章线性表boolFindList(ListType&L,ElemType&item)；初始条件：操作结果：线性表L已存在，item为给定值查找L中值与item相等的元素若成功返回真，由item返回该元素的值，否则返回假。（查找函数）第二章线性表boolUpdateList(ListType&L,constElemTyp