DS03-PE22 /**********
【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。 顺序栈的类型定义为： typedef struct {
ElemType *elem; // 存储空间的基址
int top; // 栈顶元素的下一个位置，简称栈顶位标 int size; // 当前分配的存储容量 int increment; // 扩容时，增加的存储容量 } SqStack; // 顺序栈 可调用顺序栈接口中下列函数：
Status InitStack_Sq(SqStack &S, int size, int inc); // 初始化顺序栈S Status DestroyStack_Sq(SqStack &S); // 销毁顺序栈S
Status StackEmpty_Sq(SqStack S); // 栈S判空，若空则返回TRUE，否则FALSE Status Push_Sq(SqStack &S, ElemType e); // 将元素e压入栈S
Status Pop_Sq(SqStack &S, ElemType &e); // 栈S的栈顶元素出栈到e ***********/
Status CopyStack_Sq(SqStack S1, SqStack &S2) /* 借助辅助栈，复制顺序栈S1得到S2。 */ /* 若复制成功，则返回TRUE；否则FALSE。 */ {
// if( TRUE==StackEmpty_Sq(S1) ) return FALSE;//当S1是空的时候 SqStack S3;
if( ERROR==InitStack_Sq( S2,S1.size,S1.increment ) ) return FALSE;
if( ERROR==InitStack_Sq( S3,S1.size,S1.increment ) ) return FALSE;//对S1、S2的初始化 if( !StackEmpty_Sq(S2) )return FALSE;
if( !StackEmpty_Sq(S3) )return FALSE;//对S1、S2的判空 ElemType e; while(S1.top) {
Pop_Sq(S1,e); Push_Sq(S3,e); }
while(S3.top) {
Pop_Sq(S3,e); Push_Sq(S2,e); }
// DestroyStack_Sq(S1); // DestroyStack_Sq(S3); return TRUE; }
DS03-PE37
/**********
【题目】假设将循环队列定义为：以域变量rear 和length分别指示循环队列中队尾元素的位置和内 含元素的个数。试给出此循环队列的队满条件，并 写出相应的入队列和出队列的算法（在出队列的算 法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下： typedef struct {
ElemType elem[MAXQSIZE]; int length; int rear; } CLenQueue; **********/
Status EnCQueue(CLenQueue &Q, ElemType x) /* 将元素x加入队列Q，并返回OK；*/ /* 若失败，则返回ERROR。 */ {
if( MAXQSIZE<=Q.length ) return ERROR;//队满，无法插入 Q.rear = (Q.rear+1)%MAXQSIZE; Q.elem[Q.rear]=x; Q.length+=1; return OK; }
Status DeCQueue(CLenQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK；*/ /* 若失败，则返回ERROR。 */ {
if( 0==Q.length ) return ERROR;
x=Q.elem[((Q.rear+MAXQSIZE-Q.length+1)%MAXQSIZE)]; Q.length-=1; return OK; }
DS03-PE44 /**********
【题目】已知k阶斐波那契序列的定义为: f0=0, f1=0, …, fk-2=0, fk-1=1; fn=fn-1+fn-2+…+fn-k, n=k,k+1,…
试利用循环队列编写求k阶斐波那契序列中第 项fn+1n的算法。
本题的循环队列的类型定义如下： typedef struct {
ElemType *base; // 存储空间的基址
int front; // 队头位标
int rear; // 队尾位标，指示队尾元素的下一位置 int maxSize; // 最大长度 } SqQueue; **********/
long AddSum(int n,ElemType *q) {
long sum=0; int i;
for( i=0; i /* 求k阶斐波那契序列的第n+1项fn */ { if( k<2||n<-1 ) return ERROR; if( n Q.base=(ElemType*)malloc(k*sizeof(ElemType)); if( NULL==Q.base )return ERROR; Q.maxSize=k; for( i=0; i Q.base[i]=0; } //初始化序列 Q.base[k-1]=1; Q.front=0; Q.rear=k-1; a=k; while( a<=n ) { Q.rear=(Q.rear+1)%k; Q.base[Q.rear]=AddSum(k,Q.base); a++; } return Q.base[Q.rear]; } DS03-PE81 /********** 【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式 项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0 为给定值）。 一元稀疏多项式的顺序存储结构: typedef struct { int coef; // 系数 int exp; // 指数 } Term; typedef struct { Term *elem; // 存储空间基址 int length; // 长度（项数） } Poly; **********/ float Function(Term *p,float x) { int a; float sum=1; if( 0==p->exp ) return sum; for( a=0;a float Evaluate(Poly P, float x) /* P.elem[i].coef 存放ai， */ /* P.elem[i].exp存放ei (i=1,2,...,m) */ /* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0≤e1 float sum=0; Term *p; p=P.elem; if( 0==P.length ) return sum; while( P.length-- ) { sum += p->coef*Function(p,x); p++; } return sum; } DS03-PE85 /********** 【题目】假设有两个集合A和B分别用两个线性表LA和LB 表示(即：线性表中的数据元素即为集合中的成员）， 试写一算法，求并集A＝A∪B。 1、在每个元素遍历的时候，排除相同的元素 2、插入 顺序表类型定义如下 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 Append_Sq1(SqList L, ElemType e) { L.elem[L.length]=e; } void Union(SqList &La, SqList Lb) { ElemType e; int a=ListLength_Sq(Lb); int b=ListLength_Sq(La); ElemType *p; p=(ElemType*)realloc(La.elem,(a+b)*sizeof(ElemType)); La.elem=p; La.length=b; La.size=a+b; int i=1; while( i<=a ) { GetElem_Sq(Lb,i,e); if( -1==Search_Sq(La,e) )