数据结构课后作业习题答案.doc

第二章3. 头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。4. Void Lins(Seqlist *L, ElemType x) int i; for(i=L.last;i=0;i-) if(xL.elemi) L.elemi+1=L.elemi;else L.elemi+1=x; break; 5.#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k) int j; if(i(L-last+2) printf(“输入的i，k值不合法”); return ERROR; if(i+k)=(L-last+2) L-last=i-2; ruturn OK; elsefor(j=i+k-1;jlast;j+) elemj-k=elemj; L-last=L-last-k;return OK;6. void Ldel(Seqlist *L,ElemType item) int i; i=L.last; while(i=0) while(L.elemi!=item &i=0) i-; if(i=0) For( j=I;j=0&iL.last) x=L.elemi; for( j=i+1;j=L.last;j+) if(x!=L.elemj) continue; else for(k=j;knext; While(p!=NULL) If(p-datanext; else if(p-datanext;free(r); else pre-next=p; break; 9.（1）void reverse(SeqList *L) int i,j,tmp; for(i=0, j=L.last; inext; L-next=NULL;While(p!=NULL) q=p-next; p-next= L-next; L-next= p; p=q; 10. int LocateLink(LinkList L, int k, *e) LinkList p; int i,j=0,len=0; p=L-next; while(p!=NULL) p=p-next; len+; i=len-k+1; if(inext!=NULL)&(jnext; j+; if(i=j) *e=p-data; return(TRUE); else return(FALSE);11. void MergeLink(LinkList La, LinkList Lb, LinkList Lc) LinkList pa, pan, pb, pbn; pa=La-next; pb=Lb-next; while(pa!=NULL)&(pb!=NULL) if(pa-datadata) pan=pa-next; pa-next=Lc-next; Lc-next=pa; pa=pan;else pbn=pb-next; pb-next=Lc-next; Lc-next=pb; pb=pbn; while(pa!=NULL) pan=pa-next; pa-next=Lc-next; Lc-next=pa; pa=pan;while(pb!=NULL) pbn=pb-next; pb-next=Lc-next; Lc-next=pb; pb=pbn;12. int QKSortLink(LinkList L) LinkList p,q,r; /p指向链表第一个节点，q指向当前待处理，r指向其后继 p=L-next; if(p-next=NULL) return FALSE; else q=p-next;p-next=NULL; while(q!=NULL) if(p-dataq-data) r=q-next; q-next=L-next; L-next=q; q=r; else r=q-next; q-next=p-next; p-next=q; q=r;return TRUE;13. void CirLinkDel(CirLinkList s) CirLinkList p,q; P=s-next; If(p-next=s) s-next=s; free(p);Else q=p-next; while(q-next!=s) p=q; q=q-next;p-next=s; free(q);14. int CirLinkCreat(LinkList L, LinkList Cl, LinkList Cd, LinkList Cq) LinkList p,q; Cl=( LinkList)malloc(sizeof(Node); Cd=( LinkList)malloc(sizeof(Node); Cq=( LinkList)malloc(sizeof(Node); If(Cl=NULL | Cd=NULL | Cq=NULL) return FALSE; p=L-next; q=p-next;while(p!=NULL) if(p-data=0 & p-data=9) p-next=Cd-next; Cd-next=p; p=q; q=p-next;else if(p-data=A & p-data=Z | p-data=A & p-data=Z) p-next=Cl-next; Cl-next=p; p=q; q=p-next;else p-next=Cq-next; Cq-next=p; p=q; q=p-next; return TRUE 15. int MergeLinkList(La, LinkList Lb, LinkList Lc) LinkList pa, pb, pc; Lc=(LinkList)malloc(sizeof(Node); if(Lc=NULL) return FALSE; pc=Lc; pa=La-next; pb=Lb-next; while( pa!=NULL & pb!=NULL ) pc-next=pa; pc=pa; pa=pa-next; pc-next=pb; pc=pb; pb=pb-next;While( pa!=NULL ) pc-next=pa; return TRUE; While( pb!=NULL ) pc-next=pb; return TRUE; 16. typedef struct node int power; 幂 float coef; 系数 ElemType other; 其他信息 struct node *next; 指向后继的指针 PNode,*PolyLinkedList;void PolyDis(PolyLinkedList poly)将poly表示的多项式链表分解为各含奇次幂或偶次幂项的两个循环链表 PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode); poly2表示只含奇次幂的多项式 r2=poly2; r2是只含奇次幂的多项式链表的尾指针 r1=poly; r1是只含偶次幂的多项式链表当前结点的前驱结点的指针 p=poly-next; 链表带头结点，p指向第一个元素 while(p!=poly) if(p-power % 2)处理奇次幂 r=p-next; 暂存后继 r2-next=p; 结点链入奇次幂链表r2=p; 尾指针后移 p=r; 恢复当前待处理结点 else 处理偶次幂 r1-next=p; r1=p; p=p-next; r-next=poly2; r1-next=poly; 构成循环链表 PolyDis17. double PolyvalueLink( PolyList poly, double x) PolyList p; int i; double s,sum=0; p=poly-next; while(p!=NULL) s=p-coef; for( i=1; iexp; i+ ) s=s*x;sum=sum+s;p=p-next; return sum;第三章1-8。略3. 栈有顺序栈和链栈两种存储结构。 在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。 在带头结点链栈中，栈顶指针top-next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。9. #include #include #include #define OK 1#define ERROR 0#define OVERFLOW 0typedef struct N0de int data; struct N0de *next; N0de,*QueuePtr; typedef struct QueuePtr rear; LinkQueue; int InintQueue(LinkQueue &Q) Q.rear=(QueuePtr)malloc(sizeof(N0de); if(!Q.rear) return(OVERFLOW); Q.rear-next=Q.rear; return OK; int EnQueue(LinkQueue &Q,int e) QueuePtr p; p=(QueuePtr)malloc(sizeof(N0de); p-data=e; p-next=Q.rear-next; Q.rear-next=p; Q.rear=p; return OK; int DeQueue(LinkQueue &Q,int &e) QueuePtr p; if(Q.rear-next=Q.rear) return 0; p=Q.rear-next-next; e=p-data; Q.rear-next-next=p-next; If ( Q.rear=p ) Q.rear-next=Q.rear-next-next; Q.rear=Q.rear-next; free(p); return OK; void main() LinkQueue Q; int i,e,n; InintQueue(Q); printf(input the number of the data:); scanf(%d,&n); for(i=0;in;i+) printf(enter the queue:); scanf(%d,&e); EnQueue(Q,e); printf(input the number of the datas to out:); scanf(%d,&n); for(i=0;ifront=Q-front & tag=1) /*队满*/ return(FALSE); if(Q-front=Q-front & tag=0) /*x入队前队空，x入队后重新设置标志*/ tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE); 出队算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*删除队头元素，用x返回其值*/if(Q-front=Q-rear & tag=0) /*队空*/ return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/if(Q-front=Q-rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/Return(TUUE); 11. 1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 共14种#include #include #include int count=0; char a10; /*数组a 存储入栈序列*/ void pop( char a, int k, int n) /*求所有出栈序列*/ int i, u, v, w,flag; char temp, t10; strcpy(t,a) ; if( k=n) flag=1; for( u=0; u=n- 2; u+) for( v=u+1; v=n- 1; v+) for(w=v+1; w=n; w+) if( ( avaw)&( awau) ) flag=0; if( flag) /*判断序列是否为出栈序列, 若是则输出序列*/ count+; printf( %d:%s , count, a); else for( i=k; inext; la-next=av-next; av-next=s;14. 不做。15.（1）功能：将栈中元素逆序。 （2）功能：删除栈中的所有与e相等的元素。 （3）功能：将队列Q中的元素逆序。第四章1. StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=I AM A ； SubString(sub2,s,7,1)操作结果为sub2= ；StrIndex(s,A,4) 操作结果为6； StrReplace(s,STUDENT,q) 操作结果为I AM A WORKER； StrCat(StrCat(sub1,t), StrCat(sub2,q) 操作结果为I AM A GOOD WORKER；2. StrCat(S,T)； SubString(Sub,S,pos,len)。int String_Replace(Stringtype &S,Stringtype T,Stringtype V);/将串S中所有子串T替换为V,并返回置换次数 for(n=0,i=1;iT0) /找到了与T匹配的子串:分三种情况处理 if(T0=V0) for(l=1;l=T0;l+) /新子串长度与原子串相同时:直接替换 Si+l-1=Vl; else if(T0=i+T0;l-) Sl+V0-T0=Sl; for(l=1;l=V0;l+) Si+l-1=Vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+V0;l=S0+V0-T0;l+) Sl=Sl-V0+T0; for(l=1;lnext;p;p=p-next) r=(LStrNode*)malloc(sizeof(LStrNode); r-ch=p-ch; q-next=r;q=r; q-next=NULL;/StringAssign void StringCopy(LString &s,LString t)/把串t复制为串s.与前一个程序的区别在于,串s业已存在. for(p=s-next,q=t-next;p&q;p=p-next,q=q-next) p-ch=q-ch;pre=p; while(q) p=(LStrNode*)malloc(sizeof(LStrNode); p-ch=q-ch; pre-next=p;pre=p; p-next=NULL;/StringCopy char StringCompare(LString s,LString t)/串的比较,st时返回正数,s=t时返回0,snext,q=t-next;p&q&p-ch=q-ch;p=p-next,q=q-next); if(!p&!q) return 0; else if(!p) return -(q-ch); else if(!q) return p-ch; else return p-ch-q-ch;/StringCompare int StringLen(LString s)/求串s的长度(元素个数) for(i=0,p=s-next;p;p=p-next,i+); return i;/StringLen LString * Concat(LString s,LString t)/连接串s和串t形成新串,并返回指针 p=malloc(sizeof(LStrNode); for(q=p,r=s-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串s for(r=t-next;r;r=r-next) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /for /复制串t q-next=NULL; return p;/Concat LString * Sub_String(LString s,int start,int len)/返回一个串,其值等于串s从start位置起长为len的子串 p=malloc(sizeof(LStrNode);q=p; for(r=s;start;start-,r=r-next); /找到start所对应的结点指针r for(i=1;inext) q-next=(LStrNode*)malloc(sizeof(LStrNode); q=q-next; q-ch=r-ch; /复制串t q-next=NULL; return p;/Sub_String4. 不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。 用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，其串值是常量。串值可以变化的量称为串变量。串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置。串变量与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。5. int HString_Replace(HString &S,HString T,HString V)/堆结构串上的置换操作,返回置换次数 for(n=0,i=0;i=S.length-T.length;i+) for(j=i,k=0;kT.length&S.chj=T.chk;j+,k+); if(k=T.length) /找到了与T匹配的子串:分三种情况处理 if(T.length=V.length) for(l=1;l=T.length;l+) /新子串长度与原子串相同时:直接替换 S.chi+l-1=V.chl-1; else if(T.length=i+T.length;l-) S.chl+V.length-T.length=S.chl; for(l=0;lV.length;l+) Si+l=Vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+V.length;lS.length+V.length-T.length;l+) S.chl=S.chl-V.length+T.length; for(l=0;lV.length;l+) Si+l=Vl; S.length+=V.length-T.length; i+=V.length;n+; /if /for return n;/HString_Replace第五章1. （1）数组A共占用48*6=288个字节；（2）数组A的最后一个元素的地址为1282；（3）按行存储时loc（A36）=1000+（3-1）*8+6-1*6=1126（4）按列存储时loc（A36）=1000+（6-1）*6+3-1*6=11922. void Move（Elem Type A,int n,int k） int count ,t; Elem Type temp; for(count=1;count=1;i-) Ai+1=Ai; A1=temp; 3. Loci,j= Loc1,1+j(j -1)/2+ i-14. i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：i = k/3 + 1, j = k - 2( k/3 )5. p136页7. void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)/三元组表示的稀疏矩阵加法 C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; for(x=1;x=A.mu;x+) /对矩阵的每一行进行加法 while(A.datapa.ix) pa+; while(B.datapb.iB.datapb.j) C.datapc.i=x; C.datapc.j=B.datapb.j; C.datapc.e=B.datapb.e; pb+;pc+; else C.datapc.i=x; C.datapc.j=A.datapa.j; C.datapc.e=A.datapa.e pa+;pc+; /while while(A.datapa=x) /插入A中剩余的元素(第x行) C.datapc.i=x; C.datapc.j=A.datapa.j; C.datapc.e=A.datapa.e pa+;pc+; while(B.datapb=x) /插入B中剩余的元素(第x行) C.datapc.i=x; C.datapc.j=B.datapb.j; C.datapc.e=B.datapb.e; pb+;pc+; /for C.tu=pc;/TSMatrix_Add11. （1）（a，b）（2）（c，d）（3）（b）（4）b（5）（d）第六章3. 证明：分支数=n1+2n2+knk （1） n= n0+n1+nk （2） n=分支数+1 （3） 将（1）（2）代入（3）得 n0= n2+2n3+3n4+（k-1）nk+14. 略5. n0=50，n2=n0-1=49，所以至少有99个结点。6. （1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树7. 证明：n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。 空域=nk-（n-1）=nk-n+18. 略。9. 略。11. 略。23. int leaf(BiTree root) int LeafCount; if (root=NULL) LeafCount =0; else if( ( root-LChild=NULL) & ( root-RChild=NULL ) LeafCount =1; else LeafCount =leaf(root-LChild)+leaf(root-R