ch02_Linear_List 数据结构.ppt

数据结构 Data Structures 第二章 线性表 第二章 线性表 本章内容 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 2.1 线性表的类型定义 定义：一个线性表是有n个数据元素的有限序列： (a1，a2，…，ai，…，an)。 线性表中元素之间的关系是线性关系： 存在惟一的第一个元素和惟一的最后一个元素； 除第一个元素之外，每个元素均只有一个直接前驱； 除最后一个元素之外，每个元素均只有一个直接后继。 线性表中的元素类型： 原子类型：如整数、字符等。 结构类型：如表示一个学生信息的数据元素，包含学号、姓名、性别等数据项 一个线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时称为空表。非空线性表中的每个元素都有一个确定的位序。 2.1 线性表的类型定义 线性表的抽象数据类型定义： ADT List { 数据对象：D={ ai | ai ?ElemSet, i=1,2,…n, n?0 } 数据关系： R={ ai-1,ai | ai-1,ai ?D, i=2,3,…n} 基本运算： InitList(L); //初始化线性表，构造空线性表 DestroyList(L); //销毁线性表 Length(L); //求线性表长度 GetElem(L,i,e); //获得线性表中第i个元素 LocateElem(L,e,compare()); //查找线性表中和e满足关系”compare”的元素 InsertElem(L,i,e); //在线性表的位置i插入一个元素e DeleteElem(L,i,e); //删除线性表位置i的元素,被删除元素的值放到e中 } ADT List 2.1 线性表的类型定义 抽象运算（算法2.1） 例2-1 利用两个线性表LA和LB分别表示集合A和B，求一个新的集合A=A∪B。 算法思路：集合中的元素间是松散的关系，只需将在线性表LB中而不在LA中的数据元素追加到LA的尾部即可。 2.1 线性表的类型定义 抽象运算（算法2.1） 2.2 线性表的顺序表示和实现 顺序表---线性表的顺序存储 内涵：线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。 特点： 存储单元地址连续（需要一段连续空间） 逻辑上相邻的数据元素其物理位置也相邻 存储密度大（100%） 随机存取 元素序号与存储位置存在如下关系： 2.2 线性表的顺序表示和实现 顺序表存储的Ｃ语言实现 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表，但由于是顺序表的长度可变，需要用动态数组来表示。 2.2 线性表的顺序表示和实现 创建一个空的顺序表（算法2.3） 2.2 线性表的顺序表示和实现 线性表上的基本运算 插入运算 将元素e插入到线性表：(a1, a2, …, ai-1, ai, …, an)中，构成新的线性表(a1, a2, …, ai-1, e, ai, …, an)，满足ai-1 ≤ e ≤ai,(其中≤为比较关系),即不破坏原线性关系。 表的长度变为n+1 将元素e插入到元素ai-1之后，ai-1的直接后继和ai 的直接前驱就改变了，需要在顺序表的存储结构上反映出来。 2.2 线性表的顺序表示和实现 顺序表上插入运算的实现: 2.2 线性表的顺序表示和实现 以7个元素的顺序表为例进行说明，将元素e插入a5之前。 2.2 线性表的顺序表示和实现 用类C语言实现顺序表的插入 2.2 线性表的顺序表示和实现 realloc函数 void *realloc( void *memblock, size_t size ); 扩展已分配的内存空间，保持原来的内容不变 参数： memblock--以前用malloc分配的空间 size--新的内存空间大小 返回值：新的内存空间地址，可能和原来的地址不同 2.2 线性表的顺序表示和实现 顺序表上插入运算效率分析： 时间复杂度 　　从算法流程上看，查找插入位置、插入元素的时间消耗是常数级，算法执行时间主要消耗在插入前元素的移动上，而移动元素的个数与插入位置i有关。 最好情况: 在表尾插入，不移动元素，T(n)=O(1) 最坏情况: 在表头插入，移动n个元素，T(n)=O(n) 平均复杂度 　　设pi为在第i个元素之前插入一个元素的概率，且p1=p2=…=pi=…=pn=1/(n+1)，则平均移动次数为： 2.2 线性表的顺序表示和实现 顺序表上插入运算效率分析： 空间复杂度 不需要额外空间，S(n) = O(1)。 2.2 线性表的顺序表