《3,4数据结构作业》由会员分享，可在线阅读，更多相关《3,4数据结构作业（22页珍藏版）》请在金锄头文库上搜索。
1、第三章 3.5 假设以 S 和 X 分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操 作序列可以表示为仅由 S 和 X 组成的序列。称可以操作的序列为合法序列（例如，SXSX 为 合法序列，SXXS 为非法序列） 。试给出区分给定序列为合法序列或非法序列的一般准则， 并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素 （注意：在此指的是元素实体，而不是值）序列。 解： 一般准则：任何前 n 个序列中 S 的个数一定大于或等于 X 的个数且整个序列中 S 的个 数一定等于 X 的个数。 证明：设两个合法序列为：T1=SXS T2=SXX假定前 n 个操作
2、都相同，从第 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 试将下列递推过程改写为递归过程。void ditui(int n) int i
3、; i = n; while(i1) coutx; if(x=0) sum=0; else test(sum); sum+=x; cout #include #define STACK_INIT_SIZE 100 #define TURE 1 #define FALSE 0 #define ok 1 #define error 0 #define INFEASIBLE -1 typedef int selemtype ; typedef int status; typedef struct int * base2; selemtype * top2;int stacksize; sqstack
4、; 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).b
5、ase0+(STACK_INIT_SIZE/2)-1) return error; else *(*s).top0+=e; return ok; if(i=1) if(*s).top1 #include #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
6、(i=2) i-;/ 加和减可认为是同级别的运算符 if(i=4) i-;/ 乘和除可认为是同级别的运算符while(chj 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=(selemtype *)malloc(SIZE*sizeof(selemtype); if(!sta.base ) exit(0); sta.top=sta.base; sta.size=0; *sta.top+=#; printf(“please enter the
7、expression:n“); while(ch!=# if(a #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(stack2 if(!da.base) cout=da.size) da.base=(elemtype2
8、*)realloc(da.base,(da.size+incre)*sizeof(elemtype2); if(!da.base) coutcch; if(cch!=+ else if(cch!=#) pop2(da,e2);pop2(da,e1); if(coun(e1,e2,cch)=-100) cout #include #define maxqsize 5 #define ok 1 #define error 0 typedef int qelemtype; typedef int status; typedef struct qelemtype * base; int front;
9、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(squeue e=sq.basesq.front; sq.front=(sq.front+1)%maxqsize;
10、if(sq.tag=1) sq.tag=0; return ok; void main() squeue sq; qelemtype e; int i; initqueue(sq); coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) cout #include #define max 3 #define ok 1 #define error 0 typedef int status; typedef int selemtype; typedef struct selemtype * base; int
11、 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(squeue if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueu
12、e(sq,e) cout #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=0; coutch; sq.basesq.rear=ch; sq.rear=(sq.rear+1)%max; if(sq.b
13、asesq.rear-1=) sq.rear-; if(sq.rear+1)%max=sq.front) cout=n/2 typedef int elemtype; typedef struct elemtype * base; int 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
14、.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)%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; retu
15、rn ok; status dequeue(xqueue else e=sq.basesq.front; sq.front=(sq.front+1+max)%max; sq.tag=0; return ok; void main()xqueue sq; elemtype e; initqueue(sq); coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) coute; if(enqueue(sq,e) cout #include #define max 10 #define ok 1 #define error 0 typedef int status; typedef char elemtype; typedef struct elemtype * base; int 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 enqueuerear(xqueue sq.bas
