数据结构(唐策善版)习题答案.doc

《数据结构(唐策善版)习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论习题解答1.3(1)~(5)O(n)O(n)O(n)O()O(1)1.5第二章线性表习题解答2.3设线性表存于A[arrsize]的前elenum个分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。[题目分析]在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。查到插入位置后，如果插入位置i

2、接利用题目已知条件编写程序。不进行线性表的结构体定义。（不推荐）voidInsert(ElemTypeA[],intn,ElemTypex)/*A是有n个元素空间目前仅有elenum（elenumelenum则不用后移，for循

3、环自动跳过*/for(j=elenum-1;j>=i;j--)A[j+1]=A[j];A[i]=x;elenum++;}}查找插入点时需要平均比较次数与移动元素的平均比较次数的时间复杂度都是O(n).所以整个算法的时间复杂度为O(n).方法二：按照书上顺序表结构体的定义来做。typedefintelemtype;typedefstruct{elemtypeA[arrsize];intelenum;}sequenlist;voidinsertlist(L,x)sequenlist*L;elemtypex;{inti,j;i

4、f(L->elenum>=arrsize)printf("error!");return;for(i=0;i<=L->elenum-1;i++)if(xA[i])break;for(j=L->elenum-1;j>=i;j--)L->A[j+1]=L->A[j];L->A[i]=x;L->elenum++;}2.6.设有一个线性表L=(a1,a2,….an)。试设计一个算法，将线性表逆置，即使元素次序颠倒，成为L′=(an,an-1,….a2,a1)。要求不重新开辟存储空间，并且用顺序表、单链表两种方法存储表示。

5、（1）逆置顺序表基本思想：当顺序表的长度n为偶数时，以表的中线为对称轴，进行镜像交换，可以达到逆置的目的。当顺序表的长度n为奇数时，以最中间的数据元素为轴做镜像交换即可实现就地逆置，最中间的数据元素不做交换。综合两种情况，只需镜像交换表中的第一个元素到第个元素。typedefstruct/*顺序表的结构体定义*/{elemtypevec[MAXSIZE];intlast;/*顺序表中最后一个元素在数组中的下标*/}sequenlist;voiddiverse(sequenlist*L){inti,mid,temp;mid

6、=((*L).last+1)/2;/*注意这里的mid为整型，相当于mid=*/for(i=0;i

7、修改指针前要保留该结点的后继结点的地址。②逆置须将结点p的前驱结点的地址填入结点p的指针域，因此要保存P的前驱结点的地址。③全部逆置后，头结点的指针域要指向原表的终端结点。单链表逆置前后指针域变化情况如下：逆置前sqp…..………………..….…..Lan∧a1a33a2……La1∧a2a3an逆置后voiddiverse(linklist*L){linklist*p,*q,*s;p=L->next;/*p指向链表中的第一个结点*/if(!p

8、

9、!(p->next))return1;/*空表或者只有一个结点的单链表不用逆

10、置*/q=p->next;/*q指向（或保存）p的后继*/p->next=NULL;/*逆置后尾结点后继置空*/while(q!=NULL)/*当q所指向的当前结点不为空时*/{s=q->next;/*s保存当前结点的后继*/q->next=p;/*把当前结点q的前驱p变成其后继*/p=q;/*p指针后移*/q=s;