数据结构与算法北京大学2008张 铭线 性表课件

《数据结构与算法北京大学2008张 铭线 性表课件》由会员分享，可在线阅读，更多相关《数据结构与算法北京大学2008张 铭线 性表课件（60页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法 第2章 线性表,本章由赵海燕主写 北京大学 张铭，王腾蛟，赵海燕 高等教育出版社，2012. 6。“十一五”国家级规划教材,主要内容,线性结构 顺序表 链表 线性表实现方法的比较,线性结构,元素间满足线性关系 “一对一”的关系 按此关系结构中的所有元素排成一个线性序列 二元组B = (K, R) , K = a0, a1, , an-1 , R = r ： 结点集K中有一个唯一的开始结点，它没有前驱，但有一个唯一的后继； 对于有限集K , 它存在一个唯一的终止结点，该结点有一个唯一的前驱而没有后继； 其它的结点皆称为内部结点，每一个内部结点都有且仅有一个唯一的前驱，也有一个唯一

2、的后继； a0, a1, , an-1 ai是ai+1的前驱， ai+1是ai的后继,线性结构,特点： 均匀性：虽然不同线性表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度 有序性：各数据元素在线性表中都有自己的位置，且数据元素之间的相对位置是线性的,线性结构,包括： 简单的 线性表 栈 队列 散列表 高级的 广义表 多维数组 文件 ,线性结构分类,按访问方式划分 直接访问型(direct access) 顺序访问型( sequential access) 目录索引型(directory access),线性结构分类,按操作划分 线性表 所有表目都是同一类

3、型结点的线性表 不限制操作形式 根据存储的不同分为：顺序表，链表 栈(LIFO, Last In First Out) 插入和删除操作都限制在表的同一端进行 队列(FIFO, First In First Out) 插入操作在表的一端， 删除操作在另一端,2.1 线性表 (linear list),三个方面 线性表的逻辑结构 线性表的存储结构 线性表运算分类,线性表的逻辑结构,线性表： 由称为元素（element）的数据项组成的一种有限且有序的序列，这些元素也可称为结点或表目 二元组(K , r) ： 由结点集K，以及定义在结点集K上的线性关系 r 所组成的线性结构 线性表所包含的结点个数称为

4、线性表的长度，它是线性表的一个重要参数；长度为0的线性表称为空表； 线性表的关系 r，简称前驱/后继关系，具有反对称性和传递性,线性表逻辑结构,主要属性包括： 线性表的长度 表头(head) 表尾 (tail) 当前位置(current position),线性表的存储结构,定长的一维数组结构 又称为向量型的顺序存储结构 变长的线性表存储结构 链接式存储结构 串结构、动态数组、以及顺序文件,线性表的存储结构,顺序表 按索引值从小到大存放在一片相邻的连续区域 紧凑结构，存储密度为1 链表 单链表 双链表 循环链表,线性表运算分类,创建线性表的一个实例list(-) 清除线性表（即析构函数）lis

5、t() 获取有关当前线性表的信息 访问线性表并改变线性表的内容或结构 线性表的辅助性管理操作,线性表的运算,建立线性表 清除线性表 插入一个新元素 删除某个元素 修改某个元素 排序 检索,线性表类模板,template class List void clear(); / 置空线性表 bool isEmpty(); / 线性表为空时，返回true bool append(const T value); / 在表尾添加一个元素value，表的长度增1 bool insert(const int p, const T value); / 在位置p上插入一个元素value，表的长度增1 bool d

