数据结构(C语言版)习题解答

1.3设n是正整数。试写出下列程序段中用记号“△”标注的语句的频度：(2)i=1;k=0;do{△k+=10*i;i++;}while(i=n-1)当n=1时，执行1；当n=2时，执行n-1次；(3)i=1;k=0;do{△k+=10*i;i++;}while(i==n);当n=2时，执行2次；当n!=2时，执行1次；(4)i=1;j=0;while(i+j≤n){△if(ij)i++;elsej++;}执行n次；(5)x=n;y=0;//n是不小于1的常数while(x=(y+1)*(y+1)){△y++;}执行向下取整)(6)x=91;y=100;while(y0)△if(x100){x-=10;y--;}elsex++;}If语句执行100次(7)for(i=0;in;i++)for(j=i;jn;j++)for(k=j;kn;k++)△x+=2;过程：n1n1i0jin(n1)(n2)(nj)6第二章2.3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。StatusInsert_SqList(SqList&La,intx)//把x插入递增有序表La中{if(La.length==La.listsize)returnERROR;for(i=La.length-1;La.elem[i]x&&i=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;returnOK;}//Insert_SqList2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2,...,an-1,an）逆置为(an,an-1,...,a2,a1)//思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变voidreverse(SqList&A)//顺序表的就地逆置{ElemTypep;for(i=1,j=A.length;ij;i++,j--){//A.elem[i]-A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse2.7已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L中数据元素非递减有序排列。voidDelete_SameElem(SqLink&L,intL.length){//内层循环移动参数，中层循环寻找相同元，外层循环遍历整个表inti=0;intj=i+1;intlength=L.length;while(ilength){for(j=i+1;jlength;j++){if(L.Elem[j]==L.Elem[i]){//for(k=j;klength-1;k++){L.Elem[k]=L.Elem[k+1];length--;j--;//移动元素后，由于少了一个元素，因此要减1}}//endifIf(L.Elem[j]L.Elem[i])break;//第二小问添加此句}//endfor}//endwhile}//endfunctoion2.8已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。（1）L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。StatusListDelete（Linklist&L）//L是带头结点的线性表{ElemType*p,*q;p==L-next;q=p-next;//设定p变化较慢，q变化较快while(p-next){while(q){if(p-data!=q-data)q=q-next;else{q=q-next;p-next=q;}//else}//whilep=p-next;q=p-next;//开始后一结点的寻找returnOK；}//ListDelete(2)L中数据元素非递减有序排列。思路：由于是有序的，遍历一次线性表就行了StatusListDelete(LinkList&L){ElemType*p,*q;p=L-next;q=p-next;while(p-next){if(p-data!=q-data){p=p-next;//和第一问不同地方q=p-next;}//ifelse{while(p-data==q-data)q=q-next;//多个连续的重复值}//elsep-next=q;p=q;q=p-next;//删除值重复的结点，并修改相应的指针returnOK；}//ListDelete2.9设有两个非递减有序的单链表A,B。请写出算法，将A和B就地归并成一个按元素值非递增有序的单链表。//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa-next;pb=pb-next;A-next=NULL;C=A;while(pa&&pb){if(pa-datapb-data){qa=pa;pa=pa-next;qa-next=A-next;//将当前最小结点插入A表表头A-next=qa;}else{qb=pb;pb=pb-next;qb-next=A-next;//将当前最小结点插入A表表头A-next=qb;}}while(pa){qa=pa;pa=pa-next;qa-next=A-next;A-next=qa;}while(pb){qb=pb;pb=pb-next;qb-next=A-next;A-next=qb;}pb=B;free(pb);returnOK;}2.13设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。voidReform(DuLinkedList&L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点{p=L.next;while(p-next!=L&&p-next-next!=L){p-next=p-next-next;p=p-next;}//p指向最后一个奇数结点if(p-next==L)//结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点p-next=L-pre-pre;else//结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点p-next=L-pre;p=p-next;//此时p指向最后一个偶数结点while(p-pre-pre!=L){p-next=p-pre-pre;p=p-next;}p-next=L;//最后一个结点next指向头结点//调整了next链的结构,此时pre链仍为原状//调整pre链的结构for(p=L;p-next!=L;p=p-next)p-next-pre=p;L-pre=p;//头结点的pre指向a2结点}//Reform第三章栈和队列3.6试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符‘&’,且序列2是序列1的逆序。例如，“a+b&b+a”是属于该模式的字符序列，而“1＋3&3－1”则不是。算法：intSeqReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0{InitStack(s);while((e=getchar())!='&'){if(e==’@’)return0;//不允许在’&’之前出现’@’push(s,e);}//序列1输入完毕while((e=getchar())!='@'){if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;//序列1元素还有剩余return1;}//IsReverse3.7假设一个算术表达式中可以包含三种符号：圆括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中）。算法：StatusBracketTest(char*str)//判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;//必须与当前栈顶括号匹配}//if}//forif(!StackEmpty(s))returnERROR;//进栈的符号还有剩余，ErrorreturnOK;}//BracketTest3.8设表达式由单字母变量、双目运算符和圆括号组成（如:“(a*(b+c)-d)/e）”。试写一个算法，将一个书写正确的表达式转换为逆波兰式。思路：1.遇到数字直接发送2.遇到’(’直接入栈3.遇到’)’则将栈内元素发送直至遇到’(’4.栈空则直接入栈5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈intRankOfOperator(charc){switch(c){case'#':return-1;case'(':return0;case'+':case'-':return1;case'*':case'/':case')':return2;}}intPrecede(charc,charch){returnRankOfOperator(c)RankOfOperator(ch);}voidExpressionTOPolandStyle(charsuffix[],char*exp){Stacks;InitStack(s,100);inti=0;charc;while(*exp){if(isdigital(*exp))suffix[i++]=*exp;else{switch(*exp){case'(':push(s,'(');case')':while((c=pops(s))!='(')suffix[i++]=c;break;default:if(IsEmpty(s))push(s,*exp);else{suffix[i++]=pop(s);exp--;//与后面的exp++相抵消，使得栈内优先级大于等于栈外的都出栈}}//endswitch}//endelseexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}3.10假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法（在出队算法中要传回队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typ