ToB企服应用市场:ToB评测及商务社交产业平台

标题: 《数据布局》课程综合筹划（zzu校园导航）(迪杰斯特拉算法) [打印本页]
作者: 宁睿    时间: 2024-10-17 12:02
标题: 《数据布局》课程综合筹划（zzu校园导航）(迪杰斯特拉算法)
一、体系（标题）形貌

现在根据郑州大学主校区面积地域的广大，以及南、北焦点讲授楼的课堂分布密集且较多；另外，多数舆图软件无法精致导航到一个具体的地点，容易造成原地转圈的烦恼。但是，我们转换思路，仅仅根据我们对于校园充分的熟悉度，给出了郑州大学主校区柳、荷、菊、松四个园区和南、北焦点讲授楼各个课堂的名称信息及有线路联通的地点之间的间隔，利用郑州大学主校区课堂导航体系盘算出给定的起点到止境之间的最近间隔及最优路线。
二、体系需求

zzu课堂导航体系重要提供给用户三个选项进行操作，分别为输出舆图、课堂导航、退出。它重要用于课堂导航，根据用户输入的起点和止境，为用户显示最佳路线。
程序具有的功能：
能够根据用户输入的起点和止境给出最短间隔，输出最短路线。
1、InitOutput()目录：给出用户目录以供选择。
2、initInput(Pos p)初始化点信息：存储校园各点的地名信息；
3、initGraph() 初始化图：存储校园各个地点构成的边信息；
4、Dijkstra(Pos p, int Start, int End)求两点之间的最短路径：利用算法，快速给出用户到目的地的最短间隔，并存储最佳路线；
5、PrintPath(Pos p, int start, int end, char *E)输出具体路线：给出用户具体的路线过程；
6、PrintRoad(char *d, char *end)d为进的门， end为课堂：讲授楼内部导航信息的创建；
三、筹划头脑

建图：将地点根据名称转换为数字来表现，建边和后序盘算最短路均利用该点所对应的编号来操作。
求最短路：利用迪杰斯特拉算法+堆布局优化。
求最短路线：利用递归访问路线数组。
(一)数据布局的选择和筹划

  1. //位置类
  2. typedef struct Position *Pos;
  3. struct Position
  4. {
  5.     char name[Totalcharlen];//地点名
  6.     int index; //编号
  7. };
复制代码
位置类Pos，用来根据编号来找地点名。后序进行迪杰斯特拉算法和输出道路时，均是通过编号来表现该点，即会用到Pos这个数据类型。
  1. map<string, int> mpos; //名字对应位置
复制代码
Map为c++的stl布局，利用map该数据布局实现给点编号，并可以通过点的名字来访问其的编号，在建点，建边中有用到。即通过点的名字，取得其的编号，然后按照编号来表现两点之间的关系。
  1. //边
  2. struct ty
  3. {
  4.     int t, len, next; // t:边终点，len:边长，next指向该点连的下一条边
  5. } edge[TotalEdge];
复制代码
链式前向星算法中用来存边的布局，给每条边设定编号，edge的下标为边的编号，每条边存该边的止境t,长度len,和与该边起点相同的边的上一条边的编号next。
  1. //堆里数据
  2. typedef struct Index *in;
  3. typedef struct Index Index;
  4. struct Index
  5. {
  6.     int x, dis; //最小堆里存放的，x：当前结点编号，dis：该点到其他点的距离
  7. };
复制代码
in为堆中数组里的元素，存放着该点的编号x，dis指的是起点到该点的间隔。
  1. //最小堆
  2. typedef struct MinHeap *Mh;
  3. struct MinHeap
  4. {
  5.     in i;     //数组
  6.     int last; //堆尾。
  7. };
复制代码
Mh为数据布局最小堆，该堆中存储了数组i和队尾的下标last。堆是一个类似于二叉树的布局，与其差别的是其父亲结点比孩子大(小)，为大(小)顶堆。这里利用数组布局来表现堆，其下标从1开始，设父亲节点为i,则左孩子为2*i,右孩子为2*i+1，且界说比较的巨细是对in布局体数组里的dis(起点到该点的间隔)的值来比较。
(二)算法筹划

起首来说明下建图的过程，建图包括建点和建边两部分：
建点：
  1. Pos initPos(int totalpos) //初始化点
  2. {
  3.     p = (Pos)malloc(sizeof(struct Position) * total); //分配点空间
  4.     for (i = 0; i < totalpos; i++)
  5.         p[i].index = 0; //初始化点的编号
  7.     return p;
  8. }
  9. Status InsertPos(Pos p, char *name) //插入点函数
  10. {
  11.     mappos[name] = ++total; //给该点编号
  12.     //存该点信息
  13.     p[total].index = total;
  14.     strcpy(p[total].name, name);
  15.     return OK;
  16. }
  17. Status initInput(Pos p) //初始化点  //加点
  18. {
  19.     fp = fopen("datapos.txt", "r");
  20.     if (fp == NULL) //如果文件指针为空
  21.     {
  22.         printf("文件打开失败\n");
  23.         return ERROR;
  24.     }
  25.     else
  26.     {
  27.         printf("打开成功\n");
  28.         fscanf(fp, "%d", &totaldata);
  29.         for (i = 0; i < totaldata; i++)
  30.         {
  31.             fscanf(fp, "%s", pos); //该点的名
  32.             InsertPos(p, pos);     //插入该点
  33.         }
  34.         printf("点信息输入完成!\n");
  35.     }
  36.     fclose(fp); //关闭文件
  37.     return OK;
  38. }
复制代码
利用map数据布局，即程序中的mappos将图中的点根据名字的差别实现从1开始的编号。编号后再将其存入Pos--点数组里，实现可以通过点的名称和编号双向访问。程序中，是从文件中读取点然后将其插入。
建边：
  1. Status AddEdge(PosType x, PosType y, EdgelenType len) //链式前向星，加边
  2. {
  3.     edge[++cnt].t = y;        //存边的尾
  4.     edge[cnt].len = len;      //存边的长度
  5.     edge[cnt].next = head[x]; //标志为以x的点为起点的边
  6.     head[x] = cnt;            //更新以x为起点的边的标记
  7.     return OK;
  8. }
  9. Status InsertEdge(char *name1, char *name2, EdgelenType len) //插边函数
  10. {
  11.     //找到两点编号
  12.     PosType x1 = mpos[name1]; //找name1所对应的编号
  13.     PosType x2 = mpos[name2]; //找name2所对应的编号
  14.     AddEdge(x1, x2, len); //建x1->x2
  15.     AddEdge(x2, x1, len); //建x2->x1
  16.     return OK;
  17. }
  18. Status initGraph() //初始化图  //加道路
  19. {
  20.     fp = fopen("dataedge.txt", "r");
  22.     if (fp == NULL) //如果文件指针为空
  23.     {
  24.         printf("文件打开失败\n");
  25.         return ERROR;
  26.     }
  27.     else
  28.     {
  29.         printf("打开成功\n");
  30.         printf("边信息输入完成!\n");
  31.         fscanf(fp, "%d", &totaldata);
  32.         for (i = 0; i < totaldata; i++)
  33.         {
  34.             char s1[Totalcharlen], s2[Totalcharlen];
  35.             EdgelenType len;
  36.             fscanf(fp, "%s %s %d", s1, s2, &len); //输入边的起始，终止点，长度
  37.             InsertEdge(s1, s2, len);              //加双向边
  38.         }
  39.     }
  40.     fclose(fp); //关闭文件
  41.     return OK;
  42. }