6、elete(const int p); / 删除位置p上的元素，表的长度减 1 bool getPos(int ,2.2 顺序表（array-based list）,采用定长的一维数组存储结构 也称向量,主要特性:,元素的类型相同 元素顺序地存储在连续存储空间中， 每一个元素有唯一的索引值 使用常数作为向量长度,顺序表,数组存储 读写其元素很方便 ，通过下标即可指定位置 只要确定了首地址，线性表中任意数据元素都可以随机存取。地址计算如下所示： loc(ki) = loc(k0) + c* i c = sizeof(ELEM),顺序表,顺序表类定义,class arrList : public

7、List / 顺序表，向量 private: / 线性表的取值类型和取值空间 T *aList ; / 私有变量，存储顺序表的实例 int maxSize; / 私有变量，顺序表实例的最大长度 int curLen; / 私有变量，顺序表实例的当前长度 int position; / 私有变量，当前处理位置 public: / 顺序表的运算集 arrList(const int size) / 创建一个新的顺序表，参数为表实例的最大长度 maxSize = size; aList = new TmaxSize; curLen = position = 0; arrList() / 析构函数，用

8、于消除该表实例 delete aList; void clear() / 将顺序表存储的内容清除，成为空表 delete aList; curLen = position = 0; aList = new TmaxSize; int length(); / 返回此顺序表的当前实际长度 bool append(const T value); / 在表尾添加一个元素value，表的长度增1 bool insert(const int p, const T value); / 在位置p上插入一个元素value，表的长度增1 bool delete(const int p); / 删除位置p上的元素，

9、表的长度减 1 bool setValue(const int p, const T value); / 用value修改位置p的元素值 bool getValue(const int p, T,顺序表上的运算,重点讨论 插入元素运算 bool insert(const int p, const T value); 删除元素运算 bool delete(const int p); 其他运算请大家思考,position,顺序表的插入图示,position,position,插入算法,/ 设元素的类型为T， aList是存储顺序表的数组， maxSize是其最大长度； / p为新元素value的插

10、入位置，插入成功则返回true， 否则返回false template bool arrList : insert (const int p, const T value) int i; if (curLen = maxSize) / 检查顺序表是否溢出 cout curLen) / 检查插入位置是否合法 cout p; i-) aListi = aListi-1; / 从表尾curLen -1起往右移动直到p aListp = value; / 位置p处插入新元素 curLen+; / 表的实际长度增1 return true; ,插入算法的执行时间,插入操作的主要代价体现在表中元素的移动,

11、在位置i插入元素，需移动n-i 个元素 元素总个数为k，假设各个位置插入的概率相等， 为p1/k 平均移动元素次数为,总时间开销估计为O(k),position,顺序表的删除图示,position,删除算法,/ 设元素的类型为T；aList是存储顺序表的数组； p为即将删除元素的位置 / 删除成功则返回true，否则返回false template / 顺序表的元素类型为T bool arrList : delete(const int p) int i; if (curLen curLen-1) / 检查删除位置是否合法 cout “deletion is illegaln“endl; re

12、turn false ; for (i = p; i curLen-1; i+) aListi = aListi+1; / 从位置p开始每个元素左移直到curLen curLen-; / 表的实际长度减1 return true; ,删除算法时间代价,与插入操作相似，主要的代价在于元素的移动 等概率情况下平均时间代价为O(k),顺序表各运算的算法分析,插入和删除操作的主要代价体现在表中元素的移动 插入：移动 n-i 删除：移动 n-i-1个 若在下标为 i 的位置上插入和删除元素的概率分别是pi和pi， 则插入时的平均移动次数是： n Mi = (n-i)pi； i=0 删除的平均移动次数是：

13、 n-1 Md = (n-i-1)pi i=0,算法分析,如果在顺序表中每个位置上插入和删除元素的概率相同，即： pi=1/(n+1), pi=1/n,采用大O表示法，则时间代价为O(n),顺序表的优缺点,优点 不需要附加空间 随机存取任一个元素（根据下标） 缺点 很难估计所需空间的大小 开始就要分配足够大的一片连续的内存空间 更新操作代价大,2.3 链表(Linked List),通过指针来链接结点的存储方式。 利用指针来表示数据元素之间的逻辑关系 逻辑上相邻的元素在物理位置上不要求也相邻 按照需要为表中新的元素动态地分配存储空间，动态改变长度 根据链接方式和指针多寡 单链表 双链表 循环链

14、表,链表的运算,检索： 在链表中查找满足某种条件的元素 插入 ： 在链表的适当位置插入一个元素 删除： 从链表中删除一个指定元素,单链表（singly linked list）,通过指针把它的一串存储结点链接成一个链 存储结点由两部分组成： 数据字段 + 指针字段（后继地址）,单链表的存储结构,单链表的结点类型,template class Link public: T data; / 用于保存结点元素的内容 Link * next; / 指向后继结点的指针 Link(const T info, const Link* nextValue = NULL) data = info; next =

15、 nextValue; Link(const Link* nextValue) next = nextValue; ;,单链表的定义,template class lnkList : public List private: Link * head, *tail; / 单链表的头、尾指针 Link *setPos(const int p); / 返回线性表指向第p个元素的指针值 public: lnkList(int s); / 构造函数 lnkList(); / 析构函数 bool isEmpty(); / 判断链表是否为空 void clear(); / 将链表存储的内容清除，成为空表 int length(); / 返回此顺序表的当前实际长度 bool append(cosnt T value); / 在表尾添加一个元素value，表的长度增1 bool insert(cosnt int p, cosnt T value);/ 在位置p上插入一个元素value，表的长度增1 bool delete(cosnt int p); / 删除位置p上的元素，表的长度减 1 bool getValue(cosnt int p, T / 查找值为value的元素，返回第1次出现的位置 ,查找单链表中第i个结点,/ 函数返回值是找到的结