Java版数据结构(程序员必须看).ppt

数据结构 计算机科学与技术学院张宏 第一章绪论 1 1什么是数据结构1 2有关概念和术语1 3算法和算法分析1 3 1算法1 3 2算法设计的要求1 3 3算法效率的度量1 3 4算法的存储空间的需求 第一章绪论 计算机学科一直处于高速发展中 而且这种发展速度还会持续 计算机科学已经难以完全覆盖学科新的发展 因此扩展后的学科称为计算学科 包括 计算机科学 计算机工程 软件工程 信息系统 关键问题 利用计算机进行信息表示和处理的涉及 信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率 随着计算机的普及 信息量的增加 信息范围的拓宽 使许多系统程序和应用程序的规模很大 结构又相当复杂 因此 为了编写出一个 好 的程序 必须分析待处理的对象的特征及各对象之间存在的关系 这就是数据结构这门课所要研究的问题 1 1什么是数据结构众所周知 计算机的程序是对信息进行处理 在大多数情况下 这些信息并不是没有组织的 信息 数据 之间往往具有重要的结构关系 这就是数据结构的内容 什么是数据结构呢 例子 例1 电话号码查询系统设有一个电话号码薄 它记录了N个人的名字和其相应的电话号码 假定按如下形式安排 a1 b1 a2 b2 an bn 其中 ai bi i 1 2 n 分别表示某人的名字和对应的电话号码 要求设计一个算法 当给定任何一个人的名字时 该算法能够打印出此人的电话号码 如果该电话簿中根本就没有这个人 则该算法也能够报告没有这个人的信息 数据结构含义 就是研究数据的逻辑结构和物理结构以及它们之间相互关系 并对这种结构定义相应的运算 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 所有能被输入到计算机中 且能被计算机处理的符号的集合 数据 是计算机操作的对象的总称 是计算机处理的信息的某种特定的符号表示形式 1 2有关概念和术语 是数据 集合 中的一个 个体 数据元素 是数据结构中讨论的基本单位 数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构 通常分为四类基本结构 一 集合结构中的数据元素除了同属于一种类型外 别无其它关系 二 线性结构结构中的数据元素之间存在一对一的关系 三 树型结构结构中的数据元素之间存在一对多的关系 四 图状结构或网状结构结构中的数据元素之间存在多对多的关系 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 数据在计算机中的表示称为数据的物理结构 又称为存储结构 数据对象可以是有限的 也可以是无限的 数据结构不同于数据类型 也不同于数据对象 它不仅要描述数据类型的数据对象 而且要描述数据对象各元素之间的相互关系 数据类型 在一种程序设计语言中 变量所具有的数据种类 例1 在FORTRAN语言中 变量的数据类型有整型 实型 和复数型例2 在C 语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义数据对象 某种数据类型元素的集合 例3 整数的数据对象是 3 2 1 0 1 2 3 英文字符类型的数据对象是 A B C D E F 1 3算法和算法分析1 3 1算法 是对特定问题求解步骤的一种描述 是指令的有限序列 其中每一条指令表示一个或多个操作 算法具有以下五个特性 1 有穷性一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 2 确定性算法中每一条指令必须有确切的含义 不存在二义性 3 可行性一个算法是可行的 即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 4 输入一个算法有零个或多个输入 这些输入取自于某个特定的对象集合 5 输出一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 1 3 2算法设计的要求 设计算法时 通常应考虑达到以下目标 1 正确性2 可读性3 健壮性4 高效率与低存储量需求 1 正确性 首先 算法应当满足以特定的 规格说明 方式给出的需求 其次 对算法是否 正确 的理解可以有以下四个层次 a 程序中不含语法错误 b 程序对于几组输入数据能够得出满足要求的结果 c 程序对于精心选择的 典型 苛刻且带有刁难性的几组输入数据能够得出满足要求的结果 通常以第c层意义的正确性作为衡量一个算法是否合格的标准 d 程序对于一切合法的输入数据都能得出满足要求的结果 2 可读性 算法主要是为了人的阅读与交流 其次才是为计算机执行 因此算法应该易于人的理解 另一方面 晦涩难读的程序易于隐藏较多错误而难以调试 3 健壮性 当输入的数据非法时 算法应当恰当地作出反映或进行相应处理 而不是产生莫名奇妙的输出结果 并且 处理出错的方法不应是中断程序的执行 而应是返回一个表示错误或错误性质的值 以便在更高的抽象层次上进行处理 4 高效率与低存储量需求 通常 效率指的是算法执行时间 存储量指的是算法执行过程中所需的最大存储空间 两者都与问题的规模有关 1 3 3算法效率的度量 通常有两种衡量算法效率的方法 事后统计法 事前分析估算法 缺点 1 必须执行程序2 其它因素掩盖算法本质 和算法执行时间相关的因素 1 算法选用的策略 2 问题的规模 3 编写程序的语言 4 编译程序产生的机器代码的质量 5 计算机执行指令的速度 一个特定算法的 运行工作量 的大小 只依赖于问题的规模 通常用整数量n表示 或者说 它是问题规模的函数 假如 随着问题规模n的增长 算法执行时间的增长率和f n 的增长率相同 则可记作 T n O f n 称T n 为算法的 渐近 时间复杂度 如何估算算法的时间复杂度 算法 控制结构 原操作 固有数据类型的操作 算法的执行时间 原操作 i 的执行次数 原操作 i 的执行时间 算法的执行时间与原操作执行次数之和成正比 从算法中选取一种对于所研究的问题来说是基本操作的原操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 voidmult inta intb intc for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j for mult 基本操作 乘法操作 时间复杂度 O n3 例1 例 x s 0 将x自增看成是基本操作 则语句频度为1 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为1 其时间复杂度仍为 1 即常量阶 例 for i 1 i n i x s x 语句频度为 n其时间复杂度为 O n 即时间复杂度为线性阶 i 0 赋值 次 i 1 赋值2次 i 2 赋值3次 i n 1 赋值n次 1 2 3 n 1 n n 2 n2 2 n 2 例 for i 1 i n i for j 1 j n j x s x 语句频度为 n2其时间复杂度为 O n2 即时间复杂度为平方阶 例 for i 0 i n 1 i for j 0 j i j a i j 0 定义 如果f n 是正整数n的一个函数 若存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记作f n O g n 例 f x anxn an 1xn 1 a1x a0 其中an不等0 n为正整数 则f x O xn 证明 f x anxn an 1xn 1 a1x a0 anxn an 1xn 1 a1x a0 an xn an 1 xn 1 a1 x1 a0 x0 当x 1 n0 n为正整数时 xn 1 xn 所以 an xn an 1 xn 1 a1 x1 a0 x0 an xn an 1 xn a1 xn a0 xn an an 1 a1 a0 xn c xn 其中 n0 1 c an an 1 a1 a0 g n xn 一个算法时间为O 1 的算法 它的基本运算执行的次数是固定的 因此 总的时间由一个常数 即零次多项式 来限界 而一个时间为O n2 的算法则由一个二次多项式来限界 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 1 3 4算法的存储空间的需求 算法的空间复杂度定义为 表示随着问题规模n的增大 算法运行所需存储量的增长率与g n 的增长率相同 S n O g n 算法的存储量包括 1 输入数据所占空间 2 程序本身所占空间 3 辅助变量所占空间 若输入数据所占空间只取决于问题本身 和算法无关 则只需要分析除输入和程序之外的辅助变量所占额外空间 若所需额外空间相对于输入数据量来说是常数 则称此算法为原地工作 若所需存储量依赖于特定的输入 则通常按最坏情况考虑 注意 时间与空间往往是对矛盾 要综合考虑 最坏时间复杂性 例6 有的情况下 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 例如 voidbubble sort inta intn for i n 1 i 0 i for j 0 ja j 1 a j a j 1 时间 最好情况 0次最坏情况 每次都换 n2 空间 一个数据交换的辅助空间 算法原地工作 例7 递归程序的分析intfact intn if n 1 return1 elsereturnn fact n 1 f n c f n 1 c c f n 2 2c f n 2 n 1 c f 1 n 1 c c0 课时安排与考核 学分3 授课2 5 40课时 上机0 5 8 8课时 考核 平时成绩20 作业 课后与课堂 实验课程考试80 作业 计算时间复杂度sum 1 for i 0 sum n i sum i 2 设给定若干n值 比较两函数n2和50nlog2n的增长趋势 并确定在什么范围内 函数n2的值大于50nlog2n的值 第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示及相加 2 1线性表的逻辑结构线性表 由n n 0 个数据元素 结点 a1 a2 an组成的有限序列 其中数据元素的个数n定义为表的长度 当n 0时称为空表 常常将非空的线性表 n 0 记作 a1 a2 an 这里的数据元素ai 1 i n 只是一个抽象的符号 其具体含义在不同的情况下可以不同 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 神经衰弱 17 男 790634 张立立 健康 21 男 790633 刘建平 一般 20 女 790632 陈红 健康 18 男 790631 王小林 健康情况 年龄 性别 学号 姓名 例3 学生健康情况登记表如下 从以上例子可看出线性表的逻辑特征是 1 对非空的线性表 有且仅有一个开始结点a1 它没有直接前驱 而仅有一个直接后继a2 2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前驱an 1 3 其余的内部结点ai 2 i n 1 都有且仅有一个直接前驱ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 数据的运算是定义在逻辑结构上的 而运算的具体实现则是在存储结构上进行的 2 2线性表的顺序存储结构2 2 1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里 用这种方法存储的线性表简称顺序表 假设线性表的每个元素需占用m个存储单元 并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点 则线性表中第i 1个数据元素的存储位置Loc ai 1 和第i个数据元素的存储位置Loc ai 之间满足下列关系 Loc ai 1 Loc ai m 线性表的第i个数据元素ai的存储位置为 Loc a1 i 1个元素 Loc ai i 1 m Loc a1 Loc a1 m i m 由于Loc a1 和m都是已知的所以 V0 Loc a1 mLoc ai V0 i m 由于在高级语言中的一维数组也是采用顺序存储表示 故可以用数组类型来描述顺序表 又因为除了用数组来存储线性表的元素之外 顺序表还应该用一个变量来表示线性表的长度属性 利用C 语言的结构类型来定义顺序表类型 defineListSize100 表容量typedefintDataType 以int为例structSqlist DataTypedata ListSize intlenth 当前表中元素数 Sqlist data 2 2 2顺序表上实现的基本操作在顺序表存储结构中 很容易实现线性表的一些操作 如线性表的构造 第i个元素的访问 注意 C C 语言中的数组下标从 0 开始 因此 若L是Sqlist类型的顺序表 则表中第i个元素位置是L data i 1 线性表的插入和删除两种运算 1 插入线性表的插入运算是指在表的i 1 i n 1 个位置上 插入一个新结点x 使长度为n的线性表 a1 ai 1 ai an 变成长度为n 1的线性表 a1 ai 1 x ai an 注 可用memmove L data i L dada i 1 L lenth i 1 sizeof DataType 代替for循环 包含文件 string h 一般格式格式 memmove 目的地址 源地址 移动字节数 voidInsertList L x i 在线性表L中第i个位置插入元素x if iL length 1 cout ListSize 溢出处理 else for j L length 1 j i 1 j 第i个元素 下标为i 1 开始L data j 1 L data j 顺序后移L data i 1 x L length memcpy 目的地址 源地址 字节数 memset 目的地址 字符 字节数 inta 50 50 b 50 50 a清0for i 0 i 50 i for j 0 j 50 j a i j 0 拷贝 for i 0 i 50 i for j 0 j 50 j b i j a i j memset a 0 sizeof a memcpy b a sizeof a memcpy与memmove的差异 后者允许地址重叠 算法分析设表的长度为n 该算法的时间主要化费在循环的结点后移语句上 该语句的执行次数 即移动结点的次数 是n i 1 由此 所需移动结点的次数依赖于 1 表的长度 2 插入位置 当 n 1时 不移动 最好情况 当 1时 需移动表中所有结点 最坏情况 a1 ai 1 ai an 算法的平均移动由于插入可能在表中任何位置上进行 在长度为n的线性表中第i个位置上插入一个结点 令Eis n 表示移动结点的期望值 即移动的平均次数 则在第i个位置上插入一个结点的移动次数为n i 1 Pi代表在第i个位置插入概率 则Eis n p1 n p2 n 1 pn 1 pn 1 0若表中任何位置 1 i n 1 上插入结点的概率是均等的 则p1 p2 p3 pn 1 1 n 1 因此 在等概率插入的情况下 Eis n 1 n 1 n n 1 1 0 n 2 a1 ai 1 ai an 结论 在顺序表上做插入运算 平均要移动表上一半结点 当表长n较大时 算法的效率相当低 虽然Eis n 中n的系数较小 但就数量级而言 它仍然是线性阶的 因此算法的平均时间复杂度为O n 2 删除线性表的删除运算是指将表的第i 1 i n 结点删除 使长度为n的线性表 a1 ai 1 ai ai 1 an 变成长度为n 1的线性表 a1 ai 1 ai 1 an voiddeleteList L i 表L中删除第i个元素 if iL length cout 删除序号错 endl returnERROR for j i j L length 1 j L data j 1 L data j L length 算法分析与插入算法相似 结点的移动次数也是由表长n和位置i决定 若i n 无需移动结点 若i 1 则前移元素n 1个令Edl表示所需移动结点的平均次数 删除表中第i个结点的移动次数为n i pi是删除i个元素的概率 则Edl p1 n 1 p2 n 2 pn 1 1 pn 0等概率的假设下 p1 p2 p3 pn 1 nEdl 1 n n 1 n 2 1 0 n 1 2即在顺序表上做删除运算 平均要移动表中约一半的结点 平均时间复杂度也是O n 表溢出问题的说明 2 3线性表的链式表示和实现 2 3 1线性链表链表是指用一组任意的存储单元来依次存放线性表的结点 这组存储单元即可以是连续的 也可以是不连续的 甚至是零散分布在内存中的任意位置上的 因此 链表中结点的逻辑次序和物理次序不一定相同 为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还必须存储指示其后继结点的地址 或位置 信息 这个信息称为指针 pointer 或链 link 这两部分组成了链表中的结点结构 其中 data域是数据域 用来存放结点的值 next是指针域 亦称链域 用来存放结点的直接后继的地址 或位置 链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的 由于上述链表的每一个结只有一个链域 故将这种链表称为单链表 SingleLinked 显然 单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故应设头指针head指向开始结点 同时 由于最后一个结点无后继 故结点的指针域为空 即NULL 图示中常用 表示 例1 线性表 bat cat eat fat hat jat lat mat 示意图如下 head 单链表是由表头唯一确定 因此单链表可以用头指针的名字来命名 例如 若头指针名是head 则把链表称为表head 用C 语言描述的单链表如下 typedefcharDataType structLNode DataTypedata LNode next 一旦p所指的结点变量不再需要了 应该通过deletep 或用free p 释放所指的结点变量空间 LNode p head p为动态变量指针 它可以存放Lnode内存块的首地址 能利用标准函数使得p与一块内存空间关联 即p newLNode C p structLNode malloc sizeof structLNode C new分配了一个类型为LNode的结点变量的空间并将其首地址放入指针变量p中 一 建立单链表问题 假设线性表中结点的数据类型是字符 逐个输入这些字符型的数据 并以换行符 为输入结束标记 动态地建立单链表的常用方法有如下两种 1 头插法建表该方法从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的表头上 直到读入结束标志 比如 为止 voidCreateList1 LNode LNode CreateList charch LNode h p h NULL cin ch while ch p newLNode p data ch p next h h p cin ch returnh includestructLNode chardata LNode next LNode CreateList charch LNode h p h NULL cin ch while ch p newLNode p data ch p next h h p cin ch returnh voidCreateList1 LNode cin ch while ch p newLNode p data ch p next h h p cin ch voidprint LNode h LNode p h while p NULL coutdatanext cout endl voidmain LNode h1 h2 h1 CreateList CreateList1 h2 print h1 print h2 2 尾插法建表头插法建立链表虽然算法简单 但生成的链表中结点的次序和输入的顺序相反 若希望二者次序一致 可采用尾插法建表 该方法是将新结点插入到当前链表的表尾上 为此必须增加一个尾指针r 使其始终指向当前链表的尾结点 例 LNode creat charch LNode p r head head r NULL cin ch while ch p newLNode p data ch if head NULL head p elser next p r p cin ch if r NULL r next NULL returnhead 头结点 哨兵结点 引入 增加一个表头结点 数据域可根据需要使用或不用 特点 a 表中第一个结点和在表的其它位置上的操作一致 无需进行特殊处理 b 无论链表是否为空 其头指针是指向头结点 因此空表和非空表的处理统一 head 有头结点的空表 LNode creat LNode r h charch h newLNode r h cin ch while ch r next newLNode r r next r data ch cin ch r next NULL returnh 上述算法里动态申请新结点空间时未加错误处理 在实际使用时间 可作下列判定与处理 p newLNode if p NULL 错误处理 二 查找运算1 按序号查找在链表中 即使知道被访问结点的序号i 也不能象顺序表中那样直接按序号i访问结点 而只能从链表的头指针出发 顺链域next逐个结点往下搜索 直到搜索到第i个结点为止 因此 链表不是随机存取结构 设单链表的长度为n 要查找表中第i个结点 仅当1 i n时 i的值是合法的 但有时需要找头结点的位置 故我们将头结点看做是第0个结点 其算法如下 LNode getnode head i i 1 在链表head中取第i个数据 链表有头结点 p head j 0 计数用while p next 2 按值查找按值查找是在链表中 查找是否有结点值等于给定值key的结点 若有 则返回首次找到的其值为key的结点的存储位置 否则返回NULL 查找过程从开始结点出发 顺着链表逐个将结点的值和给定值key作比较 其算法如下 LNode locatenode head key p head next while p 该算法的执行时间亦与输入实例中的的取值key有关 其平均时间复杂度的分析类似于按序号查找 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q next p next 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q next p next p next q 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q next p next p next q 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q next p next p next q 定位ai 1并将指针p指向它 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q newLNode q data x q next p next p next q 定位ai 1并将指针p指向它 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 q newLNode q data x q next p next p next q p getnode head i 1 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 并令q指针指向该新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 三 插入运算 voidinsertnode head x i LNode p q p getnode head i 1 if p NULL coutdata x q next p next p next q 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next 问题 链表的逻辑结构已正确了 但结点ai空间丢了 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next r p next p next r next deleter 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next r p next p next r next deleter 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next r p next p next r next deleter 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 p next p next next p getnode head i 1 r p next p next r next deleter 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 所以必须首先找到ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 此过程为 四 删除运算 voiddeletelist head i LNode p r p getnode head i 1 if p NULL p next NULL returnERROR r p next p next r next deleter 从上面的讨论可以看出 链表上实现插入和删除运算 无须移动结点 仅需修改指针 作业 1 链表是有序的 现在插入数据x 要求插入后仍然有序 2 链表是有序的 现在删除数据x 若x不存在 输出一段提示信息 要求 按链表有头结点和无头结点两种情况分别写出并上机调试通过 3 链表逆转 没有头结点 五 静态链 1 静态链表的概念用一维数组来实现线性链表 这种用一维数组表示的线性链表 称为静态链表 静态 体现在表的容量是一定的 数组的大小 链表 插入与删除同前面所述的动态链表方法相同2 静态链表的类型定义 defineMAXSIZE1000 链表的最大长度structComponent ElemTypedata intcur ComponentVList MAXSIZE SLinkList类型的数组变量是结构数组 每一数组分量包括两个域 data 用于存储线性表元素 cur 用于存储直接后继元素在数组中的位置 静态链表图示 0 h 5 数组下标 线性链表图示 地址 1 2 3 4 5 6 7 8 9 10 h 1020 例 静态链表的操作设插入和删除只在表的头上进行 栈 h 7 5 7 2 3 8 5 7 2 3 h 0 表中加入x 01234 7 9 3 1 5 1 2 3 5678910 2 1 VList i data x 1 在VList中找空位置i 比如0 2 VList i cur h x 7 3 h i 空位置的标识 将所有空位置构成链表 用av表示链首 av 0 删除 if h 1 x VList h data i h h VList i cur VList i cur av av i h 7 空表初始化 开始 表是空的 所以 for i 0 i n 1 i a i i 1 a n 1 1 av 0 2 3 2循环链表循环链表是一种头尾相接的链表 其特点是无须增加存储量 仅对表的链接方式稍作改变 即可使得表处理更加方便灵活 单循环链表 在单链表中 将终端结点的指针域NULL改为指向表头结点的或开始结点 就得到了单链形式的循环链表 并简单称为单循环链表 为了使空表和非空表的处理一致 循环链表中也可设置一个头结点 这样 空循环链表仅有一个自成循环的头结点表示 如下图所示 非空表 空表 在用头指针表示的单链表中 找开始结点a1的时间是O 1 然而要找到终端结点an 则需从头指针开始遍历整个链表 其时间是O n 在很多实际问题中 表的操作常常是在表的尾位置上进行 此时头指针表示的单循环链表就显得不够方便 如果改用尾指针rear来表示单循环链表 则查找开始结点a1和终端结点an都很方便 它们的存储位置分别是rear next next和rear 显然 查找时间都是O 1 因此 实际中也常采用尾指针表示单循环链表 由于循环链表中没有NULL指针 故涉及遍历操作时 其终止条件就不再像非循环链表那样判断p或p next是否为空 而是判断它们是否等于某一指定指针 如头指针或尾指针等 2 3 3双向链表双向链表 Doublelinkedlist 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior 这样就形成的链表中有两个方向不同的链 故称为双向链表 形式描述为 structDuLNode datatypedata DuLNode prior next 结点 存储前趋结点的地址 存储数据元素 存储后继结点的地址 双链表一般由头指针唯一确定的 将头结点和尾结点链接起来构成循环链表 并称之为双向链表 设指针p指向某一结点 则双向链表结构的对称性可用下式描述 p prior next p p next prior 双向链表结点p前的插如数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 双向链表结点p前的插如数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 双向链表结点p前的插如数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q p prior next p next p next prior p prior deletep p 删除p指针所指的结点 p prior next p next p next prior p prior deletep p 删除p指针所指的结点 p prior next p next p next prior p prior deletep p 删除p指针所指的结点 双向链表的插入 删除灵活 链表维护的工作量大 所需的存储空间较大 2 4一元多项式的表示及相加 Pn x pnxn pn 1xn 1 p1x p0Qm x qmxm qm 1xm 1 q1x q0 一 一元多项式的表示多项式的操作是表处理的典型用例 数学上 一元多项式可按降幂写成 指数为正整数的情况 其中 pn qm不为0 存储结构 用线性链表表示 增加头结点 每个结点有coef 系数exp指数next 指针其中 头结点的exp为 1 多项式A x 5x17 9x8 3x 7 例 求两多项式的和多项式A x 5x17 9x8 3x 7B x 9x8 22x7 8x 二 一元多项式的相加算法 一元多项式相加运算规则 指数相同的项系数相加 A x B x 相加的和多项式为C x A x B x 5x17 22x7 11x 7 设多项式A x B x 分别用带表头结点的线性链表ha hb表示 完成 ha ha hb 一元多项式加法算法主要步骤分别对两个链表ha hb进行扫描 设工作指针pa pb分别指向两个多项式当前进行比较的结点 q指针指向pa的前驱 初始 q ha pa ha next pb hb next 若pa pb都不为空 则比较两者指数 pa exp pb exp q pa后移 pa exp pb exp 将pb所指结点的系数 加 到pa所指结点的系数上 若和为0 则pa所指结点删除 q pa pb调整pa expexp 从表hb中复制pb所指结点的coef exp 并将其插入到ha表pa所指结点之前 若pb不空 hb表中从pb开始的结点插入到ha表尾上 intcomp inta intb if a b return 1 if a b return0 elsereturn1 PloyAdd ha hb q ha pa ha next pb hb next while pa NULL r coef pb coef r exp pb exp q next r r next pa q r pb pb next break while pb NULL r newNode r coef pb coef r exp pb exp q next r r next pa q r pb pb next while改成 while pb hb 在改成循环链后 此while可省去 1 线性表v的数据递增有序 试将x插入表中并保持有序性 1 表顺序表示 2 链表表示 3 带有头结点的链表2 写一个线性表的转置算法 顺序和链表表示两种情况 a1 a2 an 变为 an an 1 a1 3 写一个类 用模板 实现顺序表示的线性表 templateclassLi T p intlen intmax public 实习题目 hc ha hb要求 1 输入形式 以系数指数的递减序输入 最后以00结束 2 输出 见格式例 5x9 7x2 6x 5输入为 输出为 9 721000 5X 9 7X 2 6X 5 已知一个带有表头结点的单链表 结点结构为 假设该链表只给出了头指针list 在不改变链表的前提下 请设计一个尽可能高效的算法 查找链表中倒数第k个位置上的结点 k为整数 若查找成功 算法输出该结点的data域的之 并返回1 否则 只返回0 要求 1 描述算法的基本设计思想 2 描述算法的详细实现步骤 3 根据设计思想和实现步骤 采用程序设计语言描述算法 使用C或C 或JAVA语言实现 关键之处请给出简要注释 2009年研究生入学试题 15分 find p data k p 链表头指针 k 倒数的值 d 返回值 count 0 q p next p1 p while q if count k p1 p1 next q q next if p1 p return0 d p1 data return1 设将n n 1 个整数存放到一维数组R中 试设计一个在时间和空间两方面都尽可能高效的算法 将R中保存的序列循环左移p 0 p n 个位置 即将R中的数据由 x0 x1 xn 1 变换为 xp xp 1 xn 1 x0 x1 xp 1 要求 1 给出算法的基本思想 2 根据设计的思想 采用C或C 或JAVA语言描述算法 关键之处给出注释 3 说明你所设计算法的时间复杂度和空间复杂度 2010年研究生入学考试 13分 算法思想将x0 x1 xn 1原地转置 形成xn 1 xp xp 1 x0 时间显然是O n 后面将前n p个和后p个元素转置 形成xp xp 1 xn 1 x0 x1 xp 1 这部分时间显然也是O n 所以总时间是O n 实现时可以写一个转置函数re r l h 其中 r为数组 l h为范围 l h re r 0 n 1 re r 0 n p 1 re r n p n 1 voidre a l h i l j h while i j temp a i a i a j a j temp 第三章栈和队列 3 1栈3 1 1栈的定义3 1 2栈的表示和实现3 2栈的应用举例 3 1栈3 1 1栈的定义及基本运算栈 Stack 是限制在表的一端进行插入和删除运算的线性表 通常称插入 删除的这一端为栈顶 Top 另一端为栈底 Bottom 当表中没有元素时称为空栈 假设栈S a1 a2 a3 an 则a1称为栈底元素 an为栈顶元素 栈中元素按a1 a2 a3 an的次序进栈 退栈的第一个元素应为栈顶元素 因此 栈的修改是按后进先出的原则进行的 所以 栈称为后进先出 先进后出 表 LIFO FILO 3 1 2顺序存储栈栈是线性表的特例 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化的 故需用一个整型变量top 栈顶指针 来指出栈顶 栈顶 栈底 例 一叠盘子 弹夹等 入 出 1空栈 为指示当前栈顶的位置 需top为栈顶指针 MAXSIZE代表栈容量 初始化 x进栈 退栈 top 1 if top MAXSIZE 1上溢处理 else top stack top x if top 1 下溢处理 else y stack top top 3 1 3链栈栈的链式存储结构称为链栈 插入和删除操作仅限制在链头位置上进行 栈顶指针就是链表的头指针 3 2栈的应用举例由于栈结构具有的后进先出的固有特性 致使栈成为程序设计中常用的工具 以下是几个栈应用的例子 3 2 1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一个简单算法基于下列原理 N n d d n d例如 1348 10 2504 8 其运算过程如下 nn 8n 8134816841682102125202 voidconversion initstack s cin n while n push s n 8 n n 8 while Stackempty s pop s e cout e 3 2 2括号匹配的检验假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余 否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确 否则表明 左括弧 有余 3 2 3行编辑程序在编辑程序中 设立一个输入缓冲区 用于接受用户输入的一行字符 然后逐行存入用户数据区 允许用户输入错误 并在发现有误时可以及时更正 出口 3 2 4迷宫求解入口 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 3 2 4迷宫求解 求迷宫路径算法的基本思想是 若当前位置 可通 则纳入路径 继续前进 若当前位置 不可通 则后退 换方向继续探索 若四周 均无通路 则将当前位置从路径中删除出去 设定初值为入口位置 以正东为起始方向 do if 当前位置可通 则 将当前位置插入栈顶 if 该位置是出口位置 exit 0 else按顺时针下一方向为新的当前位置 else while 栈不空 求迷宫中一条从入口到出口的路径的算法 若栈空 则表明迷宫没有通路 if 栈不空 栈顶位置尚有其他方向未被探索 新的当前位置为 沿顺时针方向旋转找到的栈顶位置的下一相邻块 if 栈不空 栈顶位置的四周均不可通 则 删去栈顶位置 从路径中删去该通道块若栈不空 则重新测试新的栈顶位置 直至找到一个可通的相邻块或出栈至栈空 3 2 5表达式求解 表达式的三种标识方法 设exp S1OPS2 则称OPS1S2为前缀表示法 S1OPS2为中缀表示法 S1S2OP为后缀表示法 例如 exp a b c d e f前缀式 ab c def中缀式 a b c d e f后缀式 ab cde f 结论 1 操作数之间的相对次序不变 2 运算符的相对次序不同 例如 exp a b c d e f前缀式 ab c def中缀式 a b c d e f后缀式 ab cde f 结论 3 中缀式丢失了括弧信息 致使运算的次序不确定 例如 exp a b c d e f前缀式 ab c def中缀式 a b c d e f后缀式 ab cde f 结论 4 前缀式的运算规则为 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式 例如 exp a b c d e f前缀式 ab c def中缀式 a b c d e f后缀式 ab cde f 结论 5 后缀式的运算规则为 运算符在式中出现的顺序恰为表达式的运算顺序 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式 如何从后缀式求值 先找运算符 再找操作数 例如 ab cde f a b d e c d e c d e f a b c d e f 如何从原表达式求得后缀式 每个运算符的运算次序要由它之后的一个运算符来定 在后缀式中 优先数高的运算符领先于优先数低的运算符 分析 原表达式 和 后缀式 中的运算符 原表达式 a b c d e f后缀式 abc de f 从原表达式求得后缀式的规律为 1 设立运算符栈 2 设表达式的结束符为 预设运算符栈的栈底为 3 若当前字符是操作数 则直接发送给后缀式 4 若当前运算符的优先数高于栈顶运算符 则进栈 5 否则 退出栈顶运算符发送给后缀式 7 遇表达式结束 连续将栈中运算符退到后缀式 6 对它之前后的运算符起隔离作用 可理解为优先级最低的运算符号 进栈 可视为自相应左括弧开始的表达式的结束符 一直退到栈顶是 符号送后缀式 最后 退栈 a b c d e f 栈 后缀表达式 a b c d e f 栈 后缀表达式 a b c d e f a 后缀表达式 栈 a b c d e f a 后缀表达式 栈 a b c d e f a 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f a b 后缀表达式 栈 a b c d e f 栈 a b 后缀表达式 a b c d e f 栈 a b 后缀表达式 a b c d e f 栈 a b c 后缀表达式 a b c d e f a b c 后缀表达式 栈 a b c d e f a b c 后缀表达式 栈 a b c d e f a b c 后缀表达式 栈 a b c d e f a b c d 后缀表达式 栈 a b c d e f a b c d 后缀表达式 栈 a b c d e f a b c d 后缀表达式 栈 a b c d e f a b c d 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e 后缀表达式 栈 a b c d e f a b c d e f 后缀表达式 栈 a b c d e f 栈 a b c d e f 后缀表达式 a b c