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

数据结构(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-1i==1) return ERROR;??else if(tws.top[0]==0i==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(;j0;j--)?{ *p=O;p++; }?}?◆3.19④假设一个算术表达式中可以包含三种括号：圆括号( 和)，方括号[和]和花括号{和}，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。?实现下列函数：Status MatchCheck(SqList exp);?????????????????顺序表类型定义如下：typedef struct {??? ElemType *elem;??? int?????? length;??? int?????? list