数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++

马上找工作了，最近又重新学起了数据结构，打算从现在开始，把学习过程中的心得体会和大家分享一下。当然这些内容会显得肤浅，但是希望会对新手有些帮助。大牛可以绕路咯。

好了，我们直奔主题，我们开始分析一下现实中的一中典型需求，以此作为开始：

实际问题：

一个运动会：有game_num个项目；

有anthelete_num名运动员；

每个运动员最多的参加max个项目；

问：怎么安排比赛才能使比赛组数最少（即如何安排各项比赛，既没有冲突，又使得比赛时间最短？）。

分析：

首先我们根据报名情况可以建立一个运动员参赛冲突关系矩阵collusion，是game_num*game_num的二维矩阵，元素0代表无冲突，1代表有冲突。例如，某个运动员报名的项目为（0,2,4）则对应的collusion[0][2]，collusion[0][4]，collusion[2][0]，collusion[4][0]，collusion[4][2]，collusion[2][4]的值为1.

然后我们借助一个队列记录还未分组的项目，一个数组***记录与该组冲突的比赛项目，其大小为game_num。

过程：初始时，把分组的组号初始化为0，并且把所有比赛项目进队列，表示所有项目都没有分组。

然后逐一出队列，进行分组，知道队列为空，分组完毕。

对于出队列的项目i，首先判断是否开始一轮新的比赛项目。一般出队列的项目号都大于先前出队列的项目号，如果小于，则说明开始一轮新的比赛项目，一个新的分组开始。此时，把分组的组号加1，数组***置0， 准备下面的同组成员判定。

（1）如果数组项目i对应的元素***[i]为0，表示当前组可以接受该项目，记录该项目i的分组号，且把该项目的比赛冲突信息叠加到数组***中，即把运动员参赛冲突关系矩阵collusion的第i+1行叠加到数组***上。理由是，当前组可以接受项目i,则与项目i冲突的比赛项目，也就是与该组冲突的项目，所以叠加记载到数组***中。

（2）如果数组***中项目i对应的元素***[i]不为0，表示当前组不可以接受该项目，要将其重新进队列，等待下一轮的判定。

实现：

在程序中我们会用到队列这种数据结构（循环队列），所以我们对队列进行定义，定义数据结构的代码中难免有些冗余，这是为了我对数据结构学习的更全面一些。为了代码重用性更强一些，用到了类模板。

简单介绍下循环队列：队头指针指向第一个元素，队尾指针指向最后一个元素的下一个位置，队头指针前移方式front = (front + 1) % queueSize，队尾指针前移方式：rear = (rear + 1) % queueSize。

定义完队列以后，我们便开始程序的其他实现。

代码如下：

PreDefine.h 1 //代码中一些常量定义

2 #ifndef PREDEFINE_H

3 #define PREDEFINE_H

4

5 #define TRUE 1

6 #define ERROR 0

7 #define OK 1

8 #define FALSE 0

9

10 #endif

1 /////////////////////////////////////////////

2 //SqQueue.h循环顺序队列数据结构Ｃ＋＋定义

3 //////////////////////////////////////////////

4 #include "PreDefine.h"

5 #include

6 #ifndef SQQUEUE_H

7 #define SQQUEUE_H

8 template

9 class SqQueue

10 {

11 public:

12 //把循环顺序队列置空

13 void clear();

14 //判断循环队列是否为空

15 bool isEmpty();

16 //出队列（删除循环顺序队列对头元素）

17 bool deQueue(ElemType& e);

18 //判断循环顺序队列是否满

19 bool isFull();

20 //进队列

21 bool enQueue(ElemType e);

22 //读循环顺序队列头的元素

23 bool getFront(ElemType& e);

24 //求循环顺序队列中元素的个数

25 int getLenght();

26 //重载赋值运算符的定义

27 SqQueueoperator = (SqQueuerightQ);

28

29 //*************下面为系统自动调用的构造函数及析构函数声明********//

30 //构造函数

31 SqQueue(int size = 0);

32 //析构函数

33 ~SqQueue();

34 //拷贝初始化构造函数

35 SqQueue(const SqQueue& otherQ);

36

37 protected:

38 int rear;//队尾指针

39 int front;//队头指针

40 int queueSize;//队列大小

41 ElemType *base;//队列基指针

42 };

