數(shù)據(jù)結(jié)構(gòu)教程(第三版)課后答案

/*文件名: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){

inti=0;while(i<L->length&&L->elem[i]!=e)i++;if(i>=L->length)return0;elsereturni+1;}intListInsert(SqList*&L,inti,ElemTypee){intj;if(i<1||i>L->length+1)return0;i--;/*將順序表位序轉(zhuǎn)化為elem下標(biāo)*/for(j=L->length;j>i;j--)L->elem[j]=L->elem[j-1];L->elem[i]=e;L->length++;return1;/*將elem[i]及后面元素后移置*/一個(gè)位/*順序表長(zhǎng)度增1*/}intListDelete(SqList*&L,inti,ElemType&e){intj;if(i<1||i>L->length)return0;i--;/*將順序表位序轉(zhuǎn)化為elem下標(biāo)*/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/*定義單鏈表結(jié)點(diǎn)類(lèi)型*/{ElemTypedata;structLNode*next;}LinkList;voidInitList(LinkList*&L){L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;/*創(chuàng)建頭結(jié)點(diǎn)*/}

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;}

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);elsereturn(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個(gè)結(jié)點(diǎn)*/return0;else{/*找到第i-1個(gè)結(jié)點(diǎn)*p*/s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*s*/s->data=e;s->next=p->next;p->next=s;/*將*s插入到*p之后*/return1;}}intListDelete(LinkList*&L,inti,ElemType&e){

intj=0;LinkList*p=L,*q;while(j<i-1&&p!=NULL){j++;p=p->next;}if(p==NULL)return0;/*未找到第i-1個(gè)結(jié)點(diǎn)*/else/*找到第i-1個(gè)結(jié)點(diǎn)*p*/{q=p->next;p->next=q->next;free(q);/*q指向要?jiǎng)h除的結(jié)點(diǎn)*//*從單鏈表中刪除*q結(jié)點(diǎn)*//*釋放*q結(jié)點(diǎn)*/return1;}}/*文件名:algo2-3.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructDNode{/*定義雙鏈表結(jié)點(diǎn)類(lèi)型*/ElemTypedata;structDNode*prior;/*指向前驅(qū)結(jié)點(diǎn)*/structDNode*next;/*指向后繼結(jié)點(diǎn)*/}DLinkList;voidInitList(DLinkList*&L){L=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/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){

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;while(p!=NULL&&p->data!=e)

{}n++;p=p->next;if(p==NULL)return(0);elsereturn(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個(gè)結(jié)點(diǎn)*/return0;else{/*找到第i-1個(gè)結(jié)點(diǎn)*p*/s=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建新結(jié)點(diǎn)*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個(gè)結(jié)點(diǎn)*/return0;else{/*找到第i-1個(gè)結(jié)點(diǎn)*p*/

q=p->next;/*q指向要?jiǎng)h除的結(jié)點(diǎn)if(q==NULL)return0;/*不存在第i個(gè)結(jié)點(diǎn)/*從單鏈表中刪除*q結(jié)點(diǎn)*/*/p->next=q->next;*/if(p->next!=NULL)p->next->prior=p;free(q);/*釋放*q結(jié)點(diǎn)*/return1;}}voidSort(DLinkList*&head)/*雙鏈表元素排序*/{DLinkList*p=head->next,*q,*r;if(p!=NULL){/*若原雙鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn)*/r=p->next;/*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*//*構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表*/p->next=NULL;p=r;while(p!=NULL){r=p->next;q=head;/*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*/while(q->next!=NULL&&q->next->data<p->data)/*在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*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{/*定義單鏈表結(jié)點(diǎn)類(lèi)型*/ElemTypedata;structLNode*next;}LinkList;voidInitList(LinkList*&L){L=(LinkList*)malloc(sizeof(LinkList));L->next=L;/*創(chuàng)建頭結(jié)點(diǎn)*/}

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)/*單鏈表不為空表時(shí)*/{if(i==1){e=L->next->data;

return1;}else{/*i不為1時(shí)*/p=L->next;while(j<i-1&&p!=L){j++;p=p->next;}if(p==L)return0;else{e=p->data;return1;}}}else/*單鏈表為空表時(shí)*/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);elsereturn(n);}intListInsert(LinkList*&L,inti,ElemTypee){intj=0;LinkList*p=L,*s;if(p->next==L||i==1)/*原單鏈表為空表或i==1時(shí)*/{s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*s*/s->data=e;

s->next=p->next;p->next=s;/*將*s插入到*p之后*/return1;}else{p=L->next;while(j<i-2&&p!=L){j++;p=p->next;}if(p==L)return0;else/*未找到第i-1個(gè)結(jié)點(diǎn)*//*找到第i-1個(gè)結(jié)點(diǎn)*p*/{s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*s*/s->data=e;s->next=p->next;p->next=s;/*將*s插入到*p之后*/return1;}}}intListDelete(LinkList*&L,inti,ElemType&e){intj=0;LinkList*p=L,*q;if(p->next!=L)/*原單鏈表不為空表時(shí)*//*i==1時(shí)*//*刪除第{if(i==1){q=L->next;1個(gè)結(jié)點(diǎn)*/L->next=q->next;free(q);return1;}else{/*i不為1時(shí)*/p=L->next;while(j<i-2&&p!=L){j++;p=p->next;

}if(p==L)/*未找到第i-1個(gè)結(jié)點(diǎn)*/return0;else{/*找到第i-1個(gè)結(jié)點(diǎn)*p*/q=p->next;/*q指向要?jiǎng)h除的結(jié)點(diǎn)*/p->next=q->next;/*從單鏈表中刪除*q結(jié)點(diǎn)*/free(q);/*釋放*q結(jié)點(diǎn)*/return1;}}}elsereturn0;}/*文件名:algo2-5.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructDNode{/*定義雙鏈表結(jié)點(diǎn)類(lèi)型*/ElemTypedata;structDNode*prior;/*指向前驅(qū)結(jié)點(diǎn)*/structDNode*next;/*指向后繼結(jié)點(diǎn)*/}DLinkList;voidInitList(DLinkList*&L){L=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/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);}intListLength(DLinkList*L)

