数据结构(唐策善版1-3)习题答案2010

第一章绪论习题解答1.5310022223lo g2!lo g322n nn nn n n n n n ⎛⎫⎛⎫<<<<<<<<<⎪ ⎪⎝⎭⎝⎭第二章线性表习题解答2.3设线性表存于A[arrsize]的前elenum个分量中，且递增有序。

请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

[题目分析] 在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。

查到插入位置后，如果插入位置i<elenum-1，则需要从此位置直到线性表尾依次向后移动一个元素位置，如果插入位置i=elenum,则不需要后移，直接将元素x插入即可。

方法一，直接利用题目已知条件编写程序。

不进行线性表的结构体定义。

（不推荐）void Insert(ElemType A[], int n, ElemType x)/* A是有n个元素空间目前仅有elenum（elenum<n）个元素的线性表。

本算法将元素x插入到线性表中，并保持线性表的有序性。

*/{int i,j;if(elenum>=n) printf("error!");else{i=0;while(A[i]<x) i++;/*跳出循环后，i为待插入的位置。

A[i]~A[elenum-1]都要后移一个位置,如果i>elenum 则不用后移，for循环自动跳过*/for(j=elenum-1;j>=i;j--)A[j+1]=A[j];A[i]=x;elenum++;}}查找插入点时需要平均比较次数与移动元素的平均比较次数的时间复杂度都是O(n).所以整个算法的时间复杂度为O(n).方法二：按照书上顺序表结构体的定义来做。

typedef int elemtype;typedef struct{ elemtype A[arrsize];int elenum;}sequenlist;void insertlist(L,x)sequenlist *L;elemtype x;{int i,j;for(i=0;i<=L->elenum-1;i++)if(x<L->A[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)。

要求不重新开辟存储空间，并且用顺序表、单链表两种方法存储表示。

（1）逆置顺序表基本思想：当顺序表的长度n为偶数时，以表的中线为对称轴，进行镜像交换，可以达到逆置的目的。

当顺序表的长度n为奇数时，以最中间的数据元素为轴做镜像交换即可实现就地逆置，最中间的数据元素不做交换。

综合两种情况，只需镜像交换表中的第一个元素到第⎣⎦2/n个元素。

typedef struct /*顺序表的结构体定义*/{elemtype vec[MAXSIZE];int last; /*顺序表中最后一个元素在数组中的下标*/}sequenlist;void diverse(sequenlist *L){int i,mid,temp;mid=((*L).last+1)/2; /*注意这里的mid为整型，相当于mid=⎣⎦2/)1L*/last).((*+for(i=0;i<j;i++){temp=(*L).vec[i];(*L).vec[i]=(*L).vec[(*L).last-i];(*L).vec[(*L).last-i]=temp;}}（2）逆置单链表方法一：基本思想：该算法的核心思想就是修改每个结点的指针域。

a1做为最后一个结点，其后继要置为空。

a2…an结点的后继指针全部修改，指向其前驱。

在修改指针的过程中，要注意：①逆置后会使得原来指向后继结点的指针被破坏，扫描进行不下去，为此修改指针前要保留该结点的后继结点的地址。

②逆置须将结点p的前驱结点的地址填入结点p的指针域，因此要保存P的前驱结点的地址。

③全部逆置后，头结点的指针域要指向原表的终端结点。

单链表逆置前后指针域变化情况如下：void diverse(linklist *L){linklist *p,*q,*s;p=L->next;/* p指向链表中的第一个结点 */if(!p||!(p->next)) return 1;/*空表或者只有一个结点的单链表不用逆置*/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; /*q指针后移*/}L->next=p;/*重新修改头结点的后继*/Return 1;}方法二采用前插法的原理，从第二个结点起一个个插入到表头，就可实现逆置。

void diverse(linklist *L)/*q指向当前需要逆置的结点*/{linklist *p,*q,*s;p=L->next;if(!p||!(p->next)) return; /*空表或者只有一个结点的单链表不用逆置*/ q=p->next;p->next=NULL;while(q!=NULL) /*从当前单链表的第二个结点起，一个个地进行逆置*/{s=q->next;/*s用来保存q的后继*/q->next=L->next;L->next=q;q=s; /*修改q指针*/}return;}2.8假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。

该问题要求结果链表按元素值递减次序排列。

故在合并的同时，将链表结点逆置。

void union_invert(linklist *A,*B,*C)// A和B是两个带头结点的递增有序的单链表，本算法将两表合并成// 一个带头结点的递减有序单链表C，利用原表空间。

{ linklist *pa=A->next,*pb=B->next,*C=A,*r;// pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置//元素的后继指针, 使逆置元素的表避免断开。

//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。

C->next=null;//头结点摘下，指针域置空。

算法中头指针C始终不变while (pa && pb) // 两表均不空时作if (pa->data<=pb->data) // 将A表中元素合并且逆置{ r=pa->next; // 保留后继结点的指针pa->next=C->next; // 逆置C->next=pa;pa=r; // 恢复待逆置结点的指针}else // 将B表中元素合并且逆置{ r=pb->next; // 保留后继结点的指针pb->next=C->next; // 逆置C->next=pb;pb=r; // 恢复待逆置结点的指针}// 以下while (pa)和while (pb)语句，只执行一个while (pa) // 将A表中剩余元素逆置{ r=pa->next; // 保留后继结点的指针pa->next=C->next; // 逆置C->next=pa;pa=r; // 恢复待逆置结点的指针}while (pb) // 将B表中剩余元素逆置{ r=pb->next; // 保留后继结点的指针pb->next=C->next; // 逆置C->next=pb;pb=r; // 恢复待逆置结点的指针}free(B);//释放B表头结点} // 算法结束在此基础上，一种更简洁的算法……供大家鉴赏linklist * union(linklist *A,linklist *B)∥A,B分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。

{linklist *pa,*pb,*r,*s;pa=A->next;A->next=NULL;/*头结点的后继赋为空，为前插法逆置做准备*/pb=B->next;while(pa||pb) ∥当两链表不同时为空时作{ if((pb->data<pa->data)||!pa){r=pb->next;/*r保存pb的后继*/pb->next= A->next;A->next=pb;pb=r; /*pb指针后移*/}else{q=pa->next;/*q保存pa的后继*/pa->next= A->next;A->next=pa;pa=q; /*pa指针后移*/}}}［算法讨论］两递增有序表合并成递减有序表时，上述算法是边合并边逆置。

也可先合并完，再作链表逆置。

后者不如前者优化。

算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。

2.9．设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知s为指向链表中某个结点的指针，试编写在链表中删除指针s所指结点的前趋结点的算法。

方法一：基本思想：本题利用循环单链表的特点，通过s指针循环找到其前驱结点q及q 的前驱结点r,然后将其删除。

linklist *delete(linklist *s){linklist *q,*r;q=s;wwhile(q->next!=s)/*寻找s结点的前驱q以及其前驱的前驱r ，把它赋值为r;*/r=q;q=q->next;r->next=s;free(q);return s;}方法二：直接删除s结点，然后把s结点和其前驱数值进行交换，相当于逻辑上删除了s 的前驱linklist *delete(linklist *s){linklist *q,*r;q=s;while(q->next!=s)/*寻找s结点的前驱，把它赋值为r;*/q=q->next;r=q;r->next=s->next; /*删除s结点*/r->data=s->data; /*把s结点和它的前驱交换数值*/free(s);return r;}第三章栈和队列习题解答3.1设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台。