《习题讲评(二).doc》由会员分享，可在线阅读，更多相关《习题讲评(二).doc（7页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表P18 P202.32 、2.39 、2.412.32已知有一个单向循环链表，其每一个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。Status DuLNode_Pre(DuLinkList &L) /完成双向循环链表结点的pre域for(p=L; p-next-pre = = NULL; p=p-next) p-next-pre=p;return OK;/DuLNode_Pre2.39 已知稀疏多项式Pn
2、(X)=c1xe1 + c2xe2+cmxem 其中 n= em em-1.e1=0，ci0（i=1，2，m），m1。试采用存储同多项式数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0 为给定值），并分析你的算法的时间复杂度。typedef structfloat coef; /系数；int exp；/指数；PolyTerm；typedef struct PolyTerm *data; int length;int listsize; SqPoly; /类似顺序表中结构体的定义；float GetValue_SqPoly(SqPoly P,int x0)/求升幂顺序存储的稀疏多项式的值
3、PolyTerm *q;xp=1; q=P.data;sum=0; while(q-coef) /系数； ex=0;while(exexp) xp*=x0; ex+; sum+=q-coef*xp;q+;return sum;/GetValue_SqPoly 时间复杂度：n22.41试以循环链表作为稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。void QiuDao_LinkedPoly(LinkedPoly &L)/对有头结点循环链表结构存储的稀疏多项式L求导 p=L-next; if(!p-data.exp)
4、/跳过常数项 L-next=p-next; p=p-next; while(p!=L) /循环链表； p-data.coef*=p-data.exp;/对每一项求导 p-data.exp-； p=p-next; /QiuDao_LinkedPoly cmxem的导数为：cmemxem-1第三章 栈和队列3.17 3.25 3.31 3.32 3.333.17试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。 其中序列1和序列2中不包含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属于该模式的字符序列，而1+2&2-1则不是。int IsRev
5、erse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0InitStack(s);while(e=getchar() != &) push(s,e);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.25试写出递归函数F（n）的递归算法，并消除递归：F(n)=n+1 , n=0; F(n)=n*F(n/2) , n0 Status F_recu
6、rsive(int n, int &s) /递归算法；s为返回值； if(n0) return ERROR; 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(nmax,其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项 fn-k+1 ，. fn）。void GetFib_CyQueue(int k, int max)/
7、求k阶斐波那契序列的前n+1项 InitCyQueue(Q); /其MAXSIZE设置为k for(i=0;ik-1;i+) Q.basei=0; Q.basek-1=1; /给前k项赋初值0, , 0, 1 for(i=0;ik;i+) printf(%d,Q.basei);flag = 0; /设置标志； for(i=k; flag = = 0; i+) m=i % k; sum=0; for(j=0; jk; j+) sum += Q.base(m+j) % k; if(sum max; else flag=1; /退出循环； /GetFib_CyQueue 3.33在顺序存储结构上实现
8、输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。双端循环队列：两端都可以进行入列和出列操作。输出受限的双端循环队列：队头可以入列和出列，队尾只能入列。rear指向最后一个元素的下一个位置；front指向第一个元素；Status EnDQueue(DQueue &Q, int x) /输出受限的双端队列的入队操作 if(Q.rear+1)%MAXSIZE = = Q.front) return OVERFL
9、OW; /队列满;牺牲一个结点； avr = (Q.baseQ.rear-1 + Q.baseQ.front)/2; /队头和队尾作业的平均时间; if(x=avr) /插入队尾 Q.baseQ.rear=x; Q.rear=(Q.rear+1)%MAXSIZE; / rear指向最后一个元素的下一个位置; else Q.front=(Q.front-1)%MAXSIZE; / front下移一位； Q.baseQ.front=x; / front指向第一个元素； /插入在队头 return OK;/EnDQueue Status DeDQueue(DQueue &Q, int &x) /输出
10、受限的双端队列的出队操作 /只能在队头出列，队尾不允许出列； if(Q.front = = Q.rear) return ERROR; /队列空； x=Q.baseQ.front; Q.front=(Q.front+1)%MAXSIZE; return OK;/DeDQueue 第四章 串 串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。StrAssign (&T, chars) /串赋值 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。StrCopy (&T
