第02章_线性表(I)

李云清杨庆红揭安全 高等学校精品课程 人民邮电出版社 第2版 数据结构 第2版 第2章线性表及其顺序存储 线性表 顺序表 栈 队列 线性表是一种常用的数据结构 本章介绍线性表及其顺序存储 并对栈和队列及它们的顺序实现给出了详细的设计描述 2 1线性表 线性表是一个线性结构 它是一个含有n 0个结点的有限序列 对于其中的结点 有且仅有一个开始结点没有前驱但有一个后继结点 有且仅有一个终端结点没有后继但有一个前驱结点 其它的结点都有且仅有一个前驱和一个后继结点 一般地 一个线性表可以表示成一个线性序列 k1 k2 kn 其中k1是开始结点 kn是终端结点 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 例3学生健康情况登记表如下 例4 一副扑克的点数 2 3 4 J Q K A 从以上例子可看出线性表的逻辑特征是 在非空的线性表 有且仅有一个开始结点a1 它没有直接前趋 而仅有一个直接后继a2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前趋an 1 其余的内部结点ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 2 2 1顺序表 线性表采用顺序存储的方式存储就称之为顺序表 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中 如顺序表的每个结点占用len个内存单元 用location ki 表示顺序表中第i个结点ki所占内存空间的第1个单元的地址 则有如下的关系location ki 1 location ki lenlocation ki location k1 i 1 len 2 2顺序表 顺序表的存储结构如下图所示 存储结构要体现数据的逻辑结构 顺序表的存储结构中 内存中物理地址相邻的结点一定具有顺序表中的逻辑关系 存储地址location k1 location k1 i 1 len 结点序号12in lenlen len len 2 2 2顺序表的实现 用C语言中的数组存储顺序表 C语言中数组的下标是从0开始的 即数组中下标为0的元素对应的是顺序表中的第1个结点 数组中下标为i的元素对应的是顺序表中的第i 1个结点 为了方便 将顺序表中各结点的序号改为和对应数组元素的下标序号一致 即将顺序表中各结点的序号从0开始编号 这样 一个长度为n的顺序表可以表示为 k0 k1 k2 kn 1 顺序表的存储结构的C语言描述如下 顺序表的头文件 文件名sequlist h defineMAXSIZE100typedefintdatatype typedefstruct datatypea MAXSIZE intsize sequence list 表长 顺序表的几个基本操作的具体实现 函数功能 顺序表的初始化 置空表 函数参数 指向sequence list型变量的指针变量slt 函数返回值 空 文件名 sequlist c 函数名 init voidinit sequence list slt slt size 0 算法2 1顺序表的初始化 置空表 函数功能 在顺序表后部进行插入操作 函数参数 指向sequence list型变量的指针变量slt datatype类型的变量x 函数返回值 空 文件名 sequlist c 函数名 append voidappend sequence list slt datatypex if slt size MAXSIZE printf 顺序表是满的 exit 1 slt a slt size x slt size slt size 1 算法2 2在顺序表后部进行插入操作 打印顺序表的各结点值 函数功能 打印顺序表的各结点值 函数参数 sequence list型变量slt 函数返回值 空 文件名 sequlist c 函数名 display voiddisplay sequence listslt inti if slt size printf n顺序表是空的 elsefor i 0 i slt size i printf 5d slt a i 算法2 3打印顺序表的各结点值 判断顺序表是否为空 函数功能 判断顺序表是否为空 函数参数 sequence list型变量slt 函数返回值 int类型 1表示空 0表示非空 文件名 sequlist c 函数名 empty intempty sequence listslt return slt size 0 1 0 算法2 4判断顺序表是否为空 查找顺序表中值为x的结点位置 函数功能 查找顺序表中值为x的结点位置 函数参数 sequence list型变量slt datatype型变量x 函数返回值 int类型 返回x的位置值 1表示没找到 文件名 sequlist c 函数名 find intfind sequence listslt datatypex inti 0 while i slt size 算法2 5查找顺序表中值为x的结点位置 取得顺序表中第i个结点的值 函数功能 取得顺序表中第i个结点的值 函数参数 sequence list型变量slt int型变量i 函数返回值 datatype类型 返回第i个结点的值 文件名 sequlist c 函数名 get datatypeget sequence listslt inti if i slt size printf n指定位置的结点不存在 exit 1 elsereturnslt a i 算法2 6取得顺序表中第i个结点的值 顺序表的插入运算是将一个值为x的结点插入到顺序表的第i个位置0 i n 即将x插入到ki 1和ki之间 如果i n 则表示插入到表的最后 一般地可表示为 插入前 k0 k1 ki 1 ki kn 1 插入后 k0 k1 ki 1 x ki kn 1 插入过程的图示见下图 函数功能 在顺序表的position位置插入值为x的结点 函数参数 指向sequence list型变量的指针变量slt datatype型变量x int型变量position 函数返回值 空文件名 sequlist c 函数名 insert voidinsert sequence list slt datatypex intposition inti if slt size MAXSIZE printf n顺序表是满的 没法插入 exit 1 if positionslt size printf n指定的插入位置不存在 exit 1 for i slt size i position i slt a i slt a i 1 slt a position x slt size 算法2 7在顺序表的position位置插入值为x的结点 算法2 7中 所花费的时间主要是元素后移操作 对于在第i个位置上插入一个新的元素 需要移动 n i 个元素 设在第i个位置上插入一个元素的概率为pi 且在任意一个位置上插入元素的概率相等 即p0 p1 p2 pn 1 n 1 则在一个长度为n的顺序表中插入一个元素所需的平均移动次数为 即在长度为n的顺序表中插入一个元素平均需要移动表中的一半元素 该算法的时间复杂度为O n 顺序表的删除操作是指删除顺序表中的第i个结点 0 i n 1 一般地可表示为 删除前 k0 k1 ki 1 ki ki 1 kn 1 删除后 k0 k1 ki 1 ki 1 kn 1 删除过程的图示见下图 删除操作的具体实现见算法2 8 函数功能 删除顺序表中第position位置的结点 函数参数 指向sequence list型变量的指针变量slt int型变量position 函数返回值 空文件名 sequlist c 函数名 dele voiddele sequence list slt intposition inti if slt size 0 printf n顺序表是空的 exit 1 if position slt size printf n指定的删除位置不存在 exit 1 for i position isize 1 i slt a i slt a i 1 slt size 算法2 8删除顺序表中第position位置的结点 要删除顺序表中的第i个结点 则需要称动 n i 1 个元素 设删除表中第i个结点的概率为qi 且在表中每一个位置删除的概率相等 即 q0 q1 qn 1 1 n则在一个长度为n的顺序表中删除一个结点的平均移动次数为 这表明 在一个长为n的顺序表中删除一个元素平均需要移动表中大约一半的元素 该算法的时间复杂度为O n 2 3栈 2 3 1栈 栈是一种特殊的线性表 对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行 进行插入和删除的那一端称为栈顶 另一端称为栈底 栈的插入操作和删除操作也分别简称进栈和出栈 如果栈中有n个结点 k0 k1 k2 kn 1 k0为栈底 kn 1是栈顶 则栈中结点的进栈顺序为k0 k1 k2 kn 1 而出栈的顺序为kn 1 kn 2 k1 k0 如图所示 栈具有后进先出或先进后出 FILO FirstInLastOut 的性质 2 3 2顺序栈及其实现 栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行 所以同顺序表一样也可用一维数组表示 一般地 可以设定一个足够大的一维数组存储栈 数组中下标为0的元素就是栈底 对于栈顶 可以设一个指针top指示它 为了方便 设定top所指的位置是下一个将要插入的结点的存储位置 这样 当top 0时就表示是一个空的栈 一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示 栈的顺序存储结构的C语言描述如下 栈 顺序存储 的头文件 文件名seqstack h defineMAXSIZE100typedefintdatatype typedefstruct datatypea MAXSIZE inttop sequence stack 下面是顺序存储栈的几个基本操作的具体实现 栈 顺序存储 初始化 文件名seqsinit c 函数名init sequence stack voidinit sequence stack sequence stack st st top 0 算法2 9栈 顺序存储 初始化 说明 top 0表示栈空 这种情况下栈顶指示位内容始终为空 判断栈 顺序存储 是否为空 文件名seqsempt c 函数名is empty sequence stack intis empty stack sequence stackst return st top 0 1 算法2 10判断栈 顺序存储 是否为空 取得栈顶 顺序存储 结点值 文件名seqsfirs c 函数名get top datatypeget top sequence stackst if empty stack st printf n栈是空的 exit 1 elsereturnst a st top 1 算法2 11取得栈顶 顺序存储 结点值 顺序栈的进栈与出栈操作 设有类型定义 sequence stacks 下图表明进出栈情况 543210 top a 空栈 543210 A b A进栈 543210 1 A c B C D进栈 B C D 543210 A d D C出栈 B C D 543210 e E进栈 E 543210 f E B A出栈 函数功能 栈 顺序存储 的插入 进栈 操作 函数参数 指向sequence stack型变量的指针变量st datatype型变量x 函数返回值 空 文件名 seqstack c 函数名 push voidpush sequence stack st datatypex if st top MAXSIZE printf nThesequencestackisfull exit 1 st a st top x st top 算法2 12栈 顺序存储 的插入操作 函数功能 栈 顺序存储 的删除 出栈 操作 函数参数 指向sequence stack型变量的指针变量st 函数返回值 空 文件名 seqstack c 函数名pop voidpop sequence stack st if st top 0 printf nThesequencestackisempty exit 1 st top 算法2 13栈 顺序存储 的删除操作 思考 如果将栈空表示为top 1 则所有栈的所有操作为何变化呢 2 3 3栈的应用之一 括号匹配 设一个表达式中可以包含三种括号 小括号 中括号和大括号 各种括号之间允许任意嵌套 如小括号内可以嵌套中括号 大括号 但是不能交叉 举例如下 正确的 正确的 正确的 不正确的 不正确的 如何去检验一个表达式的括号是否匹配呢 大家知道当自左向右扫描一个表达式时 凡是遇到的开括号 或称左括号 都期待有一个和它对应的闭括号 或称右括号 与之匹配 按照括号正确匹配的规则 在自左向右扫描一个表达式时 后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配 函数功能 判断表达式括号是否匹配 函数参数 char类型数组c 函数返回值 int类型 返回1为匹配 返回0为不匹配 文件名 seqmatch c 函数名 match kouhao intmatch kuohao charc inti 0 sequence stacks init while c i switch c i case case case push 栈为空则匹配 否则不匹配 算法2 14判断表达式括号是否匹配 算术表达式通常是由操作数 算术运算符和一对圆括号 和 组合而成 其中操作数允许是程序语言中任意合法的变量名或常数 以下我们讨论 四种算术运算 表达式求值中的首要问题 如何确定表达式中所含运算的计算次序 算术运算的规则 1 先乘除 后加减2 从左算到右3 先括号内 后括号外 2 3 4栈的应用之二 算术表达式求值 按此原则 算术表达式A B C D 的运算次序为 A B C D 而不是A B C D 1 2 3 1 2 3 问题 如何让计算机也遵守算术运算规则 正确计算表达式的值 方法1 加括号 即对每个一运算都用一对括号将与其配对的左 右操作对象括在一起 由此上面算术表达式将写成 A B C D 利用栈求表达式的值 1 自左至右的扫描加括号的算术表达式2 将非右括号 的符号进栈3 每当遇见右括号 从栈顶向下扫描至第一个左括号 这就是和遇见的右括号 配对的左括号 该左括号 上面的表达式就是现在应该计算的表达式 从栈中弹出对应的左括号 以上的所有符号 含左括号 计算相应表达式 并将结果压入栈中 重复1 2 3 即可计算出表达式的值 特点 方法简单明了 但要求人们事先为要计算的表达式加好括号 这既繁琐 又易出错 方法2 重新改写表达式为后缀表达式 在计算机中 表达式可以有三种不同的标识方法设Exp S1 OP S2则称OP S1 S2为表达式的前缀表示法称S1 OP S2为表达式的中缀表示法称S1 S2 OP为表达式的后缀表示法 可见 它以运算符所在不同位置命名的 例 中缀表达式后缀表达式 1 AA 2 A BAB 3 A B CABC 4 A B C DABC D 5 D A B C DABC 结论 操作数之间的相对次序不变 运算符的相对次序不同 后缀表达式中没有括号 运算符排在其第二个操作数之后 前缀式的运算规则为 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式 后缀式的运算规则为 运算符在式中出现的顺序恰为表达式的运算顺序 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式 四则运算的计算方法 第一步 将中缀表达式转换成等价的后缀表达式第二步 使用后缀表达式进行计算 算法 利用后缀表达式求值 基本思想 1 从左到右扫描后缀表达式 遇到操作对象进栈 2 遇到运算符 弹出栈顶的元素 其中栈顶为第二操作对象 次栈顶为第一操作对象 对其按遇到的运算符进行运算 并将结果进栈 重复上述动作最后即可求出表达式的值 例如有中缀表达式 A B C D E其对应的后缀表达式为 AB CD E 利用后缀表达式求值过程如下所示 步骤操作数栈后缀表达式说明 1AB CD E 初始栈空 A进栈 2AAB CD E B进栈 3ABAB CD E 遇 弹出栈顶两元素做A B 并将其进栈 4 AB CD E C进栈 5 CAB CD E D进栈 步骤操作数栈后缀表达式说明 6 CDAB CD E 遇 弹出CD做C D 并将其进栈 7 AB CD E E进栈 8 EAB CD E 遇 弹出栈顶两元做 E 并将结果进栈 9 AB CD E 遇 弹出栈顶二元做 并将结果进栈 10 AB CD E 遇 结束 栈顶就是表达式的计算结果 在实际应用中 操作数可设为实数 且两个实数间用空格隔开 问题 后缀表达式为字符串 如何从其中分离出每一个操作数 解决办法 用函数Readnumber 实现将扫描到的数字字符序列转换成相应实数 floatreadnumber charf int i floatx 0 0 intk 0 while f i 0 while f i 0 处理整数部分 处理小数部分 跳过小数点 后缀表达式求值程序如下 floatevalpost charf floatobst 50 操作数栈 inti 0 top 1 floatx while f i 0 此处 0 为结束符 if f i 0 空格 elseif f i x obst top 加 obst top x obst top i elseif f i 减 x obst top obst top obst top x i elseif f i 乘 x obst top obst top obst top x i elseif f i 除 x obst top obst top obst top x i returnobst top 栈顶元即为表达式的值 算法 将中缀表达式转换为后缀表达式 根据中缀表达式与后缀表达式的特点 可得将中缀表达式变换为后缀表达式的方法 1 操作数的排列次序不变2 把每一运算符从第二操作数之前排到第二操作数之后3 删去所有括号 关键问题 如何找到一个运算符的第二个操作数的结束位置 四则运算的优先级如下 我们知道 在表达式A B C中 运算的第二个运算对象是B 这是因为 运算的优先数比 运算的优先数高 这启发我们 对一般地形如Aop1Bop2C的表达式若运算符op1的优先数大于或等于op2的优先数 则op2就标记了op1的第二个操作数的结束位置 同理形如 Aop1B 和Aop1B 的式子中的 和 显然也分别标记了op1的第二个操作数的结束位置 算法基本思想 1 从左到右扫描中缀表达式数组e2 对e中的每个元素e i 分情况处理 0 9 或 放入后缀表达数组f 且指针加1 运算符 先将 符放入f中 且指针加1 以便用空格分开两个操作数 当其优先数小于等于栈顶符号时 反复将栈顶符号弹出放入f数组当前空位且指针加1 最后将该运算符进栈 将其压入运算符栈 当运算符栈顶符号不是左括号 时 反复将栈顶符号弹出放入f当前空位且指针加1 最后将栈顶符出栈 此时栈顶符号为 将运算符栈中符号依次弹出放入f数组当前空位且指针加1 直到运算符栈栈顶为 号转换完成 初始时 运算符栈中为 中缀转后缀程序 voidpostfix chare charf seqstackopst inti j initstack 数字 elseif e i 左括号 push 用空格分开两个操作数 while priority stacktop 判断是否为运算符intis op charop switch op case case case case return1 default return0 返回运算符的优先级intpriority charop switch op case return0 case case return1 case case return2 default return 1 两个辅助函数 本题源程序后缀式 c 2 4队列 2 4 1队列 队列是一种特殊的线性表 它的特殊性在于队列的插入和删除操作分别在表的两端进行 插入的那一端称为队尾 删除的那一端称为队首 队列的插入操作和删除操作也分别简称进队和出队 对于一个队列 k0 k1 k2 kn 1 则k0是这些结点中最先插入的结点 若要做删除操作 k0将首先被删除 所以说 队列是具有 先进先出 FIFO FirstInFirstOut 特点的线性结构 队列类型的描述如下 ADTsequence queue 数据集合K K k1 k2 kn n 0 K中的元素是datatype类型 数据关系R R r r i 1 2 n 1 操作集合 1 voidinit sequence queue sq 队列 顺序存储 初始化 2 intempty sequence queuesq 判断队列 顺序存储 是否为空 3 voiddisplay sequence queuesq 打印队列 顺序存储 的结点值 4 datatypeget sequence queuesq 取得队列 顺序存储 的队首结点值 5 voidinsert sequence queue sq datatypex 队列 顺序存储 的插入操作 6 voiddele sequence queue sq 队列 顺序存储 的删除操作 ADTsequence queue 2 4 2顺序队列及其实现 队列的顺序存储在C语言中可以用一维数组表示 为了标识队首和队尾 需要附设两个指针front和rear front指示的是队列中最前面 即队首结点在数组中元素的下标 rear指示的是队尾结点在数组中元素的下标的下一个位置 也就是说rear指示的是即将插入的结点在数组中的下标 队列的几种状态 队列的顺序存储结构的C语言描述如下 队列 顺序存储 的头文件 文件名seqqueue h defineMAXSIZE100typedefintdatatype typedefstruct datatypea MAXSIZE intfront intrear sequence queue 顺序存储队列的几个基本操作的具体实现 函数功能 队列 顺序存储 初始化 函数参数 指向sequence queue类型变量的指针变量sq 函数返回值 空 文件名 seqqueue c 函数名 init voidinit sequence queue sq sq front sq rear 0 算法2 20队列 顺序存储 初始化 函数功能 判断队列 顺序存储 是否为空 函数参数 sequence queue类型变量sq 函数返回值 int类型 返回1表示空 0表示非空 文件名 seqqueue c 函数名 empty intempty sequence queuesq return sq front sq rear 1 0 算法2 21判断队列 顺序存储 是否为空 函数功能 打印队列 顺序存储 的结点值 函数参数 sequence queue类型变量sq 函数返回值 空 文件名 seqqueue c 函数名 display voiddisplay sequence queuesq inti if empty sq printf n顺序队列是空的 elsefor i sq front i sq rear i printf 5d sq a i 算法2 22打印队列 顺序存储 的结点值 函数功能 取得队列 顺序存储 的队首结点值 函数参数 sequence queue类型变量sq 函数返回值 datatype类型 返回队首结点值 文件名 seqqueue c 函数名 get datatypeget sequence queuesq if empty sq printf n顺序队列是空的 无法获得队首结点值 exit 1 returnsq a sq front 算法2 23取得队列 顺序存储 的队首结点值 函数功能 队列 顺序存储 的插入 进队 操作 函数参数 指向sequence queue类型变量的指针变量sq datatype类型的变量x 函数返回值 空文件名 seqqueue c 函数名 insert voidinsert sequence queue sq datatypex inti if sq rear MAXSIZE printf n顺序队列是满的 exit 1 sq a sq rear x sq rear sq rear 1 算法2 24队列 顺序存储 的插入操作 函数功能 队列 顺序存储 的删除 出队 操作 函数参数 指向sequence queue类型变量的指针变量sq 函数返回值 空 文件名 seqqueue c 函数名 dele voiddele sequence queue sq if sq front sq rear printf n顺序队列是空的 不能做删除操作 exit 1 sq front 算法2 25队列 顺序存储 的删除操作 在队列的几种状态图的 e 状态中 队列是一种队满状态 将不能再插入新的结点 而实际上数组的前部还有许多空的位置 为了充分地利用空间 可以将队列看作一个循环队列 在数组的前部继续作插入运算 这就是循环队列 2 4 3顺序循环队列及其实现 给定一个大小为MAXSIZE的数组存储一个队列时 经过若干次插入和删除操作后 当队尾指指rear MAXSIZE时 呈现队列满的状态 而事实上数组的前部可能还有空闲的位置 为了有效利用空间 将顺序存储的队列想象为一个环状 把数组中的最前和最后两个元素看作是相邻的 这就是循环队列 在循环队列中进行出队 入队操作时 头尾指针仍要加1 朝前移动 只不过当头尾指针指向向量上界 MaxSize 1 时 其加1操作的结果是指向向量的下界0 这种循环意义下的加1操作可以描述为 if rear 1 MaxSize rear 0 elserear 利用模运算可简化为 rear rear 1 MaxSize 队空 队满 如图所示 由于入队时尾指针向前追赶头指针 出队时头指针向前追赶尾指针 故队空和队满时头尾指针均相等 因此 我们无法通过front rear来判断队列 空 还是 满 本书采用牺牲一个数组元素的空间 即若数组的大小是MAXSIZE 则该数组所表示的循环队列最多允许存储MAXSIZE 1个结点 这样 循环队列满的条件是 rear 1 MAXSIZE front循环队列空的条件是rear front 解决此问题的方法至少有三种 其一是另设一个布尔变量以匹别队列的空和满 其二是少用一个元素的空间 约定入队前 测试尾指针在循环意义下加1后是否等于头指针 若相等则认为队满 注意 rear所指的单元始终为空 其三是使用一个计数器记录队列中元素的总数 实际上是队列长度 循环队列的插入与删除操作的实现 函数功能 循环队列 顺序存储 的插入操作 函数参数 指向sequence queue类型变量的指针变量sq datatype类型的变量x 文件名 secqinse c 函数名 insert sequence cqueue voidinsert sequence cqueue sequence queue sq datatypex if sq rear 1 MAXSIZE sq front printf n顺序循环队列是满的 无法进行插入操作 exit 1 sq a sq rear x sq rear sq rear 1 MAXSIZE 算法2 26循环队列 顺序存储 的插入操作 循环队列 顺序存储 的删除操作 函数功能 循环队列 顺序存储 的删除操作 函数参数 指向sequence queue类型变量的指针变量sq 函数返回值 空 文件名secqdele c 函数名dele sequence cqueue voiddele sequence cqueue sequence queue sq if sq front sq rear printf n循环队列是空的 无法进行删除操作 exit 1 sq front sq front 1 MAXSIZE 算法2 2