括号匹配实验报告
实 验 报 告 课程名称：数据结构
实验编号：实验二
指导教师：
一、实验目的
（1）掌握栈、队列、串和数组的抽象数据类型的特征。
（2）掌握栈、队列、串和数组的抽象数据类型在计算机中的实现方法。
（3）学会使用栈、队列来解决一些实际的应用问题。
二、实验内容与实验步骤
（1）实验内容：
假设表达式中除了变量名、常量和运算符外，还可以允许两种括号：圆括号和中括号，其嵌套的次序随意，编写程序检验输入的表达式中括号的的顺序是否合法。
（2）描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明解决设想。 抽象数据类型或函数描述：首先定义了一个结构体并且声明为栈类型，在其中定义了空间基地址的指针、栈顶指针以及栈存储空间的大小。之后设计了 Creat _Stack的函数，用此函数来创建一个空栈，这样可以使用堆栈来实现括号匹配的功能，又设计了一个名为Stack_Full的函数了来判断栈是否已满，若栈未满才可继续之后的压栈功能，如果堆栈已满，则需要使用realloc来动态分配空间，扩大栈的存储空间。我还设计了一个名为empty的函数，用它来判断堆栈是否为空，堆栈为空或不为空时分别返回0或1。之后设计了名为push和pop的函数来实现括号的入栈和出栈，之后设计了名为Match的函数，来判断括号是否匹配，设计了名为clean的函数来清空堆栈，这样可以连续判断不同的多项式的括号是否匹配。
解决设想：对于本题，首先我使用了栈结构，利用栈中数据“先进后出”的特点来实现对括号是否匹配的检验。实现过程基本如下：从左到右依次扫描多项式，如果遇到左括号便将左括号入栈，在所有左括号入栈之后便可以扫描到右括号，如果扫描到的右括号和栈顶的左括号可以匹配时，将左括号出栈，以此类推，最后判断栈是否为空，若为空，则括号匹配，否则括号不匹配。
三、实验环境
操作系统：Windows 7
调试软件名称：VC++
版本号：6.0
上机地点：综合楼311
四、实验过程与分析
（1）实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。 主要函数或操作内部的主要算法：
typedef struct//栈的声明
{
char *base;//指示存储数据元素的空间基地址的指针
char *top;//栈顶指针
int stacksize;//栈存储空间大小，以数据元素为单位
}SStack;
void Creat_Stack(SStack *s)//创建空栈 班级： 姓名： 组号： 实验成绩： 批阅教师签字： 实验日期： 实验时间： 实验名称：栈、队列、字符串和数组 学号：
{
s->base=(char*)malloc(sizeof(char)*size);
if(s->base==NULL)
printf("error\n");
else
{
s->top=s->base;
s->stacksize=size;
}
}
上面的算法用来建立栈，该算法的时间复杂度为O(1)，空间复杂度为O（n）。
int Stack_Full(SStack *s)//判断栈是否为满
{
if(s->top-s->base>=100)
return 1;
else
return 0;
}
int empty(SStack *s)//判断栈是否为空
{
if(s->base==s->top)
return 0;
else
return 1;
}
上面的算法分别用来判断栈是否已满，栈是否为空栈，上面两个算法的时间复杂度和空间复杂度均为O（1）。
void push(SStack *s,char *str)//入栈
{
if(Stack_Full(s)!=0)
{
printf("full\n");
}
else
*s->top++=*str;
}
void pop(SStack *s,char *str)//出栈
{
if(s->base==s->top)
printf("The stack is empty\n");
else
*str=*--s->top;
}
上面两个算法用来实现数据的入栈和出栈，时空复杂度均为O（1）。
void Match(SStack *s,char *str)
{
int i,j;
char t;
j=strlen(str);
for(i=0;i
{
if(str[i]=='('||str[i]=='[')
push(s,str);
}
for(i=0;i
{
if(str[i]==')')
{
if(*s->top=='(')
{
pop(s,&t);
}
else
s->top=s->top-1;
}
if(str[i]==']')
{
if(*s->top=='[')
{
pop(s,&t);
}
else
s->top=s->top-1;
}
}
if(empty(s)==0)
printf("括号匹配!\n");
else
printf("括号不匹配!\n");
}
该Match函数的作用即判断括号是否匹配，是本程序的核心函数，若假设输入的表达式的长度为n，则此函数中进行了两次循环，一次为扫描左括号使其全部入栈，另外一次为扫描右括号并且判断新扫描出来的右括号与栈顶的左括号是否匹配。在整个过程中执行了2n次循环，因此此程序的时间复杂度为O(n)。对于空间复杂度，本算法存储了长度为n的表达式，因而该算法的空间复杂度为O(n)。
设计的巧妙之处：在本程序中我使用了栈这种抽象数据类型，栈的“先进后出”的特点与检验括号是否匹配的“期限待的急迫程度相吻合，设计顺序栈来解决括号匹配问题。如果单从括号检验这个目的考虑可以有多种方法来实现该实验目的，而使用栈来实现括号匹配的检测，简化了程序的设计，比较容易理解和实现，并且可以提高时间效率。
（2）你在调试过程中发现了怎样的问题？又做了怎样的改进？
1）在开始程序编译时，编译器总是提醒函数的形式参数的写法有问题，之后我发现，我在栈声明时将SStack未声明为指针类型，而我在形式参数中将参数写成了SStack s，因而出现错误，所以我将其更改为SStack *s，这个问题得以解决。
2）之后，编译器进行编译时，编译器提醒我在调用empty，match等函数时，实际参数的输入有问题，使得编译不能够通过，经过检查我发现我在写这些函数时，形式参数定义为char *s，因而我便在实际参数中代表字符串的参数前加取地址&符号，这个问题便解决了。
3）在进行编译时还出现了这样的警告，说我的小于号没有定义或者没有匹配，经过检查我发现我在循环中将其中一个条件写成
（3）你的抽象数据类型的实现是否具有可扩展性？
我的抽象数据类型具有可扩展性，因为栈的大小可以修改，如果栈已满，则可以增加空间，因此具有可扩展性。
（4）测试结果
五、实验结果总结
回答以下问题：
（1）你的测试充分吗？为什么？你是怎样考虑的？
答：我认为我的测试充分，因为我的表达式是随机给出的，这样选择的数据具有随机性，具有很强的代表性，并且每次的结果正确，因此我认为我的测试比较充分。
（2）为什么你要选用栈或队列或字符串或数组等抽象数据类型作为你应用的数据结构？
答：我使用了栈这种抽象数据类型作为我应用的数据结构，栈是一个只能访问表的尾端数据的数据集合，是一种在表的一端进行插入和删除操作的线性表，数据具有“先进后出”的特点，而这种特点和括号匹配中检验括号的“期限待的极限程度”这个特点相符合，因此选用栈这种数据结构可以简化程序，更好的理解和实现程序，提高了程序运行的时间效率。
（3）用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。
答：下面的代码部分为Match函数中的主要处理部分，使用了两个循环来处理输入的表达式，第一个循环是用来从左到右扫描表达式遇到“（”或者“[”就将括号入栈，第二个循环是用来扫描表达式，如果遇到“）”或“]”就将其与栈顶的括号进行匹配，如果匹配，就将栈顶的左括号弹出，如果不匹配就将栈顶指针向下移动，直到所有的括号操作完成，如果栈为空，那么该表达式的括号是匹配的，否则括号不匹配。
j=strlen(str);
for(i=0;i
{
if(str[i]=='('||str[i]=='[')
push(s,str);
}
for(i=0;i
{
if(str[i]==')')
{
if(*s->top=='(')
{
pop(s,&t);
}
else
s->top=s->top-1;
}
if(str[i]==']')
{
if(*s->top=='[')
{
pop(s,&t);
}
else
s->top=s->top-1;
}
}
（4）你的应用中采用的是顺序的还是链式的存储结构？为什么要选用这种存储结构。
答：我的应用中采用的是顺序的链式存储结构，因为对于栈这种抽象的数据类型，有着“先进后出”的特点，这种特性和表达式中括号匹配的过程相符合，因此我采用了这种存储结构。
（5）源程序的大致的执行过程是怎样的？
答：先用编译器编写一个.c的文件，然后编译生成.obj的文件，通过连接将目标文件连接生成一个.exe文件，之后运行文件就可以执行了。
六、附录
（1）如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。 这次实验提高了我对数据结构中堆栈、队列的理解，提高了我的编程能力，学校以后可以增加实验课的课时，这样我们可以更大程度的提高自己的编程能力。另外对于本实验，我觉得我们还可以使用链表完成，链表中每个结点存储的数据项内容为括号，从左导游扫描表达式，将所有的括号按照扫描的顺序存成链表这种数据结构之后，可以将第一个结点的内容和最后一个结点的内容比较，如果匹配则比较第二个和倒数第二个，以此类推。否则输出括号不匹配。
（2）实验参考的资料 《数据结构（第二版）》 闫玉宝编著 清华大学出版社
思考题
（a）栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。
答：在计算机系统中，使用栈的应用有表达式的计算，迷宫以及括号匹配等。使用队列的应用有打印文档，售票系统，解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等 （b）在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？ 答：对于函数的切换，主要是一个压栈的过程，先以一种约定的方式把参数压栈，然后根据函数地址调用函数，函数执行后根据约定的方式出栈取得参数。
选作：查询以下内容的有关知识
a)函数调用、返回时，系统对栈进行的操作。
答：函数调用时指令指针中的地址加1，指向函数调用后的下一条指令。这个地址随后被放入堆栈，它将作为函数返回时的返回地址。在堆栈中为所声明的返回值类型开辟空间。此时当前的堆栈栈顶被记录下来并存入一个称为栈帧的特殊指针中，从现在开始到函数返回之前加入堆栈的任何数据都将被视为函数的局部变量。之后函数将所有形参放入堆栈，开始执行指令指针中的指令。局部变量按其定义的方式压入堆栈。当函数准备返回时，返回值放入之前开辟的内存中，随后堆栈指针指向栈帧指针，从而弹出被调函数的所有局部变量。
b)堆的管理都要做那些工作？具体怎样做的？
答：最小堆，将所有数据序列按完全二叉树从根开始放，如果所有根结点都小于或者等于左右子树，就是最小堆，反之，如果所有根结点的于或者等于左右子树，则为最大堆。如果不符合这两种规则则需要进行调整来变成最大堆或者最小堆。