数据结构部分答案耿国华2

《数据结构部分答案耿国华2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1．4试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。voidpolyvalue(){intn,p,i,x,xp,sum;  floata[];  float*p=a;  

2、printf("Inputnumberofterms:");  scanf("%d",&n);  printf("Inputthe%dcoefficientsfroma0toa%d:",n,n);  for(i=0;i<=n;i++)scanf("%f",p++);  printf("Inputvalueofx:");  scanf("%f",&x);  p=a;xp=1;sum=0;//xp用于存放x的i次方  for(i=0;i<=n;i++)  {    sum+=xp*(*p++);    xp*=x;  }  printf("Valueis:%f",sum);}//polyva

3、lue第二章线性表2．4设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{  if(va.length+1>va.listsize)returnERROR;  va.length++;  for(i=va.length-1;va.elem[i]>x&&i>=0;i--)    va.elem[i+1]=va.elem[i];  va.elem[i+1]=x;  returnOK;}//Insert_SqLis

4、t2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。StatusDelete_Between(Linklist&L,intmink,intmaxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{  p=L;  while(p->next->data<=mink)p=p->next;//p是最后一个不大于mink的元素  if(p->next)    //如果还有比min

5、k更大的元素  {    q=p->next;    while(q->datanext;//q是第一个不小于maxk的元素    p->next=q;  }}//Delete_Between2．7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。（2）以单链表作存储结构。voidreverse(SqList&A)//顺序表的就地逆置{  for(i=1,j=A.length;i

6、j--)    A.elem[i]<->A.elem[j];}//reverse2．8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。  while(pa

7、

8、pb)  {    if(pa->datadata

9、

10、!pb)    {      pc=pa;q=pa->next;pa->next=pre;pa=q;//将A的元素插入新表    }    else    {      pc=pb;q=pb->next;pb->next=pre;pb=q;

11、//将B的元素插入新表    }    pre=pc;  }  C=A;A->next=pc;//构造新表头}//reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.2．9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。StatusDelet