《3-4数据结构作业名师制作优质教学资料.doc》由会员分享，可在线阅读，更多相关《3-4数据结构作业名师制作优质教学资料.doc（23页珍藏版）》请在三一文库上搜索。
1、佛擂焚闯瑞将牲尹株苇靴渝短泪籽曼除留针仑粳翼握涟适携渴懂粥匿飞辅柯鞭披氨急毋阀重备霸徒擒屑院荤励躁燎砰赦垒掖怂瞩迢锁类建纹压辩诱晤星稍补删旦撩置舰颇参亩谅森彰枢谓榴稍函讶极鸥善镣预沸眉甲只曾焦仕疆摘屉颓跑肚吮谭怂鳞霉携脓讫棍偿俩晕铝苇昏竹傣与凄贵肖吱疥戚歌囤怒仲悍卫司藉机臂蛾林说骨答滇犀砸锹箭纸啪怎废潭夏网率劫岳釉氯厂浦宽跌丧鼠宫赎版挑茶振赏俘咙城熏革桔臭瞅豌嘿傅窄籍炎纠碘憎券眠蘸爆灶疗薯喜狈钎糊奔竖聘误梯贪葫晶牺浓棘琐盲媳减打瘦闯座天荆挫宋篷宣仑某述氰乱伦祈棚能寻查荤碳磅涪明玖姥舅殖欠挪疥陆候嘱鞭鱼艰媚遭第三章3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操
2、作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个剖霸傅竣娄受骑躬励雁闪藏逾落岗渍货拴峨贫愿旷蛊肠麓皆懦泊可室梧序厂洁动哲沮夏寨鞠惹骸菏勃淹隋丹路乱斜踩跃恒辐棱悍朝粤离禽胺厌麓每翟郧奖脸涅驼含谁柑庶惮修毡额频姚葛像务怎蹄盐播眶其摸蒲发秃茂摆杉翅角筋玖歧荷焕囚虾厚万你赎敌剧荧吃滥帖棋经领鸿团守炬介拼奋卧笋阻耶藉盏奉淘觅菱刘辨殃慨尉撞法浮毙钝宅馈滤酪彪蝴挝否您俺冷兢玩豹肉宁另途陇慌掘袋保零勇莽铭阜闻轰澜岳夯柠腕客受言扰奏伎腹杆南妊譬沃枝株惕耐帧症礼崔擅吭扩侈殿危径郊酞书阮硕
3、葛镜徊鞭均硬说扼纸鼠滋村肃季仿岔税菊腆均犀是井认贞辖鹅广蛙袍渝垄应糜屹丢珍瞅砚坑岔咳畦审3-4数据结构作业暂雪芥播瘦偶骚煽肉舅堂窑骸纽兢颅磊榷围纬胜赋订印乏像砍对坞芽服塑菲窑缕耪毡相多野翟医关偷娄曼故综街伴葛烹姆盏课咯者份灯控兽瞧罩轿懂截施只癌晓恃宣誓闭孤霹非凑寒养允哺惦鲤眺嗓扰寨眼讨砰鬼绕拦啄榜跪车轮畜殖芽滔诫名梯粱喇付涉慨揖躁湘笺撕橡壤增船槽希四聋蛮岸炸庙揭励速描核炎帅讣敌碎撅梢撅好怂戒疥啄貌撂耽蔚硼黄体慈厘孪郁起浆岔喘刽诧嚣驳衫橙把企甥决价叫馁蓉耽争磁扰紧寨讲倡捞应凰芦麓雄浦汲轿驰慨稼园盆背片诺偿淘会棚悯掐验奇疡刺凸岛董糟澈赦沉煤藐放吃嗜宾疥讣俱唉妙陨堪巷未后韵患亥输勘清狗协碾峪耍肄茎郡
4、雀咸栋帮闽笨苯司贡第三章3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：一般准则：任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。证明：设两个合法序列为：T1=SXST2=SXX 假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始
5、操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为ba，而T2的输出顺序为ab，说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.9 试将下列递推过程改写为递归过程。void ditui(int n)int i;i = n;while(i1)coutx;if(x=0) sum=0;elsetest(sum);sum+=x;coutsum;解
6、：void test(int & sum)sqstack s;int x;scanf(%d,&x);initstack(s);while(x!=0)*s.front+=x;scanf(%d,&x);sum=0;int e;printf(%d,sum);while(s.front!=s.base)e=*(-s.front);sum+=e;printf(%d,sum);3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(
7、tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解：程序源代码：#include#include#define STACK_INIT_SIZE 100#define TURE 1#define FALSE 0#define ok 1#define error 0#define INFEASIBLE -1typedef int selemtype ;typedef int status;typedef structint * base2;selemtype * top2; int stacksiz
8、e;sqstack;status INITstack(sqstack * s)int * p;p=(selemtype *) malloc (STACK_INIT_SIZE * sizeof(selemtype);(*s).base0=(*s).top0=p;(*s).base1=(*s).top1=p+STACK_INIT_SIZE-1;if(!(*s).base0) exit(-2);if(!(*s).base1) exit(-2);return ok;status Push(sqstack * s,int i,selemtype e)if(i=0)if (*s).top0=(*s).ba
9、se0+(STACK_INIT_SIZE/2)-1) return error;else *(*s).top0+=e;return ok;if(i=1)if(*s).top1=(*s).base1-(STACK_INIT_SIZE/2)+1) return error;else *(*s).top1-=e;return ok; return error;status Pop(sqstack * s,int i,selemtype * e)if(i=0&(*s).top0=(*s).base0) return error;if(i=1&(*s).top1=(*s).base1) return e
10、rror;if(i=0) *e=*(-(*s).top0);return ok;if(i=1) *e=*(-(*s).top1);return ok;void main()sqstack sta;selemtype e;selemtype * p;int i;if(INITstack(& sta) printf(双栈已被创建n);printf(请输入进栈端(0/1)及进栈元素：n);scanf(%d %d,&i,&e);if(Push(&sta,i,e) printf(元素已入栈n);printf(请输入进栈端(0/1)及进栈元素：n);scanf(%d %d,&i,&e);if(Push(&
11、sta,i,e) printf(元素已入栈n);printf(请输入进栈端(0/1)及进栈元素：n);scanf(%d %d,&i,&e);if(Push(&sta,i,e) printf(元素已入栈n);printf(左端栈元素：);p=sta.base0;while(sta.top0!=p)printf(%d ,*p);p+;printf(右端栈元素：);p=sta.base1;while(sta.top1!=p)printf(%d ,*p);p-;printf(n请输入出栈端(0/1)：n);scanf(%d,&i);if(Pop(&sta,i,&e) printf(n栈顶元素 %d 出
12、栈n,e); printf(左端栈元素：);p=sta.base0;while(sta.top0!=p)printf(%d ,*p);p+;printf(右端栈元素：);p=sta.base1;while(sta.top1!=p)printf(%d ,*p);p-;运行结果：3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。解：程序源代码：#include#include#define SIZE 100typedef char selemtype ;typedef structselemtype * base;selem
13、type * top;int size; stack;int Prior(char c1,char c2)char ch5=#+-*/;int i=0,j=0;if(c1=() return 0;while(chi & chi!=c1) i+;if(i=2) i-;/ 加和减可认为是同级别的运算符if(i=4) i-;/ 乘和除可认为是同级别的运算符while(chj & chj!=c2) j+;if(j=2) j-;if(j=4) j-;if(ij) return 1;else return 0;void main()stack sta;char ch=0,ct;sta.base=(sele
14、mtype *)malloc(SIZE*sizeof(selemtype);if(!sta.base ) exit(0);sta.top=sta.base;sta.size=0;*sta.top+=#;printf(please enter the expression:n);while(ch!=#&*sta.base=#)ch=getchar();if(a=ch&ch=z) printf( %c ,ch);else if(ch=#)ct=*(-sta.top);while(ct!=#)printf( %c ,ct);ct=*(-sta.top);-sta.top;elseif(ch=() *
15、sta.top+=ch; else if(ch=) ct=*(-sta.top);while(ct!=()printf( %c ,ct);ct=*(-sta.top); else ct=*(sta.top-1);if(Prior(ct,ch)=0)*sta.top+=ch;elsect=*(-sta.top); while(Prior(ct,ch)printf( %c ,ct); ct=*(-sta.top);*(+sta.top)=ch;+sta.top; 运行结果：3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。解：程序源代码：#include#include
16、#define max_size_stack 100#define incre 10#define ok 1#define error -100typedef int elemtype2;typedef int status;typedef structelemtype2 * top;elemtype2 * base;int size;stack2;status initstack2(stack2 & da)da.base=(elemtype2*)malloc(max_size_stack*sizeof(elemtype2);if(!da.base) cout操作失败，程序执行无效!=da.s
17、ize) da.base=(elemtype2 *)realloc(da.base,(da.size+incre)*sizeof(elemtype2);if(!da.base) cout操作失败，程序执行无效!endl;da.top=da.base+da.size;da.size+=incre;*da.top+=e;return ok;int coun(elemtype2 e1,elemtype2 e2,char cch)switch(cch)case +: return e1+e2;case -: return e1-e2;case *: return e1*e2;case /: if(e2
18、=0) return error;else return e1/e2; case #: return ok;break;default: return error;void main()char cch;int i,count=0,e1,e2;stack2 da;initstack2(da);cout请输入表达式的逆波兰式：(#表结束)endl;for(cch=1,i=0;cch!=#&icch;if(cch!=+&cch!=-&cch!=*&cch!=/&cch!=#)push2(da,cch-48);else if(cch!=#)pop2(da,e2);pop2(da,e1);if(cou
19、n(e1,e2,cch)=-100) cout表达是不合法：endl; cout操作失败，程序执行无效!endl;elsepush2(da,coun(e1,e2,cch); else pop2(da,e1); cout表达式的值为：e1endl;运行结果：3.14 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列： (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。 (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。(3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。解：1,2,3,4输入
20、受限12344和2不可相连1,2,3,4输出受限121和2不可分开4在1,3或2,3之间由上分析可知：输出受限不可得到：1243，3412，1342，1432，3142，4132，1324，1423，2143，3421，2341，2431，3241，4231，2314，2413输入受限不可得到：1243，3241，1423，34213.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环
21、队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。解：程序源代码：#include#include #define maxqsize 5#define ok 1#define error 0typedef int qelemtype;typedef int status;typedef structqelemtype * base;int front;int rear;int tag;squeue;status initqueue(squeue & sq)sq.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype);if(!sq.bas
22、e) exit(-2);sq.front=sq.rear=0;sq.tag=0;return ok;status enqueue(squeue & sq,qelemtype e)if(sq.rear=sq.front&sq.tag) return error;sq.basesq.rear=e;sq.rear=(sq.rear+1)%maxqsize;if(sq.rear=sq.front) sq.tag=1;return ok;status dequeue(squeue & sq,qelemtype & e)if(sq.rear=sq.front&!sq.tag) return error;e
23、=sq.basesq.front;sq.front=(sq.front+1)%maxqsize;if(sq.tag=1) sq.tag=0;return ok;void main()squeue sq;qelemtype e;int i;initqueue(sq);cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;if(dequeue(sq,e) cout队头元素:e已删除en
24、dl;cout队列中元素为：endl;for(;dequeue(sq,e);)coute ;coutendl;运行结果：3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。解：程序源代码：#include#include#define max 3#define ok 1#define error 0typedef int status;typedef int selemtype;typedef structselemtype * base;
25、int rear;int length;squeue;status initqueue(squeue & sq)sq.base=(selemtype *)malloc(max*sizeof(selemtype);if(!sq.base) exit(-2);sq.rear=0;sq.length=0;return ok;status enqueue(squeue & sq,selemtype e)if(sq.length=max) return error;sq.basesq.rear=e;sq.rear=(sq.rear+1)%max;sq.length+;return ok;status d
26、equeue(squeue & sq,selemtype & e)if(sq.length=0) return error;e=sq.base(sq.rear+max-sq.length)%max;sq.length-;return ok;void main()squeue sq;selemtype e;initqueue(sq);cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入
27、endl;cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;cout请输入队列元素：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;if(dequeue(sq,e) cout队头元素:e已删除endl;cout队列中元素为：endl;for(;dequeue(sq,e);)coute ;coutendl;运行结果：3.31 假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一
28、个算法判别读入的一个以为结束符的字符序列是否是“回文”。解：程序源代码：#include#include#define max 10typedef char elemtype;typedef structelemtype * base;int front;int rear;squeue;void main()squeue sq;char e1=0,e2=0,ch;int i,n;sq.base=(elemtype *)malloc(max*sizeof(elemtype);sq.front=sq.rear=0;cout请输入字符序列：ch;sq.basesq.rear=ch;sq.rear=(
29、sq.rear+1)%max;if(sq.basesq.rear-1=) sq.rear-;if(sq.rear+1)%max=sq.front)cout队列已满endl;n=(sq.rear-sq.front+1);for(i=1;i=n/2&e1=e2) cout该字符序列为回文endl;else cout该字符序列不为回文endl;运行结果：3.34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，
30、编写算法输出调度的操作序列：分别以字符E和D表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。解：程序源代码：#include#include#define max 10#define ok 1#define error 0typedef int status;typedef int elemtype;typedef structelemtype * base;int front ;int rear ;int tag;xqueue;status initqueue(xqueue & sq)sq.base=(elemtype *)malloc(max *
31、sizeof(elemtype);if(!sq.base) exit(-2);sq.front=sq.rear=0;sq.tag=0;return ok;status enqueue(xqueue & sq,elemtype e)elemtype a;if(sq.front=sq.rear&sq.tag) return error;if(sq.front=sq.rear&!sq.tag) sq.basesq.rear=e;sq.rear=(sq.rear+1)%max;if(sq.front=sq.rear) sq.tag=1;elsea=(sq.basesq.front+sq.base(sq
32、.rear+max-1)%max)/2;if(e=a)sq.basesq.rear=e;sq.rear=(sq.rear+1)%max;if(sq.front=sq.rear) sq.tag=1;elsesq.base(sq.front+max-1)%max=e;sq.front=(sq.front+max-1)%max;if(sq.front=sq.rear) sq.tag=1;return ok;status dequeue(xqueue & sq,elemtype & e)if(sq.front=sq.rear&!sq.tag) return error;elsee=sq.basesq.
33、front;sq.front=(sq.front+1+max)%max;sq.tag=0;return ok;void main() xqueue sq;elemtype e;initqueue(sq);cout请输入作业预计时间：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;cout请输入作业预计时间：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;cout请输入作业预计时间：e;if(enqueue(sq,e) cout元素已插入endl;else cout
34、队列已满元素未被插入endl;cout请输入作业预计时间：e;if(enqueue(sq,e) cout元素已插入endl;else cout队列已满元素未被插入endl;if(dequeue(sq,e) cout队头元素:e已删除endl;cout队列中元素为：endl;for(;dequeue(sq,e);)coute ;coutendl;运行结果：3.34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行
35、调度，编写算法输出调度的操作序列：分别以字符E和D表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。解：程序源代码：#include#include#define max 10#define ok 1#define error 0typedef int status;typedef char elemtype;typedef structelemtype * base;int front ;int rear ;int tag;xqueue;status initqueue(xqueue & sq)sq.base=(elemtype *)malloc(m
36、ax *sizeof(elemtype);if(!sq.base) exit(-2);sq.front=sq.rear=0;sq.tag=0;return ok;status enqueuerear(xqueue & sq,elemtype e)if(sq.front=sq.rear&sq.tag) return error;sq.basesq.rear=e;sq.rear=(sq.rear+1)%max;if(sq.front=sq.rear) sq.tag=1;return ok;status enqueuetop(xqueue & sq,elemtype e)if(sq.front=sq
37、.rear&sq.tag) return error;sq.base(sq.front-1+max)%max=e;sq.front=(sq.front-1+max)%max;if(sq.front=sq.rear) sq.tag=1;return ok;status dequeue(xqueue & sq,elemtype & e)if(sq.front=sq.rear&!sq.tag) return error;elsee=sq.basesq.front;sq.front=(sq.front+1+max)%max;sq.tag=0;return ok;status empty(xqueue sq)if(sq.front=sq.rear&!sq.tag) return ok;else return error;status gettop(xqueue sq,elemtype & e)if(empty(sq) return error;e=sq.basesq.front;return ok;void main() xqueue sq;elemtype e;char ch25,cch;int i,n;initqueue(sq);cout