西电_C++_面向对象程序设计_软件技术基础_课后答案2

1软件技术基础习题答案习题3四、1intcompare(SeqList*La,SeqList*Lb){inti;i=1;while(i=La-last&&i=Lb-Last&&La-data[i]==Lb-data[i])i++;if(i=La-last&&jLb-last||La-data[i]Lb-data[i])return1;//ABif(iLa-last&&j=Lb-last||La-data[i]Lb-data[i])return-1;//ABif(iLa-last&&jLb-last)return0;//A=B}四、2（1）顺序表intinvert(SeqList*L){inti=1;2datatypetemp;while(i=L-last/2){temp=L-data[i];L-data[i]=L-data[L-last-i+1];L-data[L-last-i+1]=temp;}}（2）链表voidinvert(linklist*head){linklist*p,*q,*r;p=head-next;q=p-next;while(q!=NULL){r=q-next;q-next=p;p=q;q=r;}head-next-next=NULL;3head-next=p;}四、5voidmergelist(Linear_list*La,Linear_list*Lb,Linear_list*&Lc){Lc=(Linear_list*)malloc(sizeof(Linear_list));//产生C表的头结点头插法Lc-next=NULL;while(La-next!=NULL&&Lb-next!=NULL)//La、Lb均非空if(La-next-data=Lb-next-data){p=La-next;La-next=La-next-next;insert(Lc,p);}else{p=Lb-next;Lb-next=Lb-next-next;insert(Lc,p);}4while(La-next!=NULL){p=La-next;La-next=La-next-next;insert(Lc,p);}while(Lb-next!=NULL){p=Lb-next;Lb-next=Lb-next-next;insert(Lc,p);}}//O(Length(La)+Length(Lb))voidinsert(Linear_list*Lc,Linear_list*p){p-next=Lc-next;Lc-next=p;}//O(1)四、8voiddeleteFront(Link*s){5Link*p=s,*q;while(p-next-next!=s)p=p-next;q=p-next;p-next=s;free(q);}习题4四、1intsymmetry(linklist*head,stack*s)//具有头结点的单链表中存放有一个字符串，每个结点的数据域存放一个字符。//head为单链表的头指针，s为栈的结构体指针{intn=length(head)/2;linklist*p=head-next;datatypex;for(inti=0;in;i++){push(s,p-data);p=p-next;}if(length(head)%2==1)p=p-next;6while(p!=NULL){x=pop(s);if(x==p-data)p=p-next;elsereturn0;}return1;}四、3voiddelete(Stack*s){Stack*temp;datatypex;InitS(temp);while(!EmptyS(s)){x=Pop(s);if(x!=m)Push(temp,x);}while(!Empty(temp))Push(s,Pop(temp));}四、47intcorrect(char*exp){InitStack(S);intflag=1;i=0;while(exp[i]!='\0'&&flag){if(exp[i]=='('||exp[i]=='['||exp[i]=='{')Push(S,exp[i]);//遇左括号入栈if(exp[i]==')')if(Pop(S)!='(')flag=0;if(exp[i]==']')if(Pop(S)!='[')flag=0;if(exp[i]=='}')if(Pop(S)!='{')flag=0;//遇右括号出栈，若栈顶不是左括号，则括号不配对i++;}if(!Empty(S))flag=0;//若栈非空，则括号不配对returnflag;}四、6循环队列的结构类型定义：constintm=5;typedefintdatatype;8typedefstruct{datatypesequ[m];intrear,quelen;}qu;说明：队满条件：sq-quelen==m队空条件：sq-quelen==0(注意：不需要空出一个位置)入队：voidenqueue(qu*sq,datatypex){if(sq-quelen==m)printf(queueisfull);else{sq-quelen++;sq-rear=(sq-rear+1)%m;//修改队尾指针sq-sequ[sq-rear]=x;}}出队：intdequeue(qu*sq,datatype&x){if(sq-quelen==0){printf(queueisempty);return0;}else{sq-quelen--;x=sq-sequ[(sq-rear-sq-quelen+m)%m];return1;}9}习题5四、3（1）顺序串intEqual(SeqString*S,SeqString*T)//比较顺序串S、T是否相等{i=0；while((S-ch[i]==T-ch[i])&&(iS-length)&&(iT-length))i++;if((i==S-length)&&(i==T-length))return1;elsereturn0;}（2）链串intEqual(LinkString*S,LinkString*T)//比较链串S、T是否相等{p=S-next；q=T-next;while((S-data==T-data)&&(p!=NULL)&&(q!=NULL)){p=p-next;10q=q-next;}if((p==NULL)&&(q==NULL))return1;elsereturn0;}四、7voidstrDelete(char*S,inti,intm){chartemp[80];intk;k=i-1;if(i=strlen(S))return;else{strncpy(temp,S,k);if(k+m=strlen(S))strcpy(temp+k,\0);elsestrcpy(temp+k,S+k+m);strcpy(S,temp);}}或者：voidstrDelete(seqstring*S,inti,intm)//字符串中字符的序号从1开始，数组元素从下标0开始使用11{chartemp[maxsize];if(i=S-len){strncpy(temp,S-str,i-1);//将S-str中第i个字符之前的i-1个字符复制到temp中strcpy(temp+i-1,S-str+i+m-1);//将S-str中第i+m个字符开始的字符连接到temp之后strcpy(S-str,temp);//将temp复制到S-str中if(i=S-len)if(i+m-1=S-len)S-len=S-len-m;//删除了字符串中间的部分字符elseS-len=i-1;//删除了字符串中从第i个字符开始的全部字符}}四、9voidcreate(Spmatrix*a){scanf(%d,%d,%d,&a-m,&a-n,&a-t);for(ano=0;anoa-t;ano++)12scanf(%d,%d,%d,&a-data[ano].i,&a-data[ano].j,&a-data[ano].v);}四、11voidminmax(array*p)//找马鞍点{inti,j,have=0;for(i=0;im;i++){p-min[i]=p-A[i][0];for(j=1;jn;j++)if(p-A[i][j]p-min[i])p-min[i]=p-A[i][j];}//分别找出m行的最小值for(j=0;jn;j++){p-max[j]=p-A[0][j];for(i=1;im;i++)if(p-A[i][j]p-max[j])p-max[j]=p-A[i][j];}//分别找出n列的最大值for(i=0;im;i++)for(j=0;jn;j++)if(p-min[i]==p-max[j])//若相等，则是一个马鞍点{couti,j,p-A[i][j]endl;//输出马鞍点13have=1;}if(!have)cout矩阵中没有马鞍点！\n;}第六章四4、知二叉树的后序序列DECBGIHFA和中序序列为DCEBAFHGI，画出这棵二叉树。ABFCHDEIG7、右交换子树算法（在上机答案）//交换左右子树bitree*swap(bitree*p){bitree*t1,*t2;14if(p!=NULL){1=swap(p-lchild);t2=swap(p-rchild);p-lchild=t2;p-rchild=t1;}returnp;}12、已知结点序列{21，18，37，42，65，24，19，26，45，25}，画出相应的二叉排序树，并画出删除结点37后的二叉排序树。有问题(1)（2）删除结点37后14某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7、19、2、6、32、3、21、10，试为这8个字母设计相应的哈夫曼编码。解：这8个字母可用A、B、C、D、E、F、G、H表示15组成的哈夫曼编码如下所示。A：1001B：101C：0010D：1000E：11F：0011G：01H：000设计的哈夫曼树如下：哈夫曼树第七章四、4、邻接表:126null2136null324null435null547null6127null756nullDFS:1234576BFS:1263745(不唯一)或1627316545、按顺序输入后的邻接表:126435null216null3145null41635null56413null61245null6、从顶点4开始:DFS:412653(有多种)BFS:413562(不唯一)7最小生成树:7615243第八章4、查找5861712345678910111213141516687155188150465505508511586656670700766897908Low=1high=16mid=(1+16)/2=8R[8]＝508586Low=mid+1=9high=16mid=(9+16)/2=12R[12]=670586Low=9high=12-1=11mid=(9+11)/2=10R[10]=586586=R[10]查找成功5线性探查13HT01234567891011125226151204311847099923725H(key)002341162841112比较121118161611拉链052，261215，703120443，8218568478999101137，111225给定关键字序列为(105，50，30，25，85，4