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

精选优质文档-倾情为你奉上第一章 绪论习题解答 1.3 (1)(5) O(n) O(n) O(n) O() O(1)1.5 第二章 线性表习题解答 2.3设线性表存于Aarrsize的前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(elenu²耀=n) printf("error!"); else i=0;while(Ai<x) i+;/*跳出循环后，i为待插入的位置。AiAelenum-1都要后移一个位置,如果i>elenum则不用后移，for循环自动跳过*/for(j=elenum-1;j>=i;j-) Aj+1=Aj; Ai=x; elenum+; 查找插入点时需要平均比较次数与移动元素的平均比较次数的时间复杂度都是O(n).所以整个算法的时间复杂度为O(n).方法二：按照书上顺序表结构体的定义来做。typedef int elemtype;typedef struct elemtype Aarrsize;int elenum;sequenlist;void insertlist(L,x)sequenlist *L;elemtype x;int i,j;if(L->elenum>=arrsize) printf("error!"); return;for(i=0;i<=L->elenum-1;i+)if(x<L->Ai) break;for(j=L->elenum-1;j>=i;j-)L->Aj+1=L->Aj;L->Ai=x;L->elenum+;2.6.设有一个线性表L=(a1,a2,.an)。试设计一个算法，将线性表逆置，即使元素次序颠倒，成为L=( an,an-1,. a2,a1)。要求不重新开辟存储空间，并且用顺序表、单链表两种方法存储表示。（1）逆置顺序表基本思想：当顺序表的长度n为偶数时，以表的中线为对称轴，进行镜像交换，可以达到逆置的目的。当顺序表的长度n为奇数时，以最中间的数据元素为轴做镜像交换即可实现就地逆置，最中间的数据元素不做交换。综合两种情况，只需镜像交换表中的第一个元素到第个元素。typedef struct /*顺序表的结构体定义*/elemtype vecMAXSIZE; int last; /*顺序表中最后一个元素在数组中的下标*/sequenlist;void diverse(sequenlist *L)int i,mid,temp; mid=(*L).last+1)/2; /*注意这里的mid为整型，相当于mid=*/ for(i=0;i<j;i+) temp=(*L).veci; (*L).veci=(*L).vec(*L).last-i; (*L).vec(*L).last-i=temp; （2）逆置单链表方法一：基本思想：该算法的核心思想就是修改每个结点的指针域。a1做为最后一个结点，其后继要置为空。a2an结点的后继指针全部修改，指向其前驱。在修改指针的过程中，要注意：逆置后会使得原来指向后继结点的指针被破坏，扫描进行不下去，为此修改指针前要保留该结点的后继结点的地址。逆置须将结点p的前驱结点的地址填入结点p的指针域，因此要保存P的前驱结点的地址。全部逆置后，头结点的指针域要指向原表的终端结点。单链表逆置前后指针域变化情况如下：逆置前sqp.Lana1a33a2La1a2a3an逆置后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)/*p永远指向头结点的下一个结点，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的后继*/L->next=q;q->next=p;p=q; /*修改p指针*/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结点*/free(s);r->data=s->data; /*把s结点和它的前驱交换数值*/return r;第三章 栈和队列习题解答 3.1设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台。具体写出这四辆列车开出车站的所有可能的顺序。题目分析借助栈结构，n个入栈元素可得到种出栈序列。本题4个元素，可得到如下14种出栈序列。1234 1243 1324 1342 14322134 2143 2314 2341 24313214 3241 3421 43213.3设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系，例如xyzzyx、xyzyx都算是中心对称的字符串。要求用尽可能少的时间完成判断。（提示：将一半字符先依次入栈。）题目分析要考虑字符串长度为奇数和为偶数的情况。如果为偶数，一半字符入栈，然后依次出栈，将栈顶元素与另一半字符依次比较。如果为奇数，一半字符入栈，中间字符不用判断，跳过该字符，将接下来的一半字符与依次出栈的将栈顶元素一一比较。Void judge(linklist *L) linklist *p;seqstack stack;int i,length=0;for(p=L->next;p&&p->data!='?' p=p->next) length+; /*计算单链表中字符的个数*/setnull(&stack); /*初始化一个空栈*/for(i=0,p=L->next;i<length/2&&p;i+,p=p->next)push(&stack,p->data); /*单链表中一半元素入栈*/if(length%2) p=p->next; /*奇数个元素的单链表中间位置元素不用判断，直接跳过*/while(p->next!=NULL) /*将另一半的链表的元素与依次出栈的栈顶元素一一比较*/if(pop(&stack)!=p->data) printf("NO!");break; /*不相等就中断循环*/ p=p->next; /*相等就顺着单链表往下扫描*/if(p->next=NULL) printf("yes!"); /*p->next=NULL说明循环自然结束，字符串对称*/3.4设计一个算法判断一个算术表达式的圆括号是否正确配对。（提示：对表达式进行扫描，凡遇到（就进栈，遇），表达式被扫描完毕，栈应为空。）题目分析题目没有说明算术表达式的存储方式。这里我们就采用最简存储方式来解决问题。假定算术表达式以字符串的形式存储。void match(char *s)seqstack stack;int i; setnull(&stack);for(i=0;si!='0'i+) /*字符串以'0'结尾*/if(si='(') push(&stack,si); /*遇到'（'就进栈 */ else if(si=')') if(!empty(&stack) printf("no!");exit(0);else pop(&stack); /*遇到'）'就出栈 */ else continue; /*其它字符不做处理*/if(empty(&stack) printf("yes!"); /*正好空栈的情况*/else printf("no!");3.5两个栈共享向量空间vm,它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作方法：push(i，x)，pop(i)和top(i)，其中i为0或1，用以指示栈号。题目分析两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。因为题目给出了函数头，所以要把双向栈变量s说明为全局变量。（因为函数内部要使用到s.）如果题目没有给出函数头，我们一般都会避免使用全局变量，而是把s也作为一个参数写入函数名中。如push(s，i，x)，pop(s,i)和top(s, i)。#define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define datatype int /假设元素类型为整型typedef structdatatype stackmaxsize; /栈空间 int top2; /top为两个栈顶指针stk;stk s; /s是如上定义的结构类型变量，为全局变量。(1)入栈操作：int push(int i,int x)/入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。if(i<0|i>1)printf(“栈号输入不对”);exit(0);if(s.top1-s.top0=1) printf(“栈已满n”);return(0);switch(i) case 0: s.stack+s.top0=x; return(1); break; case 1: s.stack-s.top1=x; return(1); /push（2） 退栈操作 datatype pop(int i) /退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。 if(i<0 | i>1)printf(“栈号输入错误n”)；exit(0); switch(i) case 0: if(s.top0=-1) printf(“栈空n”)；return（-1）； else return(s.stacks.top0-); case 1: if(s.top1=maxsize printf(“栈空n”); return(-1); else return(s.stacks.top1+); /算法结束 算法讨论 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图如下所示，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。3.7 假设以带头结点的循环链表表示队列，并且只设有一个指针指向队尾元素结点（注意不设头指针），试编写相应的置空队、入队列和出队列的算法。题目分析循环队列可由尾指针唯一标识，所以定义了一个指向尾结点的指针就唯一标识了一个循环队列，不需要再定义指向循环队列的指针了！大家写程序要注意，函数体形参或者内部没有定义的变量在函数体内部是不能使用的，除非是全局变量。#include <stdio.h>#include <malloc.h>typedef int datatype;typedef struct node /*循环链表中的一个结点的结构体定义*/datatype data; struct node *next;linkque;linkque* lq_enlinkque(linkque *lq_rear,datatype x) /*入队列，注意修改尾指针*/ linkque *s; s=(linkque *)malloc(sizeof(linkque); s->data=x; s->next=lq_rear->next; /*将头结点作为s结点的后继*/ lq_rear->next=s; /*将s结点连接到尾结点的后面*/ lq_rear=s; /*修改当前的尾指针*/ return lq_rear;void lq_setnull(linkque *lq_rear) /*置空队*/ lq_rear->next=lq_rear;datatype lq_delinkque(linkque *lq_rear) /*出队操作*/linkque *head,*s; datatype x; head=lq_rear->next; /*head指向头结点*/if(head=lq_rear) return 0; /*空队列的情况*/ else s=head->next; x=s->data; / s指向出队元素 if (s= lq_rear) lq_rear =lq_rear ->next; / 若队列中只一个元素，修改尾指针else head->next=s->next;/ 修改队头元素指针 free (s); / 释放出队结点 return x;还有另外一种更简单的算法 供大家欣赏比较呼呼datatype lq_delinkque(linkque *lq_rear) /*出队操作*/linkque *head; head=lq_rear->next; /*head指向头结点*/if(head=lq_rear) return 0; /*空队列的情况*/*使用删除头结点逻辑删除开始结点的方法，可以不用区分一个结点和多个结点队列的情况处理*/ lq_rear->next=head->next; /*删除头结点，将开始结点作为头结点*/ free(head); return(lq_rear->next->data);/*返回被删结点的值*/3.9 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判别此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。题目分析注意题设条件，循环队列使用rear和quelen两个变量来表示，没有front指针，所以循环队列的结构体需要重新定义，里面只有rear和quelen两个成员变量。如果在写程序的时候用到sq->front是错误的。相应的队空和队满的条件也应该为sq->quelen=0和sq->quelen=m ,由此可见，这样封装起来的循环队列，判断队空和队满非常方便，不需要浪费存储空间就能区分开来。（如果使用front和rear封装起来的结构体，由于对满和队空都是rear=front，所以必须要浪费一个存储空间对两种状态进行区分）typedef int datatype; /*循环队列结构体定义*/typedef struct datatype sequm; int rear; int quelen;squeue;int sq_full(squeue *sq)/*判队满*/if(sq->quelen=m) return 1; else return 0;int sq_empty(squeue *sq) /*判队空*/if(sq->quelen=0) return 1; else return 0;int enqueue(squeue *sq,datatype x)/*入队*/if(sq_full(sq) printf("overflow!");return 0; /*如果队列为满返回*/elsesq->rear=(sq->rear+1)%m; /*队尾指针后移*/sq->sequsq->rear=x; sq->quelen+; /*队列长度增1*/return 1;datatype dequeue(squeue *sq) /*出队*/int front; /*局部变量front指向队头元素的位置（下标）*/if(sq_empty(sq) printf("overflow!");return 0; /*如果队列为空返回*/front=(sq->rear-sq->quelen+1+m)%m; /*根据当前的队尾指针和队列的长度计算当前队头元素的下标*/sq->quelen-;return (sq->sequfront); /*返回被删的队头元素*/专心-专注-专业