• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

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

实际问题：

一个运动会：有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.

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

 

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

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

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

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

（2）如果数组clash中项目i对应的元素clash[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<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
   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 *clash;//预存放某组项目的冲突关系
 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     clash = new int[game_num];//申请冲突关系数组
 52     assert(clash != 0);
 53     //所有比赛项目逐一分组
 54     while (!Q.isEmpty())
 55     {
 56         int i;
 57         Q.deQueue(i);//一个项目出队列
 58         //第一个项目代表新的一轮比赛项目
 59         if (i <= pre)
 60         {
 61             ++group;//组号加1
 62             //clash全部元素赋值为0
 63             for (int j = 0; j < game_num; j++)
 64                 clash[j] = 0;
 65         }
 66 
 67         if (clash[i] == 0)
 68         {
 69             game_arrange[i] = group;//将第i个项目分配为第group组
 70             //将collusion数组第i行的元素加到clash数组上
 71             for (int j = 0; j < game_num; ++j)
 72                 clash[j] += *(collusion + i*game_num + j);
 73         }
 74         //如果clash数组中已经存在冲突项目，则将这个项目放回队列中，等待重新分配
 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 << "     第 
                       
                    
                    
 
                      





鲜花




握手




雷人




路过




鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
C#上传附件，以及下载实现发布时间：2022-07-13
下一篇：
errorC2338:NoQ_OBJECTintheclasswiththesignal(NodeCreator.cpp)发布时间：2022-07-13
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap