括号匹配实验报告

1、 五、实验结果总结回答以下问题：你的测试充分吗？为什么？你是怎样考虑的？答：我认为我的测试充分，因为我的表达式是随机给出的，这样选择的数据具有随机性，具有很强的代表性，并且每次的结果正确，因此我认为我的测试比较充分。为什么你要选用栈或队列或字符串或数组等抽象数据类型作为你应用的数据结构？答：我使用了栈这种抽象数据类型作为我应用的数据结构，栈是一个只能访问表的尾端数据的数据集合，是一种在表的一端进行插入和删除操作的线性表，数据具有“先进后出”的特点，而这种特点和括号匹配中检验括号的“期限待的极限程度”这个特点相符合，因此选用栈这种数据结构可以简化程序，更好的理解和实现程序，提高了程序运行的时间效

2、率。用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。答：下面的代码部分为Match函数中的主要处理部分，使用了两个循环来处理输入的表达式，第一个循环是用来从左到右扫描表达式遇到“(”或者“”就将括号入栈，第二个循环是用来扫描表达式，如果遇到“)”或“”就将其与栈顶的括号进行匹配，如果匹配，就将栈顶的左括号弹出，如果不匹配就将栈顶指针向下移动，直到所有的括号操作完成，如果栈为空，那么该表达式的括号是匹配的，否则括号不匹配。j=strlen(str);for(i=0;ij;i+)if(stri=(|stri=)push(s,str);for(i=0;ij;i+)if(stri=)if

3、(*s-top=()pop(s，&t);elsestop=s-top-1;if(stri=)if(*stop二二)pop(s，&t);elsestop=stop1;（4）你的应用中采用的是顺序的还是链式的存储结构？为什么要选用这种存储结构。答：我的应用中采用的是顺序的链式存储结构，因为对于栈这种抽象的数据类型，有着“先进后出”的特点，这种特性和表达式中括号匹配的过程相符合，因此我采用了这种存储结构。（5）源程序的大致的执行过程是怎样的？答：先用编译器编写一个.C的文件，然后编译生成.Obj的文件，通过连接将目标文件连接生成一个.exe文件，之后运行文件就可以执行了。六、附录（1）如果你对这个实

4、验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。这次实验提高了我对数据结构中堆栈、队列的理解，提高了我的编程能力，学校以后可以增加实验课的课时，这样我们可以更大程度的提高自己的编程能力。另外对于本实验，我觉得我们还可以使用链表完成，链表中每个结点存储的数据项内容为括号，从左导游扫描表达式，将所有的括号按照扫描的顺序存成链表这种数据结构之后，可以将第一个结点的内容和最后一个结点的内容比较，如果匹配则比较第二个和倒数第二个，以此类推。否则输出括号不匹配。（2）实验参考的资料数据结构（第二版）闫玉宝编著清华大学出版社思考题（a）栈和队列在计算机系统中有哪些应用？写出你知道的系统

5、中，这两种抽象数据类型的应用。答：在计算机系统中，使用栈的应用有表达式的计算，迷宫以及括号匹配等。使用队列的应用有打印文档，售票系统，解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等（b）在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？答：对于函数的切换，主要是一个压栈的过程，先以一种约定的方式把参数压栈，然后根据函数地址调用函数，函数执行后根据约定的方式出栈取得参数。选作：查询以下内容的有关知识a）函数调用、返回时，系统对栈进行的操作。答：函数调用时指令指针中的地址加1，指向函数调用后的下一条指令。这个地址随后被放入堆栈，它将作为函数返回时的返回地址。在堆栈中为所声明的返回值类型开辟空间。此时当前的堆栈栈顶被记录下来并存入一个称为栈帧的特殊指针中，从现在开始到函数返回之前加入堆栈的任何数据都将被视为函数的局部变量。之后函数将所有形参放入堆栈，开始执行指令指针中的指令。局部变量按其定义的方式压入堆栈。当函数准备返回时，返回值放入之前开辟的内存中，随后堆栈指针指向栈帧指针，从而弹出被调函数的所有局部变量。b）堆的管理都要做那些工作？具体怎样做的？答：最小堆，将所有数据序列按完全