数据结构(C语言版)习题集答案第三章.doc

习题三3.1 3.10 3.13 3.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.5(1) 给定操作序列P1P2P3PiPn（Pk为S或X，k=1,2,n ）是合法的，当且仅当满足下列条件：a. 序列中包含的S的个数和X的个数相等；b. 对于任意的j（1jn）；有P1P2P3Pj子序列中所包含的S的个数大于等于X的个数；(2)证明：设P1P2P3PiPn ，Q1Q2Q3QiQn是两个不同的合法序列； 两者不同， k=mini| PiQi , 1in 且k1， PkQk （因P1 ，Q1肯定是S，否则不合法！） 即，P1P2P3Pk-1 和Q1Q2Q3Qk-1是相等的，但PkQk由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于PkPk不妨设Pk=X，而Qk=S；这样，在操作序列P1P2P3PiPn中的第k-1步后输出的第一个元素是目前栈中的元素，而对于操作序列Q1Q2Q3QiQn中的第k-1步后输出的第一个元素是目前还在栈外的元素。所以输出序列不同。即两个不同的合法操作序列，不可能得到相同的输出序列。证毕！3.6 用反证法证明：假设存在这样的输出序列，P1PiPjP kPn ，满足ijk,使PjPkPi ;因Pi在这三个数中最大，且Pi最先出栈，按照题意所给进栈顺序，在Pi出栈时Pj和P k都还在栈中；又因，Pjdata=x; P-next=L; L=P;/插入在链头 scanf(x);/读下一个数 while(L) sum+=sum+L-data;/取值累加 printf(sum);/输出 P=L-next; free(L); L=P; 3.15 所用类型定义如下：#define Stack_Init_Size 100typedef struct stack SElemType base0,base1,*top0,*top1; int StackSize ; DuSqStack;void Inistack(DuSqStack &tws) tws.base0=( SElemType*)malloc(Stack_Init_Size*sizeof(SElemType); if(!tws.base0) exit(OVERFLOW); tws.top0= tws.base0; tws.base1=tws.top1=tws0.base0+ Stack_Init_Size-1; tws.StackSize= Stack_Init_Size;/ InistackStatus Push( DuSqStack &tws ,int i , SElemType x)/将元素x插在第i个栈中if (tws.top0tws.top1) return (OVERFLOW);switch(i)case 0: *tws.top0=x; tws.top0+;break;case 1: *tws.top1=x; tws.top1-;break;return OK;/ PushStatus Pop( DuSqStack &tws ,int i , SElemType &x)/将第i个栈的栈顶元素弹出，由x带回switch(i)case 0: if(tws.base0=tws.top0) return ERROR; x=*(-tws.top0);break;case 1: if(tws.base1=tws.top1) return ERROR; x=*(+tws.top0);break;return OK;/ Pop3.17Status judge( )/判断输入的字符序列是否为型如序列1&序列2，其中序列2是序列1的逆序列InitStack(S); 初始化栈Sc=getchar( );/读第一个字符while(c!= &c!= ) push(s,c); c=getchar( );if(c!= &) return FALSE;c=getchar( );/读下一个while(c!= & !EmptyStack(s) pop(s,e); if(c!=e) return FALSE; c=getchar( );if(c= & EmptyStack(s) return TRUE;return FALSE;/ judge3.19Status judged(SqList L)/L为数据元素类型为字符的顺序存储的线性表，表示一个表达式，判断该表达/式的括号是否匹配InitStack(S);/初始化栈Sfor(j=0;j=0) return 0;else if(m0 & n=0) return (g(m-1,2*n)+n);/ g329 类型定义#define MAX_Init_Size 100typedef struct QElemType *base; int front,rear ,tag; SqQueue;Status InitQueue(SqQueue &Q )/初始化一个队列Q.base=( QelemType* )malloc(MAX_Init_Size*sizeof(QelemType);If(!Q.base) exit(OVERFLOW);G.front=Q.rear=Q.tag=0;/表示队列为空return OK;/ InitQueueStatus EnQueue(SqQueue &Q , QelemType x)/将元素x入队列, 若队列满则返回函数值ERROR，否则返回OKif(Q.front=Q.rear)&(Q.tag=1) return ERROR;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAX_Init_Size;if(Q.front=Q.rear) Q.tag=1;/尾指针追上头指针return OK;/ EnQueueStatus DelQueue(SqQueue &Q , QelemType &x)/删除队头元素，让x带回，若队列为空则返回函数值ERROR，否则返回OKif(Q.front=Q.rear)&(Q.tag=0) return ERROR;x=Q.baseQ.front;Q.front= (Q.front+1)% MAX_Init_Size;if(Q.front=Q.rear) Q.tag=0;/头指针追上尾指针return OK;/DelQueue3.31Status Ispalindrome ( )/判断输入的字符序列是否为回文，是返回TRUE ，否则返回FALSEInitStack(S);/ 初始化栈SInitQueue(Q);/初始化一个队列Qc=getchar( );/读第一个字符while(c!= )push(S,c); /入栈EnQueue(Q,c);/入队列c=getchar( );while(!EmptyStack(S) Pop(S,e); DelQueue(Q,c); if(c!=e) return FALSE;return TRUE;/ Ispalindrome3.24 Status g(int m,int n,int &s)/求递归函数g的值sif(m=0&n=0) s=0;else if(m0&n=0) s=n+g(m-1,2*n);else return ERROR;return OK;/g 3.29 Status EnCyQueue(CyQueue &Q,int x)/带tag域的循环队列入队算法if(Q.front=Q.rear&Q.tag=1) /tag域的值为0表示空,1表示满return OVERFLOW;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front=Q.rear) Q.tag=1; /队列满/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带tag域的循环队列出队算法if(Q.front=Q.rear&Q.