堆栈队列字符串匹配相关算法实现.docx
《堆栈队列字符串匹配相关算法实现.docx》由会员分享，可在线阅读，更多相关《堆栈队列字符串匹配相关算法实现.docx（15页珍藏版）》请在冰点文库上搜索。
堆栈队列字符串匹配相关算法实现
堆栈、队列、字符串匹配相关算法C++实现
一、堆栈
.cpp部分
#include
#include"stack.h"
usingnamespacestd;
intmain（）{
intc;
cout<<"输入堆栈大小:
"<cin>>c;
astackSTA1（c）;
intt;
cout<<"输入栈元素:
"<for（inti=0;icin>>t;
STA1.push（t）;
}
intch;
cout<<"1:
弹栈"<cout<<"2:
获取栈顶元素:
"<cout<<"3:
入栈元素:
"<cout<<"4:
输出栈中元素;"<cout<<"5:
重设栈的大小:
"<cin>>ch;
while（ch!
=-1）{
switch（ch）{
case1:
{intre1;
STA1.pop（re1）;
cout<<"删除栈顶元素:
"<break;}
case2:
{intre2;
STA1.peek（re2）;
cout<<"获取栈顶元素:
"<break;}
case3:
{intr;
cout<<"输入入栈元素:
"<cin>>r;
STA1.push（r）;
break;}
case4:
{STA1.print（）;break;}
case5:
{ints;
cout<<"输入新的大小:
"<cin>>s;
STA1.setsize（s）;
break;}
}
cout<<"还需要什么帮助吗?
"<cin>>ch;
}
if（ch==-1）cout<<"谢谢使用"<return0;
}
.h部分
#include
template
classastack{//顺序堆栈//
private:
intsize;
T*stackarray;
inttop;
intmaxstacksize;
public:
astack（ints）{
maxstacksize=100;
size=s;
stackarray=newT[maxstacksize];
top=-1;
}
~astack（）{delete[]stackarray;}
boolpush（constT&item）{
if（isfull（））{
cout<<"栈满!
"<returnfalse;
}
stackarray[++top]=item;
returntrue;
}
boolpop（T&item）{
if（isempty（））{
cout<<"栈空!
"<returnfalse;
}
item=stackarray[top--];
returntrue;
}
boolpeek（T&item）const{
if（isempty（））{
cout<<"栈空!
"<returnfalse;
}
item=stackarray[top];
returntrue;
}
intisempty（void）const{returntop==-1;}
intisfull（void）const{returntop==size-1;}
voidclear（void）{top=-1;}
voidprint（）;
voidsetsize（ints）{size=s;}
};
template
voidastack:
:
print（）{
for（inti=0;i}
二、队列
.cpp部分
#include
#include"queue.h"
usingnamespacestd;
intmain（）{
linkqueueque1;
cout<<"输入队列大小:
"<ints;
cin>>s;
cout<<"输入元素:
"<intc;
for（inti=0;icin>>c;
que1.qinsert（c）;
}
intch;
cout<<"1:
删除元素:
"<cout<<"2:
输出队首元素:
"<cout<<"3:
输出队列元素:
"<cout<<"4:
插入元素:
"<cin>>ch;
while（ch!
=-1）{
switch（ch）{
case1:
{intre1;
cout<<"已删除元素:
"<break;}
case2:
{intre2;
que1.qget（re2）;
cout<<"队首元素:
"<break;}
case3:
{que1.print（）;
break;}
case4:
{inttemp;
cout<<"输入元素:
"<cin>>temp;
que1.qinsert（temp）;
break;}
}
cout<<"还需要什么帮助吗?
"<cin>>ch;
}
if（ch==-1）cout<<"谢谢使用"<return0;
}
.h部分
#include
template
structSLNode{
Tdata;
SLNode*next;
SLNode（SLNode*nextnode=NULL）{
next=nextnode;
}
SLNode（constT&item,SLNode*nextnode=NULL）{
data=item;next=nextnode;
}
};
template
classlinkqueue{//链式队列//
private:
SLNode*front,*rear;
intcount;
public:
linkqueue（）{front=NULL;rear=NULL;
}
~linkqueue（）{qclear（）;}
voidqinsert（constT&item）;
boolqdelete（T&item）;
boolqget（T&item）;
intisempty（）const{returnfront==NULL;}
voidqclear（）;
voidprint（）;
};
template
voidlinkqueue:
:
qinsert（constT&item）{
if（isempty（））{
front=rear=newSLNode（item,NULL）;
count=1;
}
else{
rear->next=newSLNode（item,NULL）;
rear=rear->next;
count++;
}
}
template
boollinkqueue:
:
qdelete（T&item）{
if（isempty（））{
cout<<"队列为空!
"<returnfalse;
}
SLNode*temp=front;
item=front->data;
front=front->next;
count--;
deletetemp;
if（count==0）rear=NULL;
returntrue;
}
template
boollinkqueue:
:
qget（T&item）{
if（isempty（））{
cout<<"队列为空!
"<returnfalse;
}
item=front->data;
returntrue;
}
template
voidlinkqueue:
:
qclear（）{
while（!
isempty（））{
rear=front;
front=front->next;
deleterear;
count--;
}
rear=NULL;
}
template
voidlinkqueue:
:
print（）{
SLNode*p=front;
while（p->next!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<data<}
三、字符串匹配
.cpp部分
#include
#include"Choice.h"
usingnamespacestd;
intmain（）{
charre;
SLListlist;
cout<<"输入待检测算式:
"<cin>>re;
while（re!
='#'）{
list.add（re）;
cin>>re;
}
list.listout（）;
check（list）;
return0;
}
.h部分
#include
template
structSLNode{
Tdata;
SLNode*next;
SLNode（SLNode*nextnode=NULL）{next=nextnode;}
SLNode（constT&item,SLNode*nextnode=NULL）{data=item;next=nextnode;}
};
template
classSLList{
private:
SLNode*head,*tail,*guard;
intsize;
public:
SLList（）;
SLList（T&item）;
~SLList（）;
boolisempty（）{returnhead->next==NULL;}
intlenth（）;
voidadd（T&item）;
boolget（intk,T&item）;
voidlistout（）;
voidmatch（）;
};
template
SLList:
:
SLList（）{
head=tail=guard=newSLNode（）;
size=0;
};
template
SLList:
:
SLList（T&item）{
tail=guard=newSLNode（item,NULL）;
head=newSLNode（guard）;
size=1;
};
template
SLList:
:
~SLList（）{
while（!
isempty（））{
guard=head;
head=guard->next;
deleteguard;
}
deletehead;
};
template
intSLList:
:
lenth（）{
returnsize;
}
template
voidSLList:
:
add（T&item）{
tail->next=newSLNode（item,tail->next）;
tail=tail->next;
size++;
};
template
voidSLList:
:
listout（）{
if（isempty（））{cout<<"链表空!
"<else{cout<<"链表大小:
"<inti=0;
guard=head->next;
while（guard->next!
=NULL）{
cout<<"第"<"<data<guard=guard->next;
i++;
}
cout<<"第"<"<data<}
};
template
voidSLList:
:
match（）{
chars1[50];
chars2[50];
inti=0,j=0;
intrei,rej;
guard=head;
while（guard->next!
=NULL）{
if（guard->data=='{'||guard->data=='['||guard->data=='（'）{
s1[i]=guard->data;
i++;
guard=guard->next;
}
elseif（guard->data=='}'||guard->data==']'||guard->data=='）'）{
s2[j]=guard->data;
j++;
guard=guard->next;
}
elseguard=guard->next;
}
if（guard->data=='{'||guard->data=='['||guard->data=='（'）{
s1[i]=guard->data;
i++;
}
if（guard->data=='}'||guard->data==']'||guard->data=='）'）{
s2[j]=guard->data;
j++;
}
rei=i;rej=j;intcount=0;
for（i=0,j=rej-1;i=0;）{
if（（s1[i]=='（'&&s2[j]=='）'）||（s1[i]=='['&&s2[j]==']'）||（s1[i]=='{'&&s2[j]=='}'））{
i++;j--;count++;
}
}
if（count==rei&&count==rej）cout<<"符号匹配!
"<elsecout<<"符号不匹配!
"<}
template
voidcheck（SLList&list）{
list.match（）;
}
升级会员 