ddd/README.md

#图书管理系统

2023年6月25日 成员1：王昊 成员2：孙艺哲 成员3：张江楠 成员4：郭佳慧

##项目简介

这段代码实现了一个简单的上海地铁路线查询系统，包括初始化地铁站点信息、创建邻接表和邻接矩阵、使用Dijkstra算法查询最短路径等功能。 下载地址：https://bdgit.educoder.net/mac76tib2/ddd.git

项目开发过程中采用 Kanban（看板）进行任务管理和分工协作，并使用 Git 对程序代码和文档进行版本管理。任务分工情况如下：

任务	设计	开发	测试	文档
C1	王昊	王昊	张江楠	郭佳慧
C2	张江楠	张江楠	郭佳慧	孙艺哲
C3	郭佳慧	郭佳慧	孙艺哲	王昊
C4	孙艺哲	孙艺哲	王昊	张江楠

每个成员工作量（百分比）：

王昊	张江楠	郭佳慧	孙艺哲
25	25	25	25

##需求分析

(1) 基于真实的地铁数据建立导航地图模型，编制成格式简单的数据文件包括城市线路名称、站点名称。 (2)系统能够读取地铁导航地图数据文件，建立地铁模型，也能够将模型输出成数据文件，以便验证模型的正确性。 (3)通过人机交互的方式输入起点和终点站名称，系统给出路径长度最短的导航路径，并给出换乘方案。 (4)能够读取不同的地铁导航地图进行功能测试。

##C1：定义结构体

代码：#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>

#define MAX 1000

typedef struct node {
	char a[100];
	struct node* next;
}edgenode;

struct vexnode {
	char name[100];
	struct node* firstnode;
};

struct list {
	struct vexnode adjust[6];
	int e, n;
};

##C2:地铁网络的构建

代码：

##C3：邻接表和邻接矩阵之间的转换

代码：

##C4:计算并输出最短路径

代码：

int num2=0; void Dijkstra(int v1,int v2){ int dist[MAX],s[MAX],path[MAX];//s判断v1是否已经判断最短路径，path前驱 int min,i,j,u,pre; for(i=0;i<nm.n;i++){ dist[i]=cont[v1][i]; s[i]=0; if(cont[v1][i]<MAX) path[i]=v1; else path[i]=-1; }//初始化操作 s[v1]=1; path[v1]=0; for(i=0;i<nm.n;i++){ min=MAX; u=-1; for(j=0;j<nm.n;j++){ if(s[j]==0&&dist[j]<min){ u=j; min=dist[j]; } } if(u!=-1){ s[u]=1; for(j=0;j<nm.n;j++) if(s[j]==0){ if(cont[u][j]<MAX&&dist[u]+cont[u][j]<dist[j]){ dist[j]=dist[u]+cont[u][j]; path[j]=u; } } } } printf("智能推荐路线如下(逆序):\n"); for(i=0;i<nm.n;i++){ if(i!=v1&&i==v2){ if(s[i]==1){ num2=dist[i]; pre=i; while(pre!=v1){ printf("%s-->",nm.adjust[pre].name); pre=path[pre]; } printf("%s",nm.adjust[pre].name); } else printf("路径不存在！\n"); } } } ##概要设计

1. 定义了一个结构体list，包含了地铁站点信息和邻接表。
2. 使用creatnode()函数对节点进行初始化，包括边数、站点数和站点名称。
3. 使用createlist()函数创建邻接表，包括每个站点的邻接表信息。
4. 使用aaa()函数初始化邻接矩阵，将所有元素赋值为最大值。
5. 使用createjz()函数创建邻接矩阵，将有边相连的站点间的距离赋值为1。
6. 使用print()函数打印出每个站点的邻接表信息。
7. 使用Dijkstra()函数查询最短路径，输入起点和终点站点编号，输出最短路径和路径长度。
8. 主函数中实现了一个简单的用户交互界面，让用户选择查询最短路径或退出系统。

##详细设计