基于C语言实现的校园导航系统

Benjamin

发布日期: 2019-02-14 08:56:14 浏览量: 303
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1 需求分析

  • 设计并显示某学校的校园平面图

    • 地点(地点名称、地点介绍)
    • 路线(公里数)均不少于10个(文件存储)
  • 提供图中任意地点相关信息的查询

  • 提供图中任意地点的问路查询

    • 任意两个地点之间的一条最短的简单路径(最短路径长度——中转次数最少)
    • 任意两个地点之间的一条最佳访问路线(带权(公里数)最短路径长度)
    • 任意两个地点之间的所有简单路径
  • 提供图中所有地点的最佳布网方案

  • 增加新地点和路线、撤销旧地点和路线

2 概要设计

2.1 功能模块图

2.2 各个模块详细的功能描述。

  • 地点信息:通过输入地点编号或者名称查看地址信息的简介

  • 显示地图:展示每个地点间的路线及长度

  • 中转最少:任意两个地点之间的一条最短的简单路径;(最短路径长度——中 转次数最少)

  • 最佳路径:任意两个地点之间的一条最佳访问路线;(带权(公里数)最短路径长度

  • 全部路径:任意两个地点之间的所有简单路径

  • 最佳布网:提供图中所有地点的最佳布网方案

  • 添加删除:增加新地点和路线、撤销旧地点和路线

3 详细设计

3.1 功能函数的调用关系图

3.2 重点设计及编码

求两点之间的所有路径:深度优先遍历

  1. //寻找所有简单路径
  2. void FindAllPath(AdjList *G)
  3. {
  4. char star[20], end[20];
  5. printf("输入【起点】-->【终点】:");
  6. scanf("%s %s", star, end);
  7. int starIndex = SelectIndex(G, star);
  8. int endIndex = SelectIndex(G, end);
  9. if(!starIndex || !endIndex)
  10. {
  11. printf("输入地点不存在\n");
  12. return;
  13. }
  14. int i, w, v, instack[MAXEX + 1];
  15. v = starIndex;
  16. w = -1;
  17. for(i = 1; i <= G->vexnum; i++)
  18. instack[i] = 0;
  19. SeqStack *S = InitStack();
  20. Push(S, starIndex);
  21. instack[v] = 1;
  22. ArcNode *p;
  23. while(!Empty(S))
  24. {
  25. v = Top(S);
  26. p = G->vertex[v].head;
  27. while(p != NULL)
  28. {
  29. if(w != -1)
  30. {
  31. while(p != NULL && p->adjvex != w)
  32. p = p->next;
  33. if(p != NULL)
  34. {
  35. p = p->next;
  36. while(p != NULL && instack[p->adjvex] == 1)
  37. p = p->next;
  38. }
  39. }
  40. else
  41. {
  42. while(p != NULL && instack[p->adjvex] == 1)
  43. p = p->next;
  44. }
  45. if(p == NULL)
  46. break;
  47. w = p->adjvex;
  48. Push(S, w);
  49. instack[w] = 1;
  50. if(w == endIndex)
  51. {
  52. printf("【");
  53. for(i = 0; i <= S->top; i++ )
  54. {
  55. printf("%s ", G->vertex[S->data[i]].name);
  56. }
  57. printf("\b】\n");
  58. break;
  59. }
  60. p = G->vertex[w].head;
  61. w = -1;
  62. }
  63. w = Pop(S);
  64. instack[w] = 0;
  65. }
  66. }

4 测试数据及运行结果

地点信息

显示地图

中转最少

最佳路径

全部路径

最佳布网

添加地点

添加边

删除边

删除地点

参考文献

  1. 《数据结构与算法》主编:王曙燕
上传的附件 cloud_download 校园导航系统.zip ( 414.98kb, 18次下载 )
error_outline 下载需要8点积分

发送私信

你愿苦其自身,必将掌声雷动

8
文章数
11
评论数
最近文章
eject