设计目的
《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：
了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
任务概述
设某田径比赛共有m个比赛项目，规定每个选手至多可参加三个项目，有n人报名参加比赛。设计比赛日程表，使得比赛能在尽可能短的时间内完成。要求：m个比赛项目及人员的报名情况表均事先存储在文件中，需要用数据时从文件中读取。
将参赛运动员的报名信息录入到文件里，并且用邻接矩阵输出，然后使用Welch-Powell算法对无向图进行着色，将同一运动员参赛的不同项目安排在不同时间内，减少冲突，最后，按照时间顺序输出运动项目。
本课程设计需要采用算法/函数：
1.无向图的着色问题，使用在离散数学中所学的Welch-Powell算法（即韦尔奇·鲍威尔算法）。
①将图的节点按照度数的递减顺序进行排列，相同度数的排列无顺序要求。
②对第一个点着色，并找到与之不相邻的、在序列中与它最近的点，着相同的颜色。依次类推，对序列中与以着色顶点不相邻的店按照此步骤依次进行。
③除去第一种着色的点，对尚未着色的点1采取步骤2的方法继续着色。
④直到所有顶点已着色，算法结束。
2.文件读写函数。
创建一个文件记录参赛运动员的报名信息，使用文件读取函数读取出来，存储到邻接矩阵中。
本设计采用的数据结构
采用二维数组的顺序存储结构，用邻接矩阵来存储图的相关数据。
结构体的定义：
(1)
int number;
int item; //度
int color; //颜色
}node;
其中:
1) number表示记录参赛运动员的报名情况
2) item表示一个参赛项目的度数
3) color表示该参赛项目的着色，不发生冲突的参赛项目是一个颜色。
(2)
struct Race{
char name[MAX];
};
其中：
name用来存储比赛项目的名字。
系统功能模块结构图及主要函数说明
系统功能模块结构图
该系统功能模块结构图如图4-1所示：
图 4 - 1系统功能模块图
系统流程图
该系统流程图有五个方面：输入数据，转化为邻接矩阵，着色，输出结果，具体系统流程图如图4-2所示：
图4 – 2 系统流程图
系统主要函数说明
1 系统全部函数功能介绍
1) int Draw(int k,int color); 对已经输入的数据使用Welch-Powell算法进行画图
2) void Start_Screen();打印开始界面
3) void Finish_Screen();打印结束界面
4) int Menu();打印菜单界面，并返回用户选择的菜单序号
5) void DataFromFile();接受用户从文件中导入数据
6) void DataFromKeyboard();接受用户从键盘输入数据
7) int cmp(const void *a,const void *b);比较结构体中的颜色，为后序颜色排序做准备
8) int PrintAdjMatrix();打印邻接矩阵
9) int ShortTime();打印安排的时间
2 主要函数说明
1) main()函数
main()函数是一个程序的主函数，其功能是根据用户选择菜单序号，调用相关函数，将用户输入的数据进行转换，并将时间安排好，输出相关数据。
main()函数的N-S图如图4-3所示：
图 4 - 3 main()函数N-S图
2) DataFromKeyboard()函数
DataFromKeyboard()函数的主要功能是：接受用户从键盘输入的数据，并根据用户输入的数据转换为邻接矩阵，并且根据创建的邻接矩阵调用draw()函数进行图的着色。
DataFromKeyboard()函数的N-S图如图4-4所示：
图 4 - 4 DataFromKeyboard()函数 N-S图
3) DataFromFile()函数
DataFromFile()函数的主要功能是：接受用户从文件中导入的数据，并根据用户导入的数据转换为邻接矩阵，并且根据创建的邻接矩阵调用draw()函数进行图的着色。
DataFromFile()函数的N-S图如图4-5所示：
图 4 - 4 DataFromFile()函数 N-S图
Draw()函数
Draw()函数的主要功能是，根据邻接矩阵，对不相邻的图进行着色，Draw()函数的N-S如图4-6所示
图 4 - 6 Draw()函数N-S图
程序运行数据及其结果
开始界面，菜单界面，结束界面展示：
本程序的开始界面如图5-1所示，菜单界面如图5-2所示，结束界面如图5-3所示。
图 5 - 1开始界面
图 5 - 2菜单界面
图 5 - 2结束界面
从键盘输入数据
输入的数据为：
6 5 1
2 6
4 3 6
2 4 7
9 2 6
3 6
输入数据的截图如图5-4所示，该数据的邻接矩阵如图5-5所示，该数据安排的时间如图5-6所示。
图 5 - 4输入数据
图 5 - 5该数据的邻接矩阵
图 5 - 6该数据安排的时间图
从文件录入数据
本程序需要用户按照格式进行文件编辑，并且文件名由用户自定义，然后输入到程序中，进行数据录入。
数据在文件中的格式如图5-7所示，将文件中的数据录入到程序中如图5-8所示，该数据的邻接矩阵图如图5-9所示，该数据所安排的时间如图5-10所示。
图 5 - 7数据在文件中的格式
图 5 - 8 将文件中的数据录入到程序中
图 5 -9该数据的邻接矩阵图
图 5 -10该数据所安排的时间
附录
程序代码：
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//******************************************自定义符号常量*******************************************
#define OVERFLOW -2 //内存溢出错误常量
#define ILLEGAL -1 //非法操作错误常量
#define OK 1 //表示操作正确的常量
#define ERROR 0 //表示操作错误的常量
#define MAX 20 //最大比赛项目数量
//******************************************需要的结构体********************************************
struct Node{
int number;
int item; //度
int color; //颜色
}node[MAX];
struct Race{
char name[MAX];
};
//******************************************自定义符号常量*******************************************
int a[MAX][MAX]={0};
int i , j , x;
FILE *filep;
FILE *f;
int b[3] , item , temp;
char c , ch;
bool flag = false;//判断用户是否输入数据
//******************************************自定义函数类*******************************************
int Draw(int k,int color);
int cmp(const void *a,const void *b);
void Start_Screen();
void Finish_Screen();
int Menu();
void DataFromFile();
void DataFromKeyboard();
int PrintAdjMatrix();
int ShortTime();
//******************************************主程序*************************************************
int main()
{
Start_Screen();
system("color 7");
while( true )
{
int num = Menu();
switch(num)
{
case 1:{//从键盘中输入数据
system("CLS");
DataFromKeyboard();
break;
}
case 2:{//从文件中导入数据
system("CLS");
DataFromFile();
break;
}
case 3:{//输出邻接矩阵
if( flag != true)
{
cout << "\t|| ||\n";
cout << "\t|| 您还未输入数据，请选择 1 或 2 ||\n";
cout << "\t|| ||\n";
cout << "\t =============================================================================\n\n\n\n";
cout << "正在为您跳转到主菜单，请稍等...";
Sleep(2500);
system("CLS");
continue;
}
system("CLS");
PrintAdjMatrix();
break;
}
case 4:{//输出安排的时间
if( flag != true)
{
cout << "\t|| ||\n";
cout << "\t|| 您还未输入数据，请选择 1 或 2 ||\n";
cout << "\t|| ||\n";
cout << "\t =============================================================================\n\n\n\n";
cout << "正在为您跳转到主菜单，请稍等...";
Sleep(2500);
system("CLS");
continue;
}
system("CLS");
ShortTime();
break;
}
case 5:{//退出程序
system("CLS");
Finish_Screen();
exit(0);
break;
default:
cout << "\n\t\t您输入的序号有误，请重新选择，按任意键继续...";
getchar();
getchar();
system("CLS");
break;
}
}
}
return 0;
}
//******************************************自定义函数*******************************************
void Start_Screen()
{
system("color 9");//将字体变为深蓝色
cout << "\n\n\n";
cout << "\t\t*************************************************"< cout << "\t\t****** ******"< cout << "\t\t****** ★★欢迎进入★★ ******"< cout << "\t\t****** ******"< cout << "\t\t****** 田径比赛的时间安排系统 ******"< cout << "\t\t****** ******"< cout << "\t\t*************************************************"< cout << "\n\n\n"; cout << "正在为您跳转到主菜单，请稍等..."; Sleep(3000); system("CLS"); } void Finish_Screen() { system("color 9"); cout<<"\n\n\n\n\n"; cout << "\t\t*************************************************"< cout << "\t\t****** ******"< cout << "\t\t****** ★★谢谢使用★★ ******"< cout << "\t\t****** ******"< cout << "\t\t****** 田径比赛的时间安排系统 ******"< cout << "\t\t****** ******"< cout << "\t\t*************************************************"< cout<<"\n\n\n\n\n"; } int Menu() { cout << endl; cout << "\t =============================================================================\n"; cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★田径比赛的时间安排系统★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| 本届田径比赛的项目种类 ||\n"; cout << "\t|| [1]110米跑步 [2]100米跑步 [3]跳高 ||\n"; cout << "\t|| [4]1000米长跑 [5]800米长跑 [6]110米跨栏 ||\n"; cout << "\t|| [7]100米跨栏 [8]跳远 [9]铅球 ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| 功能选项卡 ||\n"; cout << "\t|| ||\n"; cout << "\t|| 【1】--- 从键盘中输入数据 ||\n"; cout << "\t|| 【2】--- 从文件中导入数据 ||\n"; cout << "\t|| 【3】--- 输出邻接矩阵 ||\n"; cout << "\t|| 【4】--- 输出安排的时间 ||\n"; cout << "\t|| 【5】--- 退出程序 ||\n"; cout << "\t|| ||\n"; cout << "\t ==============================================================================\n"; cout << "\t\t\t请输入数字来选择对应的功能："; int num; cin >> num; return num; } void DataFromKeyboard() { cout << endl; cout << "\t =============================================================================\n"; cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★你选择的方法是键盘输入★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| 本届田径比赛的项目种类 ||\n"; cout << "\t|| [1]110米跑步 [2]100米跑步 [3]跳高 ||\n"; cout << "\t|| [4]1000米长跑 [5]800米长跑 [6]110米跨栏 ||\n"; cout << "\t|| [7]100米跨栏 [8]跳远 [9]铅球 ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| 接下来的每一行是该运动员所参加的所有运动项目序号（每人最多参加三项） ||\n"; cout << "\t|| ||\n"; cout << "\t|| 以 0 结束输入 ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; while(c != '0') { c = getchar(); if(c == '\n') { for(j = 0;j < i-1;j ++) a[b[j]][b[j+1]] = a[b[j+1]][b[j]] = 1; if(i==3) a[b[0]][b[2]] = a[b[2]][b[0]] = 1; i = 0; cout << "\t\t\t\t\t"; } if(c > '0'&& c <= '9') b[i++] = c - 48; if(c == '0') break; } for(i = 1;i < 10;i ++) { item = 0; for(j = 1;j < 10;j ++) { if(a[i][j]) item ++; } node[i].item = item; node[i].number = i; node[i].color=0; //0表示初始化无颜色 } cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★数据已成功录入★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t =============================================================================\n"; flag = true; //着色 Draw(1,1); //按颜色排序 qsort(node+1,6, sizeof(node[1]), cmp); cout << "\n\n\n"; cout << "按任意键继续..."; getchar(); getchar(); system("CLS"); } void DataFromFile() { cout << endl; cout << "\t =============================================================================\n"; cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★你选择的方法是文件导入★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| 请确保文件中的格式为 ||\n"; cout << "\t|| 接下来的每一行是该运动员所参加的所有运动项目序号（每人最多参加三项） ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| 是否继续（y或n） ||\n"; cout << "\t||============================================================================||\n"; char op;//记录用户选择 re://用户输入错误 cout << "\t\t\t\t\t请输入："; cin >> op; if(op == 'n' || op == 'N') { cout << "即将返回主菜单，请稍等..."; Sleep(3500); system("CLS"); return ; } else if(op == 'y' || op == 'Y') ; else { cout << "\t|| 输入错误重新输入 ||\n"; goto re; } char FileName[100]; //文件名 cout << "\t||============================================================================||\n"; cout << "\t\t\t\t 请输入文件名称："; cin >> FileName; cout << "\t||============================================================================||\n"; f = fopen(FileName,"r"); c = fgetc(f); //读取文件并输出 if((filep=fopen(FileName,"r"))==NULL) { cout << "\t\t\t打开文件错误！" << endl; cout << "\t\t\t即将返回主菜单..."; Sleep(3500); system("CLS"); return; } ch = fgetc(filep); while(ch!=EOF) { // putchar(ch); ch = fgetc(filep); } //把文件里的数据录入到矩阵里 i = 0; while(c != EOF) { if(c == '\n') { for(j = 0;j < i-1;j ++) a[b[j]][b[j+1]] = a[b[j+1]][b[j]] = 1; if(i==3) a[b[0]][b[2]] = a[b[2]][b[0]] = 1; i = 0; } if(c >= '0'&& c <= '9') b[i++] = c - 48; c = fgetc(f); } for(i = 1;i < 10;i ++) { item = 0; for(j = 1;j < 10;j ++) { if(a[i][j]) item ++; } node[i].item = item; node[i].number = i; node[i].color=0; //0表示初始化无颜色 } cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★数据已成功录入★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t =============================================================================\n"; flag = true; //着色 Draw(1,1); //按颜色排序 qsort(node+1,6, sizeof(node[1]), cmp); cout << "\n\n\n"; cout << "按任意键继续..."; getchar(); getchar(); system("CLS"); } int Draw(int k,int color) { bool key; //表示是否需要着色 node[k].color = color; //对于不相连的顶点着一样的颜色 for(j = 1;j < 10;j ++) { key = true; if(!a[k][j] && node[j].color == 0) { for(i = 1;i < 10;i ++) if(a[j][i] && node[i].color == color) { key = false; break; } if(key) node[j].color=color; } } for(i = 1;i < 10;i ++) if( !node[i].color ) { Draw( i , color+1); break; } return OK; } int cmp(const void *a,const void *b) { struct Node *c = (Node *)a; struct Node *d = (Node *)b; return c->color - d->color; } int PrintAdjMatrix() { cout << endl; cout << "\t =============================================================================\n"; cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★正在打印邻接矩阵★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; for(int i = 1;i < 10;i++){ printf("\t\t\t\t "); for(int j = 0;j < 10;j ++){ printf("%d ",a[i][j]); } printf("\n\n"); } cout << "\t|| ||\n"; cout << "\t =============================================================================\n"; cout << "\n\n\n"; cout << "按任意键继续..."; getchar(); getchar(); system("CLS"); } //输出比赛时间安排 int ShortTime() { cout << endl; cout << "\t =============================================================================\n"; cout << "\t|| ||\n"; cout << "\t|| ★★★★★★★本届田径比赛的安排如下★★★★★★★ ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; cout << "\t||============================================================================||\n"; cout << "\t|| ||\n"; cout << "\t|| [1]110米跑步 [2]100米跑步 [3]跳高 ||\n"; cout << "\t|| [4]1000米长跑 [5]800米长跑 [6]110米跨栏 ||\n"; cout << "\t|| [7]100米跨栏 [8]跳远 [9]铅球 ||\n"; cout << "\t|| ||\n"; cout << "\t||============================================================================||\n"; int day = 1; printf("\t\t\t第%d天\t%d",day,node[1].number); temp = node[1].color; for(i = 2;i<10;i++) //输出 { if(temp!=node[i].color) { printf("\n"); day ++; printf("\t\t\t第%d天",day); } printf("\t%d ",node[i].number); temp = node[i].color; } cout << "\n\t|| ||\n"; cout << "\t =============================================================================\n"; cout << "\n\n\n"; cout << "按任意键继续..."; getchar(); getchar(); system("CLS"); return OK; }