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

数据结构教程(第三版)课后答案/*文件名: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)数据结构教程(第三版)课后答案全文共202页，当前为第1页。{数据结构教程(第三版)课后答案全文共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)); /*创建头结点*/ L->next=NULL;数据结构教程(第三版)课后答案全文共202页，当前为第2页。数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第3页。数据结构教程(第三版)课后答案全文共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)); /*创建新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return1; }}intListDelete(LinkList*&L,inti,ElemType&e)数据结构教程(第三版)课后答案全文共202页，当前为第4页。数据结构教程(第三版)课后答案全文共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)); /*创建头结点*/ 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)数据结构教程(第三版)课后答案全文共202页，当前为第5页。数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第6页。数据结构教程(第三版)课后答案全文共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)); /*创建新结点*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*/数据结构教程(第三版)课后答案全文共202页，当前为第7页。数据结构教程(第三版)课后答案全文共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) /*若原双链表中有一个或以上的数据结点*/ { r=p->next; /*r保存*p结点后继结点的指针*/ p->next=NULL; /*构造只含一个数据结点的有序表*/ 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)); /*创建头结点*/ L->next=L;数据结构教程(第三版)课后答案全文共202页，当前为第8页。数据结构教程(第三版)课后答案全文共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) {数据结构教程(第三版)课后答案全文共202页，当前为第9页。数据结构教程(第三版)课后答案全文共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)); /*创建新结点*s*/数据结构教程(第三版)课后答案全文共202页，当前为第10页。数据结构教程(第三版)课后答案全文共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)); /*创建新结点*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++;数据结构教程(第三版)课后答案全文共202页，当前为第11页。数据结构教程(第三版)课后答案全文共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)); /*创建头结点*/ 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);}数据结构教程(第三版)课后答案全文共202页，当前为第12页。intListLen数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第13页。数据结构教程(第三版)课后答案全文共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)); /*创建新结点*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;数据结构教程(第三版)课后答案全文共202页，当前为第14页。数据结构教程(第三版)课后答案全文共202页，当前为第14页。 { j++; p=p->next; } if(p==L) /*未找到第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; 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*/ {数据结构教程(第三版)课后答案全文共202页，当前为第15页。数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第16页。数据结构教程(第三版)课后答案全文共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; /*数据域*/ 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;数据结构教程(第三版)课后答案全文共202页，当前为第17页。数据结构教程(第三版)课后答案全文共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结点作为第一个数据结点*/ s->next=p;}intPop(LiStack*&s,ElemType&e){ LiStack*p; if(s->next==NULL) /*栈空的情况*/ return0; p=s->next; /*p指向第一个数据结点*/ 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;}数据结构教程(第三版)课后答案全文共202页，当前为第18页。数据结构教程(第三版)课后答案全文共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;}数据结构教程(第三版)课后答案全文共202页，当前为第19页。数据结构教程(第三版)课后答案全文共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) /*释放数据结点占用空间*/ { r=p->next; while(r!=NULL) { free(p); p=r;r=p->next; } } free(q); /*释放头结点占用空间*/}intQueueLength(LiQueue*q){ intn=0; QNode*p=q->front;数据结构教程(第三版)课后答案全文共202页，当前为第20页。数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第21页。数据结构教程(第三版)课后答案全文共202页，当前为第21页。 return1;}/*文件名:algo4-1.cpp*/#include<stdio.h>#defineMaxSize100 /*最多的字符个数*/typedefstruct{charch[MaxSize]; /*定义可容纳MaxSize个字符的空间*/intlen; /*标记当前实际串长*/}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;数据结构教程(第三版)课后答案全文共202页，当前为第22页。数据结构教程(第三版)课后答案全文共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("参数不正确\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++) /*将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;数据结构教程(第三版)课后答案全文共202页，当前为第23页。SqS数据结构教程(第三版)课后答案全文共202页，当前为第23页。str.len=0;if(i<=0||i>s.len||i+j>s.len+1) /*参数不正确时返回空串*/ { printf("参数不正确\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)/*参数不正确时返回空串*/ { printf("参数不正确\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>数据结构教程(第三版)课后答案全文共202页，当前为第24页。数据结构教程(第三版)课后答案全文共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;数据结构教程(第三版)课后答案全文共202页，当前为第25页。数据结构教程(第三版)课后答案全文共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("参数不正确\n");returnstr; /*参数不正确时返回空串*/ }数据结构教程(第三版)课后答案全文共202页，当前为第26页。数据结构教程(第三版)课后答案全文共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) /*参数不正确时返回空串*/ { 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;数据结构教程(第三版)课后答案全文共202页，当前为第27页。数据结构教程(第三版)课后答案全文共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("参数不正确\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沿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("参数不正确\n");returnstr; /*参数不正确时返回空串*/ }for(k=0;k<i-1;k++) /*将s的前i-1个结点复制到str*/ {q=(LiString*)malloc(sizeof(LiString));数据结构教程(第三版)课后答案全文共202页，当前为第28页。数据结构教程(第三版)课后答案全文共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; /*数据元素*/ structnode*lchild; /*指向左孩子*/ structnode*rchild; /*指向右孩子*/}BTNode;voidCreateBTNode(BTNode*&b,char*str) /*由str串创建二叉链*/{数据结构教程(第三版)课后答案全文共202页，当前为第29页。 BTNo数据结构教程(第三版)课后答案全文共202页，当前为第29页。 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; else returnFindNode(b->rchild,x); }数据结构教程(第三版)课后答案全文共202页，当前为第30页。数据结构教程(第三版)课后答案全文共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]; /*定义顺序非循环队列*/ intfront,rear; /*定义队首和队尾指针*/数据结构教程(第三版)课后答案全文共202页，当前为第31页。 intlnum,数据结构教程(第三版)课后答案全文共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的结点个数*/{ intnum1,num2;数据结构教程(第三版)课后答案全文共数据结构教程(第三版)课后答案全文共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的叶子结点个数*/{ 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') /*串未结束判断*/数据结构教程(第三版)课后答案全文共202页，当前为第33页。数据结构教程(第三版)课后答案全文共202页，当前为第33页。 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); /*递归构造后续子表*/ else /*串结束*/ h->link=NULL;