数据布局进修(C++)之栈和行列
副标题#e#
栈和行列是操纵受限的线性表，仿佛每本讲数据布局的数都是这么说的。有些书凭据这个思路给出了界说和实现；可是很遗憾，本文没有这样做，所以，有些书中的做法是反复建树，这或者可以用不是一小我私家写的这样的来由来开脱。
顺序暗示的栈和行列，必需预先分派空间，而且空间巨细受限，利用起来限制较量多。并且，由于限定存取位置，顺序暗示的随机存取的利益就没有了，所以，链式布局应该是首选。
栈的界说和实现
#ifndef Stack_H
#define Stack_H
#include "List.h"
template <class Type> class Stack : List<Type>//栈类界说
{
public:
void Push(Type value)
{
Insert(value);
}
Type Pop()
{
Type p = *GetNext();
RemoveAfter();
return p;
}
Type GetTop()
{
return *GetNext();
}
List<Type> ::MakeEmpty;
List<Type> ::IsEmpty;
};
#endif
行列的界说和实现
#ifndef Queue_H
#define Queue_H
#include "List.h"
template <class Type> class Queue : List<Type>//行列界说
{
public:
void EnQueue(const Type &value)
{
LastInsert(value);
}
Type DeQueue()
{
Type p = *GetNext();
RemoveAfter();
IsEmpty();
return p;
}
Type GetFront()
{
return *GetNext();
}
List<Type> ::MakeEmpty;
List<Type> ::IsEmpty;
};
#endif
测试措施
#p#副标题#e#
#ifndef StackTest_H
#define StackTest_H
#include "Stack.h"
void StackTest_int()
{
cout << endl << "整型栈测试" << endl;
cout << endl << "结构一个空栈" << endl;
Stack<int> a;
cout << "将1～20入栈，然后再出栈" << endl;
for (int i = 1; i <= 20; i++) a.Push(i);
while (!a.IsEmpty()) cout << a.Pop() << ' ';
cout << endl;
}
#endif
#ifndef QueueTest_H
#define QueueTest_H
#include "Queue.h"
void QueueTest_int()
{
cout << endl << "整型行列测试" << endl;
cout << endl << "结构一个空行列" << endl;
Queue<int> a;
cout << "将1～20入队，然后再出队" << endl;
for (int i = 1; i <= 20; i++) a.EnQueue(i);
while (!a.IsEmpty()) cout << a.DeQueue() << ' ';
cout << endl;
}
#endif
没什么好说的，你可以清楚的看到，在单链表的基本上，栈和行列的实现是如此的简朴。
栈应用
栈的应用很遍及，栈的最大的用途是办理回溯问题，这也包括了消解递归；而当你用栈办理回溯问题成了习惯的时候，你就很少想到用递归了，好比迷宫求解。别的，人的习惯也是先入为主的，好比树的遍历，从学的那天开始，就是递归算法，固然书上也教了用栈实现的要领，但应用的时候，你首先想到的照旧递归；虽然了，假如语言自己不支持递归（如BASIC），那栈就是独一的选择了——仿佛此刻的高级语言都是支持递归的。
如下是表达式类的界说和实现，表达式可以是中缀暗示也可以是后缀暗示，用头节点数据域里的type区分，这里有一点说明的是，由于单链表的赋值函数，我本来写的时候没有复制头节点的内容，所以，要是在两个表达式之间赋值，头节点里存的信息就丢了。你可以改写单链表的赋值函数来办理这个隐患，可能你基础不不在两个表达式之间赋值也行。
#ifndef Expression_H
#define Expression_H
#include "List.h"
#include "Stack.h"
#define INFIX 0
#define POSTFIX 1
#define OPND 4
#define OPTR 8
template <class Type> class ExpNode
{
public:
int type;
union { Type opnd; char optr;};
ExpNode() : type(INFIX), optr('=') {}
ExpNode(Type opnd) : type(OPND), opnd(opnd) {}
ExpNode(char optr) : type(OPTR), optr(optr) {}
};
template <class Type> class Expression : List<ExpNode<Type> >
{
public:
void Input()
{
MakeEmpty(); Get()->type =INFIX;
cout << endl << "输入表达式，以＝竣事输入" << endl;
Type opnd; char optr = ' ';
while (optr != '=')
{
cin >> opnd;
if (opnd != 0)
{
ExpNode<Type> newopnd(opnd);
LastInsert(newopnd);
}
cin >> optr;
ExpNode<Type> newoptr(optr);
LastInsert(newoptr);
}
}
void Print()
{
First();
cout << endl;
for (ExpNode<Type> *p = Next(); p != NULL; p = Next() )
{
switch (p->type)
{
case OPND:
cout << p->opnd; break;
case OPTR:
cout << p->optr; break;
default: break;
}
cout << ' ';
}
cout << endl;
}
Expression & Postfix() //将中缀表达式转变为后缀表达式
{
First();
if (Get()->type == POSTFIX) return *this;
Stack<char> s; s.Push('=');
Expression temp;
ExpNode<Type> *p = Next();
while (p != NULL)
{
switch (p->type)
{
case OPND:
temp.LastInsert(*p); p = Next(); break;
case OPTR:
while (isp(s.GetTop()) > icp(p->optr) )
{
ExpNode<Type> newoptr(s.Pop());
temp.LastInsert(newoptr);
}
if (isp(s.GetTop()) == icp(p->optr) )
{
s.Pop(); p =Next(); break;
}
s.Push(p->optr); p = Next(); break;
default: break;
}
}
*this = temp;
pGetFirst()->data.type = POSTFIX;
return *this;
}
Type Calculate()
{
Expression temp = *this;
if (pGetFirst()->data.type != POSTFIX) temp.Postfix();
Stack<Type> s; Type left, right;
for (ExpNode<Type> *p = temp.Next(); p != NULL; p = temp.Next())
{
switch (p->type)
{
case OPND:
s.Push(p->opnd); break;
case OPTR:
right = s.Pop(); left = s.Pop();
switch (p->optr)
{
case '+': s.Push(left + right); break;
case '-': s.Push(left - right); break;
case '*': s.Push(left * right); break;
case '/': if (right != 0) s.Push(left/right); else return 0; break;
// case '%': if (right != 0) s.Push(left%right); else return 0; break;
// case '^': s.Push(Power(left, right)); break;
default: break;
}
default: break;
}
}
return s.Pop();
}
private:
int isp(char optr)
{
switch (optr)
{
case '=': return 0;
case '(': return 1;
case '^': return 7;
case '*': return 5;
case '/': return 5;
case '%': return 5;
case '+': return 3;
case '-': return 3;
case ')': return 8;
default: return 0;
}
}
int icp(char optr)
{
switch (optr)
{
case '=': return 0;
case '(': return 8;
case '^': return 6;
case '*': return 4;
case '/': return 4;
case '%': return 4;
case '+': return 2;
case '-': return 2;
case ')': return 1;
default: return 0;
}
}
};
#endif
几点说明
#p#分页标题#e#
1、表达式用单链表储存，你可以看到这个链表中既有操纵数又有操纵符，假如你看过我的《如安在一个链表中链入差异范例的工具》，这里的要领也是对那篇文章的增补。
2、输入表达式时，会将本来的内容清空，而且必需凭据中缀暗示输入。假如你细看一下中缀表达式，你就会发明，除了括号，表达式的布局是“操纵数”、“操纵符”、“操纵数”、……“操纵符（＝）”，为了统一这个纪律，同时也为了使输入函数简朴一点，划定括号必需这样输入“0（”、“）0”；这样一来，“0”就不能作为操纵数呈此刻表达式中了。因为我没有在输入函数中增加容错的语句，所以一旦输错了，那措施就“死”了。
#p#分页标题#e#
3、表达式求值的进程是，先酿成后缀暗示，然后用后缀暗示求值。因为原书讲授的是这两个算法，而且用这两个算法就能完成中缀表达式的求值，所以我就没写中缀表达式的直接求值算法。详细算法说明拜见原书，我就不空话了。
4、Calculate()注释掉的两行，“％”是因为只对整型表达式正当，“^”的Power()函数没有完成。
5、isp()，icp()的返回值，原书说的不细，我来多说两句。‘＝’（表达式开始和竣事符号）的栈内栈外优先级都是最低。‘（’栈外最高，栈内次最低。‘）’栈外次最低，不进栈。‘^’栈内次最高，栈外比栈内低。‘×÷％’栈内比‘^’栈外低，栈外比栈内低。‘＋－’栈内比‘×’栈外低，栈外比栈内低。这样，综合起来，就有9个优先级，于是就得出了书上的谁人表。
行列应用
我看的两本教科书（《数据布局（C语言版）》尚有这本黄皮书）都是以这个讲授行列应用的，并且都是银行营业模仿（太没新意了）。细较量，这两本书模仿的银行营业的方法照旧差异的。1997版的《数据布局（C语言版）》的银行照旧老式的营业模式（究竟是1997年的事了），此刻的许多处所照旧这种营业模式——几个窗口同时列队。这种方法其实不太公道，常常会呈现先来的还没有厥后的先治理业务（经常前面一小我私家磨磨蹭蹭，此外队越来越短，让你恨不得把前面那人干掉）。1999版的这本黄皮书的银行改成了一种挂牌的营业方法，每个来到的顾主发一个号码，假如哪个柜台空闲了，就叫号码最靠前的顾主来治理业务；假如同时几个柜台空闲，就凭据一种法例来抉择这几个柜台叫号的顺序（最简朴的是按柜台号码顺序）。这样，就能担保顾主凭据先来后到的顺序接管处事——因为各人排在一个队里。这样的营业模式我在北京的西直门工商银行见过，应该说这是较量公道的一种营业模式。不外，在本文中最重要的是，这样的营业模式较量好模仿（一个行列总比N个行列好操纵）。
原书的这部门太丢脸了，我看的晕晕的，我也不知道凭据原书的要领能不能做出来，因为我没看懂（旁白：靠，你小子这样还来现眼）。我凭据实际环境模仿，实现如下：
#ifndef Simulation_H
#define Simulation_H
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
class Teller
{
public:
int totalCustomerCount;
int totalServiceTime;
int finishServiceTime;
Teller() :totalCustomerCount(0), totalServiceTime(0),
finishServiceTime(0) {}
};
//#define PRINTPROCESS
class Simulation
{
public:
Simulation()
{
cout << endl << "输入模仿参数" << endl;
cout << "柜台数量："; cin >> tellerNum;
cout << "营业时间："; cin >> simuTime;
cout << "两个顾主来到的最小隔断时间："; cin >> arrivalLow;
cout << "两个顾主来到的最大隔断时间："; cin >> arrivalHigh;
cout << "柜台处事最短时间："; cin >> serviceLow;
cout << "柜台处事最长时间："; cin >> serviceHigh;
arrivalRange = arrivalHigh - arrivalLow + 1;
serviceRange = serviceHigh - serviceLow + 1;
srand((unsigned)time(NULL));
}
Simulation(int tellerNum, int simuTime, int arrivalLow, int arrivalHigh, int serviceLow, int serviceHigh)
: tellerNum(tellerNum), simuTime(simuTime), arrivalLow(arrivalLow), arrivalHigh(arrivalHigh),
serviceLow(serviceLow), serviceHigh(serviceHigh),
arrivalRange(arrivalHigh - arrivalLow + 1), serviceRange(serviceHigh - serviceLow + 1)
{ srand((unsigned)time(NULL)); }
void Initialize()
{
curTime = nextTime = 0;
customerNum = customerTime = 0;
for (int i = 1; i <= tellerNum; i++)
{
tellers[i].totalCustomerCount = 0;
tellers[i].totalServiceTime = 0;
tellers[i].finishServiceTime = 0;
}
customer.MakeEmpty();
}
void Run()
{
Initialize();
NextArrived();
#ifdef PRINTPROCESS
cout << endl;
cout << "tellerID";
for (int k = 1; k <= tellerNum; k++) cout << "\tTELLER " << k;
cout << endl;
#endif
for (curTime = 0; curTime <= simuTime; curTime++)
{
if (curTime >= nextTime)
{
CustomerArrived();
NextArrived();
}
#ifdef PRINTPROCESS
cout << "Time: " << curTime << " ";
#endif
for (int i = 1; i <= tellerNum; i++)
{
if (tellers[i].finishServiceTime < curTime) tellers[i].finishServiceTime = curTime;
if (tellers[i].finishServiceTime == curTime && !customer.IsEmpty())
{
int t = NextService();
#ifdef PRINTPROCESS
cout << ' ' << customerNum + 1 << '(' << customer.GetFront() << ',' << t << ')';
#endif
CustomerDeparture();
tellers[i].totalCustomerCount++;
tellers[i].totalServiceTime += t;
tellers[i].finishServiceTime += t;
}
#ifdef PRINTPROCESS
else cout << " ";
#endif
}
#ifdef PRINTPROCESS
cout << endl;
#endif
}
PrintResult();
}
void PtintSimuPara()
{
cout << endl << "模仿参数" << endl;
cout << "柜台数量： " << tellerNum << " 营业时间：" << simuTime << endl;
cout << "两个顾主来到的最小隔断时间：" << arrivalLow << endl;
cout << "两个顾主来到的最大隔断时间：" << arrivalHigh << endl;;
cout << "柜台处事最短时间：" << serviceLow << endl;
cout << "柜台处事最长时间：" << serviceHigh << endl;
}
void PrintResult()
{
int tSN = 0;
long tST = 0;
cout << endl;
cout << "－－－－－－－－－－－－－模仿功效－－－－－－－－－－－－－－－－－－－";
cout << endl << "tellerID ServiceNum ServiceTime AverageTime" << endl;
for (int i = 1; i <= tellerNum; i++)
{
cout << "TELLER " << i;
cout << ' ' << tellers[i].totalCustomerCount << " "; tSN += tellers[i].totalCustomerCount;
cout << ' ' << tellers[i].totalServiceTime << " "; tST += (long)tellers[i].totalServiceTime;
cout << ' ';
if (tellers[i].totalCustomerCount)
cout << (float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
else cout << 0;
cout << " " << endl;
}
cout << "TOTAL " << tSN << " " << tST << " ";
if (tSN) cout << (float)tST/(float)tSN; else cout << 0;
cout << " " << endl;
cout << "Customer Number: " << customerNum << " no Service: " << customerNum - tSN << endl;
cout << "Customer WaitTime: " << customerTime << " AvgWaitTime: ";
if (tSN) cout << (float)customerTime/(float)tSN; else cout << 0;
cout << endl;
}
private:
int tellerNum;
int simuTime;
int curTime, nextTime;
int customerNum;
long customerTime;
int arrivalLow, arrivalHigh, arrivalRange;
int serviceLow, serviceHigh, serviceRange;
Teller tellers[21];
Queue<int> customer;
void NextArrived()
{
nextTime += arrivalLow + rand() % arrivalRange;
}
int NextService()
{
return serviceLow + rand() % serviceRange;
}
void CustomerArrived()
{
customerNum++;
customer.EnQueue(nextTime);
}
void CustomerDeparture()
{
customerTime += (long)curTime - (long)customer.DeQueue();
}
};
#endif
几点说明
#p#分页标题#e#
1、Run()的进程是这样的：curTime是时钟，从开始营业计时，自然流逝到遏制营业。当顾主到的事件产生时（顾主到时间便是当前时间，小于鉴定是因为个体时候顾主同时达到——输入arrivalLow＝0的环境，而在同一时间，只给一个顾主发号码），给这个顾主发号码（用顾主到时间标示这个顾主，入队，来到顾主数增1）。当柜台处事完毕时（柜台处事完时间便是当前时间），该柜台处事人数增1，处事时间累加，顾主分开事件产生，下一个顾主到该柜台。因为柜台开始都是空闲的，所以实际代码和这个有点进出。最后，遏制营业的时候，遏制发号码，还在接管处事的顾主继承随处事完，其他还在列队的就分伙了。
#p#分页标题#e#
2、模仿功效别离是：各个柜台的处事人数、处事时间、平均处事时间，总的处事人数、处事时间、平均处事时间，来的顾主总数、没被处事的数目（来的太晚了）、接管处事顾主总期待时间、平均期待时间。
3、这个算法效率是较量低的，实际上可以不消行列完成这个模仿（用顾主到时间敦促当前时钟，柜台直接通告处事完成时间），但这样就和实际环境有很大不同了——出纳员没等瞥见人就知道什么时候完？固然功效是一样的，可是领略起来很莫名其妙，尤其是作为解说目标讲授的时候。虽然了，实际中为了提高模仿效率，本文的这个算法是不值得倡导的。
4、注释掉的#define PRINTPROCESS，去掉注释符后，在运行模仿的时候，能打印出每个时刻柜台的处工作况（第几个顾主，顾主达到时间，接管处事时间），但只限4个柜台以下，多了的话屏幕就满了（名目就乱了）。
这是数据布局中第一个实际应用的例子，并且也有现实意义。你可以看出各个柜台在差异的业务密度下的事情强度（要么给哪个柜台出纳员发奖金，要么轮换柜台），各类环境下顾主的期待时间（人都是轮到本身就不着急了），尚有各类环境下设立几个柜台公道（很少的空闲时间，很短的期待时间，险些为零的未处事人数）。譬喻这样：
for (int i = 1; i < 16; i++)
{
Simulation a(i,240,1,4,8,15);
a.Run();
}
你模仿一下就会得出，在不太忙碌的银行，4～5个柜台是符合的——此刻的银行大部门都是这样的。
