《习题讲评》word版

《《习题讲评》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章线性表P18—P202.32、2.39、2.412.32②已知有一个单向循环链表，其每一个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。StatusDuLNode_Pre(DuLinkList&L)//完成双向循环链表结点的pre域{  for(p=L;p->next->pre==NULL;p=p->next)p->next->pre=p;  retu

2、rnOK;}//DuLNode_Pre2.39③已知稀疏多项式Pn(X)=c1xe1+c2xe2+…+cmxem其中n=em>em-1>…….>e1>=0，ci≠0（i=1，2，…m），m≥1。试采用存储同多项式数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0为给定值），并分析你的算法的时间复杂度。typedefstruct{floatcoef;//系数；intexp；//指数；}PolyTerm；typedefstruct{PolyTerm*data;intlength;intlistsize;}SqPoly;//类似顺

3、序表中结构体的定义；floatGetValue_SqPoly(SqPolyP,intx0)//求升幂顺序存储的稀疏多项式的值{  PolyTerm*q;  xp=1;q=P.data;  sum=0; while(q->coef)//系数；  {ex=0;    while(exexp){xp*=x0;ex++;}    sum+=q->coef*xp;    q++;  }  return7sum;}//GetValue_SqPoly时间复杂度：n22.41②试以循环链表作为稀疏多项式的存储结构，编写求其导函数的算法，要

4、求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。voidQiuDao_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;  }}//

5、QiuDao_LinkedPolycmxem的导数为：cmemxem-1第三章栈和队列3.173.253.313.323.333.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中不包含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属于该模式的字符序列，而‘1+2&2-1’则不是。intIsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0{  InitStack(s);  while((e=g

6、etchar())!='&')    push(s,e);  while((e=getchar())!='@')  {    if(StackEmpty(s))return0;    pop(s,c);    if(e!=c)return0;  }  if(!StackEmpty(s))return0;//判断栈中是否还有元素；  return1;}//IsReverse73.25④试写出递归函数F（n）的递归算法，并消除递归：F(n)=n+1,n=0;F(n)=n*F(n/2),n>0StatusF_recursive(intn

7、,int&s)//递归算法；s为返回值；{  if(n<0)returnERROR;  if(n==0)s=n+1;  else  {    F_recurve(n/2,r);    s=n*r;  }  returnOK;}//F_recursiveStatusF_nonrecursive(intn,ints)//非递归算法{  if(n<0)returnERROR;  if(n==0)s=n+1;  else  {    InitStack(s);//s的元素类型为struct{inta;intb;}    while(n!=

8、0)    {      a=n;b=n/2;      push(s,{a,b});      n=b;    }//while    sum=1;    while(!StackEmpty(s))    {      pop(s,t);