43 //******************循环顺序队列的实现***********************

44 //队列置空

45 template

46 void SqQueue::clear()

47 {

48 front = rear;

49 }

50 //判读队列是否为空

51 template

52 bool SqQueue::isEmpty()

53 {

54 return front == rear ? TRUE : FALSE;

55 }

56 //出队列

57 template

58 bool SqQueue::deQueue(ElemType& e)

59 {

60 if (isEmpty())

61 return FALSE;

62 e = base[front];

63 front = (front + 1) % queueSize;//对头指针前移

64 return OK;

65 }

66 //判断队列是否满

67 template

68 bool SqQueue::isFull()

69 {

70 return (rear + 1) % queueSize == front% queueSize ? TRUE : FALSE;

71 }

72 //进队列

73 template

74 bool SqQueue::enQueue(ElemType e)

75 {

76 if (isFull())

77 return FALSE;

78 base[rear] = e;

79 rear = (rear + 1) % queueSize;//队尾指针前移

80 return OK;

81 }

82 //读队列的头元素

83 template

84 bool SqQueue::getFront(ElemType& e)

85 {

86 if (isEmpty())

87 return ERROR;

88 e = base[front];

89 return OK;

90 }

91 //求队列中元素的个数

92 template

93 int SqQueue::getLenght()

94 {

95 return (rear - front + queueSize) % queueSize;

96 }

97 //重载赋值运算符

98 template

99 SqQueue SqQueue::operator=(SqQueue rightQ)

100 {

101 if (this != &rightQ)//如果左右队列不一样

102 {

103 if (queueSize != rightQ.queueSize)//如果左右队列的大小不一样，则重新为左边队列分配空间

104 {

105 delete[] base;

106 base = new ElemType[rightQ.queueSize];

107 assert(base != 0);

108 queueSize = rightQ.queueSize;

109

110 }

111 //将右边的队列元素赋值到左边的队列中

112 front = rightQ.front;

113 rear = rightQ.rear;

114 for (int j = fron; j %queueSize != rear;)

115 {

116 base[j] = rightQ.base[j];

117 j = (j + 1) % queueSize;//指针前移

118

119 }

120 }

121 return *this;

122 }

123

124

125 //******************************下面为系统自动调用的构造函数和析构函数的实现***********

126 //构造函数

127 template

128 SqQueue ::SqQueue(int size)

129 {

130 base = new ElemType[size];

131 assert(base != 0);

132 front = rear = 0;

133 queueSize = size;

134 }

135 //析构函数

136 template

137 SqQueue::~SqQueue()

138 {

139 delete[]base;

140 }

141 //赋值构造函数

142 template

143 SqQueue ::SqQueue(const SqQueue& otherQ)

144 {

145 base = new ElemType[otherQ.queueSize];

146 aseert(base != 0);

147 queueSize = otherQ.queueSize;

148 front = otherQ.front;

149 rear = otherQ.rear;

150 for (int j = front; j%queueSize != rear;)

151 {

152 base[j] = otherQ.base[j];

153 j = (j + 1) % queueSize;

154

155 }

156 }

157 #endif

MySportsManagement.h 1 #ifndef MYSPORTSMANAGEMENT_H

2 #define MYSPORTSMANAGEMENT_H

3 #include "PreDefine.h"

4 #include"SqQueue.h"

5 #include

6 #include

7 using namespace std;

8 //********MySportsManagement.h定义***************

9 class MySportsManagement

10 {

11 public:

12 //安排比赛

13 void arrangeSports();

14 //显示项目冲突矩阵

15 void displayCollusion()const;

16

17 //**********下面为系统自动调用的构造函数、析构函数 和输入输出函数的声明

18 //构造函数

19 MySportsManagement(int a=9,int b=3,int c=7,int* d=NULL,int* e=NULL);

20 //析构函数

21 ~MySportsManagement();

22 //输入运动会项目及比赛情况

23 void read(istream& in);

24 //输出运动会项目以及比赛情况

25 void display(ostream& out)const;

26 private:

27 int game_num;//比赛项目数

28 int max;//每个运动员最多可以报的项目数

29 int anthelete_num;//运动员数量

30 int *collusion;//项目冲突矩阵

31 int *game_arrange;//比赛安排数组

32 };

