ch2 基本数据结构及其运算.ppt

第二章基本数据结构及其运算 线性表 什么是线性表 日常生活中常见到表格形式的一类数据列车时刻表学生成绩表周名缩写表 列车时刻表 学生成绩表 周名缩写表 1 表中每一行信息虽然组成的内容不同 但都代表某个明确独立的含义 将表中每一行信息称之为一个数据元素 2 每个数据元素在表中的位置固定 除了第一个元素和最后一个元素外 其余元素都有唯一一个前驱元素和唯一一个后继元素 3 表中数据元素的个数不相同 有长有短 4 大多数表中数据元素会增加或减少 是动态变化的 但也有一些表是固定不变 将这些表格形式的数据加以抽象 统称为线性表 上述表格数据具有如下共同特点 线性表概念 综上所述 线性表是由n n 0 个数据元素a1 a2 an组成的一个有限序列 表中的每一个数据元素 除了第一个外 有且只有一个前件 除了最后一个外 有且只有一个后件 即线性表或是一个空表 或可以表示为 a1 a2 ai an 其中ai i 1 2 n 是属于数据对象的元素 通常也称其为线性表中的一个结点 结构特征 有且只有一个根结点a1 它无前件 有且只有一个终端结点an 它无后件 除根结点与终端结点外 其他所有结点有且只有一个前件 也有且只有一个后件 线性表中结点的个数n称为线性表的长度 当n 0时 称为空表 线性表的存储 在计算机中存放线性表 一种最简单的方法是顺序存储 也称为顺序分配 顺序存储的线性表通常称为顺序表 线性表的顺序存储结构具有以下两个基本特点 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 线性表的存储 在计算机中的顺序存储结构如图所示 设有一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是多少 但此题要注意下标起点略有不同 LOC M 3 98 5 3 0 113 解 已知地址计算通式为 LOC ai LOC a1 C i 1 对线性表有哪些处理 或操作 呢 1 统计线性表里总共有多少个元素 简称求表长 记作Length L 2 获取线性表中某个数据元素的信息 简称取元素 记作Get L i 3 置换或修改线性表中某个数据元素的信息 简称置换元素 记作Replace L i x 4 在线性表中某个位置上增加一个数据元素 简称插入元素 记作Insert L i x 5 删除线性表中某个位置上的一个数据元素 简称删除元素 记作Delete L i 6 查找某个数据元素是否在线性表中存在 简称查找元素 记作Locate L x 7 对线性表中的数据元素按某个数据项的值递增 或递减 的顺序排列 简称排序 记作Sort L 顺序表的插入运算 一般来说 设长度为n的线性表为 要在线性表的第i个元素ai之前插入一个新元素b 插入后得到长度为n 1的线性表为 则插入前后的两线性表中的元素满足如下关系 已知线性表的当前状态是 a1 a2 ai 1 ai an 要在第i个位置插入一个元素x 线性表变为 a1 a2 ai 1 x ai an 其实施步骤为 1 将第n至第i个元素后移一个存储位置 2 将x插入到第i个位置 3 线性表的长度加1 a2 a1 an ai 1 ai 0 1 i 1 i n 1 在线性表的第i个元素之前插入一个新的元素 先移动 后插入 ai 1 a2 a1 alast ai 1 ai x x voidinsl v m n i b 顺序表的插入 ETv b v为顺序表空间 b为插入的元素 intm n i m为顺序表空间容量 n为指向线性表长度的指针 i为插入元素的序号 if n m 顺序表空间已满 上溢错误 返回 printf overflow n return if i n 1 i n 1 在线性表的最后插入 if i 1 i 1 在线性表的第1个元素之前插入 for j n j i j 插入位置以后的元素依次往后移动一个位置 v j v j 1 v i 1 b 插入元素b n n 1 线性表长度加1 return 顺序表的删除运算 一般来说 设长度为n的线性表为 现要删除第i个元素 删除后得到长度为n 1的线性表为 则删除前后的两线性表中的元素满足如下关系 已知线性表的当前状态是 a1 a2 ai 1 ai ai 1 an 若要删除第i个元素ai 则线性表成为 a1 a2 ai 1 ai 1 an 具体实施步骤为 1 若i值合法 则将第i 1至第n个位置上的元素依次向前移动一个存储单位 2 将线性表的长度减1 a2 a1 an ai 1 ai 0 1 i 1 i n 1 删除线性表的第i个元素 后面所有元素前移 ai 1 a2 a1 alast ai 1 ai 删除结点ai ai 1 alast voiddesl v m n i 顺序表的删除 ETv 顺序表空间 intm n i m为顺序表空间容量 n为指向线性表长度的指针 i为删除元素的序号 if n 0 线性表为空 下溢错误 返回 printf underflow n return if i 1 i n 线性表中没有这种下标的元素 返回 printf Notthiselementinthelist n return for j i j n 1 j 第i个以后的元素依次往前移动一个位置 v j 1 v j n n 1 线性表长度减1 return 算法性能分析 在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时 其时间主要耗费在移动元素上 而移动元素的个数取决于插入或删除元素的位置 假设在第i个元素之前插入一个新元素的概率为1 n 1 即在表的任何位置 包括an之后 插入新元素的概率是相等的 则插入操作中元素的平均移动次数 实际上就是时间复杂度 为 T 算法性能分析 对于删除操作 假定对长度为n的线性表 在表的任何位置上删除元素的概率是相等的 即等于1 n 则删除操作中元素的平均移动次数 即是时间复杂度 为 T 从以上分析可以看出 在顺序存储的线性表中进行插入或删除操作 平均要移动一半的元素 即T n O n 当线性表的元素很多 且每个元素的数据项较多时 花费在移动元素上的时间会很长 一般情况下 线性表的顺序存储结构适合于表中元素变动较少的线性表 顺序表的合并例 已知集合A和B 求两个集合的并集 使A A B 且B不再单独存在 现假设以线性表LA和LB分别表示集合A和B 即构造两个线性表LA和LB 它们的数据元素分别为集合A和B中的成员 由此 上述集合求并的问题便可演绎为 要求对线性表作如下操作 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 现具体操作步骤为 1 从线性表LB中取出一个数据元素 2 依值在线性表LA中进行查询 3 若不存在 则将它插入到LA中 重复上述三步直至LB为空表止 容易看出 上述的每一步恰好对应线性表的一个基本操作 1 ListDelete LB 1 e 2 LocateElem LA e equal 3 ListInsert LA n 1 e 现equal 为判定元素值是否相等的函数 n表示线性表中当前所含元素个数 由于在集合论中 元素之间是没有次序关系的 因此为操作方便 仅需将新的数据元素插入在线性表的表尾即可 这样得到的算法表示为 voidunion List union ListInsert La La len e 表示先将参数La Len增1然后将e插入到La中第La len个元素之前 顺序存储表类的优缺点 1 存取元素非常快 2 不用存关系集合 3 插入删除元素要移动一半元素 4 需要申请较大的空间 但往往只用一部分空间 5 可扩充性差 线性表的非顺序存储结构 链表 设计新的存储结构 改进顺序表的结构思路 1 线性表中有多少元素就开辟多少存储空间 不预留空间 2 元素之间不需要紧挨着存放 元素可以散落在存储器中任何地方 3 插入和删除都不需要移动大量元素 线性链表 线性表的链式存储结构称为线性链表特点是用一组任意的存储单元存储线性表中的数据元素 这组存储单元可以是连续的 也可以是不连续的 这样 逻辑上相邻的元素在物理位置上就不一定是相邻的 为了能正确反映元素的逻辑顺序 就必须在存储每个元素ai的同时 存储其直接后继元素的存储位置 这时 存放数据元素的结点至少包括两个域 一个域存放该元素的数据 称为数据域 data 另一个域存放后继结点在存储器中的地址 称为指针域或链域 next 这种链式分配的存储结构称为链表 此结构的C语言描述为 TypedefstructLnode ElemTypedata LNode next node 数据元素的结点结构如下 线性链表存储结构 在此单链表中 head是指向单链表中第一个结点的指针 我们称之为头指针 最后一个元素所在结点不存在后继 因而其指针域为 空 用NULL或 或0表示 表示链表终止 线性链表 用线性链表表示线性表时 数据元素之间的逻辑关系是由结点中的指针指示的 逻辑上相邻的两个数据元素其存储的物理位置不要求相邻 因此 这种存储结构为非顺序映像或链式映像 在使用中 我们只关心数据元素的逻辑次序而不必关心它的真正存储地址 通常 我们在单链表第一个元素所在的结点之前附设一个结点 头结点 增加的目的是统一空表与非空表的处理 头结点的指针域存储第一个元素所在结点的存储位置 头结点的数据域可以不存储任何信息 也可以存储如线性表的长度等附加信息 若线性表为空表 则头结点的指针域为 空 一般情况下 链表中每个结点可以包含若干个数据域和指针域 若每个结点中只有一个指针域 则称此链表为线性链表或单链表 否则被称为多链表 带头单链表 线性链表的基本运算 线性链表的建立 在线性链表中包含指定元素的结点之前插入一个新元素 在线性链表中删除包含指定元素的结点 线性链表的查找 将两个线性链表按要求合并成一个线性链表 将一个线性链表按要求进行分解 逆置线性链表 求线性链表长度 线性链表的排序 指针操作 假如p为指向某一结点的指针则该结点的数据域用p data表示该结点的指针域用p next表示它们都是变量 可以被赋值 也可向其他变量赋值 例如 假定data为整型变量 则p data 5 p next NULL 将结点变为 如果p为指向结点ai的指针 那么p next就是指向ai后继结点ai 1的指针 若q为另一指针变量p q指针p指向指针q所指的结点p q next指针p指向指针q所指结点的后继 指针操作 单链表的建立 在C语言的编程实现时 申请与释放一结点对应于C语言中两个标准函数malloc sizeof node 和free p 1 malloc是从可利用空间表中调用一新结点 并返回该结点的地址 s Lnode malloc sizeof Lnode 2 free p 将p指向的结点归还给可利用空间表 为方便起见 以后把指针型变量p所指向的结点称为p结点 动态建立单链表的算法 要对单链表进行操作 首先要掌握怎样建立单链表 链表是一种动态存储结构 所需的存储空间只有在程序执行malloc之后 才可能申请到一个可用结点空间 free p 的作用是系统回收一个结点 回收后的空间可以备作再次生成结点时用 整个可用存储空间可为多个链表共同享用 每个链表占用的空间不需预先分配划定 而是由系统应需求即时生成 因此 建立线性表的链式存储结构的过程就是一个动态生成链表的过程 即从 空表 的初始状态起 依次建立各元素结点 并逐个插入链表 动态建立线性表的链式存储结构有两种基本方法 分别适用于不同的场合 可根据所建链表结点的顺序要求选择采用一种方法 单链表建立方法一 反向建立链表 头插法 思想 若线性表的元素已顺序存放在一维数组A N 中 建表方法是从线性表的最后一个元素开始 从后向前依次插入到当前链表的第一个结点之前 defineNm m为链表中数据元素的个数 如m 10 intA N NODE creatlink1 NODE head s inti head NODE malloc sizeof NODE 生成头结点 head next NULL 置空表 for i N 1 i 0 i 插入10个数据 头插法 s NODE malloc sizeof NODE 生成新结点 s data A i 将输入数据放入新结点数据域 s next head next 新结点与原首结点链接 head next s 将新结点插入到表头 returnhead 返回单链表头指针 算法的时间复杂度为 T n O n 头插法 在链表的表头插入一个元素 完成插入后表头指针要指向新的表头节点实现的语句 p next h h p 单链表建立方法二 正向建立单链表 尾插法 思想 依次读入线性表的元素 从前往后依次将元素插入到当前链表的最后一个结点之后 图B新结点 s插入到单链表head的尾上 NODE creatlink2 NODE head p s intnum head NODE malloc sizeof NODE 生成头结点 scanf d 头指针 尾指针 while num 0 输入为0为输入结束符 尾插法 s NODE malloc sizeof NODE 生成新结点 s data num 新结点上填入输入值 p next s 新结点 s插入到尾结点 p之后 p s 尾指针p指向新的表尾 scanf d 返回单链表头指针 算法的时间复杂度 T n O n 尾插法 在链表结尾出插入一个元素 首先要用一个循环语句找到qq h while q next NULL q q next 然后执行插入语句 p next NULL q next p 单链表的建立 Voidcreat node p L intx cycle 1 L node malloc sizeof node L next null while cycle scanf d elsecycle 0 单链表的建立 单链表的查找 由于链表存储结构不是一种随机存取结构 要查找单链表中的一个结点 必须从头指针出发 沿结点的指针域逐个往后查找 直到找到要查找的结点为止 查找 在带头结点的单链表中找出第i个元素所在的结点 NODE get NODE head inti NODE p intcounter 1 p head next while p NULL 找不到 i n或i 0 单链表的插入设有线性表 a1 a2 ai 1 ai an 用带头结点的单链表存储 头指针为head 要求在线性表中第i个元素ai之前插入一个值为x的元素 线性表变为 a1 a2 ai 1 x ai an 插入前单链表的逻辑状态如图所示 算法思想 为插入数据元素x 1 首先要生成一个数据域为x的新结点s 2 然后确定插入位置 即找到ai之前的元素ai 1 并使指针p指向之 3 最后改变链接 将x插在ai 1与ai之间 修改结点p和结点s的指针域 即s next p next p next s插入结点s后单链表的逻辑状态如图所示 插入算法voidinsert NODE head inti intx NODE p s intj 0 p head while p NULL if p NULL j i 1 printf i值不合法 n 找不到 i n或idata x s next p next p next s 如果事先告之p指针所指的位置 则这种在p指针后插入一个元素算法的时间复杂度T n O 1 否则平均时间复杂度T n O n Ai 1 Ai X p s p next s 新结点链入表中示意图 s next p next 思考 两者能否互换 在链表中间插入一个元素 这种情况不涉及头节点的变动假如被插入位置的后方特征是数据项为x则可以执行循环语句q h while q next data x q q next 确保找到被插入地方的前方节点q 然后执行插入语句 p next q next q next p 注意语句顺序 单链表的插入 单链表的删除删除操作和插入操作一样 1 首先要搜索单链表以找到指定删除结点的前趋结点 假设为p 2 然后改变链接 即只要将待删除结点的指针域内容赋予p结点的指针域即可 判定空表寻找插入位置确认插入有错否修改链表指针收回结点空间 设有线性表 a1 a2 ai 1 ai ai 1 an 用带头结点的单链表存储 删除前的逻辑状态如图所示 删除元素ai所在的结点之后 单链表的逻辑状态如图所示 voiddelete NODE head inti NODE p s intj 0 p head while p next NULL 删除结点示意图 链表的删除 有单独头节点 首先要找到p以及p的前驱q然后执行删除语句 q next p next 当p为第一个元素时候 p的前驱是h即q h 注意上面一步仅仅是将p指向的那个节点脱离链表 并没有将那个节点删除如果这时候p指向的那个节点已经没有用处了 应该回收那个节点占用的内存free p 整个过程和只有头指针的第二种情况完全一样 单链表的删除 单链表特点分析 链式存储结构的优势在于 能有效利用存储空间 用 指针 指示元素之间的后继关系 便于进行插入 删除等操作 链式存储结构的劣势在于 其劣势则是不能随机存取数据元素 同时 它还丢失了一些顺序表有的长处 如线性表的 表长 和数据元素在线性表中的 位序 在上述的单链表中都看不见了 又如 不便于在表尾插入元素 需遍历整个表才能找到插入的位置 讨论1 链表能不能首尾相连 怎样实现 答 能 只要将表中最后一个结点的指针域指向头结点即可 P next head 这种形成环路的链表称为循环链表 特点 1 从任一结点出发均可找到表中其他结点 2 操作仅循环条件与单链表不同 单链表 p NULL或p next NULL循环链表 p head或p next head 循环链表 循环链表 CircularLinkedList 是线性表的另一种形式的链式存储表示 它的特点是表中最后一个结点的指针域指向头结点 整个链表成为一个由链指针相链接的环 并且将头指针设成指向最后一个结点 空的循环链表由只含一个自成循环的头结点表示 循环链表的操作和单链表基本一致 差别仅在于 判别链表中最后一个结点的条件不再是 后继是否为空 而是 后继是否为头结点 讨论2 单链表只能查找结点的直接后继 若想查找结点的直接前驱 该如何设计 答 只要把单链表再多开一个指针域即可 例如用 next和 prior 双向链表在非线性结构 如树结构 中将大量使用 这种链表称为双向链表 其特点是可以双向查找表中结点 双向链表 双向链表也是由指向头结点的头指针唯一确定 若将头尾结点链接起来则构成双向循环链表 空的双向循环链表则由只含一个自成双环的头结点表示 双向链表 双向链表定义如下typedefstructnode pointer structnode datatypeinfo pointerllink rlink 其中info为节点本身的信息 llink和rlink分别为指向其前驱和后继的指针 在双向链表中 如果p指向链表中某个节点 则有 p p rlink llink p llink rlink这一等式反映了双向链表结构的特点在双向链表中 删除一个节点的操作 p llink rlink p rlink p rlink llink p llink 双向链表 插入在双向链表中 将一个新节点插在p所指的节点之后的操作如图 设q指向要插入的节点 插入操作的指令如下 q rlink p rlink p rlink q q llink p q rlink llink q 例设计算法 判断带头结点的循环双向链表head按元素值是否对称 所谓对称 就是在线性表中a1 an a2 an 1 intsymmetry DNODE head DNODE p q p head next p指向首元素 q head prior q指向尾元素 while p data q data if p q p next q 0个或1个元素 return1 else p p next p向左扫描 q q prior q向右扫描 return0 2 3栈及其应用 1 栈的定义栈 stack 是限定只能在表的同一端进行插入和删除操作的线性表 其中允许进行插入和删除操作的一端称为栈顶 top 而表中固定的一端称为栈底 bottom 栈中元素个数为零时称为空栈 由于栈中元素的插入和删除只能在栈顶进行 所以总是后进栈的元素先出来 即栈具有后进先出 LastInFirstOut 缩写为LIFO 的特性 故栈又称为 后进先出表 LIFO表 堆栈的定义 堆栈指插入和删除元素操作只能在表的一端进行 这种线性表称为堆栈 堆栈又称LIFO表或FILO表 插入进栈 删除出栈 栈顶 栈底 1 Inistack S 初始化栈S为空栈 2 Empty S 判定S是否为空栈 若S是空栈则返回值为真 Ture 否则返回值为假 False 3 Push S x 进栈操作 在栈S的栈顶插入数据元素x 4 Pop S 出栈操作 若栈S不是空栈 则删除栈顶元素 5 Gettop S 取栈顶元素 它只读取栈顶元素 不改变栈中的内容 栈的运算 三个元素可能的出栈序列 例有三个元素的进栈序列是1 2 3 举出此三个元素可能的出栈序列 并写出相应的进栈和出栈操作序列如图所示 假设以I和O表示进栈和出栈操作 栈的表示和实现因为栈是线性表的一种特例 所以线性表的存储结构对它都适用 一般称采用顺序存储结构的栈为顺序栈 采用链式存储结构的栈为链栈 1 栈的顺序存储结构 顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时设指针top指示栈顶元素的当前位置 空栈的栈顶指针值为0 设用数组Stack MAXSIZE 表示栈 则对非空栈 Stack 1 为最早进入栈的bottom元素 Stack top 为最迟进入栈的元素 即栈顶元素 当top MAXSIZE时意为栈满 此时若有元素入栈则将产生 数组越界 的错误 称为栈的 上溢 overflow 反之 top 0意为栈空 若此时再作退栈操作 则发生 下溢 underflow 图展示了顺序栈中数据元素和栈顶指针之间的对应关系 设MAXSIZE 10 顺序栈的C语言描述如下 typedefintdatatype defineMAXSIZEm definemaxsize64intstack MAXSIZE typedefstruct inttop inttop 1 datatypedata maxsize seqstack seqstack s 注意 上述定义中 假设数据元素的类型为整型 m为栈中数据元素个数的最大可能值 进栈算法步骤 step1 判断栈是否已满 若满则输出栈溢出信息 并停止执行 否则 执行step2 step2 栈顶指针top后移 step3 在栈顶指针所指当前位置插入元素x defineMAXSIZEmintstack MAXSIZE 1 inttop 1 voidpush intx if top MAXSIZE 1 printf 栈满溢出 n exit 1 else top stack top x 出栈算法步骤 step1 判断栈是否为空栈 若为空则输出栈下溢信息 并停止执行 否则 执行step2 step2 弹出 删除 栈顶元素 step3 栈顶指针top下移 defineMAXSIZEmintstack MAXSIZE inttop voidpop intx if top 1 printf 栈空溢出 n exit 1 else x stack top top returnx 栈的使用非常广泛 常常会出现在一个程序中需要同时使用多个栈的情形 为了不因栈上溢而产生错误中断 必须给每个栈预分一个较大的空间 但这并不容易做到 因为各个栈实际所用空间很难估计 考虑到在实际进程中 当一个栈发生上溢时 其它栈可能还留有很多空间 所以可设法动态地加以调整 以达到多个栈共享内存时 只要有一个栈未满 其它任何栈的入栈操作均不会发生上溢 图2 20两个栈共享空间示意图 现在以两个栈为例 讨论其共享内存时的顺序分配方法 当有两个栈共享大小为m的内存空间时 可以把两个栈的栈底分别设在给定内存空间的两端 然后 各自栈顶向中间伸展 仅当两个栈顶相遇时才发生溢出 这种分配方式 在每个栈的动态变化过程中 使每个栈可利用的最大空间均有可能超过m 2 栈的链式存储结构 链栈 采用顺序存储结构 对于一个栈 两个栈可以清楚自然地表达 但当遇到多个栈共享空间的问题或栈的最大容量事先不能估计时 采用链式存储结构是有效的方法 链栈示意图 类似于单链表 链栈的C语言描述如下 structsnode ETdata structsnode next typedefstructsnodeSNODE 栈顶指针仍是top 其类型为SNODE 相当于单链表的首指针 可惟一确定一个链栈 当top NULL 表示一个空链栈 对于链栈 不会产生单个栈满而其余栈空的情形 只有当整个可用空间都被占满 malloc函数无法实现时才会发生上溢 因此多个链栈共享空间也就是自然的事了 链栈的运算1 进栈操作push stack x 步骤 step1 申请一链栈结点 若无可用内存空间 则表示栈满 否则执行step2 step2 在top所指结点之前插入新结点 并将top指向新申请的结点 voidpush SNODE top intx SNODE p p SNODE malloc sizeof SNODE if p NULL printf 内存中无可用空间 栈溢出 n exit 1 else p data x p next top top p 链栈的运算2 出栈操作pop stack 步骤 step1 若判断链栈为空 则输出栈溢出信息 否则执行step2 step2 删除top所指结点 并使top指向被删结点的后继结点 voidpop SNODE top intx SNODE p if top NULL printf 栈空溢出 下溢 n exit 1 else p top top top next x p data free p 链栈的运算 栈的应用 下图中给出了具有嵌套调用关系的五个程序 其中主程序要调用子程序SUB1 SUB1要调用子程序SUB2 SUB2要调用子程序SUB3 SUB3要调用子程序SUB4 SUB4不再调用其他子程序了 栈的应用 计算机系统在处理时要用一个栈来动态记忆调用过程中的路径 其基本原则如下 在开始执行程序前 建立一个栈 其初始状态为空 当发生调用时 将当前调用的返回点地址 在上图中用语句标号表示 入栈 当遇到从某个子程序返回时 从栈顶取出返回点地址 栈的应用 1 递归过程的实现例如 在本书的第1章例1 5中提到 对于输入的参数n 依次打印输出自然数1到n 为了不使用局部变量 其C函数如下 include stdio h wrt1 intn if n 0 wrt1 n 1 printf d n n return 栈的应用 2 表达式的计算 栈的应用 对列及其应用 队列 Queue 是一种先进先出 FIFO FirstInFirstOut 的线性表 它只允许在表的一端进行插入元素操作 而在另一端进行删除元素操作 这和日常生活中的排队是一致的 最早进入队列的元素最早离开 在队列中 允许插入的一端称为队尾 rear 允许删除的一端则称为队头 front 对列及其应用 队列的基本运算Iniqueue Queue 初始化队列Queue 即置Queue为空队列 Empty Queue 判定队列Queue是否为空 若Queue是空队列则返回值为真 True 否则返回值为假 False Addqueue Queue x 入队操作 若队列未满 则在Queue的队尾插入元素x Delqueue Queue 出队操作 若队列非空 则将Queue的队头元素删除 Getheadqueue Queue 读取队列Queue的队头元素 不改变队列中的内容 1 队列的顺序存储结构用一组地址连续的空间存放队列中的元素 即用一个能容纳最大容量元素的向量 另外还需要两个指针 front和rear 分别指示队头元素和队尾元素的存储位置 顺序队列的C语言描述如下 typedefintdatatype defineMAXSIZEm defineMAXSIZEmintqueue MAXSIZE typedefstruct intfront rear intfront rear datatypedata maxsize sequeue sequeue sq 队列的存储结构 上面定义中 假设数据元素的类型为整型 m为队列中数据元素个数的最大可能值 约定 队头指针front指向队列中队头元素的前一个位置 队尾指针rear指向队尾元素在队列中的当前位置 若不作上述约定 会出现 在实现出队列的操作时 第一个元素和其它元素的处理方法不一致 如front 读第一个元素 x queue front front 读其它元素 x queue front front 队列空的判别条件复杂化图2 23展示了顺序结构队列中头 尾指针的变化情况 一开始时 队列的头 尾指针都指向向量空间下界的前一个位置 在此设为 1 若不考虑溢出 则入队操作为 rear 尾指针加1 queue rear x x入队 出队操作为 front 头指针加1 X data front 分析 队列空的条件front rear 存在两种可能 在顺序结构队列中 队列满 即上溢 的判定条件是什么 假设当前队列处在图2 23中 d 的状态 即MAXSIZE 6 rear 5 front 3 显然不能作入队列操作 因为rear 1 MAXSIZE 1 出现上溢 但队列中还有空间 我们称这种现象为 假溢出 队列假满的状态front rear MAXSIZE 1或front 1 rear MAXSIZE 1 解决 假溢出 的办法有两种 1 将全部元素向前移动直至队头指针front为 1 使队列的第一个元素重新位于queue 0 这种方案是比较费时的 2 设想queue 0 接在queue MAXSIZE 1 之后 使一维数组成为一个首尾相接的环 即如果rear 1 maxsize 则令rear 0 这就是循环队列的概念 在循环队列中 需要解决两类问题 即队头指针及队尾指针的后移 如何判定队列的空与满 循环队列示意图 01 72 63 54 01234567 循环队列示意图 队头指针和队尾指针的后移实际上就是如何从队列的第maxsize 1个位置移到第0个位置 这很容易地通过 求模 运算实现 1 对于队头指针front if front 1 maxsize front 0elsefront front 1或者front front 1 maxsize 2 对于队尾指针rear if rear 1 maxsize rear 0elserear rear 1或者 rear rear 1 maxsize 循环对列示意图 当循环队列满时有front rear 而当循环队列空时也有front rear 当循环队列满时有front rear 而当循环队列空时也有front rear 在循环队列中 习惯上我们采用保留一个空闲位置来区别空和满 1 队空时 采用的判定条件为 rear front2 队满时 以队尾指针加1等于队头指针作为判定条件 尾追头 即front rear 1 maxsize当队列满时 队列中实际上只有maxsize 1个元素 为了将队空和对满的条件加以区分 习惯上我们采用保留一个空闲位置来区别空和满 队空条件为 front rear队满条件为 rear 1 MAXSIZE front a 循环队列空 b 非空循环队列 c 循环队列满循环队列示意图 假若想利用全部循环队列中的maxsize个存储位置 此时队列满时front rear与队列空时的关系相同 因而需要另外设一标志tag来区别队列的空和满 1 初始时front rear 说明队列空 S 0置队列空标志 2 若随着元素的入队再次满足条件front rear 说明队列满 S 1置队列满标志 由于另设标志增加了判别标志所需的时间 通常不采用此法 而前一种方法虽留有一个空额损失了一个空间 但避免了由于判别另设标志造成的时间损失 加快了算法的执行速度 循环队列的入队列操作Addqueue Queue x 步骤 step1 判定循环队列是否已满 若满 则给出队列溢出出错信息 step2 队尾指针后移 将入队元素放入队尾指针所指的存储位置 defineMAXSIZEmintqueue MAXSIZE intfront 1 rear 1 voidaddqueue intx if front rear 1 MAXSIZE printf 循环队列已满 上溢 n exit 1 else rear rear 1 MAXSIZE queue rear x 循环队列的出队列操作Delqueue Queue 步骤 step1 判定循环队列是否为空 若空 则给出队列溢出 下溢 信息 step2 队头指针后移一个位置 defineMAXSIZEmintqueue MAXSIZE intfront 1 rear 1 intdelqueue intx if front rear printf 循环队列已空 下溢 n x 1 else front front 1 MAXSIZE x queue front returnx 2 队列的链式存储结构利用带头结点的单链表作为队列的链式存储结构 由前所述 一个队列需要两个分别指向队头和队尾的指针才能惟一确定 在链队列里 将队头指针front指向单链表的头结点 而将队尾指针rear指向单链表的最后一个结点 链队列的C语言描述为 structqnode intdata structqnode next typedefstructqnodeQNODE QNODE front rear 也可将头尾指针画在一个结点里 将链队列用如图所示 判链对列空满的条件 1 链队列满的条件是 仅当内存中无可利用内存 即malloc函数无法分配到内存空间 2 链队列空的条件是 front rear 链队列指针变化示例 链队列的入队操作addqueue Queue x 结点数据结构类型定义structqnode intdata structqnode next typedefstructqnodeQNODE QNODE front rear voidaddqueue intx QNODE p p QNODE malloc sizeof QNODE if p NULL printf 内存中无可用空间 链队列已满 即上溢 n exit 1 else p data x p next NULL rear next p rear p 链队列的出队操作delqueue Queue voiddelqueue intx QNODE p if front rear printf 链队列已空 即下溢 n exit 1 else p front next front next p next x p data if p next NULL rear front free p 删除最后一个元素时 需要修改尾指针 使其指向头结点 队列采用链式存储分配可以很容易地实现多个队列共享内存空间 空队列状态也是程序设计中常用的一种控制转移的条件 在程序设计中 凡是按照 先来先处理 的原则操作的事情都需要用队列来加以管理 例如我们在后面章节中提到的树和图的某种遍历就要用到队列 队列的应用 凡是按 先来先服务 即 先进先出 原则处理的问题 都可以用队列结构来解决 1 给工人分配工作的模拟输入输出缓冲区的结构汽车加油站的工作模拟 2 5 4多项式的表示及其运算一元多项式的表示及相加一元多项式的表示 可用线性表P表示 但对S x 这样的多项式浪费空间 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构 也可以用单链表 单链表的结点定义 typedefstructnode intcoef exp structnode next JD 一元多项式相加 设p q分别指向A B中某一结点 p q初值是第一结点 运算规则 Ch2 7 c 算法描述 2 6 1数组数组是大家已经很熟悉的一种数据类型 几乎所有的程序设计语言都把数组类型设定为固有类型 数组 array 可看成是线性表的推广 是最常用的数据结构之一 数组是有限个数组元素的集合 数组的每个元素与一组下标相对应 和线性表一样 数组中所有数组元素的数据类型必须一致 2 6串和数组 A a11a12 a1na21a22 a2nam1am2 amn 如下所示 就是一个m行n列的二维数组 也称为矩阵 记作A m n 矩阵A可以看成是由m个行向量组成的向量 也可以看成是由n个列向量组成的向量 在矩阵A中 每个元素aij都属于两个线性表 一个是第i行的行表 ai1 ai2 aij ain 另一个是第j列的列表 a1j a2j aij amj 这种行表 行向量 和列表 列向量 都相当于线性表 所以说 数组可看作是线性表的推广 将线性表推广到二维或高维 就是我们所说的数组 如上例的数组A 可表示为 Am n a11 a1n a21 a2n am1 amn Am n a11 am1 a12 am2 a1n amn 在C语言中 把一个二维数组看作是一种特殊的一维数组 该一维数组的元素又是一个一维数组 例如定义 inta 3 4 中 可以把a看作是一个一维数组 它有3个元素 a 0 a 1 a 2 每个元素又是一个包含4个元素的一维数组 同样 一个三维数组可以用其数据元素为二维数组的线性表来定义 依次类推 n维数组是由数据元素为n 1维数组的线性表构成 数组通常有两种基本操作 给定下标 存取相应的数据元素 给定下标 修改相应数据元素的值 数组不能进行元素的插入和删除操作 1 数组的顺序存储结构数组的顺序分配就是用向量作为数组的存储结构 但是二维以上的多维数组 不像一维数组那样 所有的元素已经排成一个序列 所以要把多维数组顺序地存储到一维顺序的存储器中 则必须对多维数组里的元素存放顺序做出一些规定 通常数组采用两种顺序存储方式 1 行优先顺序存储行优先顺序存储就是数组元素按行表次序进行存储 即第i 1个行表紧跟在第i个行表后面进行存储 在C BASIC PASCAL COBOL等高级语言中均采用这种方法 以二维数组Am n为例 按行优先顺序存储的数组元素次序为 a11 a12 a1n a21 a22 a2n am1 am2 amn 2 列优先顺序存储列优先顺序存储就是数组元素按列表次序进行存储 即第j 1个列表紧跟在第j个列表后面进行存储 在FORTRAN语言中 数组是按列优先顺序组织存储 以二维数组Am n为例 按列优先顺序存储的数组元素次序为 a11 a21 am1 a12 a22 am2 a1n a2n amn 同样 对n维数组也有上述两种不同的顺序分配的存储结构 当把n维数组的元素这样顺序地存放在存储器里 则每个元素的存储地址可以用公式计算出来 这些计算公式称为 地址公式 图2 31二维数组的两种存储方式 假设每个数据元素占L个存储单元 则可得 1 一维数组的地址公式为 Loc ai Loc a1 i 1 L 2 若存储分配采用行优先顺序分配 则二维数组Am n的地址公式为 Loc aij Loc a11 i 1 n j 1 L 同理 可写出三维数组 n维数组的数组元素存储地址的计算公式 3 若存储分配采用列优先顺序分配 则二维数组Am n的地址公式为 Loc aij Loc a11 j 1 m i 1 L同理 可写出三维数组 n维数组的数组元素存储地址的计算公式 2 矩阵的压缩存储通常在实际计算中经常出现一些阶数很高的矩阵 同时矩阵中有许多值相同的元素或者零元素 有时为了节省存储空间 可以对这类矩阵进行压缩存储 所谓压缩存储是指 为多个值相同的元素只分配一个存储空间 对零元素不分配空间 1 特殊矩阵假若值相同的元素或零元素在矩阵中的分布有一定规律 则称此类矩阵为特殊矩阵 像三角矩阵 对称矩阵 三对角矩阵等都属于特殊矩阵 例 下三角矩阵An n 当i j时 aij 0 A a110 0a21a22 0an1an2 ann 在下三角矩阵中 对角线以上元素全部为0 我们只需存储下三角的元素 特殊矩阵的压缩存储实际上就是把二维数组的数据元素压缩到一维数组上 即要在下标 i j 与下标 k 之间建立一个映像关系 使得对二维数组的存取操作通过一维数组来完成 假设以一维数组Sa 1 n n 1 2 作为n阶下三角矩阵A的存储结构 则Sa k 和矩阵元素aij之间存在着一一对应关系 k i i 1 2 j n阶对称矩阵A的压缩存储如图2 32所示 Loc aij Loc a11 i i 1 2 j 1 其地址公式为 图2 32对称矩阵A的压缩存储 2 稀疏矩阵如果一个矩阵中大多数元素为零 非零元素较少且分布无一定规律 这类矩阵称之为稀疏矩阵 在存储稀疏矩阵时 为了节省存储单元 很自然的方法就是只存非零元素 由于每个矩阵元素可由它的行号和列号惟一地确定 这样稀疏矩阵中的每个非零元素就由一个三元组 i j val 惟一确定 其中 i是行号 j是列号 val是非零元的数值 整个稀疏矩阵可用一个三元组表表示 三元组表以非零元行号递增的顺序排列 例稀疏矩阵M6 5 M 300000000000005200000006010000 共有30个元素 仅有5个非零元 其三元组表如图2 33所示 图2 33表示矩阵M的三元组表 2 6 2串从数据结构的角度来看 串是一种每个数据元素仅由一个字符组成的特殊线性表 随着数据处理技术的发展 串在文字编辑 符号处理 词法分析 信息检索 自然语言翻译等方面的应用越来越广泛 越来越多的程序设计语言支持串作为一种变量类型 参加各种运算 本节将讨论串的基本概念 基本操作及存储方法 1 串及其操作1 串串 String 是由零个或多个字符组成的有限序列 一般记为 S a1a2 an n 0 其中 S是串的名 用单引号括起来的字符序列是串的值 ai 1 i n 可以是字母 数字或其它字符 串中字符的数目n称为串的长度 零个字符的串称为空串 nullstring 它的长度为零 为了清楚起见 以后用符号 来表示 空串 串中任意个连续的字符组成的子序列称为该串的子串 包含子串的串相应地称为主串 通常称字符在序列中的序号为该字符在串中的位置 子串在主串中的位置则以子串的第一个字符在主串中的位置来表示 例串名为A B C D的四个串如下 A verygood B C D good 串A的长度是9 串B的长度为3的空格串 串C中不包含任何字符 是空串 长度为零 串D的长度是4 显然串D是串A的子串 串A是串D的主串 串D在主串A中的位置是6 当两个串的长度相等 并且各个对应位置上的字符都相等时 称两个串是相等的 2 串的基本操作常用的串的基本操作有七种 1 ASSIGN s t 和C