大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > C语言/C++栈和队列

C语言/C++栈和队列

关键词:C语言C++队列  阅读(2133) 赞(16)

[摘要]本文是对C语言/C++栈和队列的讲解,对学习C++编程技术有所帮助,与大家分享。

栈的应用

①数制转换:

将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题,很容易通过"除B取余法"来解决。

【例】将十进制数13转化为二进制数。
解答:按除2取余法,得到的余数依次是1、0、1、1,则十进制数转化为二进制数为1101。
分析:由于最先得到的余数是转化结果的最低位,最后得到的余数是转化结果的最高位,因此很容易用栈来解决。

具体算法如下:

 #include <STACK>    //C++中使用栈要包含的头文件
 using namespace std;//这个也是要加的
 
 void conversion(int N,int B)
 {//假设N是非负的十进制整数,输出等值的B进制数
   
   stack<int> S;        //创建一个元素类型为int型的空栈
   while(N)
   {
     S.push(N%B); //将转换后的数值,从底位到高位开始入栈
     N=N/B;
   }
   while(!S.empty())//栈非空时退栈输出
   {
     printf("%d",S.top());    //打印栈顶元素
     S.pop();    //将栈顶元素出栈
   }
 }
 
 int main()
 {
   conversion(10,2);
 }

②表达式求值

表达式求值是程序设计语言编译中的一个最基本的问题。我们讨论一种简单直观的方法“算法优先级法”

算术四则运算的规则:

1、从左到右

2、先乘除后加减

3、先括号内,后括号外

相继出现的两个运算符优先级如下图:

【例】4 + 2*3 -10/5 每一步的计算顺序应该是:

4 + 2*3 -10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8