33

34 ///***********MySportsManagement C++实现*************

35 //安排比赛的实现

36 void MySportsManagement::arrangeSports()

37 {

38 int pre = game_num;//预设前一个项目号

39 int group = 0;//存放当前分组的组号，初始化为0，表示还没有分组

40 int ****;//预存放某组项目的冲突关系

41 SqQueue Q;//预存放待分组项目的队列

42 if (!collusion)

43 {

44 cout << "没有冲突矩阵，比赛无法安排" << endl;

45 }

46 //队列Q被初始化为所有比赛项目的下标

47 for (int i = 0; i < game_num; i++)

48 {

49 Q.enQueue(i);

50 }

51 *** = new int[game_num];//申请冲突关系数组

52 assert(*** != 0);

53 //所有比赛项目逐一分组

54 while (!Q.isEmpty())

55 {

56 int i;

57 Q.deQueue(i);//一个项目出队列

58 //第一个项目代表新的一轮比赛项目

59 if (i <= pre)

60 {

61 ++group;//组号加1

62 //***全部元素赋值为0

63 for (int j = 0; j < game_num; j++)

64 ***[j] = 0;

65 }

66

67 if (***[i] == 0)

68 {

69 game_arrange[i] = group;//将第i个项目分配为第group组

70 //将collusion数组第i行的元素加到***数组上

71 for (int j = 0; j < game_num; ++j)

72 ***[j] += *(collusion + i*game_num + j);

73 }

74 //如果***数组中已经存在冲突项目，则将这个项目放回队列中，等待重新分配

75 else

76 {

77 Q.enQueue(i);

78 }

79

80 pre = i;//将前一个出队列项目号设置为刚刚出队列的项目号

81 }//while

82 }

83

84 //显示冲突矩阵

85 void MySportsManagement::displayCollusion()const

86 {

87 int i, j;

88 char no[5] = "[ i]";

89 //根据比赛项目数，显示项目冲突矩阵的列号

90 cout << " ";

91 for (i = 0; i < game_num; ++i)

92 {

93 if (i<9)

94 {

95 no[2] = i + '0';

96 }

97 else

98 {

99 no[1] = i / 10 + '0';

100 no[2] = i % 10 + '0';

101 }

102 cout.width(4);//每个比赛项目序号显示占4个字符

103 cout.fill(' ');//不足空格补齐

104 cout.setf(ios::right, ios::adjustfield);//靠右对其

105 cout << no;//输出列号

106 }

107 cout << endl;//换行

108 //逐行显示项目冲突矩阵

109 for (i = 0; i < game_num; ++i)

110 {

111 cout << " ";

112 if (i < 9)

113 no[2] = i + '0';

114 else

115 {

116 no[1] = i / 10 + '0';

117 no[2] = i % 10 + '0';

118 }

119 //每个比赛项目序号显示占4个字符，不足空格补齐，靠右对齐

120 cout.width(4);

121 cout.fill(' ');

122 cout.setf(ios::right, ios::adjustfield);

123 cout << no;

124 //显示项目冲突矩阵的元素

125 for (j = 0; j < game_num; ++j)

126 {

127 cout << " " << *(collusion + i*game_num + j) << " ";

128 }

129 cout << endl;

130 }

131 }

132

133 //***********下面为系统自动调用的构造函数、析构函数和输入输出函数**********

134 //构造函数

135 MySportsManagement::MySportsManagement(int a, int b, int c, int* d, int* e)

136 {

137 game_num = a;//比赛项目

138 max = b;//每个运动员最多允许参加的比赛项目数

139 anthelete_num = c;//运动员人数

140 //申请项目冲突矩阵的存储空间

141 collusion = new int[game_num * game_num]();//冲突数组的大小为game_num的平方个,并初始化为0

142 assert(collusion != 0);

143

144 //比赛安排

145 game_arrange = new int[game_num]();//申请比赛安排的存储空间，并初始化为0

146 assert(game_arrange != 0);

147 }

148 //析构函数

149 MySportsManagement::~MySportsManagement()

150 {

151 delete[] collusion;

152 delete[] game_arrange;

153 }

154 //输入运动会项目及运动员参赛情况

