数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--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。

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

 

代码如下:

      

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

 

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

 

数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++
  1 /////////////////////////////////////////////
  2 //SqQueue.h循环顺序队列数据结构C++定义
  3 //////////////////////////////////////////////
  4 #include "PreDefine.h"
  5 #include<assert.h>
  6 #ifndef SQQUEUE_H
  7 #define SQQUEUE_H
  8 template <typename ElemType>
  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     SqQueue<ElemType>operator = (SqQueue<ElemType>rightQ);
 28 
 29     //*************下面为系统自动调用的构造函数及析构函数声明********//
 30     //构造函数
 31     SqQueue(int size = 0);
 32     //析构函数
 33     ~SqQueue();
 34     //拷贝初始化构造函数
 35     SqQueue(const SqQueue<ElemType>& otherQ);
 36 
 37 protected:
 38     int rear;//队尾指针
 39     int front;//队头指针
 40     int queueSize;//队列大小
 41     ElemType *base;//队列基指针
 42 };
 43 //******************循环顺序队列的实现***********************
 44 //队列置空
 45 template<typename ElemType>
 46 void SqQueue<ElemType>::clear()
 47 {
 48     front = rear;
 49 }
 50 //判读队列是否为空
 51 template<typename ElemType>
 52 bool SqQueue<ElemType>::isEmpty()
 53 {
 54     return front == rear ? TRUE : FALSE;
 55 }
 56 //出队列
 57 template<typename ElemType>
 58 bool SqQueue<ElemType>::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 <typename ElemType>
 68 bool SqQueue<ElemType>::isFull()
 69 {
 70     return (rear + 1) % queueSize == front% queueSize ? TRUE : FALSE;
 71 }
 72 //进队列
 73 template<typename ElemType>
 74 bool SqQueue<ElemType>::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 <typename ElemType>
 84 bool SqQueue<ElemType>::getFront(ElemType& e)
 85 {
 86     if (isEmpty())
 87         return ERROR;
 88     e = base[front];
 89     return OK;
 90 }
 91 //求队列中元素的个数
 92 template <typename ElemType>
 93 int SqQueue<ElemType>::getLenght()
 94 {
 95     return (rear - front + queueSize) % queueSize;
 96 }
 97 //重载赋值运算符
 98 template<typename ElemType>
 99 SqQueue<ElemType> SqQueue<ElemType>::operator=(SqQueue<ElemType> 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 <typename ElemType>
128 SqQueue<ElemType> ::SqQueue(int size)
129 {
130     base = new ElemType[size];
131     assert(base != 0);
132     front = rear = 0;
133     queueSize = size;
134 }
135 //析构函数
136 template <typename ElemType>
137 SqQueue<ElemType>::~SqQueue()
138 {
139     delete[]base;
140 }
141 //赋值构造函数
142 template<typename ElemType>
143 SqQueue<ElemType> ::SqQueue(const SqQueue<ElemType>& 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
数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++
数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++
   MySportsManagement.h
1
#ifndef MYSPORTSMANAGEMENT_H 2 #define MYSPORTSMANAGEMENT_H 3 #include "PreDefine.h" 4 #include"SqQueue.h" 5 #include<assert.h> 6 #include<iostream> 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<int> 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<num) 198 { 199 cout << "" << j + 1 << "个参赛项目为:"; 200 in >> x; 201 if (x>-1 && x<game_num) 202 {//判断该项目是否已经输入 203 for (i = 0; i<j; ++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
数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++
数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++
 1 //main.cpp
 2 
 3 #include"MySportsManagement.h"
 4 #include<iostream>
 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 }
数据结构中队列的典型实际应用案例分析---------场地安排、比赛赛程安排等等--C++

运行结果为:

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

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

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

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

上一篇:微信内置浏览器中实现点击电话号码自动到拨号页面


下一篇:微信第三方平台开头篇--MVC代码(第三方获取ticket和公众号授权)