数据结构课程设计

目录

项目1：计算机设计大赛赛事统计

1.需求分析

2.设计要求

3.重难点

项目2：校园导游咨询

1.需求分析

2.重难点

项目3：算术表达式求解

1.需求分析

2.重难点

3.编程语言

---

项目1：计算机设计大赛赛事统计 1.需求分析

（1）每个比赛项目至少有10支参赛队；每个学校最多有6支队伍参赛;

      （注：每个学校的每个参赛队伍只能参加一个赛事项目）

（2）统计各学校的总分;

（3）可以按照学校编号或名称查询，学校的总分、各项目的总分排序输出；

（4）可以按学校编号查询学校某个项目的获奖情况；可以按项目编号查询取得前三名的学校；

（5）数据存入文件并能随时查询

2.设计要求

（1）输入数据形式和范围：可以输入学校的名称，赛事项目的名称。

（2）输出形式：有中文提示，各学校分数为整数

（3）界面要求：交互设计要合理，每个功能可以设立菜单，根据提示，完成相关功能的要求。

（4）存储结构：学生自己根据系统功能要求自己设计，但是赛事相关数据要存储在文件中。

3.重难点

（1）字符串转数字

（2）将用户输入的字符串处理为文件名

（3）将成绩保存为用户指定名的txt文件

4.逻辑设计

（1）先进行结构体定义，分别有RNode

typedef struct RNode//成绩结点

{
    char Name[L];//队名
    int ProNum;//项目编号
    char ProName[L];//项目名称
    char School_name[L];//学校名称
    int Rank;//排名
    char Score[L];//成绩
    struct RNode *next;

}Record;

typedef struct//学校信息

{
    char name[L];//学校名称
    int num;//学校编号
    Record *RList;//学校成绩表
    int Total_score;//总分
    int Project_Total_score;//各项目总分
}School; 

typedef struct//项目

{
    char name[L];//项目名称
    int num;//项目编号
    Record *First;//第一名成绩信息
    Record *Second;//第二名成绩
    Record *Third;//第三名成绩
}Project; 

typedef struct
{
    int num;
    int score;
}Pm; 

（2）设计一个菜单页，包含初始化数据，录入数据，读取数据，查询成绩排名等功能。

（3）

---

项目2：校园导游咨询 1.需求分析

（1）设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意景点相关信息的查询。  

（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

2.重难点

（1）弗洛伊德（Floyd）算法求图的最短路径

弗洛伊德算法定义了两个二维矩阵：

1.矩阵D记录顶点间的最小路径
例如D[0][3]= 10，说明顶点0 到 3 的最短路径为10；
2.矩阵P记录顶点间最小路径中的中转点
例如P[0][3]= 1 说明，0 到 3的最短路径轨迹为：0 -> 1 -> 3。
它通过3重循环，k为中转点，v为起点，w为终点，循环比较D[v][w] 和 D[v][k] + D[k][w] 最小值，如果D[v][k] + D[k][w] 为更小值，则把D[v][k] + D[k][w] 覆盖保存在D[v][w]中。

结构定义：

typedef struct struct_graph{
    char vexs[MAXN];
    int vexnum;//顶点数 
    int edgnum;//边数 
    int matirx[MAXN][MAXN];//邻接矩阵 
} Graph;

弗洛伊德算法：

//弗洛伊德算法的核心部分 
    //k为中间点 
    for(k = 0; k < G.vexnum; k++){
        //v为起点 
        for(v = 0 ; v < G.vexnum; v++){
            //w为终点 
            for(w =0; w < G.vexnum; w++){
                if(D[v][w] > (D[v][k] + D[k][w])){
                    D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                    P[v][w] = P[v][k];//更新最小路径中间顶点 
                }
            }
        }
    }

（2）图中顶点表示校内各景点,需要存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

3.逻辑设计

（1）定义一个类，包含以下函数

    Graph(int n, int e);
    void Map();//学校平面图浏览
    void Seek(int i);//查找哪个景点
    void Floyd();//计算顶点对之间的最短路径的长度
    void Printshortpath();//输出最短路径

    vertexNode a[Maxsize];//存放顶点结点的信息
    int vertexNum,arcNum;//图的顶点数与边数
    int arc[Maxsize][Maxsize];//存放两景点之间的距离
    int dist[Maxsize][Maxsize];//存放所选择两景点之间的最短距离
    string path[Maxsize][Maxsize];//存放最短路径中两个景点的代码

（2）设计一个菜单页面meau函数

    cout<<"----------输入1    执行浏览学校平面图--------"<     cout<<"----------输入2    执行景点信息查询----------"<     cout<<"----------输入3    执行最短路径查询----------"<     cout<<"----------输入4    执行退出系统----------------"<

（3）Graph()中包含以下信息

    string code;//景点代号
    string name;//景点名字
    string information;//景点介绍

    两景点之间的距离

（4）Floyd()

for(k = 0; k < G.vexnum; k++)//k为中间点 

{ 
        for(v = 0 ; v < G.vexnum; v++) //v为起点

        {  
            for(w =0; w < G.vexnum; w++)//w为终点

            {   
                if(D[v][w] > (D[v][k] + D[k][w]))

                {
                    D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                    P[v][w] = P[v][k];//更新最小路径中间顶点 
                }
            }
        }
    }

（4）main函数中

 调用Graph();

 meau();

 输入编号，用switch函数来进行不同的功能 *** 作。

---

项目3：算术表达式求解 1.需求分析

1、实现标准整数类型的四则运算表达式的求值（包含括号，可多层嵌入）

2、 能够检验算术表达式的合法性

（1）正确解释表达式；
（2）符合四则运算规则：
（3）先乘除、后加减；
（4）从左到右运算；
（5）先括号内，后括号外；
（6）输出最后的计算结果。

2.重难点

（1）字符串转数字

int str_to_int(char A[]){//字符串转数字
    int i=0,e=0,flag=1;
    if(A[0]=='-'){flag=-1;i++;}
    while(A[i]!='')
        e=e*10+(A[i++]-'0');
    return e*flag;

3.逻辑设计

（1）存储结构设计

  本程序中建立两个栈，一个栈用来存放运算符，另一个栈是用于存放 *** 作数与计算结果。

（2）算术优先级设计

本程序中定义一个函数来比较运算符的优先级

char Table[8][8] = {//优先级表格
        { ' ', '+', '-', '*', '/', '(', ')', '=' },
        { '+', '>', '>', '<', '<', '<', '>', '>' },
        { '-', '>', '>', '<', '<', '<', '>', '>' },
        { '*', '>', '>', '>', '>', '<', '>', '>' },
        { '/', '>', '>', '>', '>', '<', '>', '>' },
        { '(', '<', '<', '<', '<', '<', '=', ' ' },
        { ')', '>', '>', '>', '>', ' ', '>', '>' },
        { '=', '<', '<', '<', '<', '<', ' ', '=' }
    };