《数据结构》实验（三）

实验目的：

1、 掌握栈的顺序存储结构的特点及算法描述。 2、 掌握顺序栈的基本操作实现，熟悉应用方法。 3、 掌握队列顺序存储结构的特点及算法描述

4、 掌握顺序队列基本操作的实现，熟悉应用的方法。 实验课时：4课时 实验内容

1、 在键盘上接收一串带括号的字符串 ，判断括号是否匹配，如果匹配，输出正确，如果不匹配，输出第一对不匹配的括号，并显示错误。例如： {p{p}) 输出 { and } { and ) error error

具体程序如下，请同学们仔细阅读，并在提示下，在有下划线的地方填上程序， #include \#include \

void initstack(SEQSTACK *s) /*顺序栈初始化*/ { s->top = 0; }

DATATYPE1 sempty(SEQSTACK *s) /*判栈空*/ { if(s->top== 0) return 1; else return 0; }

int push(SEQSTACK *s, DATATYPE1 x) /*元素x入栈*/

{ if(s->top == MAXSIZE - 1) {printf(\栈满\\n\ return 0;} else {s->top++; (s->data)[s->top] = x; return 1;} }

DATATYPE1 pop(SEQSTACK *s) /*返回栈顶元素并删除栈顶元素*/ {DATATYPE1 x;

if(s->top == 0) { x = 0;}

else {x = (s->data)[s->top]; s->top--;} return x; }

DATATYPE1 gettop(SEQSTACK *s) /*返回栈顶元素*/ {DATATYPE1 x;

if(s->top == 0) {printf(\栈空\\n\ x = 0;} else x = (s->data)[s->top]; return x; }

void check(SEQSTACK *s) {

char ch,dh;

printf(\请输入一串括号，回车键结束 ：\ ch = getchar(); while(ch != '\\n')

{ if(ch=='('||ch=='['||ch=='{') //如果遇到左括号 {

push(s,ch); //把左括号入栈 }

if(ch==')'||ch==']'||ch=='}') //如果遇到右括号 { //出栈，并把出栈的值赋给变量dh if(sempty(s)) //如果栈为空 { printf(\缺失左括号！\ break; //跳出循环 }

dh=pop(s); printf(\和%c\\n\

if(ch=='('&&dh!=\//如果dh和ch不匹配 { printf(\括号匹配错误\\n\ break; //跳出循环 } }

ch = getchar();

} /*继续处理*/

if(ch=='\\n' && sempty(s)) //如果字符串结束并且栈为空 printf(\括号配对正确\\n\

if(sempty(s)==0) //如果栈不为空 printf(\缺失右括号\\n\}

main() {

SEQSTACK st, *s; s = &st; initstack(s);

check(s); }

2、添加一个函数dTOb(),利用栈的原理实现十进制转换成二进制。 #define DATATYPE1 int #include \#include \

#define MAXSIZE 100 typedef struct

{ DATATYPE1 data[MAXSIZE]; int top; }SEQSTACK;

void initstack(SEQSTACK *s) /*初始化空栈*/ { s->top = 0; }

int empty(SEQSTACK *s) /*判栈空*/ { if(s->top == 0) return 1; else return 0; }

int push(SEQSTACK *s, DATATYPE1 x) /*进栈*/ { if(s->top == MAXSIZE - 1) { printf(\ return 0; } else {s->top++; s->data[s->top] = x; return 1; } }

DATATYPE1 pop(SEQSTACK *s) /*出栈*/ { DATATYPE1 x;

if(empty(s)) { printf(\ x = NULL; } else { x = (s->data)[s->top]; s->top--; } return x; }

int stacklen(SEQSTACK *s) /*计算栈中元素个数*/ { return(s->top ); }

void output_stack(SEQSTACK *s) /*输出栈中元素*/ {int i;

printf(\

for(i=1;i<=s->top;i++)