数据结构实验预习报告

项目一中国计算机设计大赛赛事统计

一、问题分析和任务定义
题目中没有给我们相应数据来处理，所以要自己生成。可以自己手动输入，也可以通过随机数生成。在生成时要注意以下两点：             

队伍总数（teams）、学校总数（schools）和赛事项目总数（events）存在以下关系：

10*events<=teams<=6*schools                             

需要完成的功能：     

1.照学校编号或名称查询，学校的总分输出；                                                                    
2.照学校编号或名称查询，学校各项目的总分排序输出；                                                           
3.按学校编号查询学校某个项目的获奖情况；                                                                  
4.可以按项目编号查询取得前三名的学校（注意并列的情况）；

二、逻辑设计
1.变量的类型说明：

Team类    参加的项目（int） 所在学校（string）获得成绩（int）
School类    学校的名称（string）和编号（id）参赛队伍数量（int）

2.变量说明：

schools[n]    参加的学校数组（School类型）
events[m]    比赛项目（int）
teams[i]    参加的队伍（Team类型）
total[m]    各项目人数
rank[m][total[m]]    每个项目的队伍排名（Team类型）
3.函数说明：   

prim()    对处理的数据进行初始化
printSum(String str)    照学校编号或名称查询，学校的总分输出
printScore(String str)    照学校编号或名称查询，学校各项目的总分排序输出
printPrize(String str)    按学校编号查询学校某个项目的获奖情况     
printRank(String str)    按项目编号查询取得前三名的学校
main()    主函数用于界面设计和各种函数调用
三、物理设计
伪代码：

类Team：String 项目，String学校，int 成绩，get/set；                      
类School：String 名字，String 编码，int 队伍数，get/set；     
schools[n]；
events[m]；
teams[i]；
total[m]；
rank[m][total[m]]；
prim(){初始化数据}；
printSum(String str){在teams[i]中查询本校的队伍，并加队伍的总分加起来并输出}；
printScore(String str){从teams[i]挑选出各个项目的队伍，分别计算其总分，最后降序输出}；
printPrize(String str){根据项目在rank[m][3]中查找获奖队伍，若不在，则未获奖}；
printRank(String str){使用queryScore函数得到每个学校每个项目的总分，综合计算最后得出特定项目的前三学校}；
main(){设计交互界面，根据需要调用上述函数}。

项目二校园导游咨询

一、问题分析和任务定义

这个问题可以用数据库中图的相关知识解决，由于实际校园中的路都是双向的，故此处为无向图；校园中的景点等效于图中的节点，图中的边表示景点之间的路径，查询任意两个景点之间的一条最短的简单路径，实际为寻找无向图中两个节点之间的最短路径，我们可以使用Dijkstra算法。

1.数据要求：为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的路线查询，即查询任意两个景点之间的一条最短的简单路径。

2.限制条件：所含景点不少于10个。

3.输出条件：输出一条最短路径。

二、逻辑设计
【抽象数据类型的定义】
定义景点类，类中存放景点名称(string)、代号(int)、简介(string)等信息。
定义一个边类，存放路径长度（int）。

来访者若需查询景点信息，则选择查询功能并输入要查询的景点，程序即展示该景点的相关信息；来访者若需查询路径信息，则选择查询功能并输入要查询的两个景点的路径，程序即展示一条最短路径。

【函数说明】
MGraph(int n, int e)初始化函数；
Seek(int i)查询景点信息；
Floyd()判定两景点之间是否经过一点；
Allpaths()所有路径的输出；
Allpathlengths()所有路径的长度输出；
Printshortpath()最短路径的输出

三、物理设计
结构体vertex：int景点代号，string景点名称，string景点简介；
类Mgraph；
vertex a[Maxsize]景点；
int arc[Maxsize][Maxsize];
int dist[Maxsize][Maxsize];
int vertexNum, arcNum；
string path[Maxsize][Maxsize]; MGraph(int n, int e)初始化函数；
void Seek(int i)查询景点信息；
void Floyd()判定两景点之间是否经过一点；
void Allpaths()所有路径的输出；
void Allpathlengths()所有路径的长度输出；
void Printshortpath()最短路径的输出。
项目三算术表达式求解

一、问题分析和任务定义
该问题的要求是能够实现混合四则运算，需要进行整数的四则运算还要求可多层嵌入。
分析用堆栈解析算术表达式的基本方法。实验要求给出的示例代码能求解任何包括+，-，*，/，()和0到9数字组成，可多层嵌入的算术表达式。设计一个简单的算数表达式计算器。

二、逻辑设计
基于堆栈的算法：从左到右扫描每一个字符。
1.数据要求：实现标准整数类型的四则运算表达式的求值（包含括号，可多层嵌入）.
2.输出条件：正确输出四则运算结果

数据结构：
Stack.pop() *** 作结果：取出并删除该栈的顶部元素。
Stack.top() *** 作结果：只取出栈的顶元素，而不删除。
Stack.push(T x) *** 作结果：将某数据类型的x压栈。

【函数说明】

find()用来查找位置 
reduce()用来去除括号
cele()用来计算
main()函数用来执行调用
三、物理设计
string s; 

int a[10],b[10];

char s1[100]; 

find()；

reduce()；

cele()；

main()；