算法步骤:(我们假设表达式以字符‘#’结尾)

(1)首先,创建空运算符栈OPTR,将表达式起始符‘#’压入栈底,创建空操作数栈OPND

(2)依次读入表达式中的每个字符,若是操作数则进操作数栈,若是运算符则和运算符栈顶的运算符比较优先级后,做如下相应操作:

1.如果栈顶的运算符优先级较低,则把新的运算符压入OPTR;执行(2)

2.如果栈顶的运算符优先级较高,则将其 和 操作数栈的两个栈顶元素 退栈,计算3个元素组成的表达式的值,再压入操作数栈,然后继续判断;

3.如果栈顶的运算符优先级相等(除了#符外,只有‘(’和‘)’是相等的),则将‘(’出栈;执行(2)

(3)直到整个表达式求值完毕(即OPTR栈顶元素和当前读入的字符均为‘#’)

具体算法实现:
 #include <iostream>   
 #include <stack>//C++中使用栈要包含的头文件
 
 using namespace std;
 
 //符号数组   
 char symbol[7] = {'+', '-', '*', '/', '(', ')', '#'};  
 
 //栈内元素的优先级   
 int in[7] = {3, 3, 5, 5, 1, 6, 0};  
 
 //栈外元素的优先级   
 int out[7] = {2, 2, 4, 4, 6, 1, 0};  
 
 /* 
  * 通过符号字符获取它的数组下标 
  */  
 int get(char c)  
 {  
   switch(c)  
   {  
   case '+':  
     return 0;  
   case '-':  
     return 1;  
   case '*':  
     return 2;  
   case  '/':  
     return 3;  
   case '(':  
     return 4;  
   case ')':  
     return 5;  
   case '#':  
     return 6;  
   default:   
     return 6;  
   }  
 }  
   
 /* 
  * 比较栈内运算符c1和栈外运算符c2的优先级 
  */  
 char precede(char c1, char c2)  
 {  
   int i1 = get(c1);  
   int i2 = get(c2);  
   
   if(in[i1] > out[i2])  
   {  
     return '>';  
   }  
   else if(in[i1] < out[i2])  
   {  
     return '<';  
   }  
   else  
   {  
     return '=';  
   }  
 }  
   
 /* 
  * 计算基本表达式的值 
  */  
 int figure(int a, int theta, int b)  
 {  
   switch(theta)  
   {  
   case 0:  
     return a + b;  
   case 1:  
     return a - b;  
   case 2:  
     return a * b;  
   default:  
     return a / b;  
   }  
 }  
   
 /* 
  * 计算表达式的值 
  */  
 int EvaluateExpression(const char *exp)  
 {  
   stack<int> OPND; //操作数栈   
   stack<int> OPTR; //运算符栈   
   OPTR.push(get('#'));
 
   int flag = 1; //表示正负号 1,表示正 0,表示负   
   int a, theta, b;  
   
   if(!('+' == *exp || '-' == *exp || '(' == *exp || isdigit(*exp)))  
   {//如果不是以'+'、'-'、'('或者数字的其中一个开头,则表达式错误  
     cout << "表达式出错1" << endl;  
     return -1;  
   }  
   if('+' == *exp)  
   {   
     exp++;//指向下一个字符   
   }
   else if('-' == *exp)  
   {  
     flag = 0;  
     exp++;//指向下一个字符   
   }  
   
   int index = OPTR.top();                //获取运算符栈顶元素在数组的下标号
   while(*exp || symbol[index] != '#') //如果栈顶元素是'#'且当前元素为空结束计算 
   {  
     if(isdigit(*exp))  
     {//如果当前元素是数字,计算整个操作数的值,然后压入操作数栈
       int sum = 0; 
       while(isdigit(*exp))  
       {//计算操作数的值
         sum = sum * 10 + (*exp - '0');  
         exp++;  
       }
       if (!flag)    //如果是负数
       {
         sum = -sum;
       }
       OPND.push(sum);  
       flag = 1;  
     }  
     else  
     {//如果不是数字
       switch(precede(symbol[OPTR.top()], *exp))//比较栈顶运算符和当前运算符的优先级
       {  
       case '>' :  
         b = OPND.top();
         OPND.pop();
         a = OPND.top();  
         OPND.pop();  
         theta = OPTR.top();  
         OPTR.pop();  
         OPND.push(figure(a, theta, b));  
         break;  
       case '<' :  
         OPTR.push(get(*exp));  
         if(*exp)  
         {  
           exp++;  
         }  
         break;  
       case '=' :  
         OPTR.pop();  
         if(*exp)  
         {  
           exp++;  
         }  
         break;  
       }  
     }
     index = OPTR.top();
   }  
   return OPND.top();  
 }  
   
 int main()  
 {
   char c[50] = {0};
   cout << "请输入一个表达式: ";
   cin.getline(c,50);
   cout << EvaluateExpression(c) << endl;  
 
   return 0;  
 }

队列的应用

舞伴问题

1、问题叙述
假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同,则较长的那一队中未配对者,等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
2、问题分析
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性,可用队列作为算法的数据结构。
在算法中,假设男士和女士的记录存放在一个数组中作为输入,然后依次扫描该数组的各元素,并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后,依次将两队当前的队头元素出队来配成舞伴,直至某队列变空为止。此时,若某队仍有等待配对者,算法输出此队列中等待者的人数及排在队头的等待者的名字,他(或她)将是下一轮舞曲开始时第一个可获得舞伴的人。
3、具体算法及相关的类型定义
 #include <QUEUE><span style="background-color: inherit; font-family: 微软雅黑; ">//C++中使用队列要包含的头文件</span>
 
 
 using namespace std;
 typedef struct
 {
   char name[20];
   char sex; //性别,'F'表示女性,'M'表示男性
 }Person;
 
 void DancePartner(Person dancer[],int num)
 {//结构数组dancer中存放跳舞的男女,num是跳舞的人数。
 
   Person p;
   queue<Person> Mdancers,Fdancers;
 
   for(int i = 0; i < num; i++)
   {//依次将跳舞者依其性别入队
     p=dancer[i]; 
     if(p.sex=='F')
       Fdancers.push(p); //排入女队
     else
       Mdancers.push(p); //排入男队
   }
   printf("The dancing partners are: \n \n");
   while(!(Fdancers.empty()||Mdancers.empty()))
   {
     //依次输入男女舞伴名
     p=Fdancers.front();        //获取女队第一人
     Fdancers.pop();            //出队
     printf("%s ",p.name);    //打印出队女士名
 
     p=Mdancers.front();        //获取男队第一人
     Mdancers.pop();            //出队
     printf("%s\n",p.name);    //打印出队男士名
   }
   if(!Fdancers.empty())
   {//输出女士剩余人数及队头女士的名字
     printf("\n There are %d women waitin for the next round.\n",Fdancers.size());
     p=Fdancers.front(); //取队头
     printf("%s will be the first to get a partner. \n",p.name);
   }
   else if(!Mdancers.empty())
   {//输出男队剩余人数及队头者名字
     printf("\n There are%d men waiting for the next round.\n",Mdancers.size());
     p=Mdancers.front();
     printf("%s will be the first to get a partner.\n",p.name);
   }
   else
   {
     printf("There is not person in the queue!");
   }
 }//DancerPartners
 
 int main()
 {
   Person p[] = {{"A",'F'},{"B",'F'},{"C",'M'},{"D",'M'}};
   DancePartner(p,4);
 }


相关评论