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

软件技术基础习题答案习题3 四、1int compare(SeqList*La,SeqList*Lb)int i;i=1;while(ilast&iLast& La-datai=Lb-datai)i+;if(ilast&jLb-last| La-dataiLb-datai) return 1; /ABif(iLa-last&jlast| La-dataidatai) return -1; /ALa-last&jLb-last) return 0; /A=B四、2 （1）顺序表int invert(SeqList*L)int i=1;datatype temp;while(ilast/2)temp=L-datai;L-datai=L-dataL-last-i+1;L-dataL-last-i+1=temp;（2）链表void invert (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;head-next=p;四、5void mergelist(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-datanext-data) p=La-next; La-next=La-next-next; insert(Lc,p); else p=Lb-next; Lb-next=Lb-next-next; insert(Lc,p); while(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) void insert(Linear_list*Lc,Linear_list*p)p-next=Lc-next;Lc-next=p;/O(1)四、8void deleteFront(Link*s)Link*p=s,*q;while(p-next-next!=s)p=p-next;q=p-next;p-next=s;free(q);习题4 四、1int symmetry(linklist*head,stack*s)/具有头结点的单链表中存放有一个字符串，每个结点的数据域存放一个字符。/head为单链表的头指针，s为栈的结构体指针int n=length(head)/2;linklist*p=head-next ; datatype x;for(int i=0;idata);p=p-next ; if(length(head)%2=1) p=p-next;while(p!=NULL)x=pop(s) ; if (x=p-data ) p=p-next;else return 0;return 1;四、3void delete(Stack*s)Stack*temp;datatype x;InitS(temp);while(!EmptyS(s)x=Pop(s);if(x!=m) Push(temp,x);while(!Empty(temp)Push(s,Pop(temp);四、4int correct(char*exp) InitStack(S); int flag=1;i=0;while( expi!=0&flag)if( expi=(|expi=|expi= ) Push( S,expi ); /遇左括号入栈if( expi=) if( Pop(S)!=( ) flag=0;if( expi=) if( Pop(S)!= ) flag=0;if( expi=) if( Pop(S)!= ) flag=0;/遇右括号出栈，若栈顶不是左括号，则括号不配对i+;if(!Empty(S) flag=0; /若栈非空，则括号不配对return flag;四、6循环队列的结构类型定义：const int m=5;typedef int datatype;typedef struct datatype sequm; int rear, quelen;qu;说明：队满条件：sq-quelen=m 队空条件：sq-quelen=0 (注意：不需要空出一个位置)入队：void enqueue(qu *sq, datatype x) if(sq-quelen=m) printf(queue is full); else sq-quelen+; sq-rear=(sq-rear+1)%m; /修改队尾指针 sq-sequsq-rear=x; 出队：int dequeue(qu *sq , datatype&x) if(sq-quelen=0) printf(queue is empty ); return 0; else sq-quelen-; x=sq-sequ(sq-rear-sq-quelen+m)%m; return 1;习题5 四、3（1）顺序串int Equal(SeqString*S,SeqString*T)/比较顺序串S、T是否相等 i=0；while(S-chi = = T-chi )&( ilength ) &( ilength ) i+;if ( i= =S-length ) &( i= =T-length ) return 1;else return 0;（2）链串int Equal(LinkString*S,LinkString*T)/比较链串S、T是否相等p=S-next；q=T-next;while(S-data = T-data )&( p!=NULL ) &( q!=NULL )p=p-next; q=q-next;if(p=NULL)&(q=NULL) return 1;else return 0;四、7void strDelete(char*S,int i,int m)char temp80;int k;k=i-1;if(i=strlen(S) return;elsestrncpy(temp,S,k); if(k+m=strlen(S) strcpy(temp+k,0);else strcpy(temp+k,S+k+m); strcpy(S,temp);或者：void strDelete(seqstring*S,int i,int m) /字符串中字符的序号从1开始，数组元素从下标0开始使用char tempmaxsize;if(ilen) 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(ilen) if(i+m-1len) S-len=S-len-m; /删除了字符串中间的部分字符 else S-len= i-1; /删除了字符串中从第i个字符开始的全部字符四、9void create(Spmatrix*a)scanf(%d,%d,%d,&a-m,&a-n,&a-t);for(ano=0;anot;ano+)scanf(%d,%d,%d,&a-dataano.i,&a-dataano.j,&a-dataano.v);四、11void minmax(array*p)/找马鞍点 int i,j,have=0; for(i=0;imini=p-Ai0; for(j=1;jAijmini) p-mini=p-Aij; /分别找出m行的最小值 for (j=0;jmaxj=p-A0j; for(i=1;iAijp-maxj) p-maxj=p-Aij; /分别找出n列的最大值 for(i=0;im;i+) for(j=0;jmini=p-maxj) /若相等，则是一个马鞍点 couti,j,Aijendl; /输出马鞍点 have=1; if(!have) coutlchild);t2=swap(p-rchild);p-lchild=t2;p-rchild=t1;return p;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表示组成的哈夫曼编码如下所示。A：1001B：101C：0010D：1000E：11F：0011G：01H：000设计的哈夫曼树如下：哈夫曼树第7章 四、4、邻接表:126null2136null324null435null547null6127null756nullDFS:1 2 3 4 5 7 6BFS:1 2 6 3 7 4 5(不唯一)或1 6 2 7 3 5 45、按顺序输入后的邻接表:126435null216null3145null41635null56413null61245null6、从顶点4开始:DFS: 412653(有多种)BFS: 413562(不唯一)7最小生成树: 7 6 1 5 2 4 3第8章 4、查找586 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 6 87 155 188 150 465 505 508 511 586 656 670 700 766 897 908 Low=1 high=16 mid=(1+16)/2=8 R8508586 Low=9 high=12-1=11 mid=(9+11)/2=10 R10=586 586=R10 查找成功5线性探查 13HT01234567891011125226151204311847099923725H(key)002341162841112比较121118161611拉链052，261215，703120443，82568478999101137，111225给定关键字序列为(105，50，30，25，85，40，100，12，10，28，分别写出直接插入排序、希尔排序、起泡排序、直接选择排序、快速排序和归并排序的每一趟运行结果。直接插入排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟直接插入排序：【50，105】第二趟直接插入排序：【30，50，105】第三趟直接插入排序：【25，30，50，105】第四趟直接插入排序：【25，30，50，85，105】第五趟直接插入排序：【25，30，40，50，85，105】第六趟直接插入排序：【25，30，40，50，85，100，105】第七趟直接插入排序：【12，25，30，40，50，85，100，105】第八趟直接插入排序：【10，12，25，30，40，50，85，100，105】第九趟直接插入排序：【10，12，25，28，30，40，50，85，100，105】希尔排序(增量为5，3，1)：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟希尔排序：40，50，12，10，28，105，100，30，25，85第二趟希尔排序：10，28，12，40，30，25，85，50，105，100第三趟希尔排序：10，12，25，28，30，40，50，85，100，105起泡排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟起泡排序：10，105，50，30，25，85，40，100，12，28第二趟起泡排序：10，12，105，50，30，25，85，40，100，28第三趟起泡排序：10，12，25，105，50，30，85，40，100，28第四趟起泡排序：10，12，25，28，105，50，30，85，40，100第五趟起泡排序：10，12，25，28，30，105，50，85，40，100第六趟起泡排序：10，12，25，28，30，40，105，50，85，100第七趟起泡排序：10，12，25，28，30，40，50，105，85，100第八趟起泡排序：10，12，25，28，30，40，50，85，105，100第九趟起泡排序：10，12，25，28，30，40，50，85，100，105直接选择排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟选择排序：10，50，30，25，85，40，100，12，105，28第二趟选择排序：10，12，30，25，85，40，100，50，105，28第三趟选择排序：10，12，25，30，85，40，100，50，105，28第四趟选择排序：10，12，25，28，85，40，100，50，105，30第五趟选择排序：10，12，25，28，30，40，100，50，105，85第六趟选择排序：10，12，25，28，30，40，50，100，105，85第七趟选择排序：10，12，25，28，30，40，50，85，100，105（完成）第八趟选择排序：10，12，25，28，30，40，50，85，100，105第九趟选择排序：10，12，25，28，30，40，50，85，100，105快速排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟快速排序：（28，50，30，25，85，40，100，12，10），105第二趟快速排序：（10，12，25），28，（85，40，100，30，50），105第三趟快速排序：10，12，25，28，（50，40，30），85，（100），105第四趟快速排序：10，12，25，28，（30，40），50，85，100，105第五趟快速排序：10，12，25，28，（30，40），50，85，100，105归并排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟归并排序：50，105，25，30，40，85，12，100，10，28第二趟归并排序：25，30，50，105，12，40，85，100，10，28第三趟归并排序：10，12，25，28，30，40，50，85，100，105设待排序的关键字序列为(15， 21， 6， 30， 23， 6， 20， 17)， 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。(1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序(4) 快速排序(5) 直接选择排序 (6) 锦标赛排序(7) 堆排序(8) 二路归并排序 (9) 基数排序【解答】 (2) 希尔排序(增量为5，2，1)初始关键字序列： 15，21，6，30，23，6，20，17第一趟希尔排序： 6，20，6，30，23，15，21，17第二趟希尔排序： 6，15，6，17，21，20，23，30第三趟希尔排序： 6，6，15，17，20，21，23，30(3) 起泡排序初始关键字序列：15，21，6，30，23，6，20，17第一趟起泡排序：15，6，21，23，6，20，17，30第二趟起泡排序：6，15，21，6，20，17，23，30第三趟起泡排序：6，15，6，20，17，21，23，30第四趟起泡排序：6，6，15，17，20，21，30，23第五趟起泡排序：6，6，15，17，20，21，30，23(4) 快速排序初始关键字序列： 15，21，6，30，23，6，20，17第一趟快速排序： 【6，6】15【30，23，21，20，17】第二趟快速排序： 6，6， 15【17，23，21，20】30第三趟快速排序： 6，6， 15，17【23，21，20】30第四趟快速排序： 6，6， 15，17，【20，21】23，30第五趟快速排序： 6，6，15，17，20，21，30，23(5) 直接选择排序初始关键字序列： 15，21，6，30，23，6，20，17第一趟直接选择排序： 6，21，15，30，23，6，20，17第二趟直接选择排序： 6，6，15，30，23，21，20，17第三趟直接选择排序： 6，6，15，30，23，21，20，17第四趟直接选择排序： 6，6，15，17，23，21，20，30第五趟直接选择排序： 6，6，15，17，20，21，23，30第六趟直接选择排序： 6，6，15，17，20，21，23，30第七趟直接选择排序： 6，6，15，17，20，21，23，30(6) 锦标赛排序初始关键字序列： 15，21，6，30，23，6，20，17（此题答案的格式不对，我删去了）锦标赛排序的基本思想是：首先对n个待