{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)/*雙鏈表不為空表時(shí)*/{if(i==1){e=L->next->data;return1;}else{/*i不為1時(shí)*/p=L->next;while(j<i-1&&p!=L){j++;p=p->next;}if(p==L)return0;else{e=p->data;return1;

}}}else/*雙鏈表為空表時(shí)*/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);elsereturn(n);}intListInsert(DLinkList*&L,inti,ElemTypee){intj=0;DLinkList*p=L,*s;if(p->next==L){/*原雙鏈表為空表時(shí)*/s=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建新結(jié)點(diǎn)*s*/s->data=e;p->next=s;s->next=p;p->prior=s;s->prior=p;return1;}elseif(i==1){/*原雙鏈表不為空表但i=1時(shí)*/s=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建新結(jié)點(diǎn)*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;while(j<i-2&&p!=L)

{j++;p=p->next;}if(p==L)/*未找到第i-1個(gè)結(jié)點(diǎn)*//*找到第i-1個(gè)結(jié)點(diǎn)*p*/return0;else{s=(DLinkList*)malloc(sizeof(DLinkList));/*創(chuàng)建新結(jié)點(diǎn)*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)/*原雙鏈表不為空表時(shí)*//*i==1時(shí)*//*刪除第{if(i==1){q=L->next;1個(gè)結(jié)點(diǎn)*/L->next=q->next;q->next->prior=L;free(q);return1;}else{/*i不為1時(shí)*/p=L->next;while(j<i-2&&p!=NULL){j++;p=p->next;}if(p==NULL)return0;else/*未找到第/*找到第i-1個(gè)結(jié)點(diǎn)*p*//*q指向要?jiǎng)h除的結(jié)點(diǎn)i-1個(gè)結(jié)點(diǎn)*/{q=p->next;*/

if(q==NULL)return0;/*不存在第i個(gè)結(jié)點(diǎn)*/p->next=q->next;/*從單鏈表中刪除*q結(jié)點(diǎn)*/if(p->next!=NULL)p->next->prior=p;free(q);/*釋放*q結(jié)點(diǎn)*/return1;}}}elsereturn0;/*原雙鏈表為空表時(shí)*/}/*文件名: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;}

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;}

}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;s->next=p;/*插入*p結(jié)點(diǎn)作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/}intPop(LiStack*&s,ElemType&e){LiStack*p;if(s->next==NULL)return0;/*?？盏那闆r*//*p指向第p=s->next;一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/e=p->data;s->next=p->next;free(p);return1;}intGetTop(LiStack*s,ElemType&e){if(s->next==NULL)return0;/*?？盏那闆r*/e=s->next->data;return1;}voidDispStack(LiStack*s)

