C和数据结构.pptVIP

数据结构（二） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 内容提要 线性表的定义 线性表的实现 — 顺序存储结构 线性表的实现 — 链式存储结构 单向链表 双向链表 线性表 线性表 n个结点（数据元素）的有限序列。 始结点唯一，即存在一个结点没有前趋结点。 终结点唯一，即存在一个结点没有后继结点。 除始结点外，其它结点均只有一个前趋结点。 除终结点外，其它结点均只有一个后继结点。 线性表举例 简单数据元素 (6, 17, 28, 50, 92, 188) (A, B, D, E, C) 复杂数据元素 学生成绩登记表 线性表 线性表中的各个数据元素具有相同（或相容）的类型。 线性表中的元素个数称为线性表的长度。 长度为0的线性表称为空表。 线性表可视为容纳某类对象的容器。 线性表中每个元素有一个表明其位置的编号，始结点编号为0，始结点的直接后继结点编号为1，…，终结点的编号为n-1。（线性表长度为n） 线性表 和线性表有关的操作： 构造一个空表 判断线性表是否空表 判断线性表是否已满 返回线性表的长度 将一个线性表清空 在线性表的第i个位置插入一个元素 删除线性表中第i个元素 读取线性表中第i个元素 把线性表中的第i个元素替换为另外一个元素 顺序遍历线性表中的元素，并对每个元素进行特定的处理 抽象数据类型定义 线性表操作 线性表操作 线性表的使用 线性表的实现 —顺序存储 顺序映象以存储位置先后表示元素间的前趋和后继关系。 用一组地址连续的存储单元依次存放线性表中的数据元素。 线性表的实现 —顺序存储 若每个元素占用 l 个存储单元，用其中第一个单元的地址作为元素的存储位置。则元素 ai 的存储位置可以表示为LOC(ai)。 线性表中第 i+1 个元素和第 i 个元素的存储位置间满足下列关系:LOC(ai+1) = LOC(ai) + l 线性表中第 i个元素的存储位置为：LOC(ai) = LOC(a0) + i * l其中LOC(a0)是线性表的基地址。 C++中，数组元素占据连续存储单元，可用来实现顺序存储的线性表。 线性表的实现 —顺序存储 线性表的实现 —顺序存储 线性表的实现 —顺序存储 xx 线性表的实现 —顺序存储 元素插入操作的时间复杂度分析 假设在第 i 个位置插入元素的概率为pi，则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为： 假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为： 在线性表中插入一个元素平均需要移动一半元素，时间复杂度是线性阶，即O(n)。 线性表的实现 —顺序存储 在顺序实现中：☆ insert 和 remove 的时间复杂度是O(n)。☆ List、clear、empty、full、size、replace和retrieve的时间复杂度是O(c)。 优点： ☆ 随机存取（ retrieve ） 缺点 ☆ 插入（ insert ）、删除（ remove ）需移动大量元素 ☆ 需要预先估计所需最大空间 ☆ 表的容量不能动态扩充 思考：如何实现容量可动态增长的顺序存储的线性表？ 线性表的实现 —单链表 用一组地址任意的存储单元存放线性表中的数据元素。用附加的指针指示元素的前趋和后继关系。 为了表示数据元素ai 与其直接后继元素ai+1之间的逻辑关系，对数据元素ai 而言，除存储其本身的信息外，还需要存储指示其后继的指针（地址）信息。这两部分合起来通常称为结点。结点 ＝ 元素 ＋ 指针 n个结点通过指针链接形成一个链表，即为线性表的链式存储结构。由于每个结点中包含一个指针域，所以称为单链表。 线性表的实现 —单链表 整个链表的存取必须从头指针开始进行，头指针指示链表中的第一个结点的存储位置。 最后一个元素由于没有后继结点，最后一个结点的指针应为空（NULL）。 在单链表中，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个元素，其存储的物理位置不必紧邻。 在线性表的顺序存储结构中，逻辑上相邻的元素物理位置紧邻，因而任何一个元素的存储位置都可以从线性表的起始位置计算得到，因而可实现随机存取。 线性表的实现 —单链表 在单链表中，任何两个元素的存储位置之间没有固定联系。每个元素的存储位置只能通过读取其前趋结点的指针域得到。 在单链表中，读取第i个数据元素必须从头指针出发寻找，单链表是非随机存取的存储结构。 线性表的实现 —单链表 在C++中定义单链表结点 对于线性表的客户程序而言，结点结构应该是不可见的，应把结点结构定义成链表类的私有嵌套结构。 线性表的实现 —单链表 线性表的实现 —单链表 为了实现单链表的其它操作，定义一个支持函数set_position，该