实验六-栈.doc

《数据结构》 实验六
栈的应用
——0000000000 ***
一、实验目的
熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
二、实验数据
实验随机输入。
三、实验内容与步骤
（1） 括号匹配问题：判断一个表达式中的括号（有三种括号，小、中和大括号）是否配对，编写并实现它的算法。要求：1）用不同的存储方法，求解上面的问题。2）若表达式中既有小括号，又有大括号（或中括号），且允许互相嵌套，但不能交叉，写出判断这
样的表达式是否合法的算法。如 2+3*（4-{5+2}*3） 为合法；2+3*（4-{5+2 * 3} 、2+3*（4-[5+2 * 3）为不合法。
（2）斐波那契序列求解问题：用递归函数实现斐波那契序列求解。
3.1用顺序栈求解“括号匹配问题”

#include <stdio.h>
#include <malloc.h>
#define stacksize 100

#define NULL 0
typedef struct {
int top,base;
char a[stacksize];
}Snode;

Snode * creatstack(Snode *s)
{
s=(Snode*)malloc(stacksize *sizeof (Snode));
s->top=-1;
return s;
}

char push(Snode * &s,char e)
{
if(s->top==stacksize-1)
return 0;
else
{s->top++;
s->a[s->top]=e;
return e;
}
}
char pop(Snode * &s,char e)
{
if(s->top==-1)
return 0;
else
{
e=s->a[s->top];
s->top--;
return e; }
}
void main()
{
Snode *str,*s;
char c,e;
printf("请输入左括号:\n");
scanf("%s",&c);
str=creatstack(s);
printf("请输入右括号:\n");
scanf("%s",&e);
while (c!='\n')
{
switch(c)
{
case '(':if (c==')') pop(s,e);else push(s,c);break;
case '{':if (c=='}') pop(s,e);else push(s,c);break;
case '[':if (c==']') pop(s,e);else push(s,c);break;
default:push(s,e);break;}
scanf("%s",&c);
}
if (str->top==-1)
printf("括号匹配\n");
else
printf("括号不匹配\n");
}
3.2 递归函数实现斐波那契序列

#include"stdlib.h"
#include"stdio.h"

long Fibo(int n)
{
long f;
if(n==1 || n==2)
{f=1; printf("f=",&f); return 1;}
else
{f=Fibo(n-1)+Fibo(n-2); printf("f=",&f);
return f;}
}
int main()
{
printf("please input a number:");
long Fibo(int n);
return 0;
}
四、结论与讨论

斐波那契序列的算法里，加上栈就会出错，删掉才能编译成功，该怎么用栈来编写斐波那契序列