发布时间 : 星期四 文章数据结构(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);