数据结构课设整理(校园导航系统)

图的基本操作

  1. 邻接表
  2. 邻接多重表
  3. 十字链表
  4. 邻接矩阵
  5. prim算法
  6. kruskal算法
  7. 拓扑排序
  8. 关键路径
  9. Dijkstra 算法
    这些课本上都有介绍
    所以我只重点整理了做应用部分的算法:
    <mark>利用Dijkstra 算法求最短路径</mark>

Dijkstra 算法求最短路径思路

需要新建几个全局数组和变量:
bool visited[maxn]; //用于判断顶点是否已经在最短路径树中,或者说是否已找到最短路径
int parent[maxn]; //每个顶点的父亲节点,可以用于还原最短路径树
node d[maxn]; //源点到每个顶点估算距离,最后结果为源点到所有顶点的最
短路。
priority_queue q; //优先队列 stl 实现
vernode Ver[maxn];//结点数组
int n; //顶点个数

在算法实现过程中用到队列,有点类似于邻接表的广度遍历,不过是在遍历的过程中,记录最小权值以及对应边的父结点的下标。
主要代码:


void Dijkstra(int s) //Dijkstra 算法,传入源顶点
{
for (int i = 1; i <= n; i++) //初始化
{
	d[i].id = i;
	d[i].w = INF; //估算距离置 INF
	parent[i] = -1; //每个顶点都无父亲节点
	visited1[i] = false; //都未找到最短路
	}
d[s].w = 0; //源点到源点最短路权值为 0
q.push(d[s]); //压入队列中
while (!q.empty()) //算法的核心,队列空说明完成了操作
{
	node cd = q.top(); //取最小估算距离顶点
	q.pop();
	int u = cd.id;
	if (visited1[u]) //注意这一句的深意,避免很多不必要的操作
	continue;
	visited1[u] = true;
	arcnode * p = Ver[u].firarc;
	//松弛操作
	while (p != NULL) //找所有与他相邻的顶点,进行松弛操作,更新估算距
	离,压入队列。
	{
	int v = p->vertex;
	if (!visited1[v] && d[v].w > d[u].w + p->weight)
	{
	d[v].w = d[u].w + p->weight;
	parent[v] = u;
	q.push(d[v]);
	}
	p = p->next;16
	}
}
}

找最短路径,并输出最短路径过程

此过程就需要用到parent[max]数组,这个数组的含义就是从起点到终点最短路径经过的顶点的父结点
从终点开始,找到它的父结点,也就是上一个结点,依次类推,直到找到起点。但
是整个过程是逆序的,因此我用了一个数组去存储整个最短路径过程的结点下
标,最后输出即可。
主要代码:

int base[maxn], k = 0;
while (parent[ed] != st) {
	base[k] = parent[ed];
	k++;
	ed = parent[ed];
	}
k = k - 1;
cout << "最短路线为:" << endl;
printf("从%s 出发", menu[st].c_str());
while (k >= 0) {
cout << " ==>";
printf("%s", menu[base[k]].c_str()); 
k--;
}
printf(" 最终到达%s\n", menu[temp].c_str());
return OK;

链接:https://pan.baidu.com/s/1Tn1xQSNn0mQonh_ARusxYg
提取码:gka4
图的相关操作以及校园导航系统的代码,课设实验报告均在此盘,有需要可以拿去借鉴。

全部评论

相关推荐

面试官人很好,态度和蔼可亲,没答出来时也会引导你去思考。由于是晚上面的,导致我白天一天都有点紧张,面的时候状态也不是很好,正常可能面试官提问完应该思考几秒再答,而我就像抢答一样一口气把所有会的都说出来,这样就导致逻辑比较混乱,东一句西一句的。首先是自我介绍,先把会的技术大致讲一下,由于我八股背的多所以着重讲了一下,Java,go,jvm,MySQL,Redis,计网,操作系统这些,然后一小部分闲聊,然后先问了一下项目,面试官问我这个项目是否落实之类的,直接坦言说是写的练手的,包括之前也写过IM通讯,外卖之类的。然后面试官就把提问的重点放在了八股上。先问了Java:类加载器(答:3种+自定义类加载器、tomcat、原因+双亲委派+好处)JVM参数(答:xmx,xms,newsize这些,问我是如何设定的,我回答是把内存分一半给堆,再把堆分一半给新生代,这方面确实不太了解)然后问了一下并发相关的:线程池(答:线程池的7个参数(忘了线程工厂和阻塞时间了),3个重要参数,还有线程如何启用,为什么要设计最大线程数之类的,提到Java栈默认分配1MB运行时不可以更改)AQS(答:先讲clh是自旋锁+list,然后是AQS在这个基础上做的两个优化,然后举了一下reentrantlock根据state如何获取资源)CAS(答:使用三个字段,aba问题,然后将通常搭配自旋锁实现,面试官问通常会自旋多少次,这个不太了解,答的100,然后问100次大概多少秒,回答微秒级,然后面试官讲了一下怎么做资源可能没用完,意识到可能还需要进行阻塞操作)然后考虑一下Linux命令(top,ps,如何使用管道符过滤线程和使用Linux启动线程没答出来)然后问Redis:持久化机制(答:三种aof,rdb,混合,aof的三个参数刷盘策略,rdb以快照保存,使用bgsave会使用子线程来保存不会阻塞,而aof虽然会阻塞但是只在写完数据后追加一条命令,不会太影响,然后是他俩的优缺点,还有混合是怎么保存数据的)集群模式(答:三种,主从复制到缺点再到哨兵机制,正常使用三个哨兵互相监督,主节点挂了投票选主哨兵然后选主节点,然后额外讲一下脑裂的问题,主节点进行数据更新然后把命令写入aof来同步从节点,最后cluster集群,如何实现,使用16383个哈希槽(艹答成16384了),先根据哈希码取余,再根据节点数取余决定放在哪个节点上,然后问了一下我会怎么选集群模式,首先是cluster的问题,会让管道操作之类的失效,然后哨兵会导致整个集群结构变得复杂,使用小项目可能会考虑哨兵,大的考虑cluster,然后考了一下cluster如果一个节点挂了怎么办,根据节点数重新取余然后数据转移,面试官说这么转移比较慢,有没有别的办法,我隐约记得使用一个类似环形数组的方式,想不起来了)然后考了一下MySQL的b+树(这方面的知识点太多了,导致我什么都想讲逻辑就比较乱,讲了一下聚簇索引,树的叶子节点对应着一张页16KB,MySQL有一个区的概念,把这些页放在同一个区中,这样叶子节点的双向链表遍历时速度更快,然后b+树的扇出比较大(非常二,说成扇度之类的,面试官以为说的是扇区)这样层数就比较小,一行1kb数据的话3层可以放心2000w数据)其他的暂时想不起来了算法是lru,面试官问要不要提示,我说写个,然后写了10分钟左右,说大概写好了,但是面试官指出了2个小错误,第一个马上就改回来了,第二个一直没看出来(大脑这时候已经停止工作了)反问:问学习建议,说根据实际的项目进行深入,考虑应该怎么做,还问了一下组里面是做Java的吗?面试官说他是做go的,组里什么语言都有,语言影响不大,连忙补充了一句我对go的底层有深入源码的学习)结束。总体感觉答得不太好,没有太体现出深度,细节也不够全面。
下一个更好呗:佬,我投完云智一直没消息,多久约的一面啊
查看14道真题和解析
点赞 评论 收藏
分享
04-08 10:36
已编辑
华南理工大学 C++
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务