• / 119
  • 下载费用:2 金币  

严蔚敏数据结构答案(十分详细).pdf

关 键 词:
严蔚敏 数据结构 答案 十分 详细
资源描述:
严蔚敏《数据结构(C 语言版)习题集》答案 说明: 1. 本文是对严蔚敏《数据结构(c 语言版) 习题集》一书中所有算法设计题目的解 决方案, 主要作者为一具. 以下网友:biwier,szm99,siice, 龙抬 头,iamkent,zames,birdthinking,lovebuaa 等为答案的修订和完善工作提出了宝贵意 见,在此表示感谢; 2. 本解答中的所有算法均采用类 c 语言描述,设计原则为面向交流、 面向阅读,作 者不保证程序能够上机正常运行( 这种保证实际上也没有任何意义); 3. 本解答原则上只给出源代码以及必要的注释, 对于一些难度较高或思路特殊的 题目将给出简要的分析说明,对于作者无法解决的题 目将给出必要的讨论.目前尚 未解决的题目有: 5.20, 10.40; 4. 请读者在自己已经解决了某个题目或进行了充分的思考之后, 再参考本解答, 以保证复习效果; 5. 由于作者水平所限, 本解答中一定存在不少这样或者那样的错误和不足, 希望 读者们在阅读中多动脑、勤思考, 争取发现和纠正这些错误, 写出更好的算法来. 请将你发现的错误或其它值得改进之处向作者报告: [email]yi-ju@263.net[/email] 第一章 绪论 1.16 void print_descending(int x,int y,int z)// 按从大到小顺序输出三个数 { scanf(“%d,%d,%d“, if(xy; // 为表示交换的双目运算符,以下同 if(yz; if(xy; // 冒泡排序 printf(“%d %d %d“,x,y,z); }//print_descending 1.17 Status fib(int k,int m,int if(k2||m0) return ERROR; if(mk-1) f=0; else if (m==k-1 || m==k) f=1; else { for(i=0;i=k-2;i++) temp[i]=0; temp[k-1]=1;temp[k]=1; // 初始化 sum=1; j=0; for(i=k+1;i=m;i++,j++) // 求出序列第 k 至第 m 个元素的值 temp[i]=2*sum-temp[j]; f=temp[m]; } return OK; }//fib 分析: k 阶斐波那契序列的第 m 项的值 f[m]=f[m-1]+f[m-2]++f[m-k] =f[m-1]+f[m-2]++f[m-k]+f[m-k-1]-f[m-k-1] =2*f[m-1]-f[m-k-1] 所以上述算法的时间复杂度仅为 O(m). 如果采用递归设计,将达到 O(k^m). 即使 采用暂存中间结果的方法,也将达到 O(m^2). 1.18 typedef struct{ char *sport; enum{male,female} gender; char schoolname; // 校名为'A','B','C','D' 或'E' char *result; int score; } resulttype; typedef struct{ int malescore; int femalescore; int totalscore; } scoretype; void summary(resulttype result[ ])// 求各校的男女总分和团体总分,假设结果已经储 存在 result[ ] 数组中 { scoretype score[MAXSIZE]; i=0; while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; case 'B': score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; …… …… …… } i++ ; } for(i=0;i5;i++) { printf(“School %d:\n“,i); printf(“Total score of male:%d\n“,score[i].malescore); printf(“Total score of female:%d\n“,score[i].femalescore); printf(“Total score of all:%d\n\n“,score[i].totalscore); } }//summary 1.19 Status algo119(int a[ARRSIZE])// 求 i!*2^i 序列的值且不超过 maxint { last=1; for(i=1;i=ARRSIZE;i++) { a[i-1]=last*2*i; if((a[i-1]/last)!=(2*i)) reurn OVERFLOW; last=a[i-1]; return OK; } }//algo119 分析: 当某一项的结果超过了 maxint 时,它除以前面一项的商会发生异常. 1.20 void polyvalue() { float temp; float *p=a; printf(“Input number of terms:“); scanf(“%d“, printf(“Input value of x:“); scanf(“%f“, printf(“Input the %d coefficients from a0 to a%d:\n“,n+1,n); p=a;xp=1;sum=0; //xp 用于存放 x 的 i 次方 for(i=0;i=n;i++) { scanf(“%f“, sum+=xp*(temp); xp*=x; } printf(“Value is:%f“,sum); }//polyvalue 第二章 线性表 2.10 Status DeleteK(SqList for(count=1;i+count-1va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]xi--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2.12 int ListComp(SqList A,SqList B)// 比较字符表 A 和 B, 并用返回值表示结果,值为 1, 表示 AB; 值为-1, 表示 AB.elem[i]?1:-1; if(A.length==B.length) return 0; return A.lengthB.length?1:-1; // 当两个字符表可以互相比较的部分完全相同 时,哪个较长,哪个就较大 }//ListComp 2.13 LNode* Locate(LinkList L,int x)// 链表上的元素查找,返回指针 { for(p=l-next;pp=p-next); return p; }//Locate 2.14 int Length(LinkList L)// 求链表的长度 { for(k=0,p=L;p-next;p=p-next,k++); return k; }//Length 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList p=ha; while(p-next) p=p-next; p-next=hb; }//ListConcat 2.16 见书后答案. 2.17 Status Insert(LinkList q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) { q.next=p;L=q; // 插入在链表头部 } else { while(--i1) p=p-next; q-next=p-next;p-next=q; // 插入在第 i 个元素的位置 } }//Insert 2.18 Status Delete(LinkList // 删除第一个元素 else { p=L; while(--i1) p=p-next; p-next=p-next-next; // 删除第 i 个元素 } }//Delete 2.19 Status Delete_Between(Linklist while(p-next-datanext; //p 是最后一个不大于 mink 的元素 if(p-next) // 如果还有比 mink 更大的元素 { q=p-next; while(q-datanext; //q 是第一个不小于 maxk 的元素 p-next=q; } }//Delete_Between 2.20 Status Delete_Equal(Linklist q=p-next; //p,q 指向相邻两元素 while(p-next) { if(p-data!=q-data) { p=p-next;q=p-next; // 当相邻两元素不相等时,p,q 都向后推一步 } else { while(q-data==p-data) { free(q); q=q-next; } p-next=q;p=q;q=p-next; // 当相邻元素相等时删除多余元素 }//else }//while }//Delete_Equal 2.21 void reverse(SqList iA.elem[j]; }//reverse 2.22 void LinkList_reverse(Linklist 为简化算法,假设表长大于 2 { p=L-next;q=p-next;s=q-next;p-next=NULL; while(s-next) { q-next=p;p=q; q=s;s=s-next; // 把 L 的元素逐个插入新表表头 } q-next=p;s-next=q;L-next=s; }//LinkList_reverse 分析: 本算法的思想是,逐个地把 L 的当前元素 q 插入新的链表头部,p 为新表表头. 2.23 void merge1(LinkList q=B-next;C=A; while(pp-next=q; // 将 B 的元素插入 if(s) { t=q-next;q-next=s; // 如 A 非空,将 A 的元素插入 } p=s;q=t; }//while }//merge1 2.24 void reverse_merge(LinkList pb=B-next;pre=NULL; //pa 和 pb 分别指向 A,B 的当前元素 while(pa||pb) { if(pa-datadata||!pb) { pc=pa;q=pa-next;pa-next=pre;pa=q; // 将 A 的元素插入新表 } else { pc=pb;q=pb-next;pb-next=pre;pb=q; // 将 B 的元素插入新表 } pre=pc; } C=A;A-next=pc; // 构造新表头 }//reverse_merge 分析: 本算法的思想是,按从小到大的顺序依次把 A 和 B 的元素插入新表的头部 pc 处,最后处理 A 或 B 的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList j=1;k=0; while(A.elem[i] if(A.elem[i]==B.elem[j]) { C.elem[++k]=A.elem[i]; // 当发现了一个在 A,B 中都存在的元素, i++;j++; // 就添加到 C 中 } }//while }//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList q=B-next; pc=(LNode*)malloc(sizeof(LNode)); C=pc; while(p else if(p-dataq-data) q=q-next; else { s=(LNode*)malloc(sizeof(LNode)); s-data=p-data; pc-next=s;pc=s; p=p-next;q=q-next; } }//while }//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList j=1;k=0; while(A.elem[i] else if(A.elem[i]!=A.elem[k]) { A.elem[++k]=A.elem[i]; // 当发现了一个在 A,B 中都存在的元素 i++;j++; // 且 C 中没有,就添加到 C 中 } else {i++;j++;} }//while while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList q=B-next;pc=A; while(p else if(p-dataq-data) q=q-next; else if(p-data!=pc-data) { pc=pc-next; pc-data=p-data; p=p-next;q=q-next; } }//while }//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList j=0;k=0;m=0; //i 指示 A 中元素原来的位置,m 为移动后的位置 while(iC.elem[k]) k++; else { same=B.elem[j]; // 找到了相同元素 same while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; //j,k 后移到新的元素 while(iA.length // 需保留的元素移动到新位置 while(iA.length // 跳过相同的元素 } }//while while(iA.length) A.elem[m++]=A.elem[i++]; //A 的剩余元素重新存储。 A.length=m; }// SqList_Intersect_Delete 分析: 先从 B 和 C 中找出共有元素,记为 same,再在 A 中从当前位置开始, 凡小于 same 的 元素均保留( 存到新的位置), 等于 same 的就跳过, 到大于 same 时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList q=C-next;r=A-next; while(p else if(p-dataq-data) q=q-next; else { u=p-data; // 确定待删除元素 u while(r-next-datanext; // 确定最后一个小于 u 的元素指针 r if(r-next-data==u) { s=r-next; while(s-data==u) { t=s;s=s-next;free(t); // 确定第一个大于 u 的元素指针 s }//while r-next=s; // 删除 r 和 s 之间的元素 }//if while(p-data=u) p=p-next; while(q-data=u) q=q-next; }//else }//while }//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)// 删除单循环链表中结点 s 的直接前驱 { p=s; while(p-next-next!=s) p=p-next; // 找到 s 的前驱的前驱 p p-next=s; return OK; }//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList !p-next-pre;p=p-next) p-next-pre=p; return OK; }//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) { if(isalphabet(s-data)) { p-next=s;p=s; } else if(isdigit(s-data)) { q-next=s;q=s; } else { r-next=s;r=s; } }//while p-next=A;q-next=B;r-next=C; // 完成循环链表 }//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)// 从左向右输出异或链表的元素值 { p=L.left;pre=NULL; while(p) { printf(“%d“,p-data); q=XorP(p-LRPtr,pre); pre=p;p=q; // 任何一个结点的 LRPtr 域值与其左结点指针进行异或运算即得到 其右结点指针 } }//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList pre=NULL; r=(XorNode*)malloc(sizeof(XorNode)); r-data=x; if(i==1) // 当插入点在最左边的情况 { p-LRPtr=XorP(p.LRPtr,r); r-LRPtr=p; L.left=r; return OK; } j=1;q=p-LRPtr; //当插入点在中间的情况 while(++jLRPtr,pre); pre=p;p=q; }//while // 在 p,q 两结点之间插入 if(!q) return INFEASIBLE; //i 不可以超过表长 p-LRPtr=XorP(XorP(p-LRPtr,q),r); q-LRPtr=XorP(XorP(q-LRPtr,p),r); r-LRPtr=XorP(p,q); // 修改指针 return OK; }//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList pre=NULL; if(i==1) // 删除最左结点的情况 { q=p-LRPtr; q-LRPtr=XorP(q-LRPtr,p); L.left=q;free(p); return OK; } j=1;q=p-LRPtr; while(++jLRPtr,pre); pre=p;p=q; }//while // 找到待删结点 q if(!q) return INFEASIBLE; //i 不可以超过表长 if(L.right==q) //q 为最右结点的情况 { p-LRPtr=XorP(p-LRPtr,q); L.right=p;free(q); return OK; } r=XorP(q-LRPtr,p); //q 为中间结点的情况,此时 p,r 分别为其左右结点 p-LRPtr=XorP(XorP(p-LRPtr,q),r); r-LRPtr=XorP(XorP(r-LRPtr,q),p); // 修改指针 free(q); return OK; }//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList while(p-next!=L p=p-next; } // 此时 p 指向最后一个奇数结点 if(p-next==L) p-next=L-pre-pre; else p-next=l-pre; p=p-next; // 此时 p 指向最后一个偶数结点 while(p-pre-pre!=L) { p-next=p-pre-pre; p=p-next; } p-next=L; // 按题目要求调整了 next 链的结构,此时 pre 链仍为原状 for(p=L;p-next!=L;p=p-next) p-next-pre=p; L-pre=p; // 调整 pre 链的结构,同 2.32 方法 }//OEReform 分析:next 链和 pre 链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保 存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList while(p.data!=x if(p==L) return NULL; // 没找到 p-freq++;q=p-pre; while(q-freqfreq // 查找插入位置 if(q!=p-pre) { p-pre-next=p-next;p-next-pre=p-pre; q-next-pre=p;p-next=q-next; q-next=p;p-pre=q; // 调整位置 } return p; }//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)// 求升幂顺序存储的稀疏多项式的值 { PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q-coef) { while(exexp) xp*=x0; sum+=q-coef*xp; q++; } return sum; }//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly Create_SqPoly(P3); // 建立空多项式 P3 p=P1.data;q=P2.data;r=P3.data; while(p-coef r-exp=p-exp; p++;r++; } else if(p-expexp) { r-coef=-q-coef; r-exp=q-exp; q++;r++; } else { if((p-coef-q-coef)!=0) // 只有同次项相减不为零时才需要存入 P3 中 { r-coef=p-coef-q-coef; r-exp=p-exp;r++; }//if p++;q++; }//else }//while while(p-coef) // 处理 P1 或 P2 的剩余项 { r-coef=p-coef; r-exp=p-exp; p++;r++; } while(q-coef) { r-coef=-q-coef; r-exp=q-exp; q++;r++; } }//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly if(!p-data.exp) { L-next=p-next;p=p-next; // 跳过常数项 } while(p!=L) { p-data.coef*=p-data.exp--;// 对每一项求导 p=p-next; } }//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) { if(p-data.exp!=2*(p-data.exp/2)) { pa-next=p;pa=p; } else { pb-next=p;pb=p; } p=p-next; }//while pa-next=A;pb-next=B; }//Divide_LinkedPoly 第三章 栈与队列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; // 双向栈类型 Status Init_Stack(BDStacktype tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype // 注意此时的栈满条件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push Status pop(BDStacktype x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop 3.16 void Train_arrange(char *train)// 这里用字符串 train 表示火车,'H' 表示硬席,'S' 表示 软席 { p=train;q=train; InitStack(s); while(*p) { if(*p=='H') push(s,*p); // 把'H'存入栈中 else *(q++)=*p; // 把'S' 调到前部 p++; } while(!StackEmpty(s)) { pop(s,c); *(q++)=c; // 把'H'接在后部 } }//Train_arrange 3.17 int IsReverse()// 判断输入的字符串中' while((e=getchar())!='// 不允许在’ } while( (e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1; }//IsReverse 3.18 Status Bracket_Test(char *str)// 判别表达式中小括号是否匹配 { count=0; for(p=str;*p;p++) { if(*p=='(') count++; else if(*p==')') count--; if (count0) return ERROR; } if(count) return ERROR; // 注意括号不匹配的两种情况 return OK; }//Bracket_Test 3.19 Status AllBrackets_Test(char *str)// 判别表达式中三种括号是否匹配 { InitStack(s); for(p=str;*p;p++) { if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') { if(StackEmpty(s)) return ERROR; pop(s,c); if(*p==')' if(*p==']' if(*p=='}' // 必须与当前栈顶括号匹配 } }//for if(!StackEmpty(s)) return ERROR; return OK; }//AllBrackets_Test 3.20 typedef struct { . int x; int y; } coordinate; void Repaint_Color(int g[m][n],int i,int j,int color)// 把点(i,j) 相邻区域的颜色置换为 color { old=g[i][j]; InitQueue(Q); EnQueue(Q,{I,j}); while(!QueueEmpty(Q)) { DeQueue(Q,a); x=a.x;y=a.y; if(x1) if(g[x-1][y]==old) { g[x-1][y]=color; EnQueue(Q,{x-1,y}); // 修改左邻点的颜色 } if(y1) if(g[x][y-1]==old) { g[x][y-1]=color; EnQueue(Q,{x,y-1}); // 修改上邻点的颜色 } if(xm) if(g[x+1][y]==old) { g[x+1][y]=color; EnQueue(Q,{x+1,y}); // 修改右邻点的颜色 } if(yn) if(g[x][y+1]==old) { g[x][y+1]=color; EnQueue(Q,{x,y+1}); // 修改下邻点的颜色 } }//while }//Repaint_Color 分析: 本算法采用了类似于图 的广度优先遍历的思想,用两个队列保存相邻同色 点 的横坐标和纵坐标.递归形式的算法该怎么写呢? 3.21 void NiBoLan(char *str,char *new)// 把中缀表达式 str 转换成逆波兰式 new { p=str;q=new; //为方便起见,设 str 的两端都加上了优先级最低的特殊符号 InitStack(s); //s 为运算符栈 while(*p) { if(*p 是字母)) *q++=*p; // 直接输出 else { c=gettop(s); if(*p 优先级比 c 高) push(s,*p); else { while(gettop(s) 优先级不比*p 低) { pop(s,c);*(q++)=c; }//while push(s,*p); // 运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while }//NiBoLan // 参见编译原理教材 3.22 int GetValue_NiBoLan(char *str)// 对逆波兰式求值 { p=str;InitStack(s); //s 为操作数栈 while(*p) { if(*p 是数) push(s,*p); else { pop(s,a);pop(s,b); r=compute(b,*p,a); // 假设 compute 为执行双目运算的过程 push(s,r); }//else p++; }//while pop(s,r);return r; }//GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype Initstack(s); //s 的元素为 stringtype 类型 while(*p) { if(*p 为字母) push(s,*p); else { if(StackEmpty(s)) return ERROR; pop(s,a); if(StackEmpty(s)) return ERROR; pop(s,b); c=link(link(*p,b),a); push(s,c); }//else p++; }//while pop(s,new); if(!StackEmpty(s)) return ERROR; return OK; }//NiBoLan_to_BoLan 分析: 基本思想见书后注释. 本题中暂不考虑串的具体操作的实现, 而将其看作一 种抽象数据类型 stringtype, 对其可以进行连接操作:c=link(a,b). 3.24 Status g(int m,int n,int else if(m0 else return ERROR; return OK; }//g 3.25 Status F_recursive(int n,int if(n==0) s=n+1; else { F_recurve(n/2,r); s=n*r; } return OK; }//F_recursive Status F_nonrecursive(int n,int s)// 非递归算法 { if(n0) return ERROR; if(n==0) s=n+1; else { InitStack(s); //s 的元素类型为 struct {int a;int b;} while(n!=0) { a=n;b=n/2; push(s,{a,b}); n=b; }//while s=1; while(!StackEmpty(s)) { pop(s,t); s*=t.a; }//while } return OK; }//F_nonrecursive 3.26 float Sqrt_recursive(float A,float p,float e)// 求平方根的递归算法 { if(abs(p^2-A)=e) p=(p+A/p)/2; return p; }//Sqrt_nonrecursive 3.27 这一题的所有算法以及栈的变化过程请参见 《数据结构(pascal 版) 》,作者不再详 细写出. 3.28 void InitCiQueue(CiQueue Q-next=Q; }//InitCiQueue void EnCiQueue(CiQueue p-data=x; p-next=Q-next; // 直接把 p 加在 Q 的后面 Q-next=p; Q=p; // 修改尾指针 } Status DeCiQueue(CiQueue // 队列已空 p=Q-next-next; x=p-data; Q-next-next=p-next; free(p); return OK; }//DeCiQueue 3.29 Status EnCyQueue(CyQueue Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; // 队列满 }//EnCyQueue Status DeCyQueue(CyQueue Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; // 队列空 return OK; }//DeCyQueue 分析: 当循环队列容量较小而队列 中每个元素占的空间较多时, 此种表示方法可 以 节约较多的存储空间,较有价值. 3.30 Status EnCyQueue(CyQueue Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue Status DeCyQueue(CyQueue head=(Q.rear-Q.length+1)%MAXSIZE; // 详见书后注释 x=Q.base[head]; Q.length--; }//DeCyQueue 3.31 int Palindrome_Test()// 判别输入的字符串是否回文序列,是则返回 1,否则返回 0 { InitStack(S);InitQueue(Q); while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); // 同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; } return OK; }//Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)// 求 k 阶斐波那契序列的前 n+1 项 { InitCyQueue(Q); // 其 MAXSIZE 设置为 k for(i=0;i=avr) // 根据 x 的值决定插入在队头还是队尾 { Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; } // 插入在队尾 else { Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } // 插入在队头 return OK; }//EnDQueue Status DeDQueue(DQueue // 队列空 x=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//DeDQueue 3.34 void Train_Rearrange(char *train)// 这里用字符串 train 表示火车,'P' 表示硬座,'H' 表 示硬卧,'S' 表示软卧,最终按 PSH 的顺序排列 { r=train; InitDQueue(Q); while(*r) { if(*r=='P') { printf(“E“); printf(“D“); // 实际上等于不入队列,直接输出 P 车厢 } else if(*r=='S') { printf(“E“); EnDQueue(Q,*r,0); //0 表示把 S 车厢从头端入队列 } else { printf(“A“); EnDQueue(Q,*r,1); //1 表示把 H 车厢从尾端入队列 } }//while while(!DQueueEmpty(Q)) { printf(“D“); DeDQueue(Q); }//while // 从头端出队列的车厢必然是先 S 后 H 的顺序 }//Train_Rearrange 第四章 串 4.10 void String_Reverse(Stringtype s,Stringtype // 初始化 r 为空串 for(i=Strlen(s);i;i--) { StrAssign(c,SubString(s,i,1)); StrAssign(r,Concat(r,c)); // 把 s 的字符从后往前添加到 r 中 } }//String_Reverse 4.11 void String_Subtract(Stringtype s,Stringtype t,Stringtype for(i=1;iStrlen(t)) StrAssign(r,Concat(r,c)); } }//for }//String_Subtract 4.12 int Replace(Stringtype // 将串 S 中所有子串 T 替换为 V, 并返回置换次数 { for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i++) // 注意 i 的取值范围 if(!StrCompare(SubString(S,i,Strlen(T)),T)) // 找到了与 T 匹配的子串 { // 分别把 T 的前面和后面部分保存为 head 和 tail StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V)); StrAssign(S,Concat(S,tail)); // 把 head,V ,tail 连接为新串 i+=Strlen(V); // 当前指针跳到插入串以后 n++; }//if return n; }//Replace 分析:i+=Strlen(V); 这一句是必需的, 也是容易忽略的. 如省掉这一句, 则在某些情况 下, 会引起不希望的后果, 虽然在大多数情况下没有影响. 请思考: 设 S='place', T='ace', V='face', 则省掉 i+=Strlen(V); 运行时会出现什么结果? 4.13 int Delete_SubString(Stringtype i=Strlen(s)-Strlen(t)+1;i++) if(!StrCompare(SubString(s,i,Strlen(t)),t)) { StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)); StrAssign(S,Concat(head,tail)); // 把 head,tail 连接为新串 n++; }//if return n, }//Delete_SubString 4.14 Status NiBoLan_to_BoLan(Stringtype str,Stringtype //s 的元素为 Stringtype 类型 for(i=1;it 时返回正数,s=t 时返回 0,st 时返回负数 { for(i=1;is[0] else if(is[0]) return -t[i]; else if(it[0]) return s[i]; else return s[i]-t[i]; }//StrCompare 4.17 int String_Replace(Stringtype // 将串 S 中所有子串 T 替换为 V, 并返回置换次数 { for(n=0,i=1;iT[0]) // 找到了与 T 匹配的子串: 分三种情况处理 { if(T[0]==V[0]) for(l=1;l=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l=V[0];l++) S[i+l-1]=V[l]; } else // 新子串长度小于原子串时: 先将后部左移 { for(l=i+V[0];l=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for return n; }//String_Replace 4.18 typedef struct { char ch; int num; } mytype; void StrAnalyze(Stringtype S)// 统计串 S 中字符的种类和个数 { mytype T[MAXSIZE]; // 用结构数组 T 存储统计结果 for(i=1;it[0]) r[++r[0]]=c; } }//for }//Subtract_String 4.20 int SubString_Delete(Stringtype im) // 找到了与 t 匹配的子串 { for(k=i;k=s[0]-t[0];k++) s[k]=s[k+t[0]]; // 左移删除 s[0]-=t[0];n++; } }//for return n; }//Delete_SubString 4.21 typedef struct{ char ch; LStrNode *next; } LStrNode,*LString; // 链串结构 void StringAssign(LString for(q=s,p=t-next;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 pp=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;pp=p-next,q=q-next); if(!p 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_String 4.22 void LString_Concat(LString while(p // 查找字符 c if(!p) // 没找到 { t.tail-next=s.head; t.tail=s.tail; // 把 s 连接在 t 的后面 } else { q=p-next; r=(Chunk*)malloc(sizeof(Chunk)); // 将包含字符 c 的节点 p 分裂为两个 for(j=0;jch[j]='#'; // 原结点 p 包含 c 及其以前的部分 for(j=i;jch[j]=p-ch[j]; p-ch[j]='#'; //p 的后半部分和 r 的前半部分的字符改为无效字符'#' } p-next=s.head; s.tail-next=r; r-next=q; // 把串 s 插入到结点 p 和 r 之间 }//else t.curlen+=s.curlen; // 修改串长 s.curlen=0; }//LString_Concat int Find_Char(Chunk *p,char c)// 在某个块中查找字符 c, 如找到则返回位置是第几 个字符,如没找到则返回 0 { for(i=0;ich[i]!=c;i++); if(i==CHUNKSIZE) return 0; else return i+1; }//Find_Char 4.23 int LString_Palindrome(LString L)// 判断以块链结构存储的串 L 是否为回文序列, 是则返回 1,否则返回 0 { InitStack(S); p=S.head;i=0;k=1; //i 指示元素在块中的下标,k 指示元素在整个序列中的序号( 从 1 开始) for(k=1;kch[i]); // 将前半段的字符入串 else if(k(S.curlen+1)/2) { Pop(S,c); // 将后半段的字符与栈中的元素相匹配 if(p-ch[i]!=c) return 0; // 失配 } if(++i==CHUNKSIZE) // 转到下一个元素,当为块中最后一个元素时, 转到下一 块 { p=p-next; i=0; } }//for return 1; // 成功匹配 }//LString_Palindrome 4.24 void HString_Concat(HString s1,HString s2,HString t.ch=malloc((s1.length+s2.length)*sizeof(char)); for(i=1;i=i+T.length;l--) S.ch[l+V .length-T.length]=S.ch[l]; for(l=0;lV .length;l++) S[i+l]=V[l]; } else // 新子串长度小于原子串时: 先将后部左移 { for(l=i+V .length;lS.length+V .length-T.length;l++) S.ch[l]=S.ch[l-V .length+T.length]; for(l=0;lV .length;l++) S[i+l]=V[l]; } S.length+=V .length-T.length; i+=V .length;n++; }//if }//for return n; }//HString_Replace 4.26 Status HString_Insert(HString // 当插入位置大于串长时,看作添加在串尾 S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char)); for(i=S.length-1;i=pos-1;i--) S.ch[i+T.length]=S.ch[i]; // 后移为插入字符串让出位置 for(i=0;it[0]) return i-t[0]; }//Index_New 4.28 void LGet_next(LString p-next=T;q=T; while(p-succ) { if(q==T||p-data==q-data) { p=p-succ;q=q-succ; p-next=q; } else q=q-next; }//while }//LGet_next 4.29 LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)// 链串上的 KMP 匹配 算法,返回值为匹配的子串首指针 { p=pos;q=T-succ; while(p q=q-succ; } else q=q-next; }//while if(!q) { for(i=1;inext; return p; } // 发现匹配后,要往回找子串的头 return NULL; }//LIndex_KMP 4.30 void Get_LRepSub(Stringtype S)// 求 S 的最长重复子串的位置和长度 { for(maxlen=0,i=1;imaxlen) // 发现了比以前发现的更长的重复子串 { lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; // 作记录 } }//for }//for if(maxlen) { printf(“Longest Repeating Substring length:%d\n“,maxlen); printf(“Position1:%d Position 2:%d\n“,lrs1,lrs2); } else printf(“No Repeating Substring found!\n“); }//Get_LRepSub 分析:i 代表“ 错位值“. 本算法的思想是,依次把串 S 的一个副本 S2 向右错位平移 1 格,2 格,3 格,. 与自身 S1 相匹配,如果存在最长重复子串,则必然能在此过程中被发 现.用变量 lrs1,lrs2,maxlen 来记录已发现的最长重复子串第一次出现位置,第二次 出现位置和长度.题目中未说明“ 重复子串“ 是否允许有重叠部分, 本算法假定允许. 如不允许,只需在第二个 for 语句的循环条件中加上 k=T[0]) { StrAssign(A,S);StrAssign(B,T); } else { StrAssign(A,T);StrAssign(B,S); } // 为简化设计,令 S 和 T 中较长的那个为 A, 较短的那个为 B for(maxlen=0,i=1-B[0];iA[0]-B[0]) { jmin=i;jmax=A[0]; }//B 有一部分在 A 右端的右边 else { jmin=i;jmax=i+B[0]; }//B 在 A 左右两端之间. // 以上是根据 A 和 B 不同的相对位置确定 A 上需要匹配的区间( 与 B 重合的 区间) 的端点:jmin,jmax. for(k=0,j=jmin;j=jmax;j++) { if(A[j]==B[j-i]) k++; else k=0; if(kmaxlen) { lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for if(maxlen) { if(S[0]=T[0]) { lpsS=lps1;lpsT=lps2; } else { lpsS=lps2;lpsT=lps1; } // 将 A,B 上的位置映射回 S,T 上的位置 printf(“Longest Public Substring length:%d\n“,maxlen); printf(“Position in S:%d Position in T:%d\n“,lpsS,lpsT); }//if else printf(“No Repeating Substring found!\n“); }//Get_LPubSub 分析: 本题基本思路与上题同.唯一的区别是,由于 A,B 互不相同,因此 B 不仅要向 右错位,而且还要向左错位,以保证不漏掉一些情况.当 B 相对于 A 的位置不同时, 需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解. 本算法的时 间复杂度是 o(strlrn (s )*strlen (t ) ) 。 第五章 数组和广义表 5.18 void RSh(int A[n],int k)// 把数组 A 的元素循环右移 k 位,只用一个辅助存储空间 { for(i=1;i=k;i++) if(n%i==0// 求 n 和 k 的最大公约数 p for(i=0;ip;i++) { j=i;l=(i+n-k)%n;temp=A[i]; while(l!=i) { A[j]=A[l]; j=l;l=(j+n-k)%n; }// 循环右移一步 A[j]=temp; }//for }//RSh 分析: 要把 A 的元素循环右移 k 位,则 A[0] 移至 A[k],A[k] 移至 A[2k]直到最终 回到 A[0]. 然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有 被访问过,而是被跳了过去.分析可知,当 n 和 k 的最大公约数为 p 时,只要分别以 A[0],A[1],.A[p-1] 为起点执行上述算法, 就可以保证每一个元素都被且仅被右移 一次,从而满足题目要求.也就是说,A 的所有元素分别处在 p 个“ 循环链“ 上面.举例 如下: n=15,k=6, 则 p=3. 第一条链:A[0]-A[6],A[6]-A[12],A[12]-A[3],A[3]-A[9],A[9]-A[0]. 第二条链:A[1]-A[7],A[7]-A[13],A[13]-A[4],A[4]-A[10],A[10]-A[1]. 第三条链:A[2]-A[8],A[8]-A[14],A[14]-A[5],A[5]-A[11],A[11]-A[2]. 恰好使所有元素都右移一次. 虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19 void Get_Saddle(int A[m][n])// 求矩阵 A 中的马鞍点 { for(i=0;i=0;i--) // 按降幂次序,可能出现的最高项次数为 mn Get_All(a,m,i,0); // 确定并输出所有次数为 i 的项 }//Print_Poly_Descend void Get_All(int *a,int m,int i,int seq)// 递归求出所有和为 i 的 m 个自然数 { if(seq==maxm) Print_Nomial(a,exps); // 已经求完时,输出该项 else { min=i-(m-1)*n; // 当前数不能小于 min if(min0) printf(“+“); // 系数为正时打印加号 else if(coef1) printf(“%d“,exp[i]); // 系数为 1 时无需打印 } }//Print_Nomial 分析: 本算法的关键在于如何 按照降幂顺序输出各项.这里采用了一个递归函数 来 找到所有满足和为 i 的 m 个自然数作为各变元的指数.只要先取第一个数为 j, 然后 再找到所有满足和为 i-j 的 m-1 个自然数就行了.要注意 j 的取值范围必须使剩余 m-1 个自然数能够找到,所以不能小于 i-(m-1)*maxn, 也不能大于 i. 只要找到了一 组符合条件的数,就可以在存储多项式系数的数组中 确定对应的项的系数的位置, 并且在系数不为 0 时输出对应的项. 5.21 void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; for(x=1;xB.data[pb].j) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x) // 插入 A 中剩余的元素( 第 x 行) { C.data[pc].i=x; C.data[pc].j=A.data[pa]
展开阅读全文
  语墨文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:严蔚敏数据结构答案(十分详细).pdf
链接地址:http://www.wenku38.com/p-65784.html

                                            站长QQ:1002732220      手机号:18710392703    


                                                          copyright@ 2008-2020 语墨网站版权所有

                                                             经营许可证编号:蜀ICP备18034126号

网站客服微信
收起
展开