2016广工AnyView数据结构-第1-5章答案.docx

/*【题目】试写一算法，如果三个整数a，b和c的值不是依次非递增的，则通过交换，令其为非递增。*/void Descend(int &a, int &b, int &c)/* 通过交换，令 a = b = c */ if(c=b&b=a) return; else if(ab) swap(a,b); if(ac) swap(a,c); if(bc) swap(b,c); void swap(int &a,int &b) int temp; temp=a; a=b; b=a;/*【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x2 + . + anxn的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。*/float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ float answer =a0; float temp= 1.0; for(int i=1;i=n;i+) temp*=x; answer+=ai*temp; return answer;/*【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n-2)+.+f(n-k), n=k,k+1,.试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。*/Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ if(k=1|m0) return ERROR; else if(m=k-1) f=1; else if(m=0) f=0; else int i,j,sum; int *t; t=(int*)malloc(m*sizeof(int); for(i=0;i=k-2;i+) ti=0; tk-1=1; for(i=k;i=m;i+) sum=0; for(j=i-k;jMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。*/Status Series(int a, int n) /* 求i!*2i序列的值并依次存入长度为n的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */ int t=1,p=1; for(int i=1;iMAXINT) return ERROR; return OK;/*【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为： 项目名称 性别 校名 成绩 得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。*/void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ int i=0; while(resulti.sport!=NULL) switch(resulti.schoolname) case A: score0.totalscore+=resulti.score; if(resulti.gender=male) score0.malescore+=resulti.score; else score0.femalescore+=resulti.score; break;case B: score1.totalscore+=resulti.score; if(resulti.gender=male) score1.malescore+=resulti.score; else score1.femalescore+=resulti.score; break;case C: score2.totalscore+=resulti.score; if(resulti.gender=male) score2.malescore+=resulti.score; else score2.femalescore+=resulti.score; break;case D: score3.totalscore+=resulti.score; if(resulti.gender=male) score3.malescore+=resulti.score; else score3.femalescore+=resulti.score; break;case E: score4.totalscore+=resulti.score; if(resulti.gender=male) score4.malescore+=resulti.score; else score4.femalescore+=resulti.score; break; i+;/*【题目】试写一算法，对序列S的第i个元素赋以值e。序列的类型定义为：typedef struct ElemType *elem; int length; Sequence;*/Status Assign(Sequence &S, int i, ElemType e) /* 对序列S的第i个元素赋以值e，并返回OK。 */* 若S或i不合法，则赋值失败，返回ERROR */ if(S.lengthS.length) return ERROR; else S.elemi=e; return OK; /*【题目】试写一算法，由长度为n的一维数组a构建一个序列S。序列的类型定义为：typedef struct ElemType *elem; int length; Sequence;*/Status CreateSequence(Sequence &S, int n, ElemType *a) /* 由长度为n的一维数组a构建一个序列S，并返回OK。 */* 若构建失败，则返回ERROR */ if(n1) return ERROR; else S.elem=(ElemType*)malloc(n*sizeof(ElemType); S.elem0=a0; for(int i=1;idata=x; return p;/*【题目】链表的结点和指针类型定义如下 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;试写一函数，构建长度为2且两个结点的值依次为x和y的链表。*/LinkList CreateLinkList(ElemType x, ElemType y) /* 构建其两个结点的值依次为x和y的链表。*/* 若构建失败，则返回NULL。 */ LNode * p; p=(LNode*)malloc(sizeof(LNode); if(p=NULL) return NULL; else p-next=(LNode*)malloc(sizeof(LNode); if(p-next=NULL) return NULL; p-data=x; p-next-data=y; p-next-next=NULL; return p; /*【题目】链表的结点和指针类型定义如下 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;试写一函数，构建长度为2的升序链表，两个结点的值分别为x和y，但应小的在前，大的在后。*/LinkList CreateOrdLList(ElemType x, ElemType y)/* 构建长度为2的升序链表。 */* 若构建失败，则返回NULL。 */ LNode * p; p=(LNode*)malloc(sizeof(LNode); if(p=NULL) return NULL; else p-next=(LNode*)malloc(sizeof(LNode); if(p-next=NULL) return NULL; p-data=(xnext-data=(xy)?x:y; p-next-next=NULL; return p;/*【题目】试写一算法，实现顺序栈的判空操作StackEmpty_Sq(SqStack S)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈*/Status StackEmpty_Sq(SqStack S)/* 对顺序栈S判空。 */ /* 若S是空栈，则返回TRUE；否则返回FALSE */ if(S.top=0) return TRUE; return FALSE;/*【题目】试写一算法，实现顺序栈的取栈顶元素操作GetTop_Sq(SqStack S, ElemType &e)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈*/Status GetTop_Sq(SqStack S, ElemType &e) /* 取顺序栈S的栈顶元素到e，并返回OK； */ /* 若失败，则返回ERROR。 */ if(S.top=0) return ERROR; e=S.elemS.top-1; return OK;/*【题目】试写一算法，实现顺序栈的出栈操作Pop_Sq(SqStack &S, ElemType &e)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈*/Status Pop_Sq(SqStack &S, ElemType &e) /* 顺序栈S的栈顶元素出栈到e，并返回OK；*/ /* 若失败，则返回ERROR。 */ if(S.top=0) return ERROR; e=S.elem-S.top; return OK;/*【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为size和inc的空顺序栈S。typedef struct ElemType *elem; / 存储空间的基址 ElemType *top; / 栈顶元素的下一个位置 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack2;*/Status InitStack_Sq2(SqStack2 &S, int size, int inc)/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ /* 若成功，则返回OK；否则返回ERROR。 */ S.elem=(ElemType*)malloc(sizeof(ElemType); if(S.elem=NULL|size=0|incS.size) p=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType); if(p=NULL) return ERROR; S.elem=p; S.size+=S.increment; *(S.top+)=e; return OK; /*【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的出栈操作。typedef struct ElemType *elem; / 存储空间的基址 ElemType *top; / 栈顶元素的下一个位置 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack2;*/Status Pop_Sq2(SqStack2 &S, ElemType &e) /* 若顺序栈S是空的，则返回ERROR； */ /* 否则将S的栈顶元素出栈到e，返回OK。*/ if(S.elem=S.top) return ERROR; e=*(-S.top); return OK;/*【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈可调用顺序栈接口中下列函数：Status InitStack_Sq(SqStack &S, int size, int inc); / 初始化顺序栈SStatus DestroyStack_Sq(SqStack &S); / 销毁顺序栈SStatus StackEmpty_Sq(SqStack S); / 栈S判空，若空则返回TRUE，否则FALSEStatus Push_Sq(SqStack &S, ElemType e); / 将元素e压入栈SStatus Pop_Sq(SqStack &S, ElemType &e); / 栈S的栈顶元素出栈到e*/Status CopyStack_Sq(SqStack S1, SqStack &S2) /* 借助辅助栈，复制顺序栈S1得到S2。 */ /* 若复制成功，则返回TRUE；否则FALSE。 */ if(StackEmpty_Sq(S1) S2.top=0; return TRUE; S2.elem=S1.elem; S2.top=S1.top; return TRUE;/*【题目】试写一算法，求循环队列的长度。循环队列的类型定义为：typedef struct ElemType *base; / 存储空间的基址 int front; / 队头位标 int rear; / 队尾位标，指示队尾元素的下一位置 int maxSize; / 最大长度 SqQueue;*/int QueueLength_Sq(SqQueue Q)/* 返回队列Q中元素个数，即队列的长度。 */ if(Q.rear-Q.front0) return Q.maxSize-Q.front+Q.rear; return Q.rear-Q.front;/*【题目】如果希望循环队列中的元素都能得到利用，则可设置一个标志域tag，并以tag值为0或1来区分尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构相应的入队列和出队列的算法。本题的循环队列CTagQueue的类型定义如下：typedef struct ElemType elemMAXQSIZE; int tag; int front; int rear; CTagQueue;*/Status EnCQueue(CTagQueue &Q, ElemType x)/* 将元素x加入队列Q，并返回OK；*/* 若失败，则返回ERROR。 */ if(Q.front=Q.rear&Q.tag=1) return ERROR; if(Q.rear=0) Q.elem0=x; Q.rear+=1; else Q.elemQ.rear=x; Q.rear=(Q.rear+1)%MAXQSIZE; Q.tag=1; return OK;Status DeCQueue(CTagQueue &Q, ElemType &x)/* 将队列Q的队头元素退队到x，并返回OK；*/* 若失败，则返回ERROR。 */ if(Q.front=Q.rear&Q.tag=0) return ERROR; x=Q.elemQ.front; Q.front=(Q.front+1)%MAXQSIZE; Q.tag=0; return OK;/*【题目】假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。本题的循环队列CLenQueue的类型定义如下：typedef struct ElemType elemMAXQSIZE; int length; int rear; CLenQueue;*/Status EnCQueue(CLenQueue &Q, ElemType x) /* 将元素x加入队列Q，并返回OK；*/ /* 若失败，则返回ERROR。 */ if(Q.length=MAXQSIZE) return ERROR; Q.rear=(Q.rear+1)%MAXQSIZE; Q.elemQ.rear=x; Q.length+; return OK;Status DeCQueue(CLenQueue &Q, ElemType &x) /* 将队列Q的队头元素退队到x，并返回OK；*/ /* 若失败，则返回ERROR。 */ if(Q.length=0) return ERROR; x=Q.elem(Q.rear+MAXQSIZE-Q.length+1)%MAXQSIZE; Q.length-; return OK; /*【题目】已知k阶斐波那契序列的定义为: f0=0, f1=0, , fk-2=0, fk-1=1; fn=fn-1+fn-2+fn-k, n=k,k+1,试利用循环队列编写求k阶斐波那契序列中第n+1项fn的算法。本题的循环队列的类型定义如下：typedef struct ElemType *base; / 存储空间的基址 int front; / 队头位标 int rear; / 队尾位标，指示队尾元素的下一位置 int maxSize; / 最大长度 SqQueue;*/long Fib(int k, int n)/* 求k阶斐波那契序列的第n+1项fn */ if(k2|n0) return ERROR; if(nk-1) return 0; else if(n=k-1) return 1; else SqQueue S; S.base=(ElemType*)malloc(n+1)*sizeof(ElemType); S.basek-1=1; int i,j,sum; for(i=0;ik-1;i+) S.basei=0; for(i=k;in+1;i+) sum=0; for(j=i-k;j=i;j+) sum+=S.basej; S.basei=sum; return S.basen; /*【题目】设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才进行比较）。顺序表类型定义如下：typedef struct ElemType *elem; int length; int size; int increment; SqList;*/char Compare(SqList A, SqList B)/* 比较顺序表A和B, */* 返回, 若A, 若AB */int i=0;while(i=A.length-1)&(i=B.length-1)&(A.elemi=B.elemi) +i;if(i=A.length&i=B.length)return =;else if(i=A.length&i!=B.length&A.elemiB.elemi) return ;else if(i!=A.length&i!=B.length&A.elemiB.elemi) return B.elemi)return ;elsereturn ;/*【题目】试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。顺序表类型定义如下：typedef struct ElemType *elem; int length; int size; int increment; SqList;*/void Inverse(SqList &L) ElemType temp; if(L.elem!=NULL&L.length!=1) for(int i=0;iL.length/2;i+) temp=L.elemi; L.elemi=L.elemL.length-i-1; L.elemL.length-i-1=temp; /*【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值）。一元稀疏多项式的顺序存储结构:typedef struct int coef; / 系数 int exp; / 指数 Term;typedef struct Term *elem; / 存储空间基址 int length; / 长度（项数） Poly;*/float Evaluate(Poly P, float x)/* P.elemi.coef 存放ai， */* P.elemi.exp存放ei (i=1,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.em，算法内不对此再作验证 */ float result=0; float x_sum=1; int i,j; for(i=0;iP.length;i+) for(j=0;jP.elemi.exp;j+) x_sum*=x; result+=(P.elemi.coef*x_sum); x_sum=1; return result;/*【题目】假设有两个集合A和B分别用两个线性表LA和LB表示(即：线性表中的数据元素即为集合中的成员），试写一算法，求并集AAB。顺序表类型定义如下typedef struct ElemType *elem; / 存储空间的基址 int length; / 当前长度 int size; / 存储容量 int increment; / 空间不够增加空间大小 SqList; / 顺序表可调用顺序表的以下接口函数： Status InitList_Sq(SqList &L, int size, int inc); / 初始化顺序表Lint ListLength_Sq(SqList L); / 返回顺序表L中元素个数Status GetElem_Sq(SqList L, int i, ElemType &e); / 用e返回顺序表L中第i个元素的值int Search_Sq(SqList L, ElemType e); / 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1Status Append_Sq(SqList &L, ElemType e); / 在顺序表L表尾添加元素e*/void Union(SqList &La, SqList Lb) int count= 0; for(int i=0;iListLength_Sq(Lb);i+) if(Search_Sq(La, Lb.elemi)=-1) count+; ElemType * p; p=(ElemType *)realloc(La.elem,La.size+count*sizeof(ElemType); if(p=NULL) return ; La.elem=p; for(i=0;inext=S) return TRUE; return FALSE;/*【题目】试写一算法，实现链栈的取栈顶元素操作。链栈的类型定义为：typedef struct LSNode ElemType data; / 数据域 struct LSNode *next; / 指针域 LSNode, *LStack; / 结点和链栈类型*/Status GetTop_L(LStack S, ElemType &e) /* 取链栈S的栈顶元素到e，并返回OK; */* 若S是空栈，则失败，返回ERROR。 */ if(S=NULL|S-next=S) return ERROR; e=S-data; return OK;/*【题目】试写一算法，实现链队列的判空操作。链队列的类型定义为：typedef struct LQNode ElemType data; struct LQNode *next; LQNode, *QueuePtr; / 结点和结点指针类型typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LQueue; / 链队列类型*/Status QueueEmpty_LQ(LQueue Q)/* 判定链队列Q是否为空队列。 */* 若Q是空队列，则返回TRUE，否则FALSE。*/ if(Q.front!=NULL|Q.front-next!=NULL) return FALSE; return TRUE;/*【题目】试写一算法，实现链队列的求队列长度操作。链队列的类型定义为：typedef struct LQNode ElemType data; struct LQNode *next; LQNode, *QueuePtr; / 结点和结点指针类型typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LQueue; / 链队列类型*/int QueueLength_LQ(LQueue Q)/* 求链队列Q的长度并返回其值 */ if(Q.front=NULL&Q.front-next=NULL) return 0; int len= 0; LQNode * p=Q.front; while(p!=NULL) p=p-next; len+; return len;/*【题目】假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。带头结点循环链队列CLQueue的类型定义为：typedef struct LQNode ElemType data; struct LQNode *next; LQNode, *CLQueue;*/Status InitCLQueue(CLQueue &rear) / 初始化空队列 rear = (CLQueue)malloc(sizeof(LQNode); if(!rear) return FALSE; rear - next = rear; return TRUE; Status EnCLQueue(CLQueue &rear, ElemType x) / 入队 CLQueue head,p; head = rear - next; p = (CLQueue)malloc(sizeof(LQNode); if(!p)return FALSE; p - data = x; p - next = head; rear - next = p; rear = p; return TRUE;Status DeCLQueue(CLQueue &rear, ElemType &x) / 出队 CLQueue head,p; head = re