{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;/*隊(duì)首和隊(duì)尾指針*/}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)/*隊(duì)滿(mǎn)*/return0;q->rear=(q->rear+1)%MaxSize;q->elem[q->rear]=e;return1;}intdeQueue(SqQueue*&q,ElemType&e)

{if(q->front==q->rear)/*隊(duì)空*/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ù)結(jié)點(diǎn)占用空間*/r=p->next;while(r!=NULL){}free(p);p=r;r=p->next;}free(q);/*釋放頭結(jié)點(diǎn)占用空間*/}intQueueLength(LiQueue*q){intn=0;QNode*p=q->front;while(p!=NULL)

{}n++;p=p->next;return(n);}intQueueEmpty(LiQueue*q){if(q->rear==NULL)return1;elsereturn0;}voidenQueue(LiQueue*&q,ElemTypee){QNode*s;s=(QNode*)malloc(sizeof(QNode));s->data=e;s->next=NULL;if(q->rear==NULL)/*若鏈隊(duì)為空,則新結(jié)點(diǎn)是隊(duì)首結(jié)點(diǎn)又是隊(duì)尾結(jié)點(diǎn)*/q->front=q->rear=s;else{q->rear->next=s;/*將*s結(jié)點(diǎn)鏈到隊(duì)尾,rear指向它*/q->rear=s;}}intdeQueue(LiQueue*&q,ElemType&e){QNode*t;if(q->rear==NULL)return0;/*隊(duì)列為空*/if(q->front==q->rear)/*隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)*/{t=q->front;q->front=q->rear=NULL;}else{/*隊(duì)列中有多個(gè)結(jié)點(diǎn)時(shí)*/t=q->front;q->front=q->front->next;}e=t->data;free(t);

return1;}/*文件名#include<stdio.h>#defineMaxSize100typedefstruct:algo4-1.cpp*//*最多的字符個(gè)數(shù)*/{charch[MaxSize];intlen;/*定義可容納MaxSize個(gè)字符的空間*//*標(biāo)記當(dāng)前實(shí)際串長(zhǎng)*/}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)/*長(zhǎng)度不相等時(shí)返回0*/same=0;else{for(i=0;i<s.len;i++)if(s.ch[i]!=t.ch[i])/*有一個(gè)對(duì)應(yīng)字符不相同時(shí)返回0*/same=0;}returnsame;}intStrLength(SqStrings){returns.len;}SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.len=s.len+t.len;

for(i=0;i<s.len;i++)str.ch[i]=s.ch[i];/*將s.ch[0]～s.ch[s.len-1]復(fù)制到str*//*將t.ch[0]～t.ch[t.len-1]復(fù)制到str*/for(i=0;i<t.len;i++)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ù)不正確時(shí)返回空串*/}for(k=i-1;k<i+j-1;k++)/*將s.ch[i]～s.ch[i+j]復(fù)制到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ù)不正確時(shí)返回空串*/printf("參數(shù)不正確\n");returns1;}for(j=0;j<i-1;j++)str.ch[j]=s1.ch[j];for(j=0;j<s2.len;j++)str.ch[i+j-1]=s2.ch[j];/*將s1.ch[0]～s1.ch[i-2]復(fù)制到str*//*將s2.ch[0]～s2.ch[s2.len-1]復(fù)制到str*//*將s1.ch[i-1]～s.ch[s1.len-1]復(fù)制到str*/for(j=i-1;j<s1.len;j++)str.ch[s2.len+j]=s1.ch[j];str.len=s1.len+s2.len;returnstr;}SqStringDelStr(SqStrings,inti,intj){intk;SqStringstr;

str.len=0;if(i<=0||i>s.len||i+j>s.len+1)/*參數(shù)不正確時(shí)返回空串*/{printf("參數(shù)不正確\n");returnstr;}for(k=0;k<i-1;k++)str.ch[k]=s.ch[k];/*將s.ch[0]～s.ch[i-2]復(fù)制到str*/for(k=i+j-1;k<s.len;k++)/*將s.ch[i+j-1]～ch[s.len-1]復(fù)制到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ù)不正確時(shí)返回空串*/{printf("參數(shù)不正確\n");returnstr;}for(k=0;k<i-1;k++)str.ch[k]=s.ch[k];/*將s.ch[0]～s.ch[i-2]復(fù)制到str*/for(k=0;k<t.len;k++)str.ch[i+k-1]=t.ch[k];for(k=i+j-1;k<s.len;k++)str.ch[t.len+k-j]=s.ch[k];str.len=s.len-j+t.len;returnstr;/*將t.ch[0]～t.ch[t.len-1]復(fù)制到str*//*將s.ch[i+j-1]～ch[s.len-1]復(fù)制到str*/}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>#include<malloc.h>

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的所有結(jié)點(diǎn)復(fù)制到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;}

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的所有結(jié)點(diǎn)復(fù)制到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的所有結(jié)點(diǎn)復(fù)制到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í)返回空串*/}for(k=0;k<i-1;k++)

