数据结构(C语言版)PPT第二章.ppt

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示与实现 2.3线性表的链式表示与实现 2.4 一元多项式的表示及相加 学习目标 了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 结合线性表类型的定义增强对抽象数据类型的理解。 重点难点 链表 指针操作和内存动态分配的编程技术； 链表中指针 p 和结点 *p 之间的对应关系； 头结点、头指针和首元结点的不同； 循环链表、双向链表的特点。 线性结构的特点 在数据元素的非空有限集中 存在唯一一个被称做“第一个”的数据元素； 存在唯一一个被称做“最后一个”的数据元素； 除第一个数据元素之外，每个元素都只有一个前驱； 除最后一个数据元素之外，每个元素都只有一个后继。 §2.1线性表的类型定义 线性表：是n个数据元素的有限序列。 除了第一个元素没有直接前驱和最后一个元素没有直接后继之外，其余的每个数据元素只有一个直接前驱和一个直接后继。 线性表的特征 有穷性：由有限个元素组成，元素个数n—表长度，n=0空表。 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。 有序性：线性表元素之间存在序偶关系，1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 同一性：线性表属于同类数据元素组成，每一个对象都属于同一数据对象 线性表抽象数据类型定义： ADT? List { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n } 基本操作： （1）InitList（L） 操作结果：将L初始化为空表。 （2）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L) 操作前提：线性表L已存在 。 操作结果：将表L置为空表。 （4）EmptyList（L） 操作前提：线性表L已存在。 操作结果：如果L为空表则返回真，否则返回假。 （5）ListLength（L） 操作前提：线性表L已存在。 操作结果：如果L为空表则返回0，否则返回表中的元素个数。 （6）GetItem(L,i,e) 操作前提： 表L已存在，1=i=listlength(L)。 操作结果： 用e返回L中第i个元素的值。 （7）LocateElem(L,e) 操作前提： 表L已存在，e为合法元素值。 操作结果： 如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。 （8）ListInsert(L,i,e) 操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 （9）ListDelete(L,i,e) 操作前提：表L已存在且非空 ，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 }ADT? List 利用上述定义的线性表类型，可以实现其它更复杂的操作，例如：归并、拆分、复制、排序 例2-1 假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A并B。即将存在于线性表LB中而不存在于LA中的元素插入线性表LA中。 算法举例： 例2-1 假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。(注：∪ ——并集，属于A或者属于B) 思路： 1．从线性表LB中依次取得每个数据元素; GetElem(LB, i)→e 2．依值在线性表LA中进行查访; LocateElem(LA, e, equal( ) ) 3. 若不存在，则插入之。 ListInsert(LA, n+1, e) 算法举例： 例2-2 归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。（问题分析） La = (a1, …, ai, …, an), Lb = (b1, …, bj, …, bm), Lc = (c1, …