资源描述：
《数据结构部答案耿国华2.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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[]; f
2、loat*p=a; 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("Valu
3、eis:%f",sum);}//polyvalue第二章线性表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[
4、i+1]=x; returnOK;}//Insert_SqList2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。StatusDelete_Between(Linklist&L,intmink,intmaxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{ p=L; while(p->next->data<=mink)p=p->next;/
5、/p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 { 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）以单链表作存储结构。voidre
6、verse(SqList&A)//顺序表的就地逆置{ for(i=1,j=A.length;iA.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
11、的元素插入新表 } 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．9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。StatusDelet
