數(shù)據(jù)結構教程(第三版)課后答案

數(shù)據(jù)結構教程(第三版)課后答案/*文件名:algo2-1.cpp*/#include<stdio.h>#include<malloc.h>#defineMaxSize50typedefcharElemType;typedefstruct{ ElemTypeelem[MaxSize]; intlength;}SqList;voidInitList(SqList*&L){ L=(SqList*)malloc(sizeof(SqList)); L->length=0;}voidDestroyList(SqList*L){ free(L);}intListEmpty(SqList*L){ return(L->length==0);}intListLength(SqList*L){ return(L->length);}voidDispList(SqList*L){ inti; if(ListEmpty(L))return; for(i=0;i<L->length;i++) printf("%c",L->elem[i]); printf("\n");}intGetElem(SqList*L,inti,ElemType&e){ if(i<1||i>L->length) return0; e=L->elem[i-1]; return1;}intLocateElem(SqList*L,ElemTypee)數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第1頁。{數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第1頁。 inti=0; while(i<L->length&&L->elem[i]!=e)i++; if(i>=L->length) return0; else returni+1;}intListInsert(SqList*&L,inti,ElemTypee){ intj; if(i<1||i>L->length+1) return0; i--; /*將順序表位序轉化為elem下標*/ for(j=L->length;j>i;j--) /*將elem[i]及后面元素后移一個位置*/ L->elem[j]=L->elem[j-1]; L->elem[i]=e; L->length++; /*順序表長度增1*/ return1;}intListDelete(SqList*&L,inti,ElemType&e){ intj; if(i<1||i>L->length) return0; i--; /*將順序表位序轉化為elem下標*/ e=L->elem[i]; for(j=i;j<L->length-1;j++) L->elem[j]=L->elem[j+1]; L->length--; return1;}/*文件名:algo2-2.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructLNode /*定義單鏈表結點類型*/{ ElemTypedata;structLNode*next;}LinkList;voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結點*/ L->next=NULL;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第2頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第2頁。voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p);}intListEmpty(LinkList*L){ return(L->next==NULL);}intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=NULL) { i++; p=p->next; } return(i);}voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}intGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p=L; while(j<i&&p!=NULL) { j++; p=p->next;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第3頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第3頁。 if(p==NULL) return0; else { e=p->data; return1; }}intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next; intn=1; while(p!=NULL&&p->data!=e) { p=p->next; n++; } if(p==NULL) return(0); else return(n);}intListInsert(LinkList*&L,inti,ElemTypee){ intj=0; LinkList*p=L,*s; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next; /*將*s插入到*p之后*/ p->next=s; return1; }}intListDelete(LinkList*&L,inti,ElemType&e)數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第4頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第4頁。 intj=0; LinkList*p=L,*q; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { q=p->next; /*q指向要刪除的結點*/ p->next=q->next; /*從單鏈表中刪除*q結點*/ free(q); /*釋放*q結點*/ return1; }}/*文件名:algo2-3.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructDNode /*定義雙鏈表結點類型*/{ ElemTypedata; structDNode*prior; /*指向前驅結點*/ structDNode*next; /*指向后繼結點*/}DLinkList;voidInitList(DLinkList*&L){ L=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建頭結點*/ L->prior=L->next=NULL;}voidDestroyList(DLinkList*&L){ DLinkList*p=L,*q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p);}intListEmpty(DLinkList*L)數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第5頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第5頁。 return(L->next==NULL);}intListLength(DLinkList*L){ DLinkList*p=L;inti=0; while(p->next!=NULL) { i++; p=p->next; } return(i);}voidDispList(DLinkList*L){ DLinkList*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}intGetElem(DLinkList*L,inti,ElemType&e){ intj=0; DLinkList*p=L; while(j<i&&p!=NULL) { j++; p=p->next; } if(p==NULL) return0; else { e=p->data; return1; }}intLocateElem(DLinkList*L,ElemTypee){ intn=1; DLinkList*p=L->next;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第6頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第6頁。 { n++; p=p->next; } if(p==NULL) return(0); else return(n);}intListInsert(DLinkList*&L,inti,ElemTypee){ intj=0; DLinkList*p=L,*s; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { s=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next; /*將*s插入到*p之后*/ if(p->next!=NULL)p->next->prior=s; s->prior=p; p->next=s; return1; }}intListDelete(DLinkList*&L,inti,ElemType&e){ intj=0; DLinkList*p=L,*q; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第7頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第7頁。 q=p->next; /*q指向要刪除的結點*/ if(q==NULL)return0; /*不存在第i個結點*/ p->next=q->next; /*從單鏈表中刪除*q結點*/ if(p->next!=NULL)p->next->prior=p; free(q); /*釋放*q結點*/ return1; }}voidSort(DLinkList*&head) /*雙鏈表元素排序*/{ DLinkList*p=head->next,*q,*r; if(p!=NULL) /*若原雙鏈表中有一個或以上的數(shù)據(jù)結點*/ { r=p->next; /*r保存*p結點后繼結點的指針*/ p->next=NULL; /*構造只含一個數(shù)據(jù)結點的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結點后繼結點的指針*/ q=head; while(q->next!=NULL&&q->next->data<p->data) /*在有序表中找插入*p的前驅結點*q*/ q=q->next; p->next=q->next; /*將*p插入到*q之后*/ if(q->next!=NULL)q->next->prior=p; q->next=p; p->prior=q; p=r; } }}/*文件名:algo2-4.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructLNode /*定義單鏈表結點類型*/{ ElemTypedata;structLNode*next;}LinkList;voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結點*/ L->next=L;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第8頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第8頁。voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=L) { free(p); p=q; q=p->next; } free(p);}intListEmpty(LinkList*L){ return(L->next==L);}intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=L) { i++; p=p->next; } return(i);}voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=L) { printf("%c",p->data); p=p->next; } printf("\n");}intGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p; if(L->next!=L) /*單鏈表不為空表時*/ { if(i==1) {數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第9頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第9頁。 return1; } else /*i不為1時*/ { p=L->next; while(j<i-1&&p!=L) { j++; p=p->next; } if(p==L) return0; else { e=p->data; return1; } } } else /*單鏈表為空表時*/ return0;}intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next; intn=1; while(p!=L&&p->data!=e) { p=p->next; n++; } if(p==L) return(0); else return(n);}intListInsert(LinkList*&L,inti,ElemTypee){ intj=0; LinkList*p=L,*s; if(p->next==L||i==1) /*原單鏈表為空表或i==1時*/ { s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結點*s*/數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第10頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第10頁。 s->next=p->next; /*將*s插入到*p之后*/ p->next=s; return1; } else { p=L->next; while(j<i-2&&p!=L) { j++; p=p->next; } if(p==L) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next; /*將*s插入到*p之后*/ p->next=s; return1; } }}intListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; if(p->next!=L) /*原單鏈表不為空表時*/ { if(i==1) /*i==1時*/ { q=L->next; /*刪除第1個結點*/ L->next=q->next; free(q); return1; } else /*i不為1時*/ { p=L->next; while(j<i-2&&p!=L) { j++;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第11頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第11頁。 } if(p==L) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { q=p->next; /*q指向要刪除的結點*/ p->next=q->next; /*從單鏈表中刪除*q結點*/ free(q); /*釋放*q結點*/ return1; } } } elsereturn0;}/*文件名:algo2-5.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructDNode /*定義雙鏈表結點類型*/{ ElemTypedata; structDNode*prior; /*指向前驅結點*/ structDNode*next; /*指向后繼結點*/}DLinkList;voidInitList(DLinkList*&L){ L=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建頭結點*/ L->prior=L->next=L;}voidDestroyList(DLinkList*&L){ DLinkList*p=L,*q=p->next; while(q!=L) { free(p); p=q; q=p->next; } free(p);}intListEmpty(DLinkList*L){ return(L->next==L);}數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第12頁。intListLen數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第12頁。{ DLinkList*p=L;inti=0; while(p->next!=L) { i++; p=p->next; } return(i);}voidDispList(DLinkList*L){ DLinkList*p=L->next; while(p!=L) { printf("%c",p->data); p=p->next; } printf("\n");}intGetElem(DLinkList*L,inti,ElemType&e){ intj=0; DLinkList*p; if(L->next!=L) /*雙鏈表不為空表時*/ { if(i==1) { e=L->next->data; return1; } else /*i不為1時*/ { p=L->next; while(j<i-1&&p!=L) { j++; p=p->next; } if(p==L) return0; else { e=p->data;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第13頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第13頁。 } } } else /*雙鏈表為空表時*/ return0;}intLocateElem(DLinkList*L,ElemTypee){ intn=1; DLinkList*p=L->next; while(p!=NULL&&p->data!=e) { n++; p=p->next; } if(p==NULL) return(0); else return(n);}intListInsert(DLinkList*&L,inti,ElemTypee){ intj=0; DLinkList*p=L,*s; if(p->next==L) /*原雙鏈表為空表時*/ { s=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建新結點*s*/ s->data=e; p->next=s;s->next=p; p->prior=s;s->prior=p; return1; } elseif(i==1) /*原雙鏈表不為空表但i=1時*/ { s=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next;p->next=s; /*將*s插入到*p之后*/ s->next->prior=s;s->prior=p; return1; } else { p=L->next;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第14頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第14頁。 { j++; p=p->next; } if(p==L) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ { s=(DLinkList*)malloc(sizeof(DLinkList)); /*創(chuàng)建新結點*s*/ s->data=e; s->next=p->next; /*將*s插入到*p之后*/ if(p->next!=NULL)p->next->prior=s; s->prior=p; p->next=s; return1; } }}intListDelete(DLinkList*&L,inti,ElemType&e){ intj=0; DLinkList*p=L,*q; if(p->next!=L) /*原雙鏈表不為空表時*/ { if(i==1) /*i==1時*/ { q=L->next; /*刪除第1個結點*/ L->next=q->next; q->next->prior=L; free(q); return1; } else /*i不為1時*/ { p=L->next; while(j<i-2&&p!=NULL) { j++; p=p->next; } if(p==NULL) /*未找到第i-1個結點*/ return0; else /*找到第i-1個結點*p*/ {數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第15頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第15頁。 if(q==NULL)return0; /*不存在第i個結點*/ p->next=q->next; /*從單鏈表中刪除*q結點*/ if(p->next!=NULL)p->next->prior=p; free(q); /*釋放*q結點*/ return1; } } } elsereturn0; /*原雙鏈表為空表時*/}/*文件名:algo3-1.cpp*/#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{ ElemTypeelem[MaxSize]; inttop; /*棧指針*/}SqStack;voidInitStack(SqStack*&s){ s=(SqStack*)malloc(sizeof(SqStack)); s->top=-1;}voidClearStack(SqStack*&s){ free(s);}intStackLength(SqStack*s){ return(s->top+1);}intStackEmpty(SqStack*s){ return(s->top==-1);}intPush(SqStack*&s,ElemTypee){ if(s->top==MaxSize-1) return0; s->top++; s->elem[s->top]=e; return1;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第16頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第16頁。intPop(SqStack*&s,ElemType&e){ if(s->top==-1) return0; e=s->elem[s->top]; s->top--; return1;}intGetTop(SqStack*s,ElemType&e){ if(s->top==-1) return0; e=s->elem[s->top]; return1;}voidDispStack(SqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->elem[i]); printf("\n");}/*文件名:algo3-2.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlinknode{ ElemTypedata; /*數(shù)據(jù)域*/ structlinknode*next; /*指針域*/}LiStack;voidInitStack(LiStack*&s){ s=(LiStack*)malloc(sizeof(LiStack)); s->next=NULL;}voidClearStack(LiStack*&s){ LiStack*p=s->next; while(p!=NULL) { free(s); s=p; p=p->next;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第17頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第17頁。}intStackLength(LiStack*s){ inti=0; LiStack*p; p=s->next; while(p!=NULL) { i++; p=p->next; } return(i);}intStackEmpty(LiStack*s){ return(s->next==NULL);}voidPush(LiStack*&s,ElemTypee){ LiStack*p; p=(LiStack*)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p結點作為第一個數(shù)據(jù)結點*/ s->next=p;}intPop(LiStack*&s,ElemType&e){ LiStack*p; if(s->next==NULL) /*?？盏那闆r*/ return0; p=s->next; /*p指向第一個數(shù)據(jù)結點*/ e=p->data; s->next=p->next; free(p); return1;}intGetTop(LiStack*s,ElemType&e){ if(s->next==NULL) /*?？盏那闆r*/ return0; e=s->next->data; return1;}數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第18頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第18頁。{ LiStack*p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}/*文件名:algo3-3.cpp*/#include<stdio.h>#include<malloc.h>#defineMaxSize5typedefcharElemType;typedefstruct{ ElemTypeelem[MaxSize]; intfront,rear; /*隊首和隊尾指針*/}SqQueue;voidInitQueue(SqQueue*&q){ q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0;}voidClearQueue(SqQueue*&q){ free(q);}intQueueEmpty(SqQueue*q){ return(q->front==q->rear);}intQueueLength(SqQueue*q){ return(q->rear-q->front+MaxSize)%MaxSize;}intenQueue(SqQueue*&q,ElemTypee){ if((q->rear+1)%MaxSize==q->front)/*隊滿*/ return0; q->rear=(q->rear+1)%MaxSize; q->elem[q->rear]=e; return1;}數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第19頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第19頁。{ if(q->front==q->rear)/*隊空*/ return0; q->front=(q->front+1)%MaxSize; e=q->elem[q->front]; return1;}/*文件名:algo3-4.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructqnode{ ElemTypedata; structqnode*next;}QNode;typedefstruct{ QNode*front; QNode*rear;}LiQueue;voidInitQueue(LiQueue*&q){ q=(LiQueue*)malloc(sizeof(LiQueue)); q->front=q->rear=NULL;}voidClearQueue(LiQueue*&q){ QNode*p=q->front,*r; if(p!=NULL) /*釋放數(shù)據(jù)結點占用空間*/ { r=p->next; while(r!=NULL) { free(p); p=r;r=p->next; } } free(q); /*釋放頭結點占用空間*/}intQueueLength(LiQueue*q){ intn=0; QNode*p=q->front;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第20頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第20頁。 { n++; p=p->next; } return(n);}intQueueEmpty(LiQueue*q){ if(q->rear==NULL) return1; else return0;}voidenQueue(LiQueue*&q,ElemTypee){ QNode*s;s=(QNode*)malloc(sizeof(QNode)); s->data=e; s->next=NULL;if(q->rear==NULL) /*若鏈隊為空,則新結點是隊首結點又是隊尾結點*/ q->front=q->rear=s; else { q->rear->next=s;/*將*s結點鏈到隊尾,rear指向它*/ q->rear=s; }}intdeQueue(LiQueue*&q,ElemType&e){ QNode*t; if(q->rear==NULL) /*隊列為空*/ return0; if(q->front==q->rear)/*隊列中只有一個結點時*/ { t=q->front; q->front=q->rear=NULL; } else /*隊列中有多個結點時*/ { t=q->front; q->front=q->front->next; } e=t->data;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第21頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第21頁。 return1;}/*文件名:algo4-1.cpp*/#include<stdio.h>#defineMaxSize100 /*最多的字符個數(shù)*/typedefstruct{charch[MaxSize]; /*定義可容納MaxSize個字符的空間*/intlen; /*標記當前實際串長*/}SqString;voidStrAssign(SqString&str,charcstr[]) /*str為引用型參數(shù)*/{inti;for(i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}voidStrCopy(SqString&s,SqStringt) /*s為引用型參數(shù)*/{inti;for(i=0;i<t.len;i++)s.ch[i]=t.ch[i];s.len=t.len;}intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.len!=t.len) /*長度不相等時返回0*/same=0;else {for(i=0;i<s.len;i++)if(s.ch[i]!=t.ch[i]) /*有一個對應字符不相同時返回0*/same=0;}returnsame;}intStrLength(SqStrings){returns.len;}SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第22頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第22頁。for(i=0;i<s.len;i++) /*將s.ch[0]～s.ch[s.len-1]復制到str*/str.ch[i]=s.ch[i];for(i=0;i<t.len;i++) /*將t.ch[0]～t.ch[t.len-1]復制到str*/str.ch[s.len+i]=t.ch[i];returnstr;}SqStringSubStr(SqStrings,inti,intj){SqStringstr;intk;str.len=0;if(i<=0||i>s.len||j<0||i+j-1>s.len) { printf("參數(shù)不正確\n");returnstr; /*參數(shù)不正確時返回空串*/ }for(k=i-1;k<i+j-1;k++) /*將s.ch[i]～s.ch[i+j]復制到str*/str.ch[k-i+1]=s.ch[k];str.len=j;returnstr;}SqStringInsStr(SqStrings1,inti,SqStrings2){intj;SqStringstr;str.len=0;if(i<=0||i>s1.len+1) /*參數(shù)不正確時返回空串*/ { printf("參數(shù)不正確\n");returns1; }for(j=0;j<i-1;j++) /*將s1.ch[0]～s1.ch[i-2]復制到str*/str.ch[j]=s1.ch[j];for(j=0;j<s2.len;j++) /*將s2.ch[0]～s2.ch[s2.len-1]復制到str*/str.ch[i+j-1]=s2.ch[j];for(j=i-1;j<s1.len;j++) /*將s1.ch[i-1]～s.ch[s1.len-1]復制到str*/str.ch[s2.len+j]=s1.ch[j];str.len=s1.len+s2.len;returnstr;}SqStringDelStr(SqStrings,inti,intj){intk;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第23頁。SqS數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第23頁。str.len=0;if(i<=0||i>s.len||i+j>s.len+1) /*參數(shù)不正確時返回空串*/ { printf("參數(shù)不正確\n");returnstr; }for(k=0;k<i-1;k++)/*將s.ch[0]～s.ch[i-2]復制到str*/str.ch[k]=s.ch[k];for(k=i+j-1;k<s.len;k++)/*將s.ch[i+j-1]～ch[s.len-1]復制到str*/str.ch[k-j]=s.ch[k];str.len=s.len-j;returnstr;}SqStringRepStr(SqStrings,inti,intj,SqStringt){intk;SqStringstr;str.len=0;if(i<=0||i>s.len||i+j-1>s.len)/*參數(shù)不正確時返回空串*/ { printf("參數(shù)不正確\n");returnstr; }for(k=0;k<i-1;k++) /*將s.ch[0]～s.ch[i-2]復制到str*/str.ch[k]=s.ch[k];for(k=0;k<t.len;k++) /*將t.ch[0]～t.ch[t.len-1]復制到str*/str.ch[i+k-1]=t.ch[k];for(k=i+j-1;k<s.len;k++) /*將s.ch[i+j-1]～ch[s.len-1]復制到str*/str.ch[t.len+k-j]=s.ch[k];str.len=s.len-j+t.len;returnstr;}voidDispStr(SqStringstr){inti;if(str.len>0) {for(i=0;i<str.len;i++)printf("%c",str.ch[i]); printf("\n");}}/*文件名:algo4-2.cpp*/#include<stdio.h>數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第24頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第24頁。typedefstructsnode{chardata;structsnode*next;}LiString;voidStrAssign(LiString*&s,chart[]){inti;LiString*r,*p;s=(LiString*)malloc(sizeof(LiString));s->next=NULL;r=s;for(i=0;t[i]!='\0';i++) { p=(LiString*)malloc(sizeof(LiString)); p->data=t[i];p->next=NULL; r->next=p;r=p; }}voidStrCopy(LiString*&s,LiString*t){LiString*p=t->next,*q,*r;s=(LiString*)malloc(sizeof(LiString));s->next=NULL;s->next=NULL;r=s;while(p!=NULL)/*將t的所有結點復制到s*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}}intStrEqual(LiString*s,LiString*t){LiString*p=s->next,*q=t->next;while(p!=NULL&&q!=NULL&&p->data==q->data) {p=p->next;q=q->next;}if(p==NULL&&q==NULL)return1;elsereturn0;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第25頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第25頁。intStrLength(LiString*s){inti=0;LiString*p=s->next;while(p!=NULL) {i++;p=p->next;}returni;}LiString*Concat(LiString*s,LiString*t){LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));str->next=NULL;r=str;while(p!=NULL) /*將s的所有結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}p=t->next;while(p!=NULL) /*將t的所有結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}returnstr;}LiString*SubStr(LiString*s,inti,intj){intk;LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));str->next=NULL;r=str;if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) { printf("參數(shù)不正確\n");returnstr; /*參數(shù)不正確時返回空串*/ }數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第26頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第26頁。p=p->next;for(k=1;k<=j;k++) /*將s的第i個結點開始的j個結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}returnstr;}LiString*InsStr(LiString*s,inti,LiString*t){intk;LiString*str,*p=s->next,*p1=t->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));str->next=NULL;r=str;if(i<=0||i>StrLength(s)+1) /*參數(shù)不正確時返回空串*/ { printf("參數(shù)不正確\n");returnstr; }for(k=1;k<i;k++) /*將s的前i個結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}while(p1!=NULL) /*將t的所有結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while(p!=NULL) /*將*p及其后的結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;} returnstr;數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第27頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第27頁。LiString*DelStr(LiString*s,inti,intj){intk;LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));str->next=NULL;r=str;if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) { printf("參數(shù)不正確\n");returnstr; /*參數(shù)不正確時返回空串*/ } for(k=0;k<i-1;k++) /*將s的前i-1個結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for(k=0;k<j;k++) /*讓p沿next跳j個結點*/p=p->next;while(p!=NULL) /*將*p及其后的結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;} returnstr;}LiString*RepStr(LiString*s,inti,intj,LiString*t){intk;LiString*str,*p=s->next,*p1=t->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));str->next=NULL;r=str;if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s)) { printf("參數(shù)不正確\n");returnstr; /*參數(shù)不正確時返回空串*/ }for(k=0;k<i-1;k++) /*將s的前i-1個結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第28頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第28頁。r->next=q;r=q;p=p->next;}for(k=0;k<j;k++) /*讓p沿next跳j個結點*/p=p->next;while(p1!=NULL) /*將t的所有結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while(p!=NULL) /*將*p及其后的結點復制到str*/ {q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;} returnstr;}voidDispStr(LiString*s){LiString*p=s->next;while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}/*文件名:algo7-1.cpp*/#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild; /*指向左孩子*/ structnode*rchild; /*指向右孩子*/}BTNode;voidCreateBTNode(BTNode*&b,char*str) /*由str串創(chuàng)建二叉鏈*/{數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第29頁。 BTNo數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第29頁。 inttop=-1,k,j=0; charch; b=NULL; /*建立的二叉樹初始時為空*/ ch=str[j]; while(ch!='\0') /*str未掃描完時循環(huán)*/ { switch(ch) { case'(':top++;St[top]=p;k=1;break; /*為左結點*/ case')':top--;break; case',':k=2;break; /*為右結點*/ default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL)/*p指向二叉樹的根結點*/ b=p; else /*已建立二叉樹根結點*/ { switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }}BTNode*FindNode(BTNode*b,ElemTypex) /*返回data域為x的結點指針*/{ BTNode*p; if(b==NULL) returnNULL; elseif(b->data==x) returnb; else { p=FindNode(b->lchild,x); if(p!=NULL) returnp; else returnFindNode(b->rchild,x); }數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第30頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第30頁。BTNode*LchildNode(BTNode*p) /*返回*p結點的左孩子結點指針*/{returnp->lchild;}BTNode*RchildNode(BTNode*p) /*返回*p結點的右孩子結點指針*/{returnp->rchild;}intBTNodeDepth(BTNode*b) /*求二叉樹b的深度*/{ intlchilddep,rchilddep; if(b==NULL) return(0); /*空樹的高度為0*/ else { lchilddep=BTNodeDepth(b->lchild); /*求左子樹的高度為lchilddep*/ rchilddep=BTNodeDepth(b->rchild); /*求右子樹的高度為rchilddep*/ return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); }}voidDispBTNode(BTNode*b) /*以括號表示法輸出二叉樹*/{ if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTNode(b->lchild); if(b->rchild!=NULL)printf(","); DispBTNode(b->rchild); printf(")"); } }}intBTWidth(BTNode*b)/*求二叉樹b的寬度*/{ struct { intlno; /*結點的層次編號*/ BTNode*p; /*結點指針*/ }Qu[MaxSize]; /*定義順序非循環(huán)隊列*/ intfront,rear; /*定義隊首和隊尾指針*/數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第31頁。 intlnum,數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第31頁。 front=rear=0; /*置隊列為空隊*/if(b!=NULL) { rear++; Qu[rear].p=b; /*根結點指針入隊*/ Qu[rear].lno=1; /*根結點的層次編號為1*/ while(rear!=front) /*隊列不為空*/ { front++; b=Qu[front].p; /*隊頭出隊*/ lnum=Qu[front].lno; if(b->lchild!=NULL) /*左孩子入隊*/ { rear++; Qu[rear].p=b->lchild; Qu[rear].lno=lnum+1; } if(b->rchild!=NULL) /*右孩子入隊*/ { rear++; Qu[rear].p=b->rchild; Qu[rear].lno=lnum+1; } } max=0;lnum=1;i=1; while(i<=rear) { n=0; while(i<=rear&&Qu[i].lno==lnum) { n++;i++; } lnum=Qu[i].lno; if(n>max)max=n; } returnmax; } else return0;}intNodes(BTNode*b) /*求二叉樹b的結點個數(shù)*/{ intnum1,num2;數(shù)據(jù)結構教程(第三版)課后答案全文共數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第32頁。 return0;elseif(b->lchild==NULL&&b->rchild==NULL) return1;else{num1=Nodes(b->lchild);num2=Nodes(b->rchild);return(num1+num2+1); }}intLeafNodes(BTNode*b) /*求二叉樹b的葉子結點個數(shù)*/{ intnum1,num2;if(b==NULL) return0;elseif(b->lchild==NULL&&b->rchild==NULL) return1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);return(num1+num2); }}/*文件名:algo8-1.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlnode{ inttag; /*結點類型標識*/ union { ElemTypedata;structlnode*sublist; }val;structlnode*link; /*指向下一個元素*/}GLNode;GLNode*CreatGL(char*&s) /*由串s建立一個廣義表*/{ GLNode*h; charch; ch=*s; /*取一個掃描字符*/ s++; /*串指針后移一位*/ if(ch!='\0') /*串未結束判斷*/數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第33頁。數(shù)據(jù)結構教程(第三版)課后答案全文共202頁，當前為第33頁。 h=(GLNode*)malloc(sizeof(GLNode)); /*創(chuàng)建一個新結點*/if(ch=='(') /*當前字符為左括號時*/ { h->tag=1; /*新結點作為表頭結點*/h->val.sublist=CreatGL(s); /*遞歸構造子表并鏈到表頭結點*/ } elseif(ch==')') h=NULL; /*遇到')'字符,子表為空*/ else { h->tag=0; /*新結點作為原子結點*/h->val.data=ch; } }elseh=NULL; /*串結束,子表為空*/ch=*s; /*取下一個掃描字符*/s++; /*串指針后移一位*/if(h!=NULL) /*串未結束判斷*/ if(ch==',') /*當前字符為','*/ h->link=CreatGL(s); /*遞歸構造后續(xù)子表*/ else /*串結束*/ h->link=NULL;