习题讲评(二).docVIP

第二章 线性表 P18 — P20 2.32 、2.39 、2.41 2.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_Pre 2.39③ 已知稀疏多项式Pn(X)=c1xe1 + c2xe2+…+cmxem 其中 n= em em-1…….e1=0，ci≠0（i=1，2，…m），m≥1。试采用存储同多项式数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0 为给定值），并分析你的算法的时间复杂度。 typedef struct{float coef; //系数； int exp；//指数；}PolyTerm；typedef struct{ PolyTerm *data; int length; int listsize; } SqPoly; //类似顺序表中结构体的定义； float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值{??PolyTerm *q;??xp=1; q=P.data;??sum=0; ?while(q-coef) //系数；??{ ex=0;????while(exq-exp){ xp*=x0; ex++; }???? sum+=q-coef*xp;???? q++;??}??return sum;}//GetValue_SqPoly 时间复杂度：n2 2.41②试以循环链表作为稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。 void QiuDao_LinkedPoly(LinkedPoly L)//对有头结点循环链表结构存储的稀疏多项式L求导{?? p=L-next;?? if(!p-data.exp) //跳过常数项?? {???? 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.33 3.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1序列2’模式的字符序列。 其中序列1和序列2中不包含字符’’，且序列2是序列1的逆序列。例如，‘a+bb+a’是属于该模式的字符序列，而‘1+22-1’则不是。 int IsReverse()//判断输入的字符串中前和后部分是否为逆串,是则返回1,否则返回0{??InitStack(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_recursive(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 Stat