数据结构课设 预习"/>
数据结构课设 预习
1 参赛队伍管理
能够管理各参赛队的基本信息(包含参赛队编号,参赛作品名称,参赛学校,赛事类别,参赛者,指导老师),赛事类别共11项(参见大赛官网jsjds.blcu.edu);包括增加、删除、修改参赛队伍的信息。
-
- 问题分析
这个问题主要涉及对文件的操作。
管理信息可以通过:搜索——操作——保存 的方式完成。
1.2算法设计
增加:略
删除,修改:将文本文件逐行存入二位数组;在数组中搜索关键词,定位需操作的字符串;进行操作;存入文件
1.3 算法实现
增加:
void add() {
fstream file("team.txt", ios_base::in | ios_base::out);
if (!file) { cout << "文件打开错误"; exit(0); }
cout << "输入要添加的行" << endl;
char add_string[200];
cin.get(add_string, 200);
while (add_string[0] != '*') {
int i = 0;
for (; i < 200; i++) {
if (add_string[i] == NULL)
{
add_string[i] = '\n';
break;
}
}
file.seekp(0, ios::end);
file.write(add_string, i + 1);
file.close();
cout << "输入要添加的行" << endl;
}
}
删除:
void searchOP() {
fstream file("team_ordered.txt", ios_base::in | ios_base::out);
if (!file) { cout << "文件打开错误"; exit(0); }
char copy[500][200] = {'\0'};
for (int i = 0;i<500; i++) {
file.getline(copy[i], 200);
}
file.close();
cout << "输入查找内容(*为终止)";
cin >> x;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], x)) {
cout << copy[i]<<endl;
cout << "0.返回 1.下一条 2.删除" << endl;
int a;
cin >> a;
if (a == 0)break;
else if (a == 1)continue;
else if (a == 2) {
for (int j = i; j < 499; j++)
for(int k=0;k<200;k++)
copy[j][k] = copy[j + 1][k];
}
}
}
fstream outfile("team1.txt", ios_base::in | ios_base::out|ios_base::trunc);
int count0;
for (int i = 0; i < 500; i++) {
count0 = 0;
for (int j = 0; j < 200; j++) {
if (copy[i][j] == '\n')
count0 = j;
break;
}
outfile.seekp(0, ios::end);
outfile << copy[i] << endl;
}
outfile.close();
}
替换:即为先删再添
2 基于二叉排序树的查找
实现基于二叉排序树的查找。根据提示输入参赛队编号,若查找成功,输出该赛事类别对应的基本信息(参赛作品名称、参赛学校、赛事类别、参赛者和指导老师信息),同时,输出查找成功时的平均查找长度ASL;否则,输出“查找失败!”。请输出ASL的计算表达式和结果值。
2.1 问题分析
基于二叉排序树的查找:
将数据放入二叉树的过程略
平均长度可以在元素放入二叉树的过程中就进行计算
2.2算法设计
创建根节点,自此以后,新节点编号若小于根节点编号,则放入左子树;反之,放入右子树。在此过程中,新节点每与旧节点比较一次,“sum”便+1,新节点成功放入后,sum再+1 。当节点放置完成后,sum/节点总数 便是平均查找长度。
2.3算法设计
#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;
struct binary {
int id= 2021009290;
char a[200]="出错";
binary* l=nullptr;
binary* r=nullptr;
};
void order(binary* head) {
double sum = 398;
binary* p;
p = head;
int x = 0;
char target[200];
fstream file("D:\\Program\\MatchDesign\\fileOP\\fileOP\\team.txt", ios_base::in | ios_base::out);
if (!file) { cout << "error"; exit(0); }
file.getline(target, 200);
file.getline(target, 200);
for (int i = 0; i < 200; i++)
p->a[i] = target[i];
for (int j = 0; j < 397; j++) {
x = 0;
file.getline(target, 200);
for (int i = 0; i < 10; i++) {
x = x + (int(target[i]) - '0') * int(pow(10, 9 - i));
}
while (true)
{
if (x < p->id) {
if (p->l == nullptr) {
sum++;
p->l = new binary;
p->l->id = x;
for (int i = 0; i < 200; i++)
p->l->a[i] = target[i];
p = head;
break;
}
else { p = p->l; sum++; }
}
else {
if (p->r == nullptr) {
sum++;
p->r = new binary;
p->r->id = x;
for (int i = 0; i < 200; i++)
p->r->a[i] = target[i];
p = head;
break;
}
else { p = p->r; sum++; }
}
}
}
cout << "ASL:" << sum / 398 << endl;
}
int search(binary* head) {
binary* p;
p = head;
int x;
while (1) {
p = head;
cout << "输入要查找的内容" << endl;
cin >> x;
while (1) {
if (x < p->id) {
if (p->l == nullptr) { cout << "不存在" << endl;break; }
p = p->l;
}
else if (x > p->id) {
if (p->r == nullptr) { cout << "不存在" << endl; break; };
p = p->r;
}
else
{
for (int i = 0; p->a[i] != '\0'; i++) {
cout << p->a[i];
}
cout << endl << endl;
break;
}
}
}
}
int main() {
binary a;
binary* head=&a;
order(head);
search(head);
}
3 参赛团队查询
(3)能够提供按参赛学校查询参赛团队,根据提示输入参赛学校名称,若查找成功,输出该学校参赛的所有团队的基本信息,输出的参赛团队需有序输出(按参赛队编号)。(排序算法可从选择排序、插入排序、希尔排序、归并排序、堆排序中任意选择,并为选择算法的原因做出说明。)
3.1 问题分析
可先进行排序,覆盖文件或保存到新文件,对该文件进行关键词查询。
3.2算法设计
查询部分的功能在1中已完成,排序功能先对原文件进行直接插入排序,保存到新文件,1中访问新文件即可。
3.3 算法实现
void InsertSort()
{
fstream file("team.txt", ios_base::in | ios_base::out);
if (!file) { cout << "文件打开错误"; exit(0); }
char copy[500][200] = { '\0' };
for (int i = 0; i < 500; i++) {
file.getline(copy[i], 200);
}
int x[500];
for (int j = 0; j < 500; j++) {
x[j] = 0;
for (int i = 0; i < 10; i++) {
x[j] = x[j] + (int(copy[j][i]) - '0') * int(pow(10, 9 - i));
}
}
file.close();
int temp;
char ctemp[200];
int j;
for (int i = 1; i < 500; i++)
{
if (x[i] < x[i - 1])
{
temp = x[i];
for (int m = 0; m < 200; m++)
ctemp[m] = copy[i][m];
for (j = i - 1; j >= 0 && temp < x[j]; j--)
{
x[j + 1] = x[j];
for (int m = 0; m < 200; m++)
copy[j+1][m] = copy[j][m];
}
x[j + 1] = temp;
for (int m = 0; m < 200; m++)
copy[j+1][m]=ctemp[m] ;
}
}
fstream outfile("team_ordered.txt", ios_base::in | ios_base::out | ios_base::trunc);
int count0;
for (int i = 0; i < 500; i++) {
count0 = 0;
for (int j = 0; j < 200; j++) {
if (copy[i][j] == '\n')
count0 = j;
break;
}
outfile.seekp(0, ios::end);
outfile << copy[i] << endl;
}
outfile.close();
}
4 决赛叫号模拟
为省赛现场设计一个决赛叫号系统。所有参赛队按赛事组织文件中的赛事类别分到9个决赛室,决赛室按顺序叫号,被叫号参赛队进场,比赛结束后,下一参赛队才能进赛场。请模拟决赛叫号系统,演示省赛现场各决赛室的参赛队进场情况。(模拟时,各参赛队进场比赛时间可设为0.5秒)
4.1 问题分析
这是一个较为简单的问题,暂不加入时间变量,以方便进行调试观察。
4.2算法设计
先将文件存入字符串数组,当选择排练室时,按相应的关键词搜索等候队伍;接收到入场操作后,等候队伍中的第一个删除。
4.3 算法实现
void CallNum() {
fstream file("D:\\Program\\MatchDesign\\fileOP\\fileOP\\team.txt", ios_base::in | ios_base::out);
if (!file) { cout << "文件打开错误"; exit(0); }
char copy[500][200] = { '\0' };
for (int i = 0; i < 500; i++) {
file.getline(copy[i], 200);
}
while (1) {
cout << "查看决赛室情况:" << endl;
cout << "1.大数据应用\n2.信息可视化设计\n3.人工智能应用\n4.软件应用与开发\n5.物联网应用\n6.数媒动漫与短片\n7.数媒静态设计\n8.数媒游戏与交互设计\n9.微课与教学辅助" << endl;
int x;
cin >> x;
if (x == 1) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "大数据实践"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "大数据实践"))
{
copy[i][0] = '\0';
break;
}
}
}
}
}
else if (x == 2) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "信息图形设计") || strstr(copy[i], "MG动画") || strstr(copy[i], "交互信息设计") || strstr(copy[i], "数据可视化"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "信息图形设计") || strstr(copy[i], "MG动画") || strstr(copy[i], "交互信息设计") || strstr(copy[i], "数据可视化"))
{
copy[i][0] = '\0';
break;
}
}
}
}
}
else if (x == 3) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "人工智能实践赛"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "人工智能实践赛"))
{
copy[i][0] = '\0';
break;
}
}
}
}
}
else if (x == 4) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "Web应用与开发") || strstr(copy[i], "管理信息系统") || strstr(copy[i], "算法设计与应用") || strstr(copy[i], "移动应用开发(非游戏类)"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "Web应用与开发") || strstr(copy[i], "管理信息系统") || strstr(copy[i], "算法设计与应用") || strstr(copy[i], "移动应用开发(非游戏类)"))
{
copy[i][0] = '\0'; break;
}
}
}
}
}
else if (x == 5) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "医药卫生") || strstr(copy[i], "数字生活") || strstr(copy[i], "运动健身") || strstr(copy[i], "城市管理"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "医药卫生") || strstr(copy[i], "数字生活") || strstr(copy[i], "运动健身") || strstr(copy[i], "城市管理"))
{
copy[i][0] = '\0'; break;
}
}
}
}
}
else if (x == 6) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "动画") || strstr(copy[i], "纪录片") || strstr(copy[i], "数字短片") || strstr(copy[i], "微电影") || strstr(copy[i], "新媒体漫画"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "动画") || strstr(copy[i], "纪录片") || strstr(copy[i], "数字短片") || strstr(copy[i], "微电影") || strstr(copy[i], "新媒体漫画"))
{
copy[i][0] = '\0'; break;
}
}
}
}
}
else if (x == 7) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "产品设计") || strstr(copy[i], "环境设计") || strstr(copy[i], "平面设计"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "产品设计") || strstr(copy[i], "环境设计") || strstr(copy[i], "平面设计"))
{
copy[i][0] = '\0'; break;
}
}
}
}
}
else if (x == 8) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "交互媒体设计") || strstr(copy[i], "游戏设计"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "交互媒体设计") || strstr(copy[i], "游戏设计"))
{
copy[i][0] = '\0'; break;
}
}
}
}
}
else if (x == 0) {
{
cout << "等待中:" << endl;
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "汉语言文学") || strstr(copy[i], "计算机基础与应用类课程微课") || strstr(copy[i], "虚拟实验平台") || strstr(copy[i], "中、小学数学或自然科学课程微课"))
{
cout << copy[i] << endl;
}
}
cout << endl << "进行操作:1.允许下一组进场 2.返回" << endl;
int y;
cin >> y;
if (y == 1) {
for (int i = 0; i < 500; i++) {
if (strstr(copy[i], "汉语言文学") || strstr(copy[i], "计算机基础与应用类课程微课") || strstr(copy[i], "虚拟实验平台") || strstr(copy[i], "中、小学数学或自然科学课程微课"))
{
copy[i][0] = '\0'; break;
}}}}}}}
5 校园导游咨询
赛事系统为参赛者提供赛地的校园导游程序。为参赛者提供各种路径导航的查询服务。以我校长山校区提供比赛场地为例,(请为参赛者提供不少于10个目标地的导航。可为参赛者提供校园地图中任意目标地(建筑物)相关信息的查询;提供图中任意目标地(建筑物)的问路查询,即查询任意两个目的地(建筑物)之间的一条最短的简单路径。
5.1 问题分析
这显然是一个图论问题,而且校园内道路一般是双向通行的,所以这是一个无向图。对于图的存储结构而言,图中各个景点的存储结构有邻接表和邻接矩阵两种存储结构,考虑到顶点个数少于50个,所以邻接表和邻接矩阵的复杂度相同。本题中选择使用邻接矩阵来表示图。
任务中要求求解出图中景点的问路查询,即为给定两个源点,求解出两个顶点之间的最短路径。根据数据结构课程所学知识,有多种经典算法可以解决最短路径问题,包括Dijkstra算法,Floyd-Warshell算法,Bellman-Ford算法和深度优先遍历。不同是算法有不同的算法复杂度,考虑到校园中道路没有负权边,即算法均可解决最短路径问题。
其中Dijkstra算法求的是单源最短路径:即从一个结点出发到其它所有结点的最短路径,算法的时间复杂度为O(n2),但题目要求任意两个结点的最短路径,所以还是要在外层增加一个循环,以求得多源最短路径。
而Floyd算法求的是多源最短路径:即从任意结点出发到其它所有结点的最短路径,算法的时间复杂度为O(n3),它可以一次性求得所有结点间的最短路径,且算法思想简单,便于理解。所以我们这一项目采用Floyd算法来求解最短路径。
5.2算法设计
使用二维数组存储无向图邻接矩阵与路径记录,采用floyd算法求最短路径。
若要求路程则访问修改后的邻接矩阵,若要求路径则访问路径记录数组。
5.3 算法实现
#include<iostream>
using namespace std;
int target[10][10] = { {0,150,10000, 400 ,10000, 10000,10000,10000,10000,10000 },
{150,0 , 250, 10000, 10000,10000,10000,10000,10000,10000},
{10000 ,250, 0, 50, 300, 10000, 10000, 10000 ,10000, 10000},
{400 ,10000, 50, 0, 10000, 10000, 10000, 10000, 10000, 10000} ,
{10000, 10000, 300, 10000, 0, 200, 400, 10000, 10000, 10000},
{10000,10000,10000,10000,200 ,0, 480, 280, 230, 10000} ,
{10000 ,10000, 10000, 10000, 400, 480, 0, 420, 10000, 10000},
{10000, 10000, 10000, 10000, 10000, 280, 420, 0, 10000, 190},
{10000, 10000, 10000, 10000, 10000, 230, 10000, 10000, 0, 290},
{10000, 10000, 10000, 10000, 10000, 10000, 10000, 190, 290, 0} };
int path[10][10] = { {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1} };
string sign[10] = { "一号重装实验室","能动学院楼","计算机学院楼","经管学院楼","文理大楼","明德楼","图书馆","蚕研所/生物技术学院楼","大学生活动中心","材料学院楼" };
string description[10]= { "一号重装实验室(描述)","能动学院楼(描述)","计算机学院楼(描述)","经管学院楼(描述)","文理大楼(描述)","明德楼(描述)","图书馆(描述)","蚕研所/生物技术学院楼(描述)","大学生活动中心(描述)","材料学院楼(描述)" };
void floyd() {
int i, j, k;
int tmp;
for (i = 0; i < 10; i++)
{
for (j = 0; j <10; j++)
{
path[i][j] = j;
}}
for (k = 0; k < 10; k++)
{
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
tmp = (target[i][k] == 10000 || target[k][j] == 10000) ? 10000 : (target[i][k] + target[k][j]);
if (target[i][j] > tmp)
{
target[i][j] = tmp;
path[i][j] = path[i][k];
}}}}
int m = 0;
int n = 0;
int temp = 0;
cout << endl;
for (int x = 0; x < 10; x++)
cout << x << ". " << sign[x] << endl;
cout << endl<< "输入起点编号:" << endl;cin >> m;
cout << endl << "输入终点编号:" << endl;cin >> n;
if (target[m][n] != 10000)
{
cout << "起点" << sign[m] << "—>" << "终点" << sign[n] << endl;
cout << "路程: " << target[m][n] <<"m" << endl;
cout<<"路线: " << sign[m];
temp = path[m][n];
while (temp != n)
{
cout << "—>" << sign[temp];
temp = path[temp][n];
}
cout << "—>" << sign[n] << endl;
}
cout << endl;
}
int main() {
int x;
cout <<endl<< "1.搜索学校建筑 2.导航 3.退出" << endl;
cin >> x;
while (x == 1 || x == 2) {
if (x == 1) {
cout << endl;
for (int x = 0; x < 10; x++)
cout << x << ". " << sign[x] << endl;
cout << endl << "选择建筑序号:" << endl;
int y;
cin >> y;
cout << endl << sign[y] << ":" << endl << description[y] << endl;
}
else if(x==2)floyd();
cout << endl<< "1.搜索学校建筑 2.导航 3.退出" << endl;
cin >> x;
}}
更多推荐
数据结构课设 预习
发布评论