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

习题三 3.1 3.10 3.13 3.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.5 给定操作序列P1P2P3…Pi…Pn（Pk为S或X，k=1,2,…n ）是合法的，当且仅当满足下列条件： a. 序列中包含的S的个数和X的个数相等； b. 对于任意的j（1≤j≤n）；有P1P2P3…Pj子序列中所包含的S的个数大于等于X的个数； 证明：设P1P2P3…Pi…Pn ，Q1Q2Q3…Qi…Qn是两个不同的合法序列； ∵ 两者不同， ∴ k=min{i| Pi≠Qi , 1≤i≤n }且k1， Pk≠Qk （因P1 ，Q1肯定是S，否则不合法！） 即，P1P2P3…Pk-1 和Q1Q2Q3…Qk-1是相等的，但Pk≠Qk 由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于Pk≠Pk不妨设Pk=X，而Qk=S； 这样，在操作序列P1P2P3…Pi…Pn中的第k-1步后输出的第一个元素是目前栈中的元素，而对于操作序列Q1Q2Q3…Qi…Qn中的第k-1步后输出的第一个元素是目前还在栈外的元素。所以输出序列不同。 即两个不同的合法操作序列，不可能得到相同的输出序列。 证毕！ 3.6 用反证法 证明：假设存在这样的输出序列，P1…Pi…Pj…P k…Pn ，满足ijk,使PjPkPi ; 因Pi在这三个数中最大，且Pi最先出栈，按照题意所给进栈顺序，在Pi出栈时Pj和P k都还在栈中； 又因，PjP k ，所以Pj比P k先进栈，则出栈顺序应该是P k先出栈而不是Pj先出栈，矛盾！ 证毕！ 3.10 (1) 输出序列为：0,5,9,12,14,15 由于输入的数据个数不定，采用单链表存储输入的元素，又因是先输入的，后累加到累加器里，所以用链栈的形式存储。（类型定义与书本上第二章相同） void test( ) { LinkList L ,P; int x,sum; L=NULL; //建立空链表 sum=0; printf(sum); scanf(x);//读入第一个数 while(x) { P=(LinkList)malloc(sizeof(LNode));//产生一个结点 P-data=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 100 typedef 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; }// Inistack Status 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; }// Push Status 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; }// Pop 3.17 Status judge( ){ //判断输入的字符序列是否为型如序列1序