Anyview 第四章 15年数据结构 下载本文

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;aexp; a++ ) sum *= x; return sum; }

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) )