anyview 数据结构习题集 第10章答案

数据结构习题集 第1章答案注意：此处代码可能并非最优化结果，等待代码优化中。1.16 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。要求实现下列函数：void Descend(int &x, int &y, int &z);/* 按从大到小顺序返回x，y和z的值 */void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值 */ int temp; if(xy)temp=x;x=y;y=temp; if(xz)temp=x;x=z;z=temp; if(yz)temp=y;y=z;z=temp;1.17 已知k阶裴波那契序列的定义为f0=0, f1=0, , fk-2=0, fk-1=1;fn=fn-1+fn-2+fn-k, n=k,k+1,试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。要求实现下列函数：Status Fibonacci(int k, int m, int &f);/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/* 否则（比如，参数k和m不合理）返回ERROR */Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ /没想到m竟然是从0开始的 int i; long temp; int a1000; if(k=1|m0)return ERROR; for(i=0;ik-1;i+)ai=0; ai=1; ak=1; for(temp=1,i=k+1;iMAXINT) return ERROR; temp=temp-ai-k-1+ai-1; ai=temp; f=am; return OK; 1.18 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为项目名称 性别 校名 成绩 得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。要求实现下列函数：void Scores(ResultType *result, ScoreType *score);/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 “”, male, , “”, 0 （域scorce=0）*/* 表示结束 */相关数据类型定义如下：typedef enum female,male Sex;typedef structchar *sport; / 项目名称Sex gender; / 性别（女：female；男：male）char schoolname; / 校名为A,B,C,D或Echar *result; / 成绩int score; / 得分（7,5,4,3,2或1） ResultType;typedef structint malescore; / 男子总分int femalescore; / 女子总分int totalscore; / 男女团体总分 ScoreType;void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result 数组中, */ /* 并以特殊记录 , male, , , 0 （域scorce=0）*/ /* 表示结束 */ /感觉这道题题意有点模糊. int i,j; for(j=0;jARRSIZE或对某个k(1kn)使k!2kMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。要求实现下列函数：Status Series(int ARRSIZE, int a);/* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */Status Series(int ARRSIZE, int a) /* 求i!*2i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ int i=1,temp=1; while(i=ARRSIZE) if(MAXINT/temp2*i)return OVERFLOW; temp*=2; temp*=i; ai-1=temp; +i; return OK; 1.20 试编写算法求一元多项式P(x) = a0 + a1x + a2x2 + + anxn的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。要求实现下列函数：float Polynomial(int n, int a, float x0);/* 求一元多项式的值P(x0)。 */* 数组a的元素ai为i次项的系数，i=0,1,n */float Polynomial(int n, int a, float x) /* 求一元多项式的值P(x)。 */ /* 数组a的元素ai为i次项的系数，i=0,.,n */ int i=1; float temp=1; float total=a0; if(0=n)return total; while(i=n) temp*=x; total+=ai*temp; +i; return total; 数据结构习题集 第2章答案2.11 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：void InsertOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; SqList;void InsertOrderList(SqList &L, ElemType x) / 在有序的顺序表 L 中保序插入数据元素 x ElemType *p,*q; p=L.elem; while(*px&p=p;q-) *(q+1)=*q; *p=x; +L.length; 2.12 设A=(a1,am)和B=(b1,bn)均为有序顺序表，A和B分别为A和B中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后的子表分别为A=(x,z)和B=(y,x,x,z)）。若A=B=空表，则A=B；若A=空表，而B 空表，或者两者均不为空表，且A的首元小于B的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A和B才进行比较）。要求实现下列函数：char Compare(SqList A, SqList B);/* 比较顺序表A和B, */* 返回, 若Ab; *= /* =, 若A=B; */* , 若AB */顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; SqList;char Compare(SqList A, SqList B) / 比较顺序表A和B, / 返回, 若A, 若AB char a,b; int la=1,lb=1; while(la=A.length&lb*(B.elem+lb-1)return ; else if(*(A.elem+la-1)*(B.elem+lb-1)return ; +la; +lb; if(A.length=B.length) return =; /此处应先判断长度是否相等！ if(la=A.length+1)return ; 2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkList Locate(LinkList L, ElemType x);/ If x in the linked list whose head node is pointed/ by L, then return pointer pointing node x,/ otherwise return NULL单链表类型定义如下：typedef struct LNode ElemType data;struct LNode *next; LNode, *LinkList;LinkList Locate(LinkList &L, ElemType x) / If x in the linked list whose head node is pointed / by L, then return pointer ha pointing node x, / otherwise return NULL LinkList p=L-next; while(p) if(x=p-data) return p; p=p-next; return NULL; 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数：int Length(LinkList L);/ Return the length of the linked list/ whose head node is pointed by L单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int Length(LinkList L) / Return the length of the linked list / whose head node is pointed by L int i=0; LinkList p=L; while(p-next) +i; p=p-next; return i; 2.17 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现下列函数：void Insert(LinkList &L, int i, ElemType b);单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;/思路不是很清晰，很多细节问题，调试了很长时间 /主要考虑问题：1、i为0或负数时 2、i在链表长度内 3、i为链表长度+1时 4、代码精简 void Insert(LinkList &L, int i, ElemType b) int j,count; LinkList p=L,q=L; if(inext; if(1=i) p=(LinkList)malloc(sizeof(LNode); p-data=b; p-next=L; L=p; else if (i1&i=count+1) for(p=L,j=1;jnext; p=(LinkList)malloc(sizeof(LNode); p-data=b; p-next=q-next; q-next=p; 2.18 同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。实现下列函数：void Delete(LinkList &L, int i);单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Delete(LinkList &L, int i) int j; int count=0; LinkList p=L,q; /1、求链表长度 while(p) p=p-next; +count; /2、查找第i-1号元素 /特殊位置首位、末尾 p=L; if(1=i) L=p-next; free(p); /i=0时没问题 else if(i1&i=count) for(p=L,j=1;jnext; q=p-next; p-next=q-next; free(q); 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素 (使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。实现下列函数：void Purge(LinkList &L);单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Purge(LinkList &L) ElemType last=L-next-data; LinkList q=L-next,p=L-next; while(p) if(last=p-data&p!=L-next) q-next=p-next; free(p); p=q; else last=p-data; q=p; p=p-next; 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。实现下列函数：void Inverse(SqList &L);顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; SqList;void Inverse(SqList &L) int i; ElemType *p,temp; p=L.elem; for(i=0;inext; /保存首元素地址 last=L-next;/上一个指针 cur=L-next; /当前操作的指针 if(cur) while(cur)/此处没注意，写成了！cur，大意失荆州啊！ cur=L-next; L-next=cur-next; cur-next=last; if(cur)last=cur; L-next=last; q-next=NULL; 2.23 设线性表A=(a1,am), B=(b1,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1,b1,am,bm,bm+1,bn) 当mn时；或者 C=(a1,b1,an,bn,an+1,am) 当mn时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。实现下列函数：void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依题意，合并带头结点的单链表ha和hb为hc */ LinkList cur_a,cur_b,cur_c; cur_a=ha-next; cur_b=hb-next; cur_c=ha;/这里要注意给cur_c赋值，不然地址为空 while(cur_a&cur_b) cur_c-next=cur_a;/Lc的next指向a; cur_c=cur_c-next;/cur_c指向c-next cur_a=cur_a-next;/cur_a指向a-next cur_c-next=cur_b;/cur_c的next指向b cur_c=cur_c-next;/cur_c指向b cur_b=cur_b-next;/cur_b指向b-next if(cur_a) cur_c-next=cur_a; if(cur_b) cur_c-next=cur_b; hc=ha; 2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表（即A表和B表）的结点空间构造C表。实现下列函数：void Union(LinkList &lc, LinkList la, LinkList lb);/* 依题意，利用la和lb原表的结点空间构造lc表 */单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Union(LinkList &lc, LinkList &la, LinkList &lb) LinkList temp,last,q; if(la-next-datanext-data) q=la-next;last=la-next; else q=lb-next;last=lb-next; while(la-next&lb-next) if(la-next-datanext-data) temp=la-next; la-next=temp-next; temp-next=last; last=temp; else temp=lb-next; lb-next=temp-next; temp-next=last; last=temp; / while(la-next) temp=la-next; la-next=temp-next; temp-next=last; last=temp; while(lb-next) temp=lb-next; lb-next=temp-next; temp-next=last; last=temp; q-next=NULL; lc=la; lc-next=temp; 2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。实现下列函数：ElemType DeleteNode(LinkList s);/* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ ElemType e; LinkList p,temp=s; while(temp-next-next!=s) temp=temp-next; e=temp-next-data; p=temp-next; temp-next=s; free(p); return e; 2.32 已知有一个单向循环链表，其每个结点中含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。实现下列函数：void PerfectBiLink(BiLinkList &CL);双向循环链表类型定义如下：typedef struct BiNode ElemType data;int freq; / 2.38题用struct BiNode *prev,*next; BiNode, *BiLinkList;void PerfectBiLink(BiLinkList &CL) BiLinkList p; p=CL; p-next-prev=p; p=p-next; while(p!=CL) p-next-prev=p; p=p-next; 2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。实现下列函数：void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) LinkList p,cur_c,cur_d,cur_o; p=ll-next; cur_c=lc; cur_d=ld; cur_o=lo; while(p) if(p-data=A&p-datanext=p; cur_c=cur_c-next; else if(p-data=0&p-datanext=p; cur_d=cur_d-next; else cur_o-next=p; cur_o=cur_o-next; p=p-next; cur_c-next=lc; cur_d-next=ld; cur_o-next=lo; 2.37 设以带头结点的双向循环链表表示的线性表L=(a1,a2,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,an,a4,a2)。实现下列函数：void ReverseEven(BiLinkList &L);双向循环链表类型定义如下：typedef struct BiNode ElemType data;int freq; / 2.38题用struct BiNode *prev,*next; BiNode, *BiLinkList;void ReverseEven(BiLinkList &L) BiLinkList last,p,temp; int count=0; /用count计结点个数 p=L-next; /p指向第一个元素 while(p!=L-prev)/求链表长度-1 +count; p=p-next; last=p;/获得最后一个元素的地址 if(count=2) p=p-prev; while(p!=L-next)/当p指向的不是第一个元素时 if(0=count%2)/判断是否序号为偶数的结点 temp=p; p=p-prev; temp-prev-next=temp-next; temp-next-prev=temp-prev; last-next=temp; temp-prev=last; last=temp; else/奇号结点则继续往前 p=p-prev; -count; last-next=L;/构建循环 L-prev=last;/构建循环 2.39 试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。实现下列函数：float Evaluate(SqPoly pn, float x);/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.em，算法内不对此再作验证* 多项式的顺序存储结构:typedef struct int coef;int exp; PolyTerm;typedef struct PolyTerm *data;int length; SqPoly;float Evaluate(SqPoly pn, float x) /* pn.datai.coef 存放ai， */ /* pn.datai.exp存放ei (i=1,2,.,m) */ /* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0e1e2.em，算法内不对此再作验证*/ int i=0,j=1,cur;/没想到这题目的数据i是从零开始的。 float total=0,temp=1; while(ipn.length) for(cur=pn.datai.exp;jnext,last=pa-next,tail=pa-next; if(pa-next)/此处改为cur时遇到空表会出错，不知道为什么 if(0=last-exp)cur=cur-next;last-coef=0; while(cur!=pa) last-coef=cur-coef*(cur-exp); last-exp=cur-exp-1; tail=last; last=last-next; cur=cur-next; if(cur=last-next)free(last);tail-next=pa; 数据结构习题集 第3章答案3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。实现下列函数:Status match(char *str);/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status match(char *str) /* 若str是属该模式的字符序列，*/ /* 则返回TRUE，否则返回FALSE */ /文档没有说明字符串是以结尾的 /也没有说栈的类型是SqStack，用Stack时编译出错 SqStack s; SElemType c; Status flag=1; InitStack(s); char *cur=str; while(&!=*cur) Push(s,*cur); +cur; /入栈 +cur; if(!GetTop(s,c)&*cur!=)flag=0;/判断栈空 while(*cur!= ) Pop(s,c); if(c!=*cur)flag=0;break; +cur; /依次出栈匹配 if(GetTop(s,c)flag=0;/再次判断是否非空 return flag; 3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。实现下列函数：Status MatchCheck(SqList exp);/* 顺序表exp表示表达式； */* 若exp中的括号配对，则返回TRUE，否则返回FALSE */* 注：本函数不使用栈 */顺序表类型定义如下：typedef struct ElemType *elem;int length;int listsize; SqList; / 顺序表Status MatchCheck(SqList exp) /* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ /*/ / 此题top指针和cur指针要很仔细地运用，还有判错条件也要小心 ElemType *cur,*top,*base; base=exp.elem;/模拟栈底 top=cur=base+1;/模拟栈顶(top)和当前元素(cur) if()=*cur) return FALSE; /判断第一个字符是否为右括号 if(0=exp.length) return TRUE; /判断是否为空顺序表 while(cur=base+exp.length-1)/依次遍历 if(=*cur)/当元素为左括号时 if(top!=cur) *top=*cur; *cur=0; +top; /top始终指向第二个元素 / else if()=*cur) if(top=base) return FALSE; if(=*(top-1) *(-top)=0; *cur=0; / +cur; if(0=*base)return TRUE;/此处应为base，而不是top return FALSE