/**********
【题目】假设将循环队列定义为：以域变量rear 和length分别指示循环队列中队尾元素的位置和内 含元素的个数。试给出此循环队列的队满条件，并 写出相应的入队列和出队列的算法（在出队列的算 法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下： typedef struct {
ElemType elem[MAXQSIZE]; 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.elem[Q.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 */ {
SqQueue Q; int i,j; long fn=0;
Q.base=(ElemType*)malloc(sizeof(ElemType)); Q.front=0; Q.rear=0; Q.maxSize=k; for(i=0;i Q.rear=(Q.rear+1)%Q.maxSize; } Q.base[Q.rear]=1; Q.rear=(Q.rear+1)%Q.maxSize; if(n==k-1) return 1; else if(n for(i=k;i<=n;i++){ fn=0; for(j=0;j Q.base[Q.rear]=fn; Q.rear=(Q.rear+1)%Q.maxSize; } return fn; } /********** 【题目】设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'的首元，则A int length; int size; int increment; } SqList; **********/ char Compare(SqList A, SqList B) /* 比较顺序表A和B, */ /* 返回'<', 若A while(iB.elem[i]) return '>'; i++; } if(i==A.length&&i!=B.length) return '<'; if(i!=A.length&&i==B.length) return '>'; if(i==A.length&&i==B.length) return '='; } /********** 【题目】试写一算法，实现顺序表的就地逆置， 即利用原表的存储空间将线性表(a1,a2,…,an) 逆置为(an,an-1,…,a1)。 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int size; int increment; } SqList; **********/ void Inverse(SqList &L) { int i; ElemType t; for(i=0;i L.elem[i]=L.elem[L.length-i-1]; L.elem[L.length-i-1]=t; } } /********** 【题目】试对一元稀疏多项式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.elem[i].coef 存放ai， */ /* P.elem[i].exp存放ei (i=1,2,...,m) */ /* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0≤e1 float a=1,f=0; for(i=0;i for(j=0;j f=f+P.elem[i].coef*a; } return f; } /********** 【题目】假设有两个集合A和B分别用两个线性表LA和LB 表示(即：线性表中的数据元素即为集合中的成员）， 试写一算法，求并集A＝A∪B。 顺序表类型定义如下 typedef struct { ElemType *elem; // 存储空间的基址 int length; // 当前长度 int size; // 存储容量 int increment; // 空间不够增加空间大小 } SqList; // 顺序表 可调用顺序表的以下接口函数： Status InitList_Sq(SqList &L, int size, int inc); // 初始化顺序表L int 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，成功时返回该元素在表中第一次出现的位置，否则返回-1 Status Append_Sq(SqList &L, ElemType e); // 在顺序表L表尾添加元素e **********/ void Union(SqList &La, SqList Lb) { int i; for(i=0;i if(Search_Sq(La,Lb.elem[i])==-1) Append_Sq(La,Lb.elem[i]); } } /********** 【题目】试写一算法，实现链栈的判空操作。 链栈的类型定义为： typedef struct LSNode { ElemType data; // 数据域 struct LSNode *next; // 指针域 } LSNode, *LStack; // 结点和链栈类型 ***********/ Status StackEmpty_L(LStack S) /* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */ { if(S==NULL) return TRUE; else 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) return FALSE; e=S->data; return OK; 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2015广工数据结构答案(3)在线全文阅读。
相关推荐：