解栈和队列的应用代码,C代码库,德仔网

代码语言
代码分类
【C】解栈和队列的应用
作者:Dezai.CN / 发布于2011/8/1/ 849
(1)用栈实现数制转换(2)输入一个算术表达式,其中含有（、[ 两种括号，判断括号是否匹配
<div><span style="color: rgb(0,0,0)">#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">iostream</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">using</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">namespace</span><span style="color: rgb(0,0,0)"> std;

</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> SElemType int</span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> Stack_Init_Size 20</span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> Stack_Increment 10</span><span style="color: rgb(0,0,0)">

typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)">{
SElemType </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">elem;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> top;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> stacksize;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> incrementsize;
}SqStack;

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> InitStack(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">初始化栈</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">s.elem</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> SElemType[Stack_Init_Size];
s.top</span><span style="color: rgb(0,0,0)">=-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
s.stacksize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Stack_Init_Size;
s.incrementsize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Stack_Increment;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> StackIncrement(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">增加栈长度</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">SElemType </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">a;
a</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> SElemType[s.stacksize</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">s.incrementsize];
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">s.top;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
a[i]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">s.elem[i];
delete []s.elem;
s.elem</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">a;
s.stacksize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">s.stacksize</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">s.incrementsize;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Push_stack(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s,SElemType x){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">入栈</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(s.top</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">(s.incrementsize</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">))
StackIncrement(s);
s.elem[</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">s.top]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">x;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Get_num(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">a){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">输入十进制数</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请输入十进制数</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">a;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> change(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> x){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">十进制转化为二进制，并用栈储存</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)"> (x</span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">){
Push_stack(s,x</span><span style="color: rgb(0,0,0)">%</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">);
x</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">x</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">;
}
Push_stack(s,x);
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Output(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">十进制数以二进制形式输出</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">转为二进制:</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> a</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">s.top;a</span><span style="color: rgb(0,0,0)">>=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;a</span><span style="color: rgb(0,0,0)">--</span><span style="color: rgb(0,0,0)">)
cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">s.elem[a];
cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main (){
SqStack ss;
InitStack(ss);
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> s;
Get_num(s);
change(ss,s);
Output(ss);
}
#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">iostream</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">using</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">namespace</span><span style="color: rgb(0,0,0)"> std;

</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> SElemType char </span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> Stack_Init_Size 20</span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> Stack_Increment 10</span><span style="color: rgb(0,0,0)">

typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)">{ 
SElemType </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">elem;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> top;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> stacksize;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> incrementsize;
}SqStack;

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> InitStack(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">用于初始化栈</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">s.elem</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> SElemType[Stack_Init_Size];
s.top</span><span style="color: rgb(0,0,0)">=-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
s.stacksize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Stack_Init_Size;
s.incrementsize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Stack_Increment;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> StackIncrement(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">用于增加栈长</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">SElemType </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">a;
a</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> SElemType[s.stacksize</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">s.incrementsize];
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">s.top;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
a[i]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">s.elem[i];
delete []s.elem;
s.elem</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">a;
s.stacksize</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">s.stacksize</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">s.incrementsize;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Push_stack(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s,SElemType x){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">入栈</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(s.top</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">(s.incrementsize</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">))
StackIncrement(s);
s.elem[</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">s.top]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">x;
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Pop_Stack(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">出栈</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">s.top</span><span style="color: rgb(0,0,0)">--</span><span style="color: rgb(0,0,0)">;
}
 
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Get_C(</span><span style="color: rgb(0,0,255)">char</span><span style="color: rgb(0,0,0)"> x[]){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">获取表达式，用数组存放</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请输入表达式(以等号结束):</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">){
cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">x[i];
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">=</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
</span><span style="color: rgb(0,0,255)">break</span><span style="color: rgb(0,0,0)">;
}
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> match(SqStack </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">s,</span><span style="color: rgb(0,0,255)">char</span><span style="color: rgb(0,0,0)"> x[]){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">进行括号的匹配判断</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> n</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">; </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">辅助量，用于判断括号的顺序性是否为真</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">){
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">(</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
Push_stack(s,</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">a</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">);
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">[</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
 Push_stack(s,</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">b</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">); 
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">)</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">){ 
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(s.elem[s.top]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">a</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
Pop_Stack(s); 
</span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
{n</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;</span><span style="color: rgb(0,0,255)">break</span><span style="color: rgb(0,0,0)">;}
}
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">]</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">){
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(s.elem[s.top]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">b</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
Pop_Stack(s); 
</span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
{n</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;</span><span style="color: rgb(0,0,255)">break</span><span style="color: rgb(0,0,0)">;}
}
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(x[i]</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">=</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
</span><span style="color: rgb(0,0,255)">break</span><span style="color: rgb(0,0,0)">;
}
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">((n</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">)</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">(s.top</span><span style="color: rgb(0,0,0)">==-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">)) </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">若判断括号的顺序性为真，在判断是否一一匹配</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">括号相匹配</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
</span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
cerr</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">括号不匹配</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl; 
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main (){
SqStack ss;
</span><span style="color: rgb(0,0,255)">char</span><span style="color: rgb(0,0,0)"> x[</span><span style="color: rgb(128,0,128)">10</span><span style="color: rgb(0,0,0)">];
InitStack(ss);
Get_C(x);
match(ss,x);
}</span></div>
试试其它关键字
　栈和队列　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)