括号匹配的报告.doc

实验题目 括号匹配 实验报告一、 实验目的与要求利用链栈实现括号匹配算法；要求：运用链表建立一个栈S。检验括号是否匹配的方法可用“期待的急迫程度”来描述。每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。 二、 实验方案算法思想：利用栈的后进先出性质，编写的括号（)匹配算法，如果是()形式的括号，显示匹配，如果是（)则显示不匹配，基本思想： 1.遇到左括弧，则进栈， 2.遇到右括弧，则和栈顶的括弧检验是否匹配，如果匹配，则将左括弧出栈 3.全部匹配时，栈应该是空 #define NULL 0typedef struct LNode char data; char *next; char *top; /*栈顶指针*/ LNode,*LinkStack;int Init(LinkStack S) /*置栈空*/ S=(LinkStack)malloc(sizeof(LNode); S-top=NULL; int StackEmpty(LinkStack S) /* 判栈空*/ if(S-top=0) return(1); else return(0); int Push(LinkStack S,char e) /*进栈Push*/ char *p=(LinkStack)malloc(sizeof(LNode); /*申请一个结点空间*/ p-data=e; p-next=S-top; S-top=p; return 1;Int Pop(LinkStack S,char e)char *p=(LinkStack)malloc(sizeof(LNode); if(S-top!=NULL) p-data=e; p=S-top; S-top=p-next; free(p); return 1;int Top(LinkStack S) /*取栈顶元素 */char e; if(StackEmpty(S) return 0; else e=S-top; return 1; int Brackets(LinkStack S,char *str)int i=0,X=0; char e; printf(Please input string:n); scanf(%s,str); while(stri!=0) switch(stri) case (:push(S,stri);break; case :push(S,stri);break; case :push(S,stri);break; case ):pop(S,&e);if(e!=()X=1;break; case :pop(S,&e);if(e!=)X=1;break; case :pop(S,&e);if(e!=)X=1;break; default:break; if(X)break; i+; if(!X&stackempty(S) printf(You are right!the brackets is match!n); else printf(Wrong!the brackets isnt match!n); return 1; #includevoid main() char str100;LinkStack S;Init(S);printf(-n);printf( WELCOME n) ;printf(-n) ;Brackets(S,str);printf(nnn); printf( See you n);getch();三、实验结果和数据处理四、 结论本次实验过程中主要遇到的问题有以下几点：1.说明语法错误，通常是定义的时候重复定义或者不符合c语言的表现类型的定义。2.错误 不是一个允许的类型在函数中，是因为定义类型时不符合要求。3.错误指针必需在 - 的左侧在函数中，经过我多次试验及思考，我至今不明白该怎么更改，每次都是胡乱猜中而实验成功本次实验过程中的结论：1. 为了可以克服顺序栈操作带来的大量元素的移动问题，可采用链式存储结构来构造栈。2. 由于链栈是动态分配元素的存储空间的，所以操作时无须考虑上溢问题。五、 问题与讨论问题一、栈和队列的区别？栈和队列都是操作位置受限(只允许在端点处插入和删除)的线性表.它们的不同是:1.栈是先进后出的线性表,而队列是先进先出的线性表，也就是说栈是按先进后出的原则进行修改，队列是按先进先出的原则进行修改；2. 栈只在表的一端（栈顶）进行插入和删除，队列是分别在表的两端进行插入（队尾）和删除（队头）。问题二、链栈与顺序栈的异同？和线性表类似，栈也有两种存储表示：顺序栈和链栈。栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是”后进先出”。顺序存储结构简称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。顺序栈中元素用向量存放 栈底位置是固定不变的，可设置在向量两端的任意一个端点 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 在顺序栈中有上溢和下溢的现象。上溢