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

软件技术基础习题答案 习题3 四、1 int compare(SeqList*La,SeqList*Lb) { int i; i=1; while(i=La-lasti=Lb-Last La-data[i]==Lb-data[i]) i++; if(i=La-lastjLb-last|| La-data[i]Lb-data[i]) return 1; //AB if(iLa-lastj=Lb-last|| La-data[i]Lb-data[i]) return -1; //AB if(iLa-lastjLb-last) return 0; //A=B } 四、2 （1）顺序表 int invert(SeqList*L) { int i=1; datatype temp; 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）链表 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; } 四、5 void mergelist(Linear_list*La,Linear_list*Lb,Linear_list*Lc) { Lc=(Linear_list*)malloc(sizeof(Linear_list)); //产生C表的头结点 头插法 Lc-next=NULL; while(La-next!=NULLLb-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); } 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) 四、8 void deleteFront(Link*s) { Link*p=s,*q; while(p-next-next!=s)p=p-next; q=p-next; p-next=s; free(q); } 习题4 四、1 int symmetry(linklist*head,stack*s) //具有头结点的单链表中存放有一个字符串，每个结点的数据域存放一个字符。 //head为单链表的头指针，s为栈的结构体指针 { int n=length(head)/2; linklist*p=head-next ; datatype x; for(int i=0;in;i++){ push(s,p-data); 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; } 四、3 void 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)); } 四、4 int corr