堆栈队列字符串匹配相关算法实现.doc

堆栈、队列、字符串匹配相关算法C+实现一、堆栈.cpp部分#include#includestack.husing namespace std;int main () int c; cout输入堆栈大小:c;astack STA1(c); int t; cout输入栈元素:endl;for(int i=0;it;STA1.push(t); int ch;cout1:弹栈endl;cout2:获取栈顶元素:endl;cout3:入栈元素:endl;cout4:输出栈中元素;endl;cout5:重设栈的大小:ch;while(ch!=-1)switch(ch)case 1:int re1; STA1.pop(re1); cout删除栈顶元素:re1endl; break;case 2:int re2 ; STA1.peek(re2); cout获取栈顶元素:re2endl; break;case 3:int r; cout输入入栈元素:r; STA1.push(r); break;case 4:STA1.print();break;case 5:int s; cout输入新的大小:s; STA1.setsize(s); break;cout还需要什么帮助吗?ch;if(ch=-1)cout谢谢使用endl;return 0;.h部分#includetemplateclass astack /顺序堆栈/private:int size;T * stackarray;int top;int maxstacksize;public:astack(int s )maxstacksize=100;size=s;stackarray=new T maxstacksize;top=-1;astack()delete stackarray;bool push(const T& item)if(isfull() cout栈满!endl;return false;stackarray+top=item;return true;bool pop( T &item)if(isempty()cout栈空!endl;return false;item =stackarraytop-;return true;bool peek(T &item)constif(isempty()cout栈空!endl;return false;item=stackarraytop;return true;int isempty(void)constreturn top=-1;int isfull(void)constreturn top=size-1;void clear(void)top=-1;void print();void setsize(int s)size=s;templatevoid astack:print()for(int i=0;isize;i+)coutstackarrayi ;二、队列.cpp部分#include#includequeue.husing namespace std;int main () linkqueue que1;cout输入队列大小:s;cout输入元素:endl;int c;for(int i=0;ic;que1.qinsert(c);int ch;cout1:删除元素:endl;cout2:输出队首元素:endl;cout3:输出队列元素:endl;cout4:插入元素:ch;while(ch!=-1)switch(ch)case 1:int re1; cout已删除元素: que1.qdelete(re1)endl; break;case 2:int re2; que1.qget(re2); cout队首元素:re2endl; break;case 3:que1.print();break;case 4:int temp; cout输入元素:temp; que1.qinsert(temp); break;cout还需要什么帮助吗?ch;if(ch=-1)cout谢谢使用endl;return 0;.h部分#includetemplatestruct SLNodeT data;SLNode * next;SLNode( SLNode * nextnode=NULL)next=nextnode;SLNode(const T& item , SLNode * nextnode=NULL)data=item; next=nextnode;templateclass linkqueue/ 链式队列/private:SLNode * front, * rear;int count;public:linkqueue()front=NULL;rear=NULL;linkqueue()qclear();void qinsert(const T & item);bool qdelete(T & item); bool qget(T& item);int isempty()constreturn front=NULL;void qclear();void print();templatevoid linkqueue:qinsert(const T&item)if(isempty()front=rear=new SLNode(item,NULL);count=1;else rear-next=new SLNode(item,NULL);rear=rear-next;count+;template bool linkqueue: qdelete(T& item)if(isempty()cout队列为空!endl;return false;SLNode * temp=front;item=front-data;front=front-next;count-; delete temp;if(count=0)rear=NULL;return true;template bool linkqueue: qget(T& item)if(isempty()cout队列为空!data;return true;template void linkqueue:qclear()while(!isempty()rear=front;front=front-next;delete rear;count-;rear=NULL;templatevoid linkqueue:print() SLNode * p=front; while(p-next!=NULL) coutdatanext; coutdataendl;三、字符串匹配.cpp部分#include#includeChoice.husing namespace std;int main ()char re;SLList list;cout输入待检测算式:re;while(re!=#)list.add(re);cinre; list.listout();check(list);return 0;.h部分#includetemplatestruct SLNodeT data;SLNode * next;SLNode( SLNode * nextnode=NULL)next=nextnode;SLNode(const T& item , SLNode * nextnode=NULL)data=item; next=nextnode;templateclass SLList private: SLNode * head, *tail ,*guard; int size; public: SLList(); SLList(T& item); SLList(); bool isempty()return head-next=NULL; int lenth(); void add(T& item); bool get(int k, T& item); void listout(); void match();templateSLList:SLList()head=tail=guard=new SLNode();size=0;templateSLList:SLList(T& item) tail=guard=new SLNode(item,NULL);head=new SLNode(guard);size=1;templateSLList:SLList()while(!isempty()guard=head; head=guard-next;delete guard;delete head;templateint SLList:lenth()return size;templatevoid SLList:add(T& item) tail-next=new SLNode (item,tail-next); tail=tail-next; size+;templatevoid SLList:listout()if(isempty()cout链表空!endl;elsecout链表大小:sizenext;while(guard-next!=NULL)cout第i个元素是:datanext;i+;cout第i个元素是:dataendl;templatevoid SLList:match()char s150;char s250;int i=0, j=0;int rei ,rej; guard=head;while(guard-next!=NULL)if(guard-data=|guard-data=|guard-data=()s1i=guard-data;i+; guard=guard-next;else if(guard-data=|guard-data=|guard-data=)s2j=guard-data;j+;guard=guard-next;else guard=guard-next;if(guard-data=|guard-data=|guard-data=()s1i=guard-data;i+;if(guard-data=|guard-data=|guard-dat