155 void MySportsManagement::read(istream& in)

156 {

157 int i, j, k;//预控制循环的变量

158 int x;//预存放某个运动员的参赛项目

159 int num;//预存放某个运动员的参赛数目

160 int temp[10];//预存放某个运动员的所有参赛项目

161

162 cout << " 请输入比赛项目数：";

163 in >> game_num;

164

165 cout << "请输入每个运动员最多允许参加的比赛项目：";

166 in >> max;

167

168 cout << "请输入运动员人数：";

169 in >> anthelete_num;

170

171

172 collusion = new int[game_num*game_num]();//申请冲突矩阵的存储空间，并初始化为0

173 assert(collusion != 0);

174

175 cout << "\n 请输入每个运动员参赛情况：" << endl << endl;

176

177 for (k = 1; k <= anthelete_num; ++k)

178 {

179 cout << " 请输入第" << k << "个运动员报名参赛情况：" << endl;

180 while (1)

181 {

182 cout << " 输入第" << k << "个运动员参赛数目：";

183 in >> num;

184 if (num>0 && num <= max)

185 {

186 break;

187 }

188 else

189 {

190 cout << " 每个运动员最多允许参加的比赛项目为：" << max << endl;

191 }

192 }

193

194 //输入第i个运动员所有参赛项目（不能有重复的参赛项目）

195

196 j = 0;

197 while (j

198 {

199 cout << " 第" << j + 1 << "个参赛项目为：";

200 in >> x;

201 if (x>-1 && x

202 {//判断该项目是否已经输入

203 for (i = 0; i

204 {

205 if (temp[i] == x)

206 {

207 break;

208 }

209 }

210 if (i == j)

211 temp[j++] = x;

212 else

213 {

214 cout << " 该比赛项目已经输入" << endl;

215 }

216 }

217 else

218 {

219 cout << " 参赛项目应该在0到" << game_num - 1;

220 cout << "之间，请重新输入！" << endl;

221 }

222 }//while

223 //根据每个运动员的参赛项目temp数组，填写项目冲突矩阵

224 for (int i = 0; i < num; ++i)

225 for (j = i + 1; j < num; ++j)

226 {

227 //对称矩阵

228 *(collusion + temp[i] * game_num + temp[j]) = 1;

229 *(collusion + temp[j] * game_num + temp[i]) = 1;

230 }

231 cout << endl;

232 }//for

233 //显示冲突矩阵

234 displayCollusion();

235 }

236 //重载输入运算符的定义

237 istream& operator>>(istream& in, MySportsManagement& sQ)

238 {

239 sQ.read(in);

240 return in;

241 }

242 //输出运动会项目及比赛情况

243 void MySportsManagement::display(ostream& out)const

244 {

245 char no[5] = "[ i]";//比赛项目序号的字符表示

246

247 if (!game_num)

248 {

249 out << " 没有任何运动会的信息！" << endl;

250 return;

251 }

252

253 out << " 比赛项目数：" << game_num << endl;

254

255 out << " 每个运动员最多允许参加的比赛项目数：" << max << endl;

256

257 if (!anthelete_num)

258 {//如果运动员的数目为0，则提示还没有运动员报名，返回

259 out << " 还没有运动员报名！" << endl;

260 return;

261 }

262 out << " 项目冲突矩阵：";

263

264 displayCollusion();

265 if (!game_arrange)

266 {//如果比赛安排为空，则提示各项比赛分组还没有安排，返回

267 out << " 各项比赛分组还没有安排！" << endl;

268 return;

269 }

270 out << "\n 各项比赛分组安排如下：" << endl;

271 out << " ";

272 //为显示各项比赛的分组安排，事先显示一行比赛项目号

273 for (int i = 0; i < game_num; ++i)

274 {

275 if (i < 9)

276 no[2] = i + '0';

277 else

278 {

279 no[1] = i / 10 + '0';

280 no[2] = i % 10 + '0';

281 }

282 //每个比赛项目号显示占4个字符，不足以空格补齐，靠右对齐

283 out.width(4);

284 out.fill(' ');

285 out.setf(ios::right, ios::adjustfield);

286 out << no;

287 }

288 out << endl;

289 out << " ";

290 for (int i = 0; i < game_num; ++i)

291 {

292 out.width(4);

293 out.fill(' ');

294 out.setf(ios::right, ios::adjustfield);

295 out << *(game_arrange + i);

296

297 }

298 out << endl;//换行

299 }

300 //重载输出运算符的定义

301 ostream& operator<<(ostream& out, MySportsManagement& sQ)

302 {

303 sQ.display(out);

304 return out;

305 }

306

307 #endif

1 //main.cpp

2

3 #include"MySportsManagement.h"

4 #include

5 using namespace std;

6 int main()

7 {

8 cout << "***********************开始安排比赛*********************" << endl << endl;

9 MySportsManagement MSM;

10 cin >> MSM;

11 MSM.arrangeSports();

12 cout << MSM;

13 return 0;

14 }

运行结果为：

上述过程难免有错误，大家批评指正。

另附：链式队列的实现代码

#ifndef LINKQUEUE_H

#define LINKQUEUE_H

#include

//非循环链队数据结构Ｃ＋＋类声明

template

class LinkQueue

{

private:

class LinkNode

{

public:

ElemType data;

LinkNode* next;

};

typedef LinkNode* NodePointer;

public:

//循环链队置空

void clear();

//出队列

bool deQueue(ElemType& e);

//进队列

bool enQueue(ElemType e);

//读非循环练队列头结点的数据域

bool getFront(ElemType& e);

//判断链队是否为空

bool isEmpty();

//求链队中结点的个数

int getLength();

//重载赋值运算符的定义

LinkQueue operator= (LinkQueue rightQ);

//****************下面为系统自动调用的构造函数以及析构函数声明***************

//构造函数

LinkQueue();

//析构函数

~LinkQueue();

//初始化构造函数

LinkQueue(const LinkQueue& otherQ);

protected:

NodePointer rear;

NodePointer front;

};

//**********非循环链队的定义**********************

//把链队置空

template

void LinkQueue::clear()

{

NodePointer q;

NodePointer p = front;

while (p)

{

q = p;

p = p->next;

delete q;

}

front = rear = 0;

}

//出队列

template

bool LinkQueue::deQueue(ElemType& e)

{

if (!front)

{

return -1;

}

NodePointer s = front;

e = s->data;

front = front->next;

delete s;

if (!front)

{//rear还指向原来的内存，所以需要置空

rear = 0

}

return 0;

}

//进队列

template

bool LinkQueue::enQueue(ElemType e)

{

NodePointer s;

s = new(LinkNode);

assert(s != 0);

s->data = e;

s ->next = 0;

if (!front)

{

front = rear = s;

}

else

{

rear->next = s;

rear = s;

}

}

//读队列头结点的数据域

template

bool LinkQueue::getFront(ElemType& e)

{

if (!front)

{

return -1;

}

e = front->data;

front = front->next;

}

//判断队列是否为空

template

bool LinkQueue::isEmpty()

{

return (!front ? 0 : -1);

}

//求队列的元素个数

template

int LinkQueue::getLength()

{

int lenghth = 0;

NodePointer p = front;

while (p)

{

++lenght;

p = p->next;

}

return lenghth;

}

//重载赋值运算符

template

LinkQueue LinkQueue::operator=(LinkQueue rightQ)

{

NodePointer s;

NodePointer rp = rightQ.front;

if (this!=&right)

{

clear();

while (rp)

{

s = new(LinkNode);

assert(s != 0);

s->data = rp->data;

s->next=NULL:

if (!fron)

{

front = rear = s;

}

else

{

rear->next = s;

rear = s;

}

}

}

return *this;

}

//***********下面为系统自动调用的构造函数以及析构函数的定义**************

//构造函数

template

LinkQueue::LinkQueue()

{

front=rear=NULL:

}

//析构函数

template

LinkQueue::~LinkQueue()

{

clear();

}

//拷贝初始化构造函数

template

LinkQueue::LinkQueue(const LinkQueue& otherQ)

{

NodePointer s;

NodePointer op = otherQ.front;

rear = front = NULL;

while (op)

{

s = new(LinkNode);

assert(s != 0);

s->data = op->data;

s->next = NULL;

if (!fron)

{

front = rear = s;

}

else

{

rear->next = s;

rear = s;

}

op = op->next;

}

}

#endif