《计算机应用基础课件》1.2线性表

第1章数据结构 1 1基本数据结构与算法1 2线性表1 3栈和队列1 4树和二叉树1 5查找1 6内部排序 姓名学号成绩班级李红976105995机97 6 10 65 865 1 2线性表 1 线性表的定义1 定义 具有相同数据类型的n n 0 个数据元素组成的有限序列 是最简单 最常用的数据结构 2 表示 L a0 a2 a3 ai 1 ai ai 1 an 1 其中 n为线性表长度 n 0称为空表 表中相邻元素之间存在着顺序关系 a0 表头元素 an 1 表尾元素 ai 1称为ai的直接前驱 ai 1称为ai的直接后继 表头 表尾 1 2线性表 1 线性表的定义1 定义 具有相同数据类型的n n 0 个数据元素组成的有限序列 是最简单 最常用的数据结构 2 表示 L a0 a2 a3 ai 1 ai ai 1 an 1 3 线性结构特点 1 有且只有一个根结点a0 无前驱 2 有且只有一个终端结点an 1 无后继 3 其他结点有且只有一个直接前驱和一个直接后继 1 2线性表 1 线性表的定义1 定义 具有相同数据类型的n n 0 个数据元素组成的有限序列 是最简单 最常用的数据结构 2 表示 3 线性结构特点 4 线性表的分类 1 简单线性表 数据元素是简单项 数字 字母 季节名等 如 12 34 4 67 8 2 复杂线性表 数据元素由若干个数据项组成 此时数据元素称为记录或结点 如学生成绩表 L a0 a2 a3 ai 1 ai ai 1 an 1 学生健康情况登记表如下 1 顺序表基本概念 1 2 2线性表的顺序存储结构 1 顺序存储结构 用一组地址连续的存储空间依次存放线性表的各元素 顺序表 采用顺序存储结构的线性表称为顺序表 一维数组 表中的所有元素所占存储空间连续表中各元素在存储空间中按逻辑顺序存放 顺序存储结构特点 1 2线性表 1 顺序表基本概念 4 2 2线性表的顺序存储结构 1 顺序存储结构 2 第i个元素地址 4 2线性表 其中 m 每个元素占m个存储单元Loc a0 第一个元素地址 基址 b b m b i m b n m 存储地址 存储状态 空闲 数据元素在线性表中的位序 12 n i 从存取方式看 线性表的顺序存储结构是可以随机存储的存储结构 1 顺序表基本概念 1 2 2线性表的顺序存储结构 1 顺序存储结构 2 第i个元素地址 1 2线性表 2 顺序表的基本运算存取 访问线性表的第i个元素 使用或改变数据元素的值 查找 在线性表中查找满足某种条件的数据元素 插入 在线性表的第i个元素之前 插入一个同类型的元素 删除 删除线性表中第i个元素 求表长 求出线性表中元素的个数 置空表 建立一个空表 清除表 将已有线性表变为空表 即删除表中所有元素 1 顺序表基本概念 1 2 2线性表的顺序存储结构 1 顺序存储结构 2 第i个元素地址 1 2线性表 2 顺序表的基本运算 插入和删除 1 顺序表的插入运算 在线性表的第i个元素之前插入一个新的元素 先移动 后插入 x ai 先移动后插入 x 步骤 1 将ai an顺序向后移动 为新元素让出位置 2 将x置入 空出 的第i个位置 举例 在第4个和第5个元素之间插入元素91 21 91 插入程序举例 在8个数中任意位置插入一个数 defineN8main inta N 1 12 34 45 6 78 9 10 91 i j x printf inputthelocationtobeinserted scanf d d for j i 1 j N 1 j a j 1 a j for j N 1 j i 1 j a j 1 a j 在第i个位置上作插入x 则需将第i个至第n个元素移动 即共需移动 n i 1 个元素 插入运算时间性能分析 插入运算 时间主要消耗在数据移动上 在长度为n的线性表中插入一个元素 则平均移动元素次数 期望值 pi 在第i个位置上作插入的概率 等差数列求和公式 首项 末项 项数 2 n i 1 线性表 a0 a1 a2 平局移动元素个数 3 2 1 0 1 5 在一线性表 a0 a1 a2 中插入任意一数i 求平局移动元素次数 i移动次数 n i 1 1 插入到第个数a0前 32 插入到第2个数a1前 23 插入到第3个数a2前 1 插入到第3个数a2后 0 1 顺序表基本概念 1 2 2线性表的顺序存储结构 1 顺序存储结构 2 第i个元素地址 1 2线性表 2 顺序表的基本运算 插入和删除 2 顺序表删除运算 定义 指将表中第i个元素从线性表中去掉 原表长为n a0 a1 ai 1 ai ai 1 an 1 新表长为n 1 a0 a1 ai 1 ai 1 an 1 步骤 1 将ai 1 an 1 顺序向前移动 2 表长减一 举例 删除第五个元素21 时间性能分析 时间消耗与插入运算相同 平均移动元素次数 qi 在第i个位置上作插入的概率 设qi 1 n共需移动 n i 个元素 67 i移动次数 n i 1 删除第1个数a0 22 删除第2个数a1 13 删除第3个数a2 0 线性表 a0 a1 a2 平局移动元素个数 1 3 2 1 0 1 在一线性表 a0 a1 a2 中删除任意一数i 求平局移动元素次数 作业 有一数组 存储十个数 编程序删除其中任意一个数 1 顺序表基本概念 3 顺序表优点和缺点 优点 逻辑上相邻元素存储位置也相邻 无需增加额外存储空间可方便随机存取表中任一元素 缺点 插入和删除运算不方便 必须移动大量结点 效率较低不适合元素经常变动的大的线性表 1 2 2线性表的顺序存储结构 1 2线性表 2 顺序表的基本运算 链式存储结构特点 1 2 3线性表的链式存储结构 存储空间可以不连续 不要求逻辑上相邻的元素在物理位置上也相邻 数据元素间逻辑关系由指针域确定 1 2线性表 即链表存储结构是一种动态数据结构 其特点是它包含的据对象的个数及其相互关系可以按需要改变 存储空间是程序根据需要在程序运行过程中向系统申请获得 链表也不要求逻辑上相邻的元素在物理位置上也相邻 它没有顺序存储结构所具有的弱点 name sum next 结构体元素 结构体元素的地址 结构体元素的成员是地址型数据 structstudent charname 10 intsum structstudent next p structstudent p strcpy p name zhang p sum 335 p next head p1 p2 p3 有四个结构体元素 head 有四个结构体元素 head 3 尾结点的指针域置为 NULL 空 作为链表结束的标志 1 头指针变量head 指向链表的首结点 2 每个结点由2个域组成 1 数据域 存储结点本身的信息 2 指针域 指向后继结点的指针 structstudent charname 10 intsum structstudent next 链式存储结构特点 2 线性链表 定义 线性表的链式存储结构称为线性链表 1 2 3线性表的链式存储结构 数据域 一部分存放数据元素值指针域 存放指针 用于指向该结点的前一个结点或后一个结点 线性链表中结点组成 分类 单链表 循环单链表 双向链表 1 2线性表 其单链表示意图如下 有一线性表 bat cat eat fat hat jat lat mat 110 130135 160头指针head165170 200205 简化为 链尾 略 单链表是由表头唯一确定 因此单链表可以用头指针的名字来命名 例如 若头指针名是head 则把链表称为表head head 用C语言描述的单链表如下 structnode charname 20 structnode next structnode head typedefstructnode charname 20 structnode next LinkList LinkList head 新的类型名代换旧的类型名 也就是说 LinkList等价与structnode 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 定义 由n个结点链接 且每个结点中只包含一个指针域的链表 例 线性单链表 A B C D E F 逻辑状态 其中 head称为单链表的头指针 指向表中的第一个结点 物理状态 头指针存储地址数据域指针域 1713192531 单链表存取 必须从头指针开始进行 依次顺着指针向链尾方向扫描 找到各个元素 因此说线性表的链式存储结构是一种顺序存储的存储结构 head head head 带头节点的单链表 编程 创建带头节点的单链表 程序算法 1 定义三个结构体类型的指针变量head p s 2 利用malloc函数开辟头结点 由head p共同来指向 3 再利用malloc函数开辟相应的内存空间 由s来指向 4 由键盘输入数据 赋给s所指向的内存空间 5 p next s 6 p s 7 回到第 3 步 程序算法 1 定义三个结构体类型的指针变量head p s 2 利用malloc函数开辟头结点 由head p共同来指向 3 再利用malloc函数开辟相应的内存空间 由s来指向 4 由键盘输入数据 赋给s所指向的内存空间 5 p next s 6 p s 7 回到第 3 步 head p strutcnode malloc sizeof structnode head p 对带头结点的复杂链表的基本操作 创建 程序算法 1 定义三个结构体类型的指针变量head p s 2 利用malloc函数开辟头结点 由head p共同来指向 3 再利用malloc函数开辟相应的内存空间 由s来指向 4 由键盘输入数据 赋给s所指向的内存空间 5 p next s 6 p s 7 回到第 3 步 A s data getchar s p 对带头结点的复杂链表的基本操作 创建 head p 程序算法 1 定义三个结构体类型的指针变量head p s 2 利用malloc函数开辟头结点 由head p共同来指向 3 再利用malloc函数开辟相应的内存空间 由s来指向 4 由键盘输入数据 赋给s所指向的内存空间 5 p next s 6 p s 7 回到第 3 步 s p 对带头结点的复杂链表的基本操作 创建 A s head p B head head 带头节点的单链表 typedefstructnode chardata structnode next Linklist Linklist head p s charch head Linklist malloc sizeof Linklist printf inputletterstocreatealist n while ch getchar n s Linklist malloc sizeof Linklist s data ch p next s p s p next NULL 编程 创建带头节点的单链表 带头节点的单链表 typedefstructnode chardata structnode next Linklist Linklist head p s charch head Linklist malloc sizeof Linklist printf inputletterstocreatealist n p head while ch getchar n s Linklist malloc sizeof Linklist s data ch p next s p s p next NULL 2000 B data next structnode chardata structnode next Linklist Linklist head p s charch head Linklist malloc sizeof Linklist printf inputletterstocreatealist n p head while ch getchar n s Linklist malloc sizeof Linklist s data ch p next s p s p next NULL A head p 用户输入为 ABC s p typedef structnode chardata structnode next Linklist Linklist head p s charch head Linklist malloc sizeof Linklist printf inputletterstocreatealist n p head while ch getchar n s Linklist malloc sizeof Linklist s data ch p next s p s p next NULL A head 用户输入为 ABC s p s B p typedef structnode chardata structnode next Linklist Linklist head p s charch head Linklist malloc sizeof Linklist printf inputletterstocreatealist n p head while ch getchar n s Linklist malloc sizeof Linklist s data ch p next s p s p next NULL A head 用户输入为 ABC s B p s C p NULL typedef 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 1 单链表插入 增加新结点 修改链接指针 后插结点 在指针p所指结点之后插入一个指针s所指的结点修改p和s所指结点的指针域的指针即可 插入步骤 修改s指针域 使其指向p结点的后继结点 s next p next p B X s 修改p指针域 使其指向新结点s p next s 考虑上述两步骤若颠倒会怎样 插入步骤 修改s指针域 使其指向p结点的后继结点 s next p next p B X s 修改p指针域 使其指向新结点s p next s 考虑上述两步骤若颠倒会怎样 后面的结点都将从链表中脱离 它们占用着内存空间 程序却找不到它们了 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 2 单链表删除 不需要移动元素 仅修改指针链接 删除结点 删除p指向的结点只修改p 被删除结点 的前驱结点的指针域即可 删除步骤 修改q结点指针域q next p next 删除后 q p free p 先找到p的前驱结点q q next q next next 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 4 循环链表 特点 表中最后一个结点的指针域指向头结点 整个链表首尾相连形成一个环 带头节点的循环链表 优点 从表中任一结点出发均可找到表中其它结点 对带头结点的单循环链表head为空的判定条件是head next head 带头结点的空循环链表 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 4 循环链表 5 双向链表 定义 在双向链表中 每个结点有两个指针域 next指向后继结点 prior指向前趋结点 作用 可以方便地沿向前或向后两个方向查找 克服单链表中每个结点只能找到它的后继结点 不能找到前驱结点 若要找前驱结点 必须从头指针开始重新查找的不足 next prior 对指向双向链表任一结点的指针p 有下面的关系 p next priou p priou next p p next prious prious next 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 4 循环链表 5 双向链表 1 插入结点 在p指针所指的结点后插入一个结点q 只需要修改p q结点的prior和next域即可 p c b a x q p p结点作为q结点的前驱 q prior p p结点的后继作为q结点的后继 q next p next q结点作为p结点的后继结点的前驱结点 p next prior q q结点作为p结点的后继 p next q p的后继指向新结点q 确定新结点q的前驱和后继 链式存储结构特点 2 线性链表 1 2 3线性表的链式存储结构 1 2线性表 3 单链表 4 循环链表 5 双向链表 p 2 删除结点 删除P指针所指结点 只需修改P指针的前驱和后继结点的next prior域即可 p p prior next p next p next prior p prior free p c b a 习题讲解 1 线性表的顺序存储结构和线性表的链式存储结构分别是 A 顺序存取的存储结构 顺序存取的存储结构B 随机存取的存储结构 顺序存取的存储结构C 随机存取的存储结构 随机存取的存储结构D 任意存取的存储结构 任意存取的存储结构2 在单链表中 增加头结点的目的是 A 方便运算的实现B 使单链表至少有一个结点C 标识表结点中首结点的位置D 说明单链表是线性表的链式存储实现 3用链表表示线性表的优点是 A 便于插入和删除操作B 数据元素的物理顺序与逻辑顺序相同C 花费的存储空间较顺序存储少D 便于随机存取4 某线性表采用顺序存储结构 每个元素占4个存储单元 首地址为200 则第12个元素的存储地址是 A 248B 247C 246D 244 5 下列对于线性链表的描述中正确的是 05 4月 A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 6 线性表是 A 一个有限序列 可以为空B 一个有限序列 不能为空C 一个无限序列 可以为空D 一个无限序列 不能为空 7 在一个长度为n的线性表中 删除值为x的元素时需要比较元素和移动元素的总次数为 A n 1 2B n 2C nD n 1 详见 计算机基础综合实训教程 P175 8 一个长度为n的顺序存储的线性表中 向第i个元素 1 i n 1 位置插入一个新元素时 需要从后面向前依次后移 个元素 A n iB n i 1C n i 1D i 9 设单链表中指针p指向结点ai 若要删除ai之后的结点 若存在 则需修改指针的操作为 A p next p next nextB p p nextC p p next nextD next p 10 设单链表中指针p指向结点ai 指针q指向将要插入的新结点x 则当x插在链表中两个数据元素ai和ai 1之间时 只要先修改q next p next 后修改 即可 A p next qB p next p next nextC p next q nextD q next null 11 在一个单链表中 若要在p所指向的结点之后插入一个新结点 则需要相继修改 个指针域的值 A 1B 2C 3D 4 12 不带头结点的单链表L为空的判定条件是 A L NULLB L next NULLC L next LD L NULL13 带头结点的单链表L为空的判定条件是 A L NULLB L next NULLC L next LD L NULL14 在一个带有头结点的双向循环链表中 若要在p所指向的结点之前插入一个新结点 则需要相继修改 个指针域的值 A 2B 3C 4D 615 在一个带有头结点的双向循环链表中 若要在p所指向的结点之后插入一个q指针所指向的结点 则需要对q next赋值为 A p priorB p nextC p next nextD p prior prior16 线性表采用链式存储时 其地址 A 必须是连续的B 一定是不连续的C 部分地址必须是连续的D 连续与否均可以 2 在一个单链表中删除指针p所指向结点时 应执行一下操作 q p next p data p next data p next free q 填空题1 数据结构分为逻辑结构和存储结构 循环队列属于 结构 05 9月 存储结构 p next next p q B C 3 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时 首先把 的值赋给q next 然后把 的值赋给p next p next q 4 假定指向单链表中第一个结点的表头指针为head 则向该单链表的表头插入指针p所指向的新结点时 首先执行 赋值操作 然后执行 赋值操作 p next head head p head p 5 在一个单链表中删除指针p所指向结点的后继结点时 需要把 的值赋给p next指针域 p next next 6 在 链表中 既可以通过设定一个头指针也可以通过设定一个尾指针来确定它 即通过头指针或尾指针可以访问到该链表中的每个结点 循环 7 在一个带有头结点的双向循环链表中的p所指向的结点之前插入一个指针s所指向结点时 可执行如下操作 1 s prior 2 p prior next s 3 s next 4 p prior p prior p s 8 线性表的长度是