p=p->next;for(k=1;k<=j;k++){/*將s的第i個(gè)結(jié)點(diǎn)開(kāi)始的j個(gè)結(jié)點(diǎn)復(fù)制到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ù)不正確時(shí)返回空串*/{printf("參數(shù)不正確\n");returnstr;}for(k=1;k<i;k++){/*將s的前i個(gè)結(jié)點(diǎn)復(fù)制到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的所有結(jié)點(diǎn)復(fù)制到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及其后的結(jié)點(diǎn)復(fù)制到str*/q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}returnstr;}

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ù)不正確時(shí)返回空串*/}for(k=0;k<i-1;k++){/*將s的前i-1個(gè)結(jié)點(diǎn)復(fù)制到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=p->next;while(p!=NULL){/*讓p沿next跳j個(gè)結(jié)點(diǎn)*//*將*p及其后的結(jié)點(diǎn)復(fù)制到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ù)不正確時(shí)返回空串*/}for(k=0;k<i-1;k++){/*將s的前i-1個(gè)結(jié)點(diǎn)復(fù)制到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=p->next;/*讓p沿next跳j個(gè)結(jié)點(diǎn)*//*將t的所有結(jié)點(diǎn)復(fù)制到str*/while(p1!=NULL){q=(LiString*)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while(p!=NULL){/*將*p及其后的結(jié)點(diǎn)復(fù)制到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)建二叉鏈*/{BTNode*St[MaxSize],*p=NULL;

inttop=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!='\0'){/*建立的二叉樹(shù)初始時(shí)為空*//*str未掃描完時(shí)循環(huán)*/switch(ch){case'(':top++;St[top]=p;k=1;break;/*為左結(jié)點(diǎn)*//*為右結(jié)點(diǎn)*/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指向二叉樹(shù)的根結(jié)點(diǎn)*//*已建立二叉樹(shù)根結(jié)點(diǎn)*/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域?yàn)閤的結(jié)點(diǎn)指針*/{BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b->rchild,x);}}

BTNode*LchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針*/{returnp->lchild;}BTNode*RchildNode(BTNode*p)/*返回*p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針*/{returnp->rchild;}intBTNodeDepth(BTNode*b)/*求二叉樹(shù)b的深度*/{intlchilddep,rchilddep;if(b==NULL)return(0);else/*空樹(shù)的高度為0*/{lchilddep=BTNodeDepth(b->lchild);/*求左子樹(shù)的高度為lchilddep*/rchilddep=BTNodeDepth(b->rchild);/*求右子樹(shù)的高度為rchilddep*/return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}voidDispBTNode(BTNode*b)/*以括號(hào)表示法輸出二叉樹(shù)*/{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)/*求二叉樹(shù)b的寬度*/{struct{intlno;/*結(jié)點(diǎn)的層次編號(hào)*//*結(jié)點(diǎn)指針/*定義順序非循環(huán)隊(duì)列*//*定義隊(duì)首和隊(duì)尾指針BTNode*p;}Qu[MaxSize];intfront,rear;*/*/intlnum,max,i,n;

front=rear=0;if(b!=NULL){/*置隊(duì)列為空隊(duì)*/rear++;Qu[rear].p=b;/*根結(jié)點(diǎn)指針入隊(duì)/*根結(jié)點(diǎn)的層次編號(hào)為1*//*隊(duì)列*/Qu[rear].lno=1;while(rear!=front)不為空*/{front++;b=Qu[front].p;/*隊(duì)頭出隊(duì)*/lnum=Qu[front].lno;if(b->lchild!=NULL)/*左孩子入隊(duì)*/{rear++;Qu[rear].p=b->lchild;Qu[rear].lno=lnum+1;}if(b->rchild!=NULL)/*右孩子入隊(duì)*/{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;}elsereturn0;}intNodes(BTNode*b)/*求二叉樹(shù)b的結(jié)點(diǎn)個(gè)數(shù)*/{intnum1,num2;if(b==NULL)

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)/*求二叉樹(shù)b的葉子結(jié)點(diǎn)個(gè)數(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;/*結(jié)點(diǎn)類(lèi)型標(biāo)識(shí)*/union{ElemTypedata;structlnode*sublist;}val;structlnode*link;/*指向下一個(gè)元素*/}GLNode;GLNode*CreatGL(char*&s)/*由串s建立一個(gè)廣義表*/{GLNode*h;charch;ch=*s;s++;/*取一個(gè)掃描字符*//*串指針后移一位*//*串未結(jié)束判斷*/if(ch!='\0'){

h=(GLNode*)malloc(sizeof(GLNode));/*創(chuàng)建一個(gè)新結(jié)點(diǎn)*/if(ch=='('){/*當(dāng)前字符為左括號(hào)時(shí)*/h->tag=1;/*新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)*/h->val.sublist=CreatGL(s);/*遞歸構(gòu)造子表并鏈到表頭結(jié)點(diǎn)*/}elseif(ch==')')h=NULL;else/*遇到')'字符,子表為空*//*新結(jié)點(diǎn)作為原子結(jié)點(diǎn)*/{h->tag=0;h->val.data=ch;}}elseh=NULL;ch=*s;/*串結(jié)束,子表為空*//*取下一個(gè)掃描字符*//*串指針后移一位*//*串未結(jié)束判斷*/s++;if(h!=NULL)if(ch==',')/*當(dāng)前字符為','*/h->link=CreatGL(s);/*遞歸構(gòu)造后續(xù)子表*//*串結(jié)束*/elseh->link=NULL;/*處理表的最后一個(gè)元素*//*返回廣義表指針*/returnh;}intGLLength(GLNode*g)/*求廣義表g的長(zhǎng)度*/{intn=0;g=g->val.sublist;while(g!=NULL){/*g指向廣義表的第一個(gè)元素*/n++;g=g->link;}returnn;}intGLDepth(GLNode*g){/*求帶頭結(jié)點(diǎn)的廣義表g的深度*/intmax=0,dep;if(g->tag==0)return0;g=g->val.sublist;if(g==NULL)return1;/*g指向第一個(gè)元素*//*為空表時(shí)返回1*/while(g!=NULL)/*遍歷表中的每一個(gè)元素*/

{if(g->tag==1){/*元素為子表的情況*/dep=GLDepth(g);/*遞歸調(diào)用求出子表的深度*/if(dep>max)max=dep;/*max為同中深度的最大值*/一層所求過(guò)的子表}g=g->link;/*使g指向下一個(gè)元素/*返回表的深度廣義表g*/*/}return(max+1);*/}voidDispGL(GLNode*g)/*輸出{if(g!=NULL){/*表不為空判斷*/if(g->tag==1)/*為表結(jié)點(diǎn)時(shí)*//*輸出'('*/{printf("(");if(g->val.sublist==NULL)printf("");elseDispGL(g->val.sublist);/*輸出空子表*//*遞歸輸出子表*/}elseprintf("%c",g->val.data);/*為原子時(shí)輸出元素值*//*為表結(jié)點(diǎn)時(shí)輸出')'*/if(g->tag==1)printf(")");if(g->link!=NULL){printf(",");DispGL(g->link);}/*遞歸輸出后續(xù)表的內(nèi)容*/}}/*文件名:algo8-2.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlnode{inttag;/*結(jié)點(diǎn)類(lèi)型標(biāo)識(shí)*/union{ElemTypedata;structlnode*sublist;}val;structlnode*link;/*指向下一個(gè)元素*/}GLNode;GLNode*GLCopy(GLNode*p)/*p為被復(fù)制的廣義表的頭結(jié)點(diǎn)指針*/{GLNode*q;

if(p==NULL)returnNULL;q=(GLNode*)malloc(sizeof(GLNode));q->tag=p->tag;if(p->tag==1)q->val.sublist=GLCopy(p->val.sublist);elseq->val.data=p->val.data;q->link=GLCopy(p->link);returnq;}GLNode*head(GLNode*h)/*h為一個(gè)廣義表的頭結(jié)點(diǎn)指針*/{GLNode*p=h->val.sublist;GLNode*q,*t;if(p==NULL){printf("空表不能求表頭\n");returnNULL;}elseif(h->tag==0){printf("原子不能求表頭\n");returnNULL;}if(p->tag==0){/*為原子結(jié)點(diǎn)時(shí)*/q=(GLNode*)malloc(sizeof(GLNode));q->tag=0;q->val.data=p->val.data;q->link=NULL;}else{/*為子表時(shí),產(chǎn)生虛子表t*/t=(GLNode*)malloc(sizeof(GLNode));t->tag=1;t->val.sublist=p->val.sublist;t->link=NULL;q=GLCopy(t);free(t);}returnq;}GLNode*tail(GLNode*g)/*g為一個(gè)廣義表的頭結(jié)點(diǎn)指針*/{GLNode*p=g->val.sublist;GLNode*q,*t;

if(g==NULL){/*為空表時(shí)*/printf("空表不能求表尾\n");returnNULL;}elseif(g->tag==0){/*為原子時(shí)*/printf("原子不能求表尾\n");returnNULL;}p=p->link;t=(GLNode*)malloc(sizeof(GLNode));t->tag=1;t->link=NULL;t->val.sublist=p;q=GLCopy(t);/*建立一個(gè)虛表t*/free(t);returnq;}/*文件名:algo9-1.cpp*/#include<stdio.h>#include<malloc.h>#include"graph.h"#defineINF32767/*INF表示∞*/voidMatToList(MGraphg,ALGraph*&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{inti,j,n=g.vexnum;ArcNode*p;/*n為頂點(diǎn)數(shù)*/G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)/*給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值*/G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)/*檢查鄰接矩陣中每個(gè)元素*/for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0)/*鄰接矩陣的當(dāng)前元素不為0*/{p=(ArcNode*)malloc(sizeof(ArcNode));/*創(chuàng)建一個(gè)結(jié)點(diǎn)*p*/p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;/*將*p鏈到鏈表后*/}G->n=n;G->e=g.arcnum;}voidListToMat(ALGraph*G,MGraph&g)/*將鄰接表G轉(zhuǎn)換成鄰接矩陣g*/

{inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++)/*g.edges[i][j]賦初值0*/for(j=0;j<n;j++)g.edges[i][j]=0;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.vexnum=n;g.arcnum=G->e;}voidDispMat(MGraphg)/*輸出鄰接矩陣g*/{inti,j;for(i=0;i<g.vexnum;i++){for(j=0;j<g.vexnum;j++)if(g.edges[i][j]==INF)printf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("\n");}}voidDispAdj(ALGraph*G)/*輸出鄰接表G*/{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if(p!=NULL)printf("%3d:",i);while(p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;

}printf("\n");}}/*文件名:algo9-2.cpp*/#include<stdio.h>#include<malloc.h>#include"graph.h"intvisited[MAXV];voidDFS(ALGraph*G,intv){/*全局?jǐn)?shù)組*/ArcNode*p;visited[v]=1;/*置已訪(fǎng)問(wèn)標(biāo)記/*輸出被訪(fǎng)問(wèn)頂點(diǎn)的編號(hào)/*p指向頂點(diǎn)v的第*/printf("%3d",v);p=G->adjlist[v].firstarc;while(p!=NULL){*/一條弧的弧頭結(jié)點(diǎn)*/if(visited[p->adjvex]==0)/*若p->adjvex頂點(diǎn)未訪(fǎng)問(wèn),遞歸訪(fǎng)問(wèn)它*//*p指向頂點(diǎn)v的下一條弧的DFS(G,p->adjvex);p=p->nextarc;弧頭結(jié)點(diǎn)*/}}voidDFS1(ALGraph*G,intv){inti,visited[MAXV],St[MAXV],top=-1;ArcNode*p;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);top++;/*結(jié)點(diǎn)訪(fǎng)問(wèn)標(biāo)志均置成0*//*訪(fǎng)問(wèn)頂點(diǎn)v*//*v入棧*/St[top]=v;visited[v]=1;while(top>=-1){/*棧不空時(shí)循環(huán)*//*取棧頂頂點(diǎn)v=St[top];top--;p=G->adjlist[v].firstarc;*/while(p!=NU