数据结构教程(第三版)课后答案

/*文件名: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--;/*将顺序表位序转化为elem下标*/for(j=L->length;j>i;j--)L->elem[j]=L->elem[j-1];L->elem[i]=e;L->length++;return1;/*将elem[i]及后面元素后移置*/一个位/*顺序表长度增1*/}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));L->next=NULL;/*创建头结点*/}

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个结点*/return0;else{/*找到第i-1个结点*p*/s=(LinkList*)malloc(sizeof(LinkList));/*创建新结点*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个结点*/else/*找到第i-1个结点*p*/{q=p->next;p->next=q->next;free(q);/*q指向要删除的结点*//*从单链表中删除*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));/*创建头结点*/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个结点*/return0;else{/*找到第i-1个结点*p*/s=(DLinkList*)malloc(sizeof(DLinkList));/*创建新结点*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*/

q=p->next;/*q指向要删除的结点if(q==NULL)return0;/*不存在第i个结点/*从单链表中删除*q结点*/*/p->next=q->next;*/if(p->next!=NULL)p->next->prior=p;free(q);/*释放*q结点*/return1;}}voidSort(DLinkList*&head)/*双链表元素排序*/{DLinkList*p=head->next,*q,*r;if(p!=NULL){/*若原双链表中有一个或以上的数据结点*/r=p->next;/*r保存*p结点后继结点的指针*//*构造只含一个数据结点的有序表*/p->next=NULL;p=r;while(p!=NULL){r=p->next;q=head;/*r保存*p结点后继结点的指针*/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));L->next=L;/*创建头结点*/}

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){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;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);elsereturn(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));/*创建新结点*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个结点*//*找到第i-1个结点*p*/{s=(LinkList*)malloc(sizeof(LinkList));/*创建新结点*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)/*原单链表不为空表时*//*i==1时*//*删除第{if(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++;p=p->next;

}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));/*创建头结点*/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)/*双链表不为空表时*/{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;return1;

}}}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);elsereturn(n);}intListInsert(DLinkList*&L,inti,ElemTypee){intj=0;DLinkList*p=L,*s;if(p->next==L){/*原双链表为空表时*/s=(DLinkList*)malloc(sizeof(DLinkList));/*创建新结点*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));/*创建新结点*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个结点*//*找到第i-1个结点*p*/return0;else{s=(DLinkList*)malloc(sizeof(DLinkList));/*创建新结点*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)/*原双链表不为空表时*//*i==1时*//*删除第{if(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)return0;else/*未找到第/*找到第i-1个结点*p*//*q指向要删除的结点i-1个结点*/{q=p->next;*/

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

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;/*数据域*//*指针域*/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结点作为第一个数据结点*/}intPop(LiStack*&s,ElemType&e){LiStack*p;if(s->next==NULL)return0;/*栈空的情况*//*p指向第p=s->next;一个数据结点*/e=p->data;s->next=p->next;free(p);return1;}intGetTop(LiStack*s,ElemType&e){if(s->next==NULL)return0;/*栈空的情况*/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;/*队首和队尾指针*/}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;}intdeQueue(SqQueue*&q,ElemType&e)

{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){/*释放数据结点占用空间*/r=p->next;while(r!=NULL){}free(p);p=r;r=p->next;}free(q);/*释放头结点占用空间*/}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)/*若链队为空,则新结点是队首结点又是队尾结点*/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;free(t);

