数据结构-02线性表要点.ppt

线性表结构 本章主要内容 2.1 线性表的基本概念 线性表的逻辑结构特点 2.1.1 线性表举例 例2－2：学生成绩登记表 2.2 线性表的顺序存储结构 2.2.1 顺序表中元素存储位置的计算 2.2.2 顺序表存储结构的C语言描述 2.2.3 顺序表的操作 添加插入 添加插入 随机插入 随机插入 删除算法 删除算法 定位算法 合并算法 合并算法 2.2.4 顺序存储结构小结 特点： 空间利用率高，几乎不需要额外的空间开销 数据的逻辑结构与物理结构完全一致 结点地址计算的时间与线性表的规模大小无关 可以随机存取任一元素 缺点 顺序表的存储空间是静态分配，必须有足够大小的成片存储空间，建表时存储空间大小有时无法确切估计 插入操作和删除操作在大多情况下引起大量结点的频繁移动，降低了算法的时间效率 2.3.1单链表 对上述结构的改进 需要澄清的几个概念 2.3.2单链表的操作 创建 头插入法 尾插入法 按号定位 按值定位 求表长 插入 删除 合并 2.3.3循环链表和双向链表 改进的循环链表 双向链表 双向循环链表 双向链表的对称性 双向链表操作演示 链式存储结构小结 2.4线性表结构的应用 2.4.1数据查重 实例演示 有序表查重 2.4.2基于线性表排序 直接插入排序 实例演示 改进 简单交换排序 简单交换排序过程实例 简单选择排序 简单选择排序过程实例 2.4.3基于线性表的查找 顺序查找 改进的顺序查找 快速顺序查找 单链表中，为找第 i 个数据元素，必须从单链表的头指针出发，沿着链指针方向对结点顺序逐个扫描、计数；当计数值等于i时，定位完成。 令指针 p 始终指向线性表中第 j 个数据元素 例如： 算法有哪些信誉好的足球投注网站表Q，找出第i结点的指针输出 21 18 30 75 42 56 ∧ p p p j 1 2 3 Q i=3 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。 程序见书中P××。 算法有哪些信誉好的足球投注网站表Q，找出结点数据与x值相等的结点，并输出该结点指针 当遇到结点数据与x 值相等时，或比较完所有结点时，即结束扫描。 因此，查找值为x结点的基本操作为：移动指针，比较 p-data和 x 。 21 18 30 75 42 56 ∧ Q x=30 p p p p p p p p p p p p-data==x 返回p x=53 p==NULL 返回p 例如： 程序见书中P××。 只要设一个移动指针沿着链指针方向对结点顺序逐个扫描、计数；当扫描完所有结点，计数完成。 例如：p为移动指针 ，j为计数器 统计单链表L中结点的个数，并输出 因此，求表长的基本操作为：移动指针，计数器自加 。 程序见书中P××。 21 18 30 75 42 56 ∧ p p p j 1 2 3 Q p p p 4 5 6 next(p)=∧,结束扫描，返回j的值 x s s ?? next = p ?? next; p ?? next = s; p ai ai –1 插入该新结点，使之成为单链表Q的第i个结点 1 首先找到 ai -1 的存储位置 p 2 生成一个数据域为 x 的新结点 3 插入新结点：①、结点 ai -1的指针域指向新结点 ②、新结点的指针域指向结点 ai 程序见书中P××。 把第i个结点从单链表Q中删除掉 1 首先找到 ai -1 的存储位置 p 2 令 p－next 指向 ai ＋1 3 释放结点ai的空间 p ?? next = p ?? next ?? next; p ai –1 ai ai+1 程序见书中P××。 操作把A、B两单链表进行合并，A在前B在后，并把合并结果仍存储在A中 分析： 对链表来说，“插入”和“删除”仅需修改指针即可完成，并且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变，则算法的实际操作为： 找到A的终点，修改A的终点指针，即将 (b1, b2, …, bn) 链接到am之后； A a1 a2 am … ^ b1 b2 bn ^ … B A a1 a2 am … ^ b1 b2 bn ^ … B P P P 程序见书中P××。 d1 dn … 非空环链表 (使用头指针) H 循环链表： 是一种首尾相接的链表 (即：把终结点指针域的值为“空”改为指向头结点，整个链表形成一个环),简称环链表 创建空表时，其头结点指针域的指针值就是头指针 空表 (使用头指针) H ∧ 特点：从表的任意结点出发，都可以通过后移指针的方法找到表中所有结点 没有 ∧ 指针如何判别终 结点？