复制代码
根据点的编号来建边，利用链式前向星的头脑，先将head数组初始化为-1，head数组的下标代表点的编号，其存储的为该点所连的最后一条边的编号。每次建一条边，就用edge布局体数组来存储，其下标即为边的编号。
当在图中插入一条边时，先将边的总数编号+1，则此时总数为该边的编号，然后存储该边长度len，上一个同一起点的边的编号head[x该边起点)]，更新head[起点] = 该边的编号。按照这样来建边。
按照这种方式来建边，使得每次访问以x为起点的边时，就从i = head[x]开始，即从以x为起点的最后一条边开始访问，edge[head[x]]即为该边信息。然后i = edge.next即为以x为起点的上一条边。程序中对于边的插入是通过文件读取每条边的起点，止境，长度来插入。
然后是来说明下怎样求最短路：
  1. //最短路算法
  2. EdgelenType Dijkstra(Pos p, PosType Start, PosType End) //求两点之间的最短路径，并记下路径,返回路径
  3. {
  4.     memset(vis, 0, sizeof(vis));                   //初始化vis数组，指所有元素均未访问国
  5.     memset(dis, Maxx, sizeof(dis));                //初始化dis数组，标记所有节点到start数组距离均为无穷大
  6.     path = (int *)malloc(sizeof(int) * TotalEdge); //存经过路径
  7.     Mh m = InitMinheap(TotalEdge);                 // 边的个数
  9.     dis[Start] = 0;             //自己到自己的距离为0
  10.     tmp.dis = 0, tmp.x = Start; //赋tmp值
  11.     pushMinHeap(m, tmp);        //将第一个点放入堆中
  12.     path[Start] = 0;            //记录下起点的path值为0，方便后序访问
  13.     //遍历len，找更新所有和end的距离dis
  14.     while (!IsEmptyHeap(m)) //如果堆不为空
  15.     {
  16.         tmp = getHeapTop(m);                           //取出堆顶元素（即dis最小的下标）
  17.         popMinHeap(m);                                       //取出下标
  18.         if (vis[tmp.x])                                      //如果该下标访问过
  19.             continue;                                        //跳过
  20.         vis[tmp.x] = 1;                                      //未访问过就将其标记
  21.         for (i = head[tmp.x]; i != -1; i = edge[i].next) //遍历该点所连的边
  22.         {
  23.             y = edge[i].t;                     // y值为该边所指向的终点
  24.             if (edge[i].len + dis[tmp.x] < dis[y]) //如果start到x的长度(dis[x]) + 该边长度 小于 start到X的长度
  25.             {
  26.                 dis[y] = edge[i].len + dis[tmp.x]; //更新start到y的长度(dis[y])
  27.                 path[y] = tmp.x;                   //记录到y，所经过点x
  28.                 tmp2.x = y, tmp2.dis = edge[i].len + dis[tmp.x];
  29.                 pushMinHeap(m, tmp2); //压入堆
  30.             }
  31.         }
  32.     }
  33.     FreeMinHeap(m);  //释放堆内存
  34.     return dis[End]; //返回start到end的最短距离
  35. }
复制代码
利用堆优化+迪杰斯特拉算法，vis数组表现起点到该点的最短间隔是否已经求出。若为1，表现已求出，为0表现未求出。先初始化vis数组全为0，表现此时起点到该点的最短间隔均未求出。dis数组表现起点到其他点的最短间隔，先初始化为最大值。
开始盘算最短路，每次从小顶堆顶中取出与起点间隔最短的点，然后判定该点是否访问过，便是否已经求出起点到该点的最短间隔，访问过就跳过该点，未访问过，就将该点x作为中心节点来更新起点到其他未求出最短间隔的节点的间隔，并标记该点访问过了。如果起点到该点的间隔dis[x]+该点到其他点y的间隔<起点到y的最短间隔dis[y]，就更新这个最短间隔dis[y]，然后将该点y的信息放入堆中。
输出道路：
  1. //输出道路算法
  2. void PrintPath(Pos p, PosType start, PosType end, char *E) //输出道路
  3. {
  4.     if (path[end] == 0) //因为起始点的path为0，因此此时递归到起始点
  5.     {
  6.         printf("%s", p[start].name); //输出起始点
  7.         return;
  8.     }
  9.     else
  10.     {
  11.         PrintPath(p, start, path[end], E);   //一直递归到起始点后，开始输出
  12.         if (!strcmp(p[end].name, E))         //如果当前点的下一个为终点
  13.             strcpy(door, p[path[end]].name); //保存当前门（终点为教室，门为教室的上一个点）
  15.         printf("->%s", p[end].name); //输出当前遍历的点名
  16.     }
  17. }
