这个学期的数据结构真心有点难……不过程序写出来后还是挺有成就感的。
贴两个程序上来吧，分别是简易计算器和银行叫号系统。简易计算器重点考察对栈的应用（中缀表达式转后缀表达式、后缀表达式计算），银行叫号系统考察对队列的应用。
银行叫号系统的user的多态有点小问题。
源代码在codeblocks下编译通过。
简易计算器
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstring>
#include<cstdlib>
using namespace std;
int getPrio(char x){ //优先级判断函数
if(x == '*' || x == '/' ||x == '(')
return 1;
else
return 0;
}
template<class T> //顺序栈类
class Stack{
public:
void Clear();
bool Push(const T item);
bool Pop(T &item);
bool Top(T &item);
};
template<class T>
class ArrayStack:public Stack<T>{
private:
int maxSize;
int top;
T *st;
public:
ArrayStack(int Size){
maxSize = Size;
top = -1;
st = new T[maxSize];
}
~ArrayStack(){
delete []st;
}
void Clear(){
top = -1;
}
bool Push(const T item){
if(top == maxSize - 1){
cout<<"栈满溢出"<<endl;
return false;
}
else{
st[++top] = item;
return true;
}
}
bool Pop(T &item){
if(top == -1){
cout<<"栈为空，不能进行删除操作"<<endl;
return false;
}
else{
item = st[top--];
return true;
}
}
bool Top(T &item){
if(top == -1){
cout<<"栈为空，不能读取栈顶元素"<<endl;
return false;
}
else{
item = st[top];
return true;
}
}
void print(){ //调试时为了方便可打印栈
for(int i = 0; i <= top; i++){
cout<<st[i]<<' ';
}
cout<<endl;
}
};
class Calculator{ //计算器类
public:
string infixToSuffix(string inFix){ //中缀表达式转后缀表达式函数
ArrayStack<char> temp(100); //此栈用于存储运算符，之后简称运算符栈
temp.Push('#'); //先Push#作为栈底方便处理
string sufFix; //此字符串用于存储后缀表达式
char tmp; //一个临时变量，方便处理比较等情况
for(int i = 0; i < inFix.size(); i++){ //扫描中缀表达式
if(47 < inFix[i] && inFix[i] < 58 || inFix[i] == 46){ //处理数字，直接加入后缀表达式
sufFix += inFix[i];
}
else{
tmp = sufFix[sufFix.size()-1]; //处理符号
if(inFix[i] == '('){ //处理开括号，直接入运算符栈
temp.Push('(');
}
else if(inFix[i] == ')'){ //处理闭括号
temp.Top(tmp);
while(tmp != '('){ //将栈中元素依次弹出，直到遇到第一个开括号为止
temp.Pop(tmp); //出运算符栈
sufFix += ' '; //加空格方便阅读
sufFix += tmp; //加入后缀表达式
temp.Top(tmp); //获取新的栈顶元素
}
temp.Pop(tmp); //将开括号弹出
}
else{ //处理运算符
temp.Top(tmp);
while(tmp!= '#' && tmp != '(' && getPrio(inFix[i]) <= getPrio(tmp)){ //当栈非空 && 栈顶不是开括号
temp.Pop(tmp); //同上
sufFix += ' ';
sufFix += tmp;
temp.Top(tmp);
}
temp.Push(inFix[i]);
}
sufFix += ' '; //加空格方便阅读
}
//cout<<inFix[i]<<endl;
//temp.print(); //方便调试
//cout<<endl<<sufFix<<endl; //方便调试
}
temp.Top(tmp);
while(tmp != '#'){ //将栈中剩余运算符依次弹出，压入后缀表达式栈
temp.Pop(tmp); //同上
sufFix += ' ';
sufFix += tmp;
temp.Top(tmp);
}
cout<<sufFix<<endl;
return sufFix;
}
double calSufFix(string sufFix){
ArrayStack<double> temp(100); //计算时所用的栈
double num,x,y; //为方便计算而设的变量
char sufToChar[100];
strcpy(sufToChar,sufFix.c_str());
char *charStr = strtok(sufToChar," "); //根据空格分割字符串
while(charStr)
{
//cout<<"charStr的值："<<charStr<<endl;
if(atof(charStr)){ //字符串转数字函数
temp.Push(atof(charStr));
}
else{ //扫描到运算符后进行计算
temp.Pop(x);
temp.Pop(y);
switch(charStr[0]){
case '+':num = y + x;break;
case '-':num = y - x;break;
case '*':num = y * x;break;
case '/':num = y / x;break;
default:break;
}
temp.Push(num);
}
charStr = strtok(NULL," ");
}
temp.Pop(num);
return num;
}
};
int main(){
Calculator c1;
string str;
cin>>str;
cout<<c1.calSufFix(c1.infixToSuffix(str));
return 0;
}
银行叫号系统
#include<iostream>
#include<typeinfo>
#include <ctime>
#include <cstdlib>
#include<typeinfo>
#include<stdlib.h>
using namespace std;
template<class T>
class LinkNode{
public:
T data; //保存节点元素的内容
LinkNode<T> *next; //指向后继节点的指针
LinkNode(const T info = NULL, LinkNode<T> *nextVal = NULL){
data = info;
next = nextVal;
}
~LinkNode(){
}
};
template<class T>
class Queue{
public:
void Clear();
bool EnQueue(const T item);
bool DeQueue(T & item);
bool IsEmpty();
bool IsFull();
bool GetFront(T & item);
};
template<class T>
class LinkQueue:public Queue<T>{
public:
int Size;
LinkNode<T> * Front;
LinkNode<T> * Rear;
LinkQueue(){
Size = 0;
Front = Rear = NULL;
}
~LinkQueue(){
Clear();
}
void Clear(){
while(Front != NULL){
Rear = Front;
Front = Front->next;
delete Rear;
}
Rear = NULL;
Size = 0;
}
bool EnQueue(const T item){
if(Rear == NULL){
Front = Rear = new LinkNode<T>(item,NULL);
}
else{
Rear->next = new LinkNode<T>(item,NULL);
Rear = Rear->next;
}
Size++;
return true;
}
bool DeQueue(T & item){
LinkNode<T> * temp;
if(Size == 0){
//cout<<"队列为空"<<endl;
return false;
}
item = Front->data;
temp = Front;
Front = Front->next;
delete temp;
if(Front == NULL){
Rear = NULL;
}
Size--;
return true;
}
bool GetFront(T & item){
if(Size == 0){
cout<<"队列为空"<<endl;
return false;
}
item = Front->data;
return true;
}
};
class User{
public:
int id;
int ArriveTime;
int ServeTime;
string type;
static int counter;
User(){
ServeTime = (rand()%9)/3 + 1;
}
void getServed(){
cout<<type<<id<<"正在接受服务"<<endl;
}
};
int User::counter = 0;
class NormalUser:public User{
public:
NormalUser(){
type = "普通用户";
id = counter++;
}
void getServed(){
cout<<"普通用户"<<id<<"正在接受服务"<<endl;
}
};
class VIPUser:public User{
public:
VIPUser(){
type = "VIP用户";
id = counter++;
}
void getServed(){
cout<<"VIP用户"<<id<<"正在接受服务"<<endl;
}
};
class OfficalUser:public User{
public:
OfficalUser(){
type = "对公用户";
id = counter++;
}
void getServed(){
cout<<"VIP用户"<<id<<"正在接受服务"<<endl;
}
};
class BankWindow{
public:
bool isBusy;
int id;
User client;
static int counter;
BankWindow(){
isBusy = false;
id = counter++;
}
void HandleUser();
};
int BankWindow::counter = 0;
class NormalBankWindow:public BankWindow{
public:
void HandleUser(){
cout<<"普通窗口"<<id<<"叫号,"<<client.type<<client.id<<endl;
}
};
class VIPBankWindow:public BankWindow{
public:
void HandleUser(){
cout<<"VIP窗口"<<id<<"叫号,"<<client.type<<client.id<<endl;
}
};
class OfficalBankWindow:public BankWindow{
public:
void HandleUser(){
cout<<"对公窗口"<<id<<"叫号,"<<client.type<<client.id<<endl;
}
};
class Simulater{
public:
LinkQueue<User> NormalUserQueue;
LinkQueue<User> VIPUserQueue;
LinkQueue<User> OfficalUserQueue;
NormalBankWindow *NormalList;
VIPBankWindow *VIPList;
OfficalBankWindow *OfficalList;
int NormalNum;
int VIPNum;
int OfficalNum;
Simulater(int NormalNum,int VIPNum,int OfficalNum){
this->NormalNum = NormalNum;
this->VIPNum = VIPNum;
this->OfficalNum = OfficalNum;
NormalList = new NormalBankWindow[NormalNum];
VIPList = new VIPBankWindow[VIPNum];
OfficalList = new OfficalBankWindow[OfficalNum];
}
~Simulater(){
delete NormalList;
delete VIPList;
delete OfficalList;
}
void simulateCustomerEnter(){
srand(unsigned(time(0)));
switch((rand()%9)){
case 0:case 1:break;
case 2:case 3:case 4:case 5:
NormalUserQueue.EnQueue(NormalUser());break;
case 6:case 7:case 8:case 9:
NormalUserQueue.EnQueue(NormalUser());
NormalUserQueue.EnQueue(NormalUser());break;
}
if((rand()%9)>6){
VIPUserQueue.EnQueue(VIPUser());
}
if((rand()%9)>6){
OfficalUserQueue.EnQueue(OfficalUser());
}
cout<<"现有"<<NormalUserQueue.Size<<"个普通用户，"<<VIPUserQueue.Size<<"个VIP用户,"<<OfficalUserQueue.Size<<"个对公用户等候"<<endl;
}
void simulateCallCustomer(time_t now_time){ //依次循环普通窗口、VIP窗口、对公窗口
for(int i = 0; i < NormalNum; i++){
if(NormalList[i].isBusy){
cout<<"普通窗口"<<i<<"正在为";
NormalList[i].client.getServed(); //接受服务
if(now_time - NormalList[i].client.ArriveTime >= NormalList[i].client.ServeTime){
NormalList[i].isBusy = false;
}
}
else if(NormalUserQueue.DeQueue(NormalList[i].client)){
NormalList[i].client.ArriveTime = now_time;
NormalList[i].isBusy = true;
NormalList[i].HandleUser();
}
else{
cout<<"普通窗口"<<i<<"为空"<<endl;
}
}
for(int i = 0; i < VIPNum; i++){
if(VIPList[i].isBusy){
cout<<"VIP窗口"<<i+NormalNum<<"正在为";
VIPList[i].client.getServed();
if(now_time - VIPList[i].client.ArriveTime >= VIPList[i].client.ServeTime){
VIPList[i].isBusy = false;
}
}
else if(VIPUserQueue.DeQueue(VIPList[i].client)){
VIPList[i].client.ArriveTime = now_time;
VIPList[i].isBusy = true;
VIPList[i].HandleUser();
}
else if(NormalUserQueue.DeQueue(VIPList[i].client)){
VIPList[i].client.ArriveTime = now_time;
VIPList[i].isBusy = true;
VIPList[i].HandleUser();
}
else{
cout<<"VIP窗口"<<i<<"为空"<<endl;
}
}
for(int i = 0; i < OfficalNum; i++){
if(OfficalList[i].isBusy){
cout<<"对公窗口"<<i+NormalNum+VIPNum<<"正在为";
OfficalList[i].client.getServed();
if(now_time - OfficalList[i].client.ArriveTime >= OfficalList[i].client.ServeTime){
OfficalList[i].isBusy = false;
}
}
else if(OfficalUserQueue.DeQueue(OfficalList[i].client)){
OfficalList[i].client.ArriveTime = now_time;
OfficalList[i].isBusy = true;
OfficalList[i].HandleUser();
}
else if(NormalUserQueue.DeQueue(OfficalList[i].client)){
OfficalList[i].client.ArriveTime = now_time;
OfficalList[i].isBusy = true;
OfficalList[i].HandleUser();
}
else{
cout<<"对公窗口"<<i<<"为空"<<endl;
}
}
}
void Simulate(){ //模拟函数，负责调用前两个函数和计时
time_t start_time = unsigned(time(0));
time_t now_time = unsigned(time(0));
while(now_time - start_time < 20){
simulateCustomerEnter();
simulateCallCustomer(now_time);
_sleep((1-((time(0))-now_time))*1000);
now_time = unsigned(time(0));
cout<<now_time - start_time<<endl;
}
cout<<"模拟时间结束"<<endl;
}
};
int main(){
Simulater bank(3,1,1);
bank.Simulate();
return 0;
}