return1;}/*文件名#include<stdio.h>#defineMaxSize100typedefstruct:algo4-1.cpp*//*最多的字符个数*/{charch[MaxSize];intlen;/*定义可容纳MaxSize个字符的空间*//*标记当前实际串长*/}SqString;voidStrAssign(SqString&str,charcstr[])/*str为引用型参数*/{inti;for(i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}voidStrCopy(SqString&s,SqStringt)/*s为引用型参数*/{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;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]复制到str*//*将t.ch[0]～t.ch[t.len-1]复制到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("参数不正确\n");returnstr;/*参数不正确时返回空串*/}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){/*参数不正确时返回空串*/printf("参数不正确\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]复制到str*//*将s2.ch[0]～s2.ch[s2.len-1]复制到str*//*将s1.ch[i-1]～s.ch[s1.len-1]复制到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)/*参数不正确时返回空串*/{printf("参数不正确\n");returnstr;}for(k=0;k<i-1;k++)str.ch[k]=s.ch[k];/*将s.ch[0]～s.ch[i-2]复制到str*/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)/*参数不正确时返回空串*/{printf("参数不正确\n");returnstr;}for(k=0;k<i-1;k++)str.ch[k]=s.ch[k];/*将s.ch[0]～s.ch[i-2]复制到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]复制到str*//*将s.ch[i+j-1]～ch[s.len-1]复制到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的所有结点复制到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的所有结点复制到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("参数不正确\n");returnstr;/*参数不正确时返回空串*/}for(k=0;k<i-1;k++)

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)/*参数不正确时返回空串*/{printf("参数不正确\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;}

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("参数不正确\n");returnstr;/*参数不正确时返回空串*/}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=p->next;while(p!=NULL){/*让p沿next跳j个结点*//*将*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("参数不正确\n");returnstr;/*参数不正确时返回空串*/}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=p->next;/*让p沿next跳j个结点*//*将t的所有结点复制到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及其后的结点复制到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;/*数据元素*//*指向左孩子*//*指向右孩子*/structnode*lchild;structnode*rchild;}BTNode;voidCreateBTNode(BTNode*&b,char*str)/*由str串创建二叉链*/{BTNode*St[MaxSize],*p=NULL;

inttop=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!='\0'){/*建立的二叉树初始时为空*//*str未扫描完时循环*/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;elsereturnFindNode(b->rchild,x);}}

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);else/*空树的高度为0*/{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];intfront,rear;*/*/intlnum,max,i,n;

front=rear=0;if(b!=NULL){/*置队列为空队*/rear++;Qu[rear].p=b;/*根结点指针入队/*根结点的层次编号为1*//*队列*/Qu[rear].lno=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;}elsereturn0;}intNodes(BTNode*b)/*求二叉树b的结点个数*/{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)/*求二叉树b的叶子结点个数*/{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'){

h=(GLNode*)malloc(sizeof(GLNode));/*创建一个新结点*/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);/*递归构造后续子表*//*串结束*/elseh->link=NULL;/*处理表的最后一个元素*//*返回广义表指针*/returnh;}intGLLength(GLNode*g)/*求广义表g的长度*/{intn=0;g=g->val.sublist;while(g!=NULL){/*g指向广义表的第一个元素*/n++;g=g->link;}returnn;}intGLDepth(GLNode*g){/*求带头结点的广义表g的深度*/intmax=0,dep;if(g->tag==0)return0;g=g->val.sublist;if(g==NULL)return1;/*g指向第一个元素*//*为空表时返回1*/while(g!=NULL)/*遍历表中的每一个元素*/

{if(g->tag==1){/*元素为子表的情况*/dep=GLDepth(g);/*递归调用求出子表的深度*/if(dep>max)max=dep;/*max为同中深度的最大值*/一层所求过的子表}g=g->link;/*使g指向下一个元素/*返回表的深度广义表g*/*/}return(max+1);*/}voidDispGL(GLNode*g)/*输出{if(g!=NULL){/*表不为空判断*/if(g->tag==1)/*为表结点时*//*输出'('*/{printf("(");if(g->val.sublist==NULL)printf("");elseDispGL(g->val.sublist);/*输出空子表*//*递归输出子表*/}elseprintf("%c",g->val.data);/*为原子时输出元素值*//*为表结点时输出')'*/if(g->tag==1)printf(")");if(g->link!=NULL){printf(",");DispGL(g->link);}/*递归输出后续表的内容*/}}/*文件名:algo8-2.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlnode{inttag;/*结点类型标识*/union{ElemTypedata;structlnode*sublist;}val;structlnode*link;/*指向下一个元素*/}GLNode;GLNode*GLCopy(GLNode*p)/*p为被复制的广义表的头结点指针*/{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为一个广义表的头结点指针*/{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){/*为原子结点时*/q=(GLNode*)malloc(sizeof(GLNode));q->tag=0;q->val.data=p->val.data;q->link=NULL;}else{/*为子表时,产生虚子表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为一个广义表的头结点指针*/{GLNode*p=g->val.sublist;GLNode*q,*t;

if(g==NULL){/*为空表时*/printf("空表不能求表尾\n");returnNULL;}elseif(g->tag==0){/*为原子时*/printf("原子不能求表尾\n");returnNULL;}p=p->link;t=(GLNode*)malloc(sizeof(GLNode));t->tag=1;t->link=NULL;t->val.sublist=p;q=GLCopy(t);/*建立一个虚表t*/free(t);returnq;}/*文件名:algo9-1.cpp*/#include<stdio.h>#include<malloc.h>#include"graph.h"#defineINF32767/*INF表示∞*/voidMatToList(MGraphg,ALGraph*&G)/*将邻接矩阵g转换成邻接表G*/{inti,j,n=g.vexnum;ArcNode*p;/*n为顶点数*/G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)/*给邻接表中所有头结点的指针域置初值*/G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)/*检查邻接矩阵中每个元素*/for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0)/*邻接矩阵的当前元素不为0*/{p=(ArcNode*)malloc(sizeof(ArcNode));/*创建一个结点*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转换成邻接矩阵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){/*全局数组*/ArcNode*p;visited[v]=1;/*置已访问标记/*输出被访问顶点的编号/*p指向顶点v的第*/printf("%3d",v);p=G->adjlist[v].firstarc;while(p!=NULL){*/一条弧的弧头结点*/if(visited[p->adjvex]==0)/*若p->adjvex顶点未访问,递归访问它*//*p指向顶点v的下一条弧的DFS(G,p->adjvex);p=p->nextarc;弧头结点*/}}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++;/*结点访问标志均置成0*//*访问顶点v*//*v入栈*/St[top]=v;visited[v]=1;while(top>=-1){/*栈不空时循环*//*取栈顶顶点v=St[top];top--;p=G->adjlist[v].firstarc;*/while(p!=NU