复制代码
在迪杰斯特拉算法中，还维护了一个数组path。先将path[start] = 0，然后每次更新到起点到其他节点y的最短间隔时，也同时更新y的path，即path[y] = x(中心节点)，即path数组，除了起点外，其存储的为最短间隔要经过path下标节点的道路的上一个节点。
然后在输出道路的函数中，递归输出，即从止境的path值开始递归，直到止境的path值为0，即此时止境的path值和起点相同，输出起点，这时回退，输出上一层止境的path值，再输出点，以此类推。
最小堆：
  1. Status pushMinHeap(Mh m, Index x) //将x存入堆
  2. {
  3.     m->last++;                                      //堆数组最后的下标+1
  4.     m->i[m->last] = x;                              //将X存入堆数组的最后一个位置。
  5.     parent = m->last / 2, i = m->last;          // parent指向最后一个元素的父亲节点下标，i指向最后一个元素下标
  6.     while (m->i[parent].dis > x.dis && parent != 0) //从下往上滤
  7.     {
  8.         swap(m->i[parent], m->i[i]); //因为为最小堆，如果父亲节点大于儿子节点，就交换
  9.         i = parent;                  //儿子 = 父亲
  10.         parent /= 2;                 //父亲 = 父亲的父亲
  11.     }
  12.     return OK;
  13. }
复制代码
对于堆的插入操作，起首是将堆的最后一个下标自增1，即last++，然后将插入的元素x插入堆中数组下标为last值的位置，开始从下到上调整堆的布局。即用一个指针i指向x元素的下标，一个指针p指向x元素的父亲节点，开始比较两者巨细，如果父亲节点大于孩子节点而且此时父亲节点不为0(由于数组下标从1开始)，说明不满足最小堆的要求，将二者调换，然后i指向p,p再指向i的父亲，再次比较，以此类推，直到父亲节点小于孩子节点，大概父亲节点下标为0为止。
  1. Status popMinHeap(Mh m) //将堆头元素删除
  2. {
  3.     m->i[1] = m->i[m->last];                                           //先将第一个赋值为最后一个元素，也算删除了第一个元素
  4.     i = 1;                                                         // i指向第一个元素的下标
  5.     m->last--;                                                         //最后一个元素下标-1
  6.     child = i * 2;                                                 //指向第一个元素的左孩子
  7.     if (m->i[child].dis > m->i[child + 1].dis && child + 1 <= m->last) //如果有右孩子，且右孩子比左孩子小
  8.         child++;                                                       //那么就指向右孩子
  9.     while (m->i[child].dis < m->i[i].dis && child <= m->last)          //从上往下滤
  10.     {
  11.         swap(m->i[child], m->i[i]);                                        //如果i节点指向元素比最小的孩子还小，就交换
  12.         i = child;                                                         // i指向孩子
  13.         child *= 2;                                                        //孩子指向孩子的孩子
  14.         if (m->i[child].dis > m->i[child + 1].dis && child + 1 <= m->last) //再次找最小的孩子
  15.             child++;
  16.     }
  17.     return OK
  18. }
复制代码
对于堆的删除操作，由于堆中只能删除堆顶元素，即取出最小元素，那么就将堆中数组的最后一个元素提上来覆盖掉堆顶元素，然后开始从上往下调整。指针i指向根结点，指针c指向i的左孩子，先比较i的左孩子和右孩子谁更小，如果右孩子更小，则c指向右孩子。然后开始比较i指向的值和孩子节点值的巨细，如果孩子节点的值小于父亲节点，说明不符合最小堆的性质，这时将两个节点进行交换，然后再将i指向c节点， c指向i的最小的孩子节点，然后再次比较，以此类推，直到符合最小堆性质为止。 
四、实现细节说明

求最短路径：迪杰斯特拉+堆优化，
利用迪杰斯特拉算法，用数组的下标表现点的编号，利用链式前向星头脑来找每一个点的边，利用最小堆来存储每个点到起点的间隔，然后每次从堆顶取出到起点间隔最小的点来更新其他点到起点的最小间隔，每次更新将该点的上一个点给记住，方便后序输出道路。

