3,4大数据结构作业

1、实用标准文案 第三章 3.5 假设以 S 和 X 分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操 作序列可以表示为仅由 S和 X组成的序列。 称可以操作的序列为合法序列 （例如， SXSX 为 合法序列， SXXS 为非法序列） 。试给出区分给定序列为合法序列或非法序列的一般准则， 并证明：两个不同的合法 （栈操作） 序列（对同一输入序列） 不可能得到相同的输出元素 （注 意：在此指的是元素实体，而不是值）序列。 解： 一般准则：任何前 n 个序列中 S的个数一定大于或等于 X 的个数且整个序列中 S的个 数一定等于 X 的个数。 证明：设两个合法序列为： T1=S X S T

2、2=S XX 假定前 n 个操作都相同，从第 n+1 个操作开始，为序列不同的起始操作点。由于前 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 试将下列递推过程改写为递归过程

3、。 void ditui（int n） 精彩文档 实用标准文案 int i; i = n; while(i1) coutx; if(x=0) sum=0; else test(sum); sum+=x; 精彩文档 实用标准文案 coutsum; 解： void test(int int x; scanf(%d, initstack(s); while(x!=0) *s.front+=x; scanf(%d, sum=0; int e; printf(%d,sum); while(s.front!=s.base) e=*(-s.front); sum+=e; printf(%d,sum); 3.

4、15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它 精彩文档 实用标准文案 的三个操作：初始化 为 0 或 1 ，用以分别指 )或函数设计这些操作 们的栈底分别设在数组的两个端点。试编写实现这个双向栈 tws inistack(tws) 、入栈 push(tws,i,x) 和出栈 pop(tws,i) 的算法，其中 i 示设在数组两端的两个栈，并讨论按过程(正/ 误状态变量可设为变参 算法各有什么有缺点。 解： 程序源代码： #include #include #define STACK_INIT_SIZE 100 #define TURE 1 #define F

5、ALSE 0 #define ok 1 #define error 0 #define INFEASIBLE -1 typedef intselemtype ; typedef int status; typedef struct int * base2; selemtype * top2; int stacksize; sqstack; status INITstack(sqstack * s) 精彩文档 实用标准文案 int * p; p=(selemtype *) malloc (STACK_INIT_SIZE * sizeof(selemtype); (*s).base0=(*s).t

6、op0=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).base0+(STACK_INIT_SIZE/2)-1) return error; else *(*s).top0+=e; return ok; if(i=1) if(*s).top1=(*s).base1-(STACK_INIT_SI

7、ZE/2)+1) return error; else *(*s).top1-=e; return ok; return error; status Pop(sqstack * s,int i,selemtype * e) 精彩文档 实用标准文案 if(i=0 if(i=1 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( printf( 请输入进栈端

8、 (0/1) 及进栈元素： n); scanf(%d %d, if(Push( printf( 请输入进栈端 (0/1) 及进栈元素： n); 精彩文档 实用标准文案 scanf(%d %d, if(Push( printf( 请输入进栈端 (0/1) 及进栈元素： n); scanf(%d %d, if(Push( printf( 左端栈元素： ); p=sta.base0; while(sta.top0!=p) printf(%d ,*p); p+; printf( 右端栈元素： ); p=sta.base1; while(sta.top1!=p) printf(%d ,*p); p-;

9、printf(n 请输入出栈端 (0/1) ：n); scanf(%d, if(Pop( 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 精彩文档 实用标准文案 #i

10、nclude #define SIZE 100 typedef char selemtype ; typedef struct selemtype * base; selemtype * top; int size; stack; int Prior(char c1,char c2) char ch5=#+-*/; int i=0,j=0; if(c1=() return 0; while(chi if(i=2) i-;/ 加和减可认为是同级别的运算符 if(i=4) i-;/ 乘和除可认为是同级别的运算符 while(chj if(j=2) j-; if(j=4) j-; if(ij) re

11、turn 1; else return 0; 精彩文档 实用标准文案 void main() stack sta; char ch=0,ct; sta.base=(selemtype *)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!=# if(a=ch else if(ch=#) ct=*(-sta.top); while(ct!=#) printf

12、( %c ,ct); ct=*(-sta.top); -sta.top; else if(ch=() *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; else ct=*(-sta.top); while(Prior(ct,ch) printf( %c ,ct); ct=*(-sta.top); *(+sta.top)=ch; +sta

13、.top; 运行结果： 精彩文档 实用标准文案 3.22 如题 3.21 的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。 解： 程序源代码： #include #include #define max_size_stack 100 #define incre 10 #define ok 1 #define error -100 typedef int elemtype2; typedef int status; typedef struct elemtype2 * top; elemtype2 * base; int size; stack2; status initstack2(s

14、tack2 if(!da.base) cout 操作失败，程序执行无效 !=da.size) da.base=(elemtype2 *)realloc(da.base,(da.size+incre)*sizeof(elemtype2); !endl; if(!da.base) cout 操作失败，程序执行无效 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; 精彩

15、文档 实用标准文案 case -: return e1-e2; case *: return e1*e2; case /: if(e2=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!=# if(cch!=+ else if(cch!=#)

16、pop2(da,e2);pop2(da,e1); if(coun(e1,e2,cch)=-100) cout 表达是不合法： endl; cout 操作失败，程序执行无效 !endl; 精彩文档 实用标准文案 else push2(da,coun(e1,e2,cch); else pop2(da,e1); cout 表达式的值为： e1endl; 运行结果： 3.14 若以 1234 作为双端队列的输入序列，试分别求出满足以下条件的输出序列： (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。 (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出

17、序列。 (3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序 列。 解： 1,2,3,4 输入受限 1 2 3 4 精彩文档 实用标准文案 4 和 2 不可相连 1,2,3,4 输出受限 1 2 1 和 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 ，3421 3.29 如果希望循环

18、队列中的元素都能得到利用，则需设置一个标志域 tag ，并以 tag 的值 为 0 和 1 来区分，尾指针和头指针值相同时的队列状态是“空”还是“满” 。试编写与此结 构相应的入队列和出队列的算法， 并从时间和空间角度讨论设标志和不设标志这两种方法的 使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好） 。 解： 程序源代码： #include #include 精彩文档 实用标准文案 #define maxqsize 5 #define ok 1 #define error 0 typedef int qelemtype; typedef int status; t

19、ypedef struct qelemtype * base; int front; int rear; int tag; squeue; status initqueue(squeue if(!sq.base) exit(-2); sq.front=sq.rear=0; sq.tag=0; return ok; status enqueue(squeue sq.basesq.rear=e; sq.rear=(sq.rear+1)%maxqsize; 精彩文档 实用标准文案 if(sq.rear=sq.front) sq.tag=1; return ok; status dequeue(squ

20、eue e=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; endl; endl; if(enqueue(sq,e) cout 元素已插入 cout 请输入队列元素： e; if(enqueue(sq,e) cout 元素已插入 cout 请输入队列元素： e; if(enqueue(sq,e) cout元素已插入 endl; i

21、f(dequeue(sq,e) cout队头元素 :e 已删除 endl; cout 队列中元素为： endl; for(;dequeue(sq,e);) coute ; coutendl; 运行结果： 3.30 假设将循环队列定义为 :以域变量 rear 和 length 分别指示循环队列中队尾元素的位置 和内含元素的个数。 试给出此循环队列的队满条件， 并写出相应的入队列和出队列的算法 出队列的算法中要返回队头元素） 解： 程序源代码： #include #include #define max 3 精彩文档 实用标准文案 #define ok 1 #define error 0 type

22、def int status; typedef int selemtype; typedef struct selemtype * base; int rear; int length; squeue; status initqueue(squeue if(!sq.base) exit(-2); sq.rear=0; sq.length=0; return ok; status enqueue(squeue sq.basesq.rear=e; sq.rear=(sq.rear+1)%max; sq.length+; return ok; 精彩文档 实用标准文案 status dequeue(s

23、queue 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 队列已满元素未被插入 endl; cout 请输入队列元素： e; if(enqueue(

24、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 和 ab

25、abab 则不是回文。试写一个算法判别读入的一个以 为结束符的 字符序列是否是“回文” 解： 精彩文档 实用标准文案 程序源代码： #include #include #define max 10 typedef char elemtype; typedef struct elemtype * 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=

26、0; cout 请输入字符序列： ch; sq.basesq.rear=ch; sq.rear=(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 else cout 该字符序列不为回文 endl; 运行结果： 3.34 假设在如教科书 3.4.1 节中图 3.9 所示的铁道转轨网的输入端有 n 节车厢：硬座、硬 卧和软卧（分别以 P,H 和 S 表示）等待调度，

27、 要求这三种车厢在输出端铁道上的排列次序为： 硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这 n 节车厢进行调度，编 写算法输出调度的操作序列：分别以字符E和 D 表示对双端队列的头端进行入队列 精彩文档 实用标准文案 和出队列的操作；以字符 A 表示对双端队列的尾端进行入队列的操作。 解： 程序源代码： #include #include #define max 10 #define ok 1 #define error 0 typedef int status; typedef int elemtype; typedef struct elemtype * base; int

28、front ; int rear ; int tag; xqueue; status initqueue(xqueue if(!sq.base) exit(-2); sq.front=sq.rear=0; sq.tag=0; return ok; 精彩文档 实用标准文案 status enqueue(xqueue if(sq.front=sq.rear if(sq.front=sq.rear sq.rear=(sq.rear+1)%max; if(sq.front=sq.rear) sq.tag=1; else a=(sq.basesq.front+sq.base(sq.rear+max-1)

29、%max)/2; if(e=a) sq.basesq.rear=e; sq.rear=(sq.rear+1)%max; if(sq.front=sq.rear) sq.tag=1; else sq.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 else e=sq.basesq.front; sq.front=(sq.front+1+max)%max; sq.tag=0; r

30、eturn 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 队列已满元素未

31、被插入 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 表示）等待调度， 要求这三种车厢在输出端铁道上的排

32、列次序为： 硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这 n 节车厢进行调度，编 写算法输出调度的操作序列：分别以字符E和 D 表示对双端队列的头端进行入队列 和出队列的操作；以字符 A 表示对双端队列的尾端进行入队列的操作 。 解： 程序源代码： #include #include #define max 10 #define ok 1 #define error 0 typedef int status; typedef char elemtype; typedef struct 精彩文档 实用标准文案 elemtype * base; int front ; int rea

33、r ; int tag; xqueue; status initqueue(xqueue if(!sq.base) exit(-2); sq.front=sq.rear=0; sq.tag=0; return ok; status enqueuerear(xqueue sq.basesq.rear=e; sq.rear=(sq.rear+1)%max; if(sq.front=sq.rear) sq.tag=1; return ok; status enqueuetop(xqueue sq.base(sq.front-1+max)%max=e; 精彩文档 实用标准文案 sq.front=(sq

34、.front-1+max)%max; if(sq.front=sq.rear) sq.tag=1; return ok; status dequeue(xqueue else e=sq.basesq.front; sq.front=(sq.front+1+max)%max; sq.tag=0; return ok; status empty(xqueue sq) if(sq.front=sq.rear else return error; status gettop(xqueue sq,elemtype e=sq.basesq.front; return ok; 精彩文档 实用标准文案 voi

35、d main() xqueue sq; elemtype e; char ch25,cch; int i,n; initqueue(sq); cout 请输入车厢节数： n; cout 请输入车厢次序： endl; for(i=1;icch; chi-1=cch; for(i=1;i=n;i+) if(empty(sq) enqueuetop(sq,chi-1);cout E ; else if(chi-1=H) enqueuerear(sq,chi-1);cout A ; if(chi-1=P) enqueuetop(sq,chi-1);cout E ; if(chi-1=S) gettop

36、(sq,e); if(e=S) enqueuetop(sq,chi-1);cout E ; 精彩文档 实用标准文案 else while(e=P) dequeue(sq,e); cout D ; gettop(sq,e); enqueuetop(sq,chi-1); cout E ; if(!empty(sq) for(;dequeue(sq,e);) cout D ; coutendl; 运行结果： 精彩文档 实用标准文案 第四章 4.11 编写算法，求得所有包含在串 s中而不包含在串 t 中的字符(s中重复的字符只选一个) 构成的新串 r，以及 r 中每个字符在 s 中第一次出现的位置。

37、解： 程序源代码： #include #include #include #define ok 1 typedef int status; typedef struct char * ch; int * pos; int length; string; status strassign(string char * c,* cc; 精彩文档 实用标准文案 if(r.ch) free(r.ch); i=0;c=chars; while(*c) if(*c!=*) i+; c+; c+; if(!i)r.ch=0;r.pos=0; else if(!(r.ch=(char *)malloc(i*si

38、zeof(char) exit(-2); if(!(r.pos=(int *)malloc(i*sizeof(int) exit(-2); j=k=i=1; c=chars; cc=r.ch; while(cj-1) if(cj-1!=*) cci-1=cj-1; r.posk-1=j-1; 精彩文档 实用标准文案 i+;k+; r.length+; j+; return ok; void main() int i,j,m,n; string r=0,0,0; char s20,t20; cout 请输入串 s:s; cout 请输入串 t:t; for(n=0;sn;n+); for(m=0;tm;m+); for(i=1;i=n;i+) if(si-1!=*) for(j=i+1;j=n;j+) if(si-1=sj-1) sj-1=*; 精彩文档 实用标准文案 for(i=1;i=m;i+