2015广工数据结构答案(2)

}

/**********

【题目】试写一算法，实现顺序栈的判空操作 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.elem[S.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(NULL==S.elem||size<=0||inc<=0) return ERROR; S.top=S.elem; S.size=size;

S.increment=inc; return OK; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的判空操作。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status StackEmpty_Sq2(SqStack2 S)

/* 对顺序栈S判空。 */ /* 若S是空栈，则返回TRUE；否则返回FALSE */ { if(S.top==S.elem) return TRUE; return FALSE; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的入栈操作。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status Push_Sq2(SqStack2 &S, ElemType e)

/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/ /* 将e压入S，返回OK。 */ { ElemType *newbase; if(S.top-S.elem>S.size)

{ newbase=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType)); if(NULL==newbase) return ERROR; S.elem=newbase;

S.size=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.top-S.elem==0) 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); // 初始化顺序栈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(StackEmpty_Sq(S1)==TRUE) { 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中元素个数，即队列的长度。 */

{ int s;

s=Q.rear-Q.front;

if(s<0) s=Q.maxSize-Q.front+Q.rear; return s; }

/**********

【题目】如果希望循环队列中的元素都能得到利用， 则可设置一个标志域tag，并以tag值为0或1来区分尾 指针和头指针值相同时的队列状态是\空\还是\满\。 试编写与此结构相应的入队列和出队列的算法。 本题的循环队列CTagQueue的类型定义如下： typedef struct {

ElemType elem[MAXQSIZE]; 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.elem[0]=x;Q.rear+=1;} else{

Q.elem[Q.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.elem[Q.front];

Q.front=(Q.front+1)%MAXQSIZE; Q.tag=0; return OK; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2015广工数据结构答案(2)在线全文阅读。