如以上界面，输入起始地点，止境。然后输出最短间隔和道路。
体系根据用户输入的起点，先从体系中找该点是否存在，存在则继承下一步，，不存在就让用户再次输入。然后是判定用户输入的止境是否存在，且是否为课堂，若不满足要求，则再次输入。若为课堂则继承下一步，利用迪杰斯特拉算法盘算两点间的最短间隔，并生存路线，然后输出。
五、测试数据及测试效果

大体说明：
根据我们的测试效果，与我们校园实地的环境是同等的。

校园舆图测试：


导航路线测试：

具体说明：
起首说明下体系中文件的导入：
点文件：用来存放所有舆图上要初始化的点，即用户可以输入的地点，体系根据该文件来建点。

第一个311指总共有311个点。
然后每行一个地点。
边文件：用来存放所有边的文件，体系通过该文件内容建边。

第一个1121指总共有1121条边。
每行一条边，按照起点、止境、长度分列顺序。比方第二行的指从秋实西1到厚德北1长度为161米，且厚德北1到秋实西1也有一条161的边，实际上一举动两条边。
然后是先容用户输入所实现的功能：
输入1，输出简化舆图：


输入2，根据用户输入的起点和止境课堂，输出路线。

如图所示，选择起点为本源南1，止境课堂为南4-302。然后程序给出了具体走法，该走法可以参照舆图来理解。
再次输入：

这次输入的起点为厚德北1，止境课堂为为北3-204。

如图所示为程序给出的最佳路径。
输入3，退出体系，并释放内存。

六、总结

(一)体系特点及创新

特点：
1、简洁输出关键有用的信息，输出界面有简化舆图的展示，输出间隔和路线简洁明白。
2、更人性化，到达讲授楼地域，有笔墨引导方向至具体课堂。
创新性：
1、利用地点名到序号的映射，使代码写起来更清晰易懂。可以直接通过地点名来进行建图。
2、利用链式前向星的头脑来建边，可以使访问一个点所连的边更快，避免了访问其他没有连边的节点。
3、利用堆来优化迪杰斯特拉算法，使算法效率提升。
4、利用数组递归方式来输出最短路线。
5、联合实际，将每个门怎样到达课堂的具体路线完善。
(二)遇到的标题及办理思路

1、路线间隔丈量困难

办理方法：我们通过查阅资料，在电脑端高德舆图找到了测距尺，快速确定了各个地点间的间隔。

2、地点名难与序号逐一对应
办理方法：刚开始考虑的是利用哈希表，然后思索怎样界说一种求有用快速的关键字的筹划，实现更好的根据名字来定位元素。但是由于地点名为中文，有关中文怎样编码不是很清晰，有想过将中文改为拼音来建图。但是拼音很容易就会打堕落，对于体系维护来说不是很方便，因此就利用了c++的stl内里的map布局，来实现名字对应序号，至于序号对应名字，就可以利用布局体数组的下标来实现。
3、建点和建边部分的程序很长，且没太大意义
办理方法：将其用文件的方式输出。刚开始利用文件，发现根本运行不了，发现原来是对于中文的编码，文件要选择ANSI的格式。
4、程序输出最佳路线无法明白指向课堂
办理方法：将讲授楼的大门与每一个可以从该门口到达的课堂连一条为0长度的边，这样用户输入课堂止境时，其路线的止境就会指向课堂了。
5、对于用户输入的起点和止境缺少判定，导致随便输入代码也会继承执行堕落
办理方法：起首是对起始点的判定，起始点输入的，要为点文件中给出的已经初始化的点，通过map的性质进行判定，如果用户输入的点不在map中，那么直接该点的map值为0，而我们初始化点的序号从1开始，就可以判定了。对于止境输入是否为课堂的判定，读取点文件，看输入的课堂是否存在来判定。
最后，可能以上的程序照旧存在瑕疵，各人可以得当修改和完善，感谢阅读！
完整代码：
【免费】数据据布局课程筹划-zzu校园导航(迪杰斯特拉算法)资源-CSDN文库

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4