数据结构(C语言版)例题(第三章：栈和队列)

数据结构(C语言版)例题（第三章：栈和队列） (2008-05-09 12:33:13)

转载▼

◆3.15③ 假设以顺序存储结构实现一个双向栈，即在一维数组的存 储空间中存在着两个栈，它们的栈底分别设在数组的的两个端点。 试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈 push(tws,i,x)和出栈pop(tws,i,x)的算法, 其中i为0或1，用以分 别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设 为变参）或函数设计这些操作算法各有什么优缺点。

实现下列3个函数：

Status InitStack(TwoWayStack &tws, int size);

Status Push(TwoWayStack &tws, int i, SElemType x); Status Pop(TwoWayStack &tws, int i, SElemType &x); 双向栈类型定义如下： typedef struct {

SElemType *elem; int top[2];

int size; // 分配给elem的总容量 }TwoWayStack; // 双端栈

Status InitStack(TwoWayStack &tws, int size){

tws.elem=(SElemType*)malloc(sizeof(SElemType)*size); tws.size=size;

tws.top[0]=0; //hao

tws.top[1]=size-1; //以数组下标作为指针； return OK; }

Status Push(TwoWayStack &tws, int i, SElemType x) {int w=tws.top[0];

if(w==tws.top[1]) return ERROR; else if(i==0) {

tws.elem[tws.top[0]]=x; tws.top[0]=tws.top[0]+1; }

else if(i==1) {

tws.elem[tws.top[1]]=x; tws.top[1]=tws.top[1]-1; }

return OK;

}

Status Pop(TwoWayStack &tws, int i, SElemType &x) { if(tws.top[1]==tws.size-1&&i==1) return ERROR; else if(tws.top[0]==0&&i==0) return ERROR; else if(i==0) {

tws.top[0]-=1;

x=tws.elem[tws.top[0]]; }

else if(i==1) {

tws.top[1]+=1;

x=tws.elem[tws.top[1]]; }

return x;

}

◆3.16② 假设如题3.1所述火车调度站的入口处有n节 硬席或软席车厢（分别以H和S表示）等待调度，试编 写算法，输出对这n节车厢进行调度的操作（即入栈 或出栈操作）序列，以使所有的软席车厢都被调整到 硬席车厢之前。

实现下列函数：

void SwitchYard(SqList train, char *s);

顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表

void SwitchYard(SqList train, char *s) { int i,j=0,L; char *p;

L=train.length;p=s; for(i=0;i<=L-1;i++) {

if(train.elem[i]=='H') {*(p++)='U';j++;} else

{

*p='U'; p++; *p='O'; p++; } }

for(;j>0;j--) { *p='O';p++; }

}

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号\和 \，方括号\和\和花括号\和\，且这三种括号可按任意的 次序嵌套使用（如：…*…,…-…*…+…+…*…+…(…)…）。编写判别给定表达 式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素 为字符的顺序表中)。

实现下列函数：

Status MatchCheck(SqList exp); 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表

Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

Status MatchCheck(SqList exp) { Stack s; char *p;

SElemType c; InitStack(s);

for(p=exp.elem;*p;p++) {

if(*p=='('||*p=='['||*p=='{') Push(s,*p); else if(*p==')'||*p==']'||*p=='}') {

if(StackEmpty(s)) return FALSE; Pop(s,c);

if(*p==')'&&c!='(') return FALSE;

if(*p==']'&&c!='[') return FALSE; if(*p=='}'&&c!='{') return FALSE; } }

if(!StackEmpty(s)) return FALSE; return TRUE;

}

◆3.20③ 假设以二维数组g(1..m,1..n)表示一个图像 区域，g[i,j]表示该区域中点(i,j)所具颜色，其值

为从0到k的整数。编写算法置换点(i0,j0)所在区域 的颜色。约定和(i0,j0)同色的上、下、左、右的邻 接点为同色区域的点。

实现下列函数：

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0);

表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1];

Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef int SElemType; // 栈Stack的元素类型 Status StackInit(Stack &s, int initsize); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

void ChangeColor(GTYPE g, int m, int n,char c, int i0, int j0) { int x,y,old; Stack s; old=g[i0][j0];

StackInit(s,m*n*2); Push(s,i0); Push(s,j0);

while(!StackEmpty(s)) {

Pop(s,y); Pop(s,x); if(x>1)

if(g[x-1][y]==old) {

g[x-1][y]=c; Push(s,x-1); Push(s,y);