第2章顺序表 BSj-i-1=B[j;ns+-:·Bs为B的子表* if (ms--ns &&ms==0)printf("A-BVie if (ms==0&.& ns>0)i!(ms>4<x ns>0&xAS[1<BS 1: printf"A>Bn”); .有两个向量A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列编 写一个函数将它们合并成一个向量C要求C的元素也是以从小到大的升序排列。 解:本题的算法思想是:依次扫描通过A和B的元素比较当前的元素的值,将较小值 的元素赋给C,如此直到一个向量扫描完毕,然后将未完的一个向量的余下所有元素赋给C 即可:实现本题功能的函数如下 void ink(A, B: vector :m, n: integer VAR C: vector vector A.B. C: nti=1,=1k=1,; whe(i<=m&&.κ=n)/扫描通过A和B,将当前扫描的较小元素赋给C* i(A[1<B[j) k=A[i:;i+-;k→ if (i==n) 当A未完时,当A的余下元素赋给C for(=(+1):<=m|-+) CLk_=ALl_:k x当B未完时,当B的余下元素賦给C j-1:<=n;-)
数据结构习题与解析(C语言篇) 2.3.2栈 1.对于一个栈给出输入项ABC。如果输入项序列由A,B,C所组成,试给出全部可 能的输出序列。 解:本题利用栈的“后进先出”的特点,有如下几种情况 A进A出B进B出C进C出产生输出序列ABC A进A出B进C进C出B出产生输出序列ACB A进B进B出A出C进C出产生输出序列BAC A进B进B出C进C出A出产生输出序列BCA A进B进C进C出B出A出产生输出序列CBA 不可能产生输出序列CAB 2有字符串次序为3“-y-B/y↑2,试利用栈排出将次序改变为3y-*ay↑/-的操 作步骤。(可用X代表扫描该字符串函数中顺序取一字符进栈的操作,用S代表从栈中取出 字符加到新字符串尾的出栈的操作)。例如:ABC变为BCA,则操作步骤为 XXSXSS 解:实现上述转换的进出栈操作如下: 进3出*进一进y进y出一出*出一进a进 a出/进y进y出↑进2进2出↑出/出一出 所以操作步骤为: XSXXXSSSXXSXXSXXSSSS 莱3.有两个栈s1和s2共享存储空间c[1,m],其中一个栈底设在c[1]处,另一个栈底 设在cm0]处,分别编写s1和s2的进栈push(i,x)退栈pop()和设置栈空senu(i)的函 数其中i1,2。注意:仅当整个空间c[1,m0]占满时才产生上溢。 解:该共享找的结构如图2.3所示,两栈的最多元素个数为m0,topl是栈1的找指针 op2是栈2的找指针,当top2=top1+1时出现上溢出,当topl=0时栈1出现下溢出,当 top2=m0+1时栈2出现下溢出。根据上述原理得到如下函数: topl top2 c的元素序号1 b 栈1底 找1頂 栈2底 图2.3共享栈
第2章顺序表 topl,top2和m均为L初值的int型全屙变坻x void push(xi int x.ii if(topl==top2-1) printf("上溢出!Ⅶ”); i(*孙第个找进行入找操作 ese“对第二个栈进行入找操作 函数pop void pop(i) if(i=≠k)对第个找进行出找操作* 栈1下溢出!") cLtop1]:top else‘*对第二个栈进行出栈操作 it(top2==m0+1) printf(找2下溢出!n 函数 setula setout(i) int i ifi==1)tpl=日; 4.证明:有可能从初始输入序列1,2,,n,利用一个栈得到输出序列p1p2…p .,pn是1,2,,n的一种排列)的充分必要条件是:不存在这样的i,j,k满足还j <k同时p<p<
数据结构习题与解析C语言篇) 证明:【充分条件】如果不存在这样的k满足<j<k同时p<P<p,即对于输入序 p p (p」<p<p) 不存在这样的输出序列: pi (或简单地对于输入序列12,3不存在输出序列3,1,2) 从中看到,p后进先出,是满足栈的特点因为p最大也就是在p和pk之后进入,却在 输出序列中排在p和p之前,同时也说明,在pk之前先进入的p不可能在px之后出来,反 过来说明满足先进后出的特点,所以构成一个栈。 【必要条件】如果初始输入序列是1,2,n,假设是进栈,又同时存在这样的i,jk满 足还<j<k同时p<p<P,即对于输入序列: (p<p<p;) 存在这样的输出序列: 从中看到,p先进后出,是满足栈的特点,因为p最大也就是在p和pk之后进入同时 看到在p之前先进入的p却在p之前出来,反过来说明不满足先进后出的特点,与前面的 假设是找不一致,本题即证。 5.假定一个有n个“栈”的铁路转轨网络,如图2.4所示n=4时的情况。初始时有2 列列车位于网络右边。试证明:通过实施一系列适当的操作(要求操作的方向与图中箭头的 方向相一致),最终在左边可形成2!种不同的列车排列顺序。 注:假设每个栈足以容纳所有的列车。 图2.44个铁路栈 证明:本题若能证明在上述条件下,对于输入序列 a1,a2,an(a表示一列列车,m=2) 产生的输出序列可以是任意的a1,a2,,am的排列组合,那么根据排列组合的原理输 出的排列顺序是2!种,下面我们利用数学归纳法来证明满足这种情况。 当n=1时,输入序列为a1a2,显然通过一个栈后的输出序列可以为a1a2和a2,a1即输 出序列为21!=2种。 假设m=n时成立,即21-1列列车通过n个“栈后可以产生这2列列车的任意排列序
第2章顺序表 列 当m=n+1时,对于要求产生的任意输出序列: aa1,ag,,a(k=2",共有k+k=2k=2列列车) 先通过第一个“栈”将初始序列: 中的a1,a2,ajk这k列列车不考虑顺序进入第一个“找”,余下的a1a (不 考虑顺序)不入第一个栈”,这样将输入序列分成两部分,现在还余下n个“栈”,依前面的假 设,先可以将未入第一个“栈”的a1a,ak(不考虑顺序)通过后面的n-1“栈”产生有序 的输出序列: 然后对于入第一个“栈"的序列a1a2…,,(不考虑顺序)通过后面的n-1“栈”产生 有序的输出序列: 1·逻 这样便产生最终输出序列: Ai2· 为此我们证明本题 6.假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,编写一个判 别表达式中括弧是否正确配对的函数 correct(exp,tag);其中exp为字符串类型的变址,表 示被判别的表达式,tag为布尔型变量。 解:本题使用一个栈s进行判定,将'('、['或’{’入栈,当遇到)′、]'或'}'时,检查 当前栈顶元素是否是对应的(、[或{,若是则退栈,否则返回表示不配对。当整个算术 表达式检查完毕时栈为空,表示括号正确配对;否则不配对。实现本题功能的函数如下: w define mn J00 /*m0为算术表达式中最多字符个数 correct(exp. tag while (i<=m(&& tag if (expir /*遇到'(,[‘或,则将其入伐