实验三 栈的基本操作

实验三 栈的基本运算

学号：0700710319 姓名：梁浩然 实验日期：2009年5月6日

一、 实验目的：

（1）掌握栈的各种存储结构及基本运算的实现。

（2）掌握堆栈后进先出的运算原则在解决实际问题中的应用。 （3）复习c语言中相关语句及函数的用法。

（4）进一步熟悉c语言的相关知识，能够把某些c语言知识应用得自如一点。 （5）一定要自己先完成实验的课后习题，认真的思考，能够达到独立思考。

二、 实验要求：

（1） 熟练掌握栈的存储结构及其基本操作。

（2）理解所给出的算法，掌握栈在实际中的应用。

（3）将上机程序调试通过，并能独立完成一至两个拓展题目。

（4）一定要读书老师所给出来的程序。

三、 实验内容：

认真阅读数据结构的课本，熟悉所学的知识，认真复习c语言的相关的知识，然后对括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对算法的理解。

四、 实验步骤：

首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句

或带括号的数学表达式，同时将它们保存在一个字符型数组exps[]中。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。（程序略）

五、 实验预期的效果：

（1）认真的研究实验所给的程序；

（2）能读懂实验所给的程序，并且自己可以在计算机上调试成功；

（3）根据实验所学的知识能做好老师布置给我们的作业，编写程序并且调试出来运行

成功。

（4）在试验后自己要认真的总结该次实验所收获的东西。

六、 实验方法

实验所给程序修改如下：

#include \#define MAXSIZE 100 #define TRUE 1 #define FALSE 0 #define NULL 0

typedef int datatype;

typedef struct /*顺序栈的结构体类型定义*/ {datatype stack[MAXSIZE]; int top; }seqstack;

void setnull(seqstack *s) //置空栈-由于c语言的数组下标是从0开始的，所以置 {s->top=-1;} //空栈操作时将栈顶指针放在下标为0之前，即-1处。 int empty(seqstack *s) /*判断当前栈是否为空栈*/ {if(s->top<0) return TRUE; else return FALSE; }

int push(seqstack *s,datatype x) /*把元素x压入栈s中*/ {if(s->top>=MAXSIZE-1)

{printf(\发生上溢*/ return FALSE;} else

{s->stack[++s->top]=x; /*栈顶指针上移，数据元素入栈*/ return TRUE;} }

datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ {if(s->top<0)

{printf(\栈空，返回空值*/ return NULL;} else

{s->top--;

return(s->stack[s->top+1]);

} //由于return语句的特点，必须先使top减1，然后再执行return语句。而此 } //时栈顶元素的表示应该为s->top+1.

int judge(seqstack *s) //括号匹配检查算法。遇到\、\、\时，将其压入栈s中。 { datatype symb,ch,store; push(s,'#');

symb=getchar(); //从键盘接受字符 while(symb!='#') {

switch(symb) {

case '(': case '[':

case '{': push(s,symb);break; case ')': ch=pop(s);

if(ch!='(') return FALSE; break; case ']': ch=pop(s);

if(ch!='[') return FALSE; break; case '}': ch=pop(s);

if(ch!='{') return FALSE; break; default:; }

symb=getchar(); }

if(pop(s)=='#') return TRUE; else return FALSE; } main()

{ seqstack q; setnull(&q);

printf(\ if(judge(&q)) printf(\括号匹配，则输出yes*/ else printf(\括号不匹配，则输出no*/ }

运行结果如下： A、结果匹配

B、结果不匹配

分析讨论题：

数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1

结果为余数的逆序:102 。如果用栈的算法来实现，怎样实现？其基本原理是什么？

以下程序实现了10进制数N转化为r进制的数，如十进制数字6将其转化成二进制数即r＝2，入栈的顺序为011，出栈的顺序为110，即6对应的二进制数110，利用了栈的后进先出的原理。（程序里其他函数的定义与上面的例子相同，在此省略。）

void conversion(seqstack *s,int N,int r) { datatype x;

while(N) //当N不为0时，做while中的循环语句 { push(s,N%r); //将N%r的结果入栈 N=N/r; }

//栈不为空时执行以下循环语句 while (!empty(s))

{ x=pop(s); //出栈操作

printf(\依次输出出栈结果 } printf(\}

/*实现了将一个十进制数N转化为r进制的数 如十进制数字6将其转化成二进制数即r＝2，入栈的顺序为011，出栈的顺序为110，即6对应的二进制数110*/ void main() { int i=0,j=0; seqstack q; setnull(&q);

printf(\ scanf(\ conversion(&q,i,j); }

程序运行实例：

A、十进制66转换为八进制

B、十进制66转换为二进制

C、十进制6转换为二进制

D、十进制76转换为三进制

七、 实验小结

1、通过本次实验掌握了栈的顺序存储结构，及其基本操作函数的定义。

2、理解所给出的算法，复习c语言中相关语句及函数的用法。

3、通过分析讨论题对数字进制转换程序的编写，掌握了堆栈后进先出的运算原则在解决实际问题中的应用。

B、十进制66转换为二进制

C、十进制6转换为二进制

D、十进制76转换为三进制

七、 实验小结

1、通过本次实验掌握了栈的顺序存储结构，及其基本操作函数的定义。

2、理解所给出的算法，复习c语言中相关语句及函数的用法。

3、通过分析讨论题对数字进制转换程序的编写，掌握了堆栈后进先出的运算原则在解决实际问题中的应用。

本文来源：https://www.bwwdw.com/article/mop3.html