精华内容
下载资源
问答
  • 关系数据结构包不包含平面数据
    千次阅读 多人点赞
    2020-12-29 10:08:28

    1.课程设计内容

    设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
    基本要求:
    设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。
    为来访客人提供图中任意景点相关信息的查询。
    为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。

    问题分析:
    这个校园导航系统,主要是需要构建校园平面图,并将之信息用邻接矩阵存储,然后进行最短路径查找及景点信息查询。

    西安工程大学校园平面图如下:
    在这里插入图片描述

    邻接矩阵

    在这里插入图片描述

    在这里插入图片描述

    (1) 输入形式:输入1个范围1-3的整数,选择功能;若选择功能2,还需输入两个范围1-10的整数,空格隔开
    (2) 输出形式:输出10个景点的编号,名称,简介;输出两个点的最短距离及最短路径
    (3) 程序功能:功能1将会输出10个景点的编号,名称,简介;功能2将会输出两个点的最短距离及最短路径
    (4) 测试数据:
    正确数据:
    第一组:输入1,输出结果为:
    西安工程大学共有以下十处景点:
    1.校医院: 校医院由十几位医护组成,负责医保报销,学生生病诊断等服务

    2.南环操场: 南环操场是田径场,常在此举行运动会,动员会等仪式

    3.计算机科学学院: 计算机科学学院具备多功能机房,是计算机院学生进行实验的地方

    4.锅炉房: 锅炉房负责全校师生的热水供应,是学校后勤保障的重要组成部分

    5.图书馆: 图书馆内藏书三百余万册,是陕西省十佳图书馆之一

    6.东环操场: 东环操场是运动场,具有篮球场,足球场,羽毛球场,网球场等,是学生运动的主要场地

    7.C栋教学楼: C栋教学楼主要是全校学生上英语课的地方

    8.人文学院: 人文学院主要是人文学院学生上课及实验的地方

    9.校门: 校门是西安工程大学的标志型建筑之一,恢弘古典

    10.电子信息学院: 电子信息学院主要承担电信学院学生的日常教学工作,具有精密电子实验室
    第二组:输入2,再输入1 9,输出为:
    校医院->校门的最小路径为:190米
    最短路径为: 校医院-> 图书馆-> 人文学院-> 校门
    第三组:输入2,再输入4 7,输出为:
    锅炉房->C栋教学楼的最小路径为:160米
    最短路径为: 锅炉房-> 图书馆-> 计算机科学学院-> C栋教学楼
    第四组:输入2,再输入6 2,输出为:
    东环操场->南环操场的最小路径为:150米
    最短路径为: 东环操场-> 锅炉房-> 校医院-> 南环操场

    错误数据:
    第一组:输入0,输出:输入错误,请重新输入:
    第二组:输入4,输出:输入错误,请重新输入:
    第三组:输入2,再输入1 45,输出为:输入错误,请重新输入:
    第四组:输入2,再输入3 3,输出为:输入错误,你已经在此地,请重新输入:

    2.程序设计

    <1>函数定义
    (1)GraphCreateGraph() // 初始化图
    (2)Graph
    short_path_floyd(Graph*G,int p[20][20],int d[20][20]) // 弗洛伊德算法,求最短路径
    (3)void print() // 界面函数
    (4)int main() //主函数

    <2>程序流程
    (1) 开始
    (2) 调用CreateGraph()函数进行初始化
    (3) 调用short_path_floyd()函数进行最短路径遍历
    (4) 输入一个整数c,选择功能
    (5) If(c=1),输出各个景点信息,输出后返回第(4)步
    (6) If(c=2),输入两个景点编号,输出两个景点最短路径信息,返回第(4)步
    (7) If(c=3),退出程序,结束

    <3>程序流程图

    在这里插入图片描述

    3.数据存储结构设计
    抽象数据类型定义
    typedef struct Vertex
    {
    int num; //顶点编号
    char name[5000]; //顶点名称
    char jianjie[15000]; //顶点简介
    }Vertex; //结构体定义顶点

    typedef struct Graph
    {
    Vertex vexs[10]; //图中有十个顶点
    int arc[20][20]; //图中两点间的弧线权值,也即路程
    int vnum,e; // 图中顶点个数和边数
    }Graph; //结构体定义图

    5.用户使用说明

    在这里插入图片描述

             图(c)程序界面
    

    程序运行界面如上图所示
    <1>若要查询景点信息,输入1
    <2>若要查询两个景点最短路径,输入2,回车,再输入两个景点编号,空格隔开
    <3>若要退出程序,输入3

    6.测试结果
    正确数据:
    第一组:输入1,输出结果为:
    西安工程大学共有以下十处景点:
    1.校医院: 校医院由十几位医护组成,负责医保报销,学生生病诊断等服务

    2.南环操场: 南环操场是田径场,常在此举行运动会,动员会等仪式

    3.计算机科学学院: 计算机科学学院具备多功能机房,是计算机院学生进行实验的地方

    4.锅炉房: 锅炉房负责全校师生的热水供应,是学校后勤保障的重要组成部分

    5.图书馆: 图书馆内藏书三百余万册,是陕西省十佳图书馆之一

    6.东环操场: 东环操场是运动场,具有篮球场,足球场,羽毛球场,网球场等,是学生运动的主要场地

    7.C栋教学楼: C栋教学楼主要是全校学生上英语课的地方

    8.人文学院: 人文学院主要是人文学院学生上课及实验的地方

    9.校门: 校门是西安工程大学的标志型建筑之一,恢弘古典

    10.电子信息学院: 电子信息学院主要承担电信学院学生的日常教学工作,具有精密电子实验室
    第二组:输入2,再输入1 9,输出为:
    校医院->校门的最小路径为:190米
    最短路径为: 校医院-> 图书馆-> 人文学院-> 校门
    第三组:输入2,再输入4 7,输出为:
    锅炉房->C栋教学楼的最小路径为:160米
    最短路径为: 锅炉房-> 图书馆-> 计算机科学学院-> C栋教学楼
    第四组:输入2,再输入6 2,输出为:
    东环操场->南环操场的最小路径为:150米
    最短路径为: 东环操场-> 锅炉房-> 校医院-> 南环操场

    错误数据:
    第一组:输入0,输出:输入错误,请重新输入:
    第二组:输入4,输出:输入错误,请重新输入:
    第三组:输入2,再输入1 45,输出为:输入错误,请重新输入:
    第四组:输入2,再输入3 3,输出为:输入错误,你已经在此地,请重新输入:

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define jida  32768     // 定义极大值,代表无穷大 
    typedef struct Vertex  
    {
    	int num;  //顶点编号 
    	char name[5000];  //顶点名称 
    	char jianjie[15000];   //顶点简介 
     }Vertex;    //结构体定义顶点 
     
     typedef struct Graph
     {
     	Vertex vexs[11];   //图中有十个顶点 
     	int arc[20][20];   //图中两点间的弧线权值,也即路程 
     	int vnum,e;    // 图中顶点个数和边数 
     }Graph;  //结构体定义图 
     
     Graph*CreateGraph()   //  初始化图 
     {
     	Graph *G;
     	int i,j,k;  
     	G=(Graph*)malloc(sizeof(Graph));  //开辟内存 
     	G->e=18;   //  图有18条边 
     	G->vnum=10;   //   图有十个顶点 
     	for(i=1;i<=G->vnum;i++) 
     	G->vexs[i].num=i;    //初始化顶点编号为1-10 
     	for(j=1;j<=10;j++)   
     	for(k=1;k<=10;k++)
     	{
     	G->arc[j][k]=jida;  // 初始化每两个点间的距离为极大值 
     	}
     	
     	G->arc[1][2]=G->arc[2][1]=50;    //用邻接矩阵存储两点间的权值,依次赋值存储 
     	G->arc[1][5]=G->arc[5][1]=60;    // 未在此赋值的弧,其权值为之前初始化的极大值 
     	G->arc[1][4]=G->arc[4][1]=60;
     	G->arc[2][5]=G->arc[5][2]=75;
     	G->arc[2][3]=G->arc[3][2]=80;
     	G->arc[4][6]=G->arc[6][4]=40;
     	
     	G->arc[4][5]=G->arc[5][4]=40;
     	G->arc[3][5]=G->arc[5][3]=20;
     	G->arc[3][7]=G->arc[7][3]=100;
     	G->arc[5][7]=G->arc[7][5]=400;
     	G->arc[7][8]=G->arc[8][7]=100;
     	G->arc[7][9]=G->arc[9][7]=200;
     	
     	G->arc[8][9]=G->arc[9][8]=30;
     	G->arc[6][8]=G->arc[8][6]=100;
     	G->arc[5][8]=G->arc[8][5]=100;
     	G->arc[5][10]=G->arc[10][5]=400;
     	G->arc[6][10]=G->arc[10][6]=50;
     	G->arc[8][10]=G->arc[10][8]=80;
    
     	strcpy(G->vexs[1].name,"校医院");   //存储图中每个点的名字,依次赋值存储
     	strcpy(G->vexs[2].name,"南环操场");
     	strcpy(G->vexs[3].name,"计算机科学学院");
     	strcpy(G->vexs[4].name,"锅炉房");
     	strcpy(G->vexs[5].name,"图书馆");
     	strcpy(G->vexs[6].name,"东环操场");
     	strcpy(G->vexs[7].name,"C栋教学楼");
     	strcpy(G->vexs[8].name,"人文学院");
     	strcpy(G->vexs[9].name,"校门");
     	strcpy(G->vexs[10].name,"电子信息学院");
     	strcpy(G->vexs[1].jianjie,"校医院由十几位医护组成,负责医保报销,学生生病诊断等服务");    //为图中每个景点存储关于它的简介 
     	strcpy(G->vexs[2].jianjie,"南环操场是田径场,常在此举行运动会,动员会等仪式");
     	strcpy(G->vexs[3].jianjie,"计算机科学学院具备多功能机房,是计算机院学生进行实验的地方");
     	strcpy(G->vexs[4].jianjie,"锅炉房负责全校师生的热水供应,是学校后勤保障的重要组成部分");
     	strcpy(G->vexs[5].jianjie,"图书馆内藏书三百余万册,是陕西省十佳图书馆之一");
     	strcpy(G->vexs[6].jianjie,"东环操场是运动场,具有篮球场,足球场,羽毛球场,网球场等,是学生运动的主要场地");
     	strcpy(G->vexs[7].jianjie,"C栋教学楼主要是全校学生上英语课的地方");
     	strcpy(G->vexs[8].jianjie,"人文学院主要是人文学院学生上课及实验的地方");
     	strcpy(G->vexs[9].jianjie,"校门是西安工程大学的标志型建筑之一,恢弘古典");
     	strcpy(G->vexs[10].jianjie,"电子信息学院主要承担电信学院学生的日常教学工作,具有精密电子实验室");
     	return G;
    }
    
    Graph* short_path_floyd(Graph*G,int p[20][20],int d[20][20])    //  弗洛伊德算法,求最短路径 
    {
    		int v,w,k; // v,w,k分别表示出发点,目的地,新加入的点 
    		for(v=1;v<=G->vnum;v++){
    		for(w=1;w<=G->vnum;w++)
    {
    			d[v][w]=G->arc[v][w]; // d[20][20]代表两点间最短路径,初始化为两点间权值 
    			p[v][w]=w;   //  p[20][20]记录最短路径的前一个点 
    		}
    	}
    	for(k=1;k<=10;k++) //利用三阶循环,找出每两个点的最短路径 
    	{
    		for(v=1;v<=10;v++)
    		{
    			for(w=1;w<=10;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];
    				/* 如果新加入的点组成的路径小于最小路径,更新最小路径,
    				并且将新加入的点加入最短路径中 */ 
    				}
    			}
    		}
    	}
    	return G;  // 返回图的类型 
    }
    
    void print()   //  界面函数 
    {
    	printf("\n\n\n");
    	printf("\t****************************************\t\n");
    	printf("\t*      西安工程大学校园导航系统        *\t\n");
    	printf("\t****************************************\t\n");
    	printf("\t*                                      *\t\n");
    	printf("\t*                                      *\t\n");
    	printf("\t*      1.景点信息查询                  *\t\n");
    	printf("\t*                                      *\t\n");
    	printf("\t*      2.路线信息查询                  *\t\n");
    	printf("\t*                                      *\t\n");
    	printf("\t*      3.退出系统                      *\t\n");
    	printf("\t*                                      *\t\n");
    	printf("\t****************************************\t\n");
    	printf("\n\n请选择你需要的功能,输入代号:\n");
    }
    
    int main()
    {
    	int c,i,f,k,l;  // f,k分别为出发点与目的地编号 
    	Graph *T;
    	int q,w;
    	int d[20][20];  // d[20][20]代表两点间最短路径
     	int p[20][20];  //  p[20][20]记录最短路径的前一个点 
     	system("color 06");  //  改变输出界面颜色 
     	 	for(q=1;q<=10;q++)
     	for(w=1;w<=10;w++)
     	{
     		d[q][w]=jida;    //  任意两点间最短路径初始化为极大值 
     	}
    	T=CreateGraph();   //  调用函数初始化图 
    	T=short_path_floyd(T,p,d);  //调用函数求最短路径 
    	
    	while(1)  
    	{
    		print();     //  输出界面栏 
    		scanf("%d",&c);  //接受选项 
    		while(c>3||c<1)
    		{
    			printf("输入错误,请重新输入:\n");
    			scanf("%d",&c); 
    		}
    		if(c==1)
    		{
    			printf("\n西安工程大学共有以下十处景点:\n");
    			for(i=1;i<=10;i++)
    			{
    				printf("%d.",T->vexs[i].num);   //输出景点编号 
    				printf("%s: ",T->vexs[i].name);   //输出景点名字 
    				printf("%s\n\n",T->vexs[i].jianjie);  // 输出景点简介 
    			}
    		}
    		else if(c==2)
    		{
    			printf("请输入当前景点编号和你想要去的景点编号(空格隔开):\n");
    			scanf("%d %d",&f,&k);   // f,k分别接受出发点与目的地编号 
    			while(f<1||f>10||k<1||k>10)  //非法输入 
    			{
    				printf("输入错误,请重新输入:\n");
    				scanf("%d %d",&f,&k);
    			}
    			if(f==k)  //非法输入 
    			{
    				printf("输入错误,你已经在此地,请重新输入:\n");
    				scanf("%d %d",&f,&k);	
    			}
    			
    			printf("\n%s->%s的最小路径为:%d米\n",T->vexs[f].name,T->vexs[k].name,d[f][k]);
    			l=p[f][k];  // l作为中间变量用来接受最短路径中的父亲节点 
    			printf("最短路径为:   %s",T->vexs[f].name);   // 输出最短路径 
    			while(l!=k)  
    			{
    				printf("-> %s",T->vexs[l].name);
    				l=p[l][k];  //  不断更新l节点 
    			}
    			printf("-> %s\n",T->vexs[k].name);
    				
    		}
    		else
    		    break;  //退出程序 
    	}
    	
    }
    
    更多相关内容
  • 包含一个主程序和15个分程序,使用X-mind画出的烟台大学的平面图和数据结构课程设计最终版实验报告。(主要内容都在报告里,包括项目描述、数据和逻辑结构分析、存储结构分析、主要算法及其复杂度分析、程序实现和...
  • (1) 设计校园平面图,所包含景点少于10个,以图中顶点表示学校各景点,存放景点名称、代号、简介等信息:以边表示路径,存放路径长度等相关信息。注意:设校园平面图是无向图。 (2) 为来访客人提供图中任意...
  • 《算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    本文已收录于专栏 《画解数据结构》 饭食,水饮,题必须刷 C语言免费动漫教程,和我一起打卡! 《光天化日学C语言》 LeetCode 太难?先看简单题! 《C语言入门100例》 数据结构难?存在的! 《画解数据结构》 ...
    本文已收录于专栏
    🌳《画解数据结构》🌳

    🙉饭不食,水不饮,题必须刷🙉

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    LeetCode 太难?先看简单题!
    🧡《C语言入门100例》🧡

    数据结构难?不存在的!
    🌳《画解数据结构》🌳

    闭关刷 LeetCode,剑指大厂Offer!
    🌌《LeetCode 刷题指引》🌌

    LeetCode 太简单?算法学起来!
    💜《夜深人静写算法》💜

    前言

      所谓活到老,学到老,虽然我感觉自己已经学了很多算法了,但是昨天熬夜整理完以后发现,自己还是个弟弟,实在忍不住了,打算把 算法学习路线 发出来,我把整个算法学习的阶段总结成了五个步骤,分别为: 基础语法学习(重要)、语法配套练习、数据结构、算法入门、算法进阶。本文梳理了这五个大项的思维导图,在下文会有详细介绍。
      希望各位能够找到自己的定位,通过自己的努力在算法这条路上越走越远。
      刚开始切勿心浮气躁,千万不要给自己立 flag,说一定要把这么多东西都学会。就算你的精力旺盛,日夜操劳,时间也是有限的。所以,首先是明确我们要做什么,然后制定好一个合理的 目标 ,再一点一点将要学习的内容逐步付诸实践才是最重要的。


    图片较大,文章中有拆解,需要原图可以留言找我要哈

    1、基础语法学习

    • 算法是以编程语言为基础的,所以选择一门编程语言来学习是必须的。
    • 因为作者本身是C/C++技术栈的,所以就拿C语言来举例子吧。如果是 Java、Python 技术栈,可以跳过 C语言相关的内容。这一小节,先给出学习路线图,然后我再来讲,每部分应该如何去学。

    1)HelloWorld

    • 无论是 Java、Python、C/C++,想要上手一门语言,第一步一定是 HelloWorld,先不要急着去配环境。如果环境配了几个小时,可能一开始的雄心壮志就被配环境的过程消磨殆尽,更加不要谈日后的丰功伟业了。

    2)让自己产生兴趣

    • 所以,我们需要让这件事情从一开始就变得 有趣,这样才能坚持下去。比如找一个相对较为有趣的教程,这里我会推荐这个:《光天化日学C语言》。听名字就比较搞笑,可能作者本身也不是什么正经人,哈哈哈!虽然不能作为一个严谨的教程去学,起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
    • 刚才提到的这个系列,可以先收藏起来。回头再去看,它讲述的是 对白式C语言教学,从最简单的输出 HelloWorld 这个字符串开始讲起,逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手,一直致力于 将困难的问题讲明白 。我看了他的大部分教程,基本都能一遍看懂。算了,不装了,摊牌了,因为我就是这个作者。

    3)目录是精髓

    • 然后,我们大致看下你选择的教程的前几个章节,那些标题是否有你认知以外的名词出现,比如以这个思维导图为例。
    • 如果你觉得这些名词中有 3 / 4 以上是没有什么概念的。那么,可能需要补齐一些数学、计算机方面的基础知识。反之,我们就可以继续下一步了。

    4)习惯思考并爱上它

    • 只要对一件事情养成习惯以后,你就会发现,再难的事情,都只是一点一点积累的过程。重要的是,每天学习的过程一定要吃透,养成主动思考的好习惯。因为,越到后面肯定是越难的,如果前期不养成习惯,后面很可能心有余而力不足。
    • 就像刷题,一旦不会做就去找解题报告,最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯,只不过不是一种好习惯罢了。

    5)实践是检验真理的唯一标准

    • 光看教程肯定是不行的,写代码肯定还是要动手的,因为有些语法你看一遍,必定忘记。但是写了几遍,永世难忘。这或许就是写代码的魅力所在吧。
    • 所以,记得多写代码实践哟 (^U^)ノ~YO

    6)坚持其实并没有那么难

    • 每天把教程上的内容,自己在键盘上敲一遍,坚持一天,两天,三天。你会发现,第四天就变成了习惯。所以坚持就是今天做了这件事情,明天继续做。

    7)适当给予正反馈

    • 然而,就算再有趣的教程,看多了都会乏味,这是人性决定的,你我都逃不了。能够让你坚持下去的只有你自己,这时候,适当给予自己一些正反馈就显得尤为重要。比如,可以用一张表格将自己的学习计划记录下来,然后每天都去分析一下自己的数据。
    • 当然,你也可以和我一样,创建一个博客,然后每天更新博文,就算没有内容,也坚持日更,久而久之,你会发现,下笔如有神,键盘任我行!更新的内容,可以是自己的学习笔记,心路历程 等等。
    • 看着每天的粉丝量呈指数级增长,这是全网对你的认可,应该没有什么会是比这个更好的正反馈了。
    • 那么,至此,不知道屏幕前的你感想如何,反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了!
    • 介于篇幅,我会把C语言基础的内容,放在这个专栏 《光天化日学C语言》 里面去讲,一天更新一篇,对啊,既然说了要坚持,要养成习惯,我当然也要做到啦~如果你学到了哪一章,可以在评论区评论 “打卡” ,也算是一种全网见证嘛!
    • 我也很希望大家的学习速度能够超越我的更新速度。

    2、语法配套练习

    • 学习的过程中,做题当然也是免不了的,还是应征那句话:实践是检验真理的唯一标准。
    • 而这里的题库,是我花了大量时间,搜罗了网上各大C语言教程里的例题,总结出来的思维导图,可以先大致看一眼:

    • 从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序 等几个方面,总结出的具有概括性的例题 100 道 《C语言入门100例》,目前还在更新中。
    • 这里可以列举几个例子:

    1、例题1:交换变量的值

    一、题目描述

      循环输入,每输入两个数 a a a b b b,交换两者的值后输出 a a a b b b。当没有任何输入时,结束程序。

    二、解题思路

    难度:🔴⚪⚪⚪⚪

    • 这个题的核心是考察如何交换两个变量的值,不像 python,我们可以直接写出下面这样的代码就实现了变量的交换。
    a, b = b, a
    
    • 在C语言里,这个语法是错误的。
    • 我们可以这么理解,你有两个杯子 a a a b b b,两个杯子里都盛满了水,现在想把两个杯子里的水交换一下,那么第一个想到的方法是什么?

    当然是再找来一个临时杯子:
      1)先把 a a a 杯子的水倒进这个临时的杯子里;
      2)再把 b b b 杯子的水倒进 a a a 杯子里;
      3)最后把临时杯子里的水倒进 b b b 杯子;

    • 这种就是临时变量法,那么当然,还有很多很多的方法,接下来就让我们来见识一下吧。

    三、代码详解

    1、正确解法1:引入临时变量

    #include <stdio.h>
    int main() {
        int a, b, tmp;
    	while (scanf("%d %d", &a, &b) != EOF) {
    	    tmp = a;   // (1)
    	    a = b;     // (2)
    	    b = tmp;   // (3)
    	    printf("%d %d\n", a, b);
    	}
    	return 0;
    }
    
    • ( 1 ) (1) (1) tmp = a;表示把 a a a 杯子的水倒进这个临时的杯子里;
    • ( 2 ) (2) (2) a = b;表示把 b b b 杯子的水倒进 a a a 杯子里;
    • ( 3 ) (3) (3) b = tmp;表示把临时杯子里的水倒进 b b b 杯子里;
    • 这三步,就实现了变量 a a a b b b 的交换。

    2、正确解法2:引入算术运算

    #include <stdio.h>
    int main() {
        int a, b;
    	while (scanf("%d %d", &a, &b) != EOF) {
    	    a = a + b;   // (1)
    	    b = a - b;   // (2)
    	    a = a - b;   // (3)
    	    printf("%d %d\n", a, b);
    	}
    	return 0;
    }
    
    • ( 1 ) (1) (1) a = a + b;执行完毕后,现在最新的a的值变成原先的a + b的值;
    • ( 2 ) (2) (2) b = a - b;执行完毕后,相当于b的值变成了a + b - b,即原先a的值;
    • ( 3 ) (3) (3) a = a - b;执行完毕后,相当于a的值变成了a + b - a,即原先b的值;
    • 从而实现了变量ab的交换。

    3、正确解法3:引入异或运算

    • 首先,介绍一下C语言中的^符号,代表的是异或。
    • 二进制的异或,就是两个数转换成二进制表示后,按照位进行以下运算:
    左操作数右操作数异或结果
    000
    110
    011
    101
    • 也就是对于 0 和 1,相同的数异或为 0,不同的数异或为 1。
    • 这样就有了三个比较清晰的性质:
    • 1)两个相同的十进制数异或的结果一定位零。
    • 2)任何一个数和 0 的异或结果一定是它本身。
    • 3)异或运算满足结合律和交换律。
    #include <stdio.h>
    int main() {
        int a, b;
    	while (scanf("%d %d", &a, &b) != EOF) {
    	    a = a ^ b;   // (1)
    	    b = a ^ b;   // (2)
    	    a = a ^ b;   // (3)
    	    printf("%d %d\n", a, b);
    	}
    	return 0;
    }
    
    • 我们直接来看 ( 1 ) (1) (1) ( 2 ) (2) (2) 这两句话,相当于b等于a ^ b ^ b,根据异或的几个性质,我们知道,这时候的b的值已经变成原先a的值了。
    • 而再来看最后一句话,相当于a等于a ^ b ^ a,还是根据异或的几个性质,这时候,a的值已经变成了原先b的值。
    • 从而实现了变量ab的交换。

    4、正确解法4:奇淫技巧

    • 当然,由于这个题目问的是交换变量后的输出,所以它是没办法知道我程序中是否真的进行了交换,所以可以干一些神奇的事情。比如这么写:
    #include <stdio.h>
    int main() {
        int a, b;
    	while (scanf("%d %d", &a, &b) != EOF) {
    	    printf("%d %d\n", b, a);
    	}
    	return 0;
    }
    
    • 你学废了吗 🤣?

    2、例题2:整数溢出

    一、题目描述

      先输入一个 t ( t ≤ 100 ) t (t \le 100) t(t100),然后输入 t t t 组数据。每组输入为 4 个正整数 a , b , c , d ( 0 ≤ a , b , c , d ≤ 2 62 ) a,b,c,d(0 \le a,b,c,d \le 2^{62}) a,b,c,d(0a,b,c,d262),输出 a + b + c + d a+b+c+d a+b+c+d 的值。

    二、解题思路

    难度:🔴🔴⚪⚪⚪

    • 这个问题考察的是对补码的理解。
    • 仔细观察题目给出的四个数的范围: [ 0 , 2 62 ] [0, 2^{62}] [0,262],这四个数加起来的和最大值为 2 64 2^{64} 264。而C语言中,long long的最大值为: 2 63 − 1 2^{63}-1 2631,就算是unsigned long long,最大值也只有 2 64 − 1 2^{64}-1 2641
    • 但是我们发现,只有当四个数都取得最大值 2 62 2^{62} 262 时,结果才为 2 64 2^{64} 264,所以可以对这一种情况进行特殊判断,具体参考代码详解。

    三、代码详解

    #include <stdio.h>
    typedef unsigned long long ull;                           // (1)
    const ull MAX = (((ull)1)<<62);                           // (2)
    
    int main() {
    	int t;
    	ull a, b, c, d;
    	scanf("%d", &t);
    	while (t--) {
    		scanf("%llu %llu %llu %llu", &a, &b, &c, &d);     // (3)
    		if (a == MAX && b == MAX && c == MAX && d == MAX) // (4)
    			printf("18446744073709551616\n");             // (5)
    		else
    			printf("%llu\n", a + b + c + d);              // (6)
    	}
    	return 0;
    }
    
    • ( 1 ) (1) (1) 由于这题数据量较大,所有数据都需要用64位无符号整型。ull作为unsigned long long的别名;
    • ( 2 ) (2) (2) 用常量MAX表示 2 62 2^{62} 262,这里采用左移运算符直接实现 2 2 2 是幂运算;
    数学C语言
    2 n 2^n 2n1<<n
    • 需要注意的是,由于 1 是int类型,所以需要对 1 进行强制转换。(ull)1等价于(unsigned long long)1
    • ( 3 ) (3) (3) %llu是无符号64位整型的输入方式;
    • ( 4 ) (4) (4) 这里是对所有数都等于最大值的特殊判断,&&运算符的优先级低于==,所以这里不加括号也没事;
    • ( 5 ) (5) (5) 由于 2 64 2^{64} 264 是无法用数字的形式输出的,所以我们提前计算机算好以后,用字符串的形式进行输出;
    • ( 6 ) (6) (6) 其它情况都在 [ 0 , 2 64 − 1 ] [0, 2^{64}-1] [0,2641] 范围内,直接相加输出即可。

    3、数据结构

    • 《C语言入门100例》上的例题,如果能理解前面 25 道,那基本C语言的学习就可以告一段落了,接下来就要开始我们的数据结构的学习了。

    1、什么是数据结构

    • 你可能听说过 数组、链表、队列、栈、堆、二叉树、图,没错,这些都是数据结构,但是你要问我什么是数据结构,我突然就一脸懵逼了。
    • 如果一定要给出一个官方的解释,那么它就是:

    计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。

    • 是不是还不如说它是堆,是栈,是队列呢?
    • 是这样的,我们学习的过程中,跳过一些不必要的概念,能够节省我们更多的时间,从而达到更好的效果,当你还在理解数据结构是什么的时候,可能人家已经知道了栈有哪些操作了。

    2、数据结构和算法的关系

    • 很多同学搞不明白,数据结构与算法有哪些千丝万缕的关系?甚至有些同学以为算法里本身就包含了数据结构。
    • 数据结构主要讲解数据的组织形式,比如链表,堆,栈,队列。
    • 而算法,则注重的是思想,比如链表的元素怎么插入、删除、查找?堆的元素怎么弹出来的?栈为什么是先进后出?队列又为什么是先进先出?
    • 讲得直白一点,数据结构是有实体的,算法是虚拟的;数据结构是物质上的,算法是精神上的。当然,物质和精神 缺一不可。

    3、数据结构概览

    • 周末花了一个下午整理的思维导图,数据结构:
    • 数据结构相关入门可以参考以下文章:数据结构入门

    4、算法入门

    • 算法入门,其实就是要开始我们的刷题之旅了。先给出思维导图,然后一一介绍入门十大算法。
    • 十个最基础的算法可以参考以下文章:算法入门精选

    5、算法进阶

    • 算法进阶这块是我打算规划自己未来十年去完成的一个项目,囊括了 大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法 的算法全集,也就是之前网络上比较有名的 《夜深人静写算法》 系列,这可以说是我自己对自己的一个要求和目标吧。
    • 如果只是想进大厂,那么 算法入门 已经足够了,不需要再来看算法进阶了,当然如果对算法有浓厚兴趣,也欢迎和我一起打卡。由于内容较难,工作也比较忙,所以学的也比较慢,一周基本也只能更新一篇。

    这个系列主要分为以下几个大块内容:
      1)图论
      2)动态规划
      3)计算几何
      4)数论
      5)字符串匹配
      6)高级数据结构(课本上学不到的)
      7)杂项算法

    • 先来看下思维导图,然后我大致讲一下每一类算法各自的特点,以及学习方式:

    在这里插入图片描述

    1)图论

    1、搜索概览

    • 图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能,给出人类制定好的规则,枚举出所有可行的情况,找到可行解或者最优解。
    • 比较常见的搜索算法是 深度优先搜索(又叫深度优先遍历) 和 广度优先搜索(又叫广度优先遍历 或者 宽度优先遍历)。各种图论的算法基本都是依靠这两者进行展开的。

    2、深度优先搜索

    • 深度优先搜索一般用来求可行解,利用剪枝进行优化,在树形结构的图上用处较多;而广度优先搜索一般用来求最优解,配合哈希表进行状态空间的标记,从而避免重复状态的计算;
    • 原则上,天下万物皆可搜,只是时间已惘然。搜索会有大量的重复状态出现,这里的状态和动态规划的状态是同一个概念,所以有时候很难分清到底是用搜索还是动态规划。
    • 但是,大体上还是有迹可循的,如果这个状态不能映射到数组被缓存下来,那么大概率就是需要用搜索来求解的。
    • 如图所示,代表的是一个深度优先搜索的例子,红色实箭头表示搜索路径,蓝色虚箭头表示回溯路径。
    • 红色块表示往下搜索,蓝色块表示往上回溯,遍历序列为:
    	0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
    
    • 同样,搜索的例子还有:
    • 计算的是利用递归实现的 n n n 的阶乘。

    3、记忆化搜索

    • 对于斐波那契函数的求解,如下所示:
    • f ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) = \begin{cases}1 & (n = 0) \\1 & (n = 1) \\f(n-1) + f(n-2) & (n > 2) \end{cases} f(n)=11f(n1)+f(n2)(n=0)(n=1)(n>2)
    • 对于 f ( 5 ) f(5) f(5) 的求解,程序调用如下:
      在这里插入图片描述
    • 这个过程用到了很多重复状态的搜索,我们需要将它优化,一般将一些状态缓存起来。
    • 我们通过一个动图来感受一下:
      在这里插入图片描述
    • 当第二次需要计算 f ( 2 ) f(2) f(2) f ( 3 ) f(3) f(3) 时,由于结果已经计算出来并且存储在 h [ 2 ] h[2] h[2] h [ 3 ] h[3] h[3] 中,所以上面这段代码的fib != inf表达式为真,直接返回,不再需要往下递归计算,这样就把原本的 “递归二叉树” 转换成了 “递归链”, 从而将原本指数级的算法变成了多项式级别。
    • 这就是记忆化搜索,像这种把状态缓存起来的方法,就是动态规划的思想了。

    4、广度优先搜索

    • 单向广搜就是最简化情况下的广度优先搜索(Breadth First Search),以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路,就是广搜的加强版。
    • 我们通过一个动图来对广搜有一个初步的印象。

    • 从图中可以看出,广搜的本质还是暴力枚举。即对于每个当前位置,枚举四个相邻可以行走的方向进行不断尝试,直到找到目的地。有点像洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水灌溉,所以我们也把这种算法称为 FloodFill。
    • 那么,如何把它描述成程序的语言呢?这里需要用到一种数据结构 —— 队列。
    • 这时候,算法和数据结构就完美结合了。

    2)动态规划

    动态规划算法三要素:
      ①所有不同的子问题组成的表;
      ②解决问题的依赖关系可以看成是一个图;
      ③填充子问题的顺序(即对②的图进行拓扑排序,填充的过程称为状态转移);

    • 如果子问题的数目为 O ( n t ) O(n^t) O(nt),每个子问题需要用到 O ( n e ) O(n^e) O(ne) 个子问题的结果,那么我们称它为 tD/eD 的问题,于是可以总结出四类常用的动态规划方程:(下面会把opt作为取最优值的函数(一般取 m i n min min m a x max max ), w ( j , i ) w(j, i) w(j,i)为一个实函数,其它变量都可以在常数时间计算出来)。

    1、1D/1D

    • d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d[i] = opt( d[j] + w(j, i) | 0 <= i < j ) d[i]=opt(d[j]+w(j,i)0<=i<j)
    • 状态转移如图四所示(黄色块代表 d [ i ] d[i] d[i],绿色块代表 d [ j ] d[j] d[j]):
    • 这类状态转移方程一般出现在线性模型中。

    2、2D/0D

    • d [ i ] [ j ] = o p t ( d [ i − 1 ] [ j ] + x i , d [ i ] [ j − 1 ] + y j , d [ i − 1 ] [ j − 1 ] + z i j ) d[i][j] = opt( d[i-1][j] + x_i, d[i][j-1] + y_j, d[i-1][j-1] + z_{ij} ) d[i][j]=opt(d[i1][j]+xi,d[i][j1]+yj,d[i1][j1]+zij)
    • 状态转移如图四所示:
    • 比较经典的问题是最长公共子序列、最小编辑距离。
    • 有关最长公共子序列的问题,可以参考以下文章:夜深人静写算法(二十一)- 最长公共子序列
    • 有关最小编辑距离的问题,可以参考以下文章:夜深人静写算法(二十二)- 最小编辑距离

    3、2D/1D

    • d [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k − 1 ] + d [ k ] [ j ] ) d[i][j] = w(i, j) + opt( d[i][k-1] + d[k][j] ) d[i][j]=w(i,j)+opt(d[i][k1]+d[k][j])
    • 区间模型常用方程,如图所示:
      在这里插入图片描述
    • 另外一种常用的 2D/1D 的方程为:
    • d [ i ] [ j ] = o p t ( d [ i − 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[i][j] = opt( d[i-1][k] + w(i, j, k) | k < j ) d[i][j]=opt(d[i1][k]+w(i,j,k)k<j)

    4、2D/2D

    • d [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[i][j] = opt( d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j) d[i][j]=opt(d[i][j]+w(i,j,i,j)0<=i<i,0<=j<j)
    • 如图所示:
      在这里插入图片描述
    • 常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。
    • 对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是 O ( n t + e ) O(n^ {t+e}) O(nt+e),空间复杂度是 O ( n t ) O(n^t) O(nt) 的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,后续章节将详细讲解各种情况下的动态规划优化算法。

    3)计算几何

    • 计算几何的问题是代码量最大的。它是计算机科学的一个分支,以往的解析几何,是用代数的方法,建立坐标系去解决问题,但是很多时候需要付出一些代价,比如精度误差,而计算几何更多的是从几何角度,用向量的方法来尽量减少精度误差,例如:将除法转化为乘法、避免三角函数等近似运算 等等。
    • 如果一个比赛中,有一道计算几何的题,那么至少,它不会是一道水题。

    1、double 代替 float

    • c++ 中 double 的精度高于 float,对精度要求较高的问题,务必采用 double;

    2、浮点数判定

    • 由于浮点数(小数)中是有无理数的,即无限不循环小数,也就是小数点后的位数是无限的,在计算机存储的时候不可能全部存下来,一定是近似的存储的,所以浮点数一定是存在精度误差的(实际上,就算是有理数,也是存在误差的,这和计算机存储机制有关,这里不再展开,有兴趣可以参见我博客的文章:C++ 浮点数精度判定);
    • 两个浮点数是否相等,可以采用两数相减的绝对值小于某个精度来实现:
    const double eps = 1e-8;
    bool EQ(double a, double b) {
        return fabs(a - b) < eps;
    }
    
    • 并且可以用一个三值函数来确定某个数是零、大于零还是小于零:
    int threeValue(double d) {
        if (fabs(d) < eps)
            return 0;
        return d > 0 ? 1 : -1;
    }
    

    3、负零判定

    • 因为精度误差的存在,所以在输出的时候一定要注意,避免输出 -0.00:
        double v = -0.0000000001;
        printf("%.2lf\n", v);
    
    • 避免方法是先通过三值函数确定实际值是否为0,如果是0,则需要取完绝对值后再输出:
        double v = -0.0000000001;
        if(threeValue(v) == 0) {
            v = fabs(v);
        }
        printf("%.2lf\n", v);
    

    4、避免三角函数、对数、开方、除法等

    • c++ 三角函数运算方法采用的是 CORDIC算法,一种利用迭代的方式进行求解的算法,其中还用到了开方运算,所以实际的算力消耗还是很大的,在实际求解问题的过程中,能够避免不用就尽量不用。
    • 除法运算会带来精度误差,所以能够转换成乘法的也尽量转换为乘法运算。

    5、系统性的学习

    基础知识:点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积;
    进阶知识:多边形面积、凸多边形判定、点在多边形内判定;
    相关算法:二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。

    • 学习计算几何,最好是系统性的,刷题的过程中不断提炼出自己的模板。

    4)数论

    • 刷题的时候遇到不会的数论题,真的是很揪心,从头学起吧,内容实在是太多了,每个知识点都要证明吃透,不然下次遇到还是不会;不学吧,又不甘心,就是单纯的想把这个题过了,真是进退两难!
    • 数论对一个人的数学思维要求较高,但是一般也是一些固定的模式,所以把模板整理出来很重要。
    • 当然,数论也有简单问题,一般先做一些入门题提升信心。

    1、数论入门

    • 主要是一些基本概念,诸如:
    • 整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和 最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节;

    2、数论四大定理

    • 这四个定理学完,可以KO很多题:
    • 欧拉定理、中国剩余定理、费马小定理、威尔逊定理

    3、数论进阶

    • 系统性的学习,基本也就这些内容了:
    • 扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。

    5)字符串匹配

    • 字符串匹配学习路线比较明确。
    • 先学习前缀匹配:字典树。
    • 然后可以简单看一下回文串判定算法:Manacher。
    • 以及经典的单字符串匹配算法:KMP。
    • 实际上平时最常用的还是 BM 算法,而ACM中基本不考察。
    • 然后就是较为高阶的 前缀自动机、后缀数组、后缀树、后缀自动机了。

    • 关于 《画解数据结构》学习路线 的内容到这里就结束了。
    • 如果还有不懂的问题,可以 「 想方设法 」找到作者的「 联系方式 」 ,随时线上沟通。

    展开全文
  • 假设有一些代码用来从字符串的固定位置中取出具体的数据(比如从一个平面文件或类似的格式:平面文件flat file是一种包含没有相对关系结构的记录文件): ########...
  • 空间数据结构

    千次阅读 2021-10-22 17:08:19
    空间分割、引擎场景图、场景管理,CSG、光追加速等等都需要用到空间数据结构,它是一些通用的算法抽象,主要用于空间2D 、3D等等所以才称为空间数据结构,我这次是做了PPT、研究讨论最后演讲也分享部分出来~

    空间数据结构我这个是项目中用来解决一些问题,包括在引擎中的场景管理!做了一个ppt来演讲,所以地下有的直接就用ppt的内容或者截图~
    二维下使用四叉树、Kd-tree等等在三维下使用八叉树、bvh-tree、BSP-tree
    BVH-tree在动态场景下使用(游戏使用的最多);Oc-tree八叉树是对于室外大场景来说的;BSP-tree是对于室内场景;
    用途:场景管理、碰撞检测、LOD、光线追踪、 视椎体面剔除、几何加速;

    KD-tree(以光追为例)

    其每次将空间划分为两部分,且划分依次沿着x-axis,y-axis,z-axis,即如图中所示,第一次横着将2维空间分为上下,第二次再竖着将上下两个子空间分别划分为左右部分,依次递归划分,终止条件与八叉树类似,但是是以空间划分为依据;
    在这里插入图片描述

    循环以下步骤:
    1 依次沿着x-axis,y-axis,z-axis划分,使得空间被划分的更加平衡
    2 划分的位置由空间中三角面的分布决定,具体细节不展开
    3 叶子节点存储对应空间的所有物体或三角面信息,中间节点仅存储指针指向两个子空间
    4 当划分空间太小或是子空间内只有少量三角形则停止划分
    区别:直接对空间进行划分,都是二分空间!比如先左右划分当前场景,再对子场景进行上下的划分

    优点:
    利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交,那么则可以省略该部分空间所有子空间的判断过程,在原始的纯粹的AABB之上更进一步提升了加速效率。
    缺点:
    缺点是判断包围盒与三角面的是否相交较难,因此划分的过程不是那么想象的简单,其次同一个三角面可能被不同的包围盒同时占有,这两个不同包围盒内的叶节点会同时存储这一个三角形面
    近十年来 用的比较少;

    层次包围盒树 (Bounding Volume Hierarchy Based On Tree)

    不再以空间作为划分依据,而是从对象的角度考虑,即三角形面(主要是应用于动态场景)

    层次包围盒树(BVH树)是一棵多叉树,用来存储包围盒形状。它的根节点代表一个最大的包围盒,其多个子节点则代表多个子包围盒。此外为了统一化层次包围盒树的形状,它只能存储同一种包围盒形状。 算法核心大概:形状的位移/旋转/伸缩更新对应的叶节点,然后一级一级更新上面的节点,使它们的包围体包住子节点, 构造时间复杂度只有O(NlogN)。
    在这里插入图片描述

    区别:利用了Bounding box(AABB)从物体来开始划分

    **优点:**现代用的最多
    1、每次划分一般选择最长的那一轴划分,假设是x轴,那么划分点选择所有三角面的重心坐标在x坐标上的中位数进行划分,如此便能保证划分的三角形左右两边三角形数量尽可能差不多,当然也就使得树形结构建立的更加平衡,深度更小,平均搜索次数更少,提高了效率,这些都是数据结构的知识,相信大家掌握的都不错,就不多赘述了。
    2、与KD-Tree一样,中间节点不存储物体三角面信息,只在叶节点中存储,终止条件可设定为当前包围盒内三角形数量足够少 (e.g. 5个)

    四叉树与八叉树:

    二维使用四叉树、
    在这里插入图片描述
    三维是使用的八叉树(室外大场景)为了防止满树,优化需要线性八叉树(tree本质上就是数组)
    在这里插入图片描述
    递归分割立方体

    • F: 子立方体被场景内容填充满内容标记为F(full)该子立方体不再被分割;

    • E:子立方体没有场景内容标记为E(empty)该子立方体不再被分割;

    • 叶子节点是F或E;(缺点)

    松散四叉树/八叉树:减少边界问题

    解决四叉树/八叉树一个问题,物体有可能在边界处来回(即在A象限也在B象限),从而导致物体总是在切换节点,从而不得不断更新四叉树/八叉树。除此之外较小的物体可能因为其特殊位置被存储到一个具有非常大的包围盒体积的八叉树节点中。

    在《Game Programming
    Gems》中该问题被描述为层次划分过程中产生的“粘性(Sticky)”区域,较小的物体却保持在树的较高层次,降低了划分的效率

    在这里插入图片描述

    而松散四叉树/八叉树正是解决这种边界问题的一种方式:

    1. 首先它定义一个节点有入口边界(inner boundary),出口边界(outerboundary)。
    2. 判定一个物体现在在哪个节点
    3. 若物体还没添加进四叉树/八叉树,则检测现在位于哪个节点的入口边界内;
    4. 若物体先前已经存在于某个节点,则先检测现在是否越出该节点的出口边界,若越出再检测位于哪个节点的入口边界内。

    在非松散的四叉树/八叉树中,入口边界和出口边界是一样的。而松散四叉树/八叉树的松散,是指出口边界比入口边界要稍微宽些(各节点的出口边界也会发生部分重叠,松散比较符合这种描述),从而使节点不容易越过出口边界,减少了物体切换节点的次数。
    随之而来一个问题就是,如何定义出口边界的长度。因为太短会退化成正常四叉树/八叉树,太长又可能会导致节点存储冗余的物体。而在一篇关于松散四叉树/八叉树的论文里,实验表明出口边界长度为入口边界2倍时可以表现得很好。

    线性八叉树:

    在这里插入图片描述

    BSP树(Binary Space Partitioning Tree):二叉空间分割

    在游戏工业算是老功臣了,第一次被应用用是在1993年的商业游戏《DOOM》上,可是随时渲染硬件的进步,基于BSP树的渲染慢慢淘汰。但是即使在今天,BSP仍是在其他分支(引擎编辑器)不可或缺的一个重要数据结构。
    (用在室内场景)用空间超平面,递归的将空间分割为凸多面体,用二叉树表示被分割的的空间(AVL树),场景中的平面都有前平面与后平面(平面法向量的为前平面)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 数据结构课设 校园导游
  • 该程序运行为实现设计我们的学校的平面图,包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 以方便进一步初次来观光和了解我们学校,找到...
  • 为了支持新的网络体系结构,Openflow通过管道基于多个表实现流转发,这增加了实现的难度。随着多核CPU的问世,提出了一... LabelCast提供了可靠的可编程数据平面,并且可以加载多种网络体系结构,以促进Internet创新。
  • 数据结构 课程设计报告 :校园导航系统

    千次阅读 多人点赞 2020-07-14 22:30:51
    完整代码及文档已上传 一 . 设计目的 随着高校的发展,校园面积不断扩大,校园内跨区域活动频繁,为了给校内师生和校外人士办公、教学、生活...设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且

    完整代码及文档已上传https://download.csdn.net/download/qq_45772158/12615918
    一 . 设计目的

    随着高校的发展,校园面积不断扩大,校园内跨区域活动频繁,为了给校内师生和校外人士办公、教学、生活等方面带来更大的便利,以及面对校园信息化建设的全面推广和迅猛发展,本系统,将通过迪杰斯特拉和弗洛伊德算法,求出所需最短路径,进一步加强数字化校园建设。

    二 . 设计内容和要求
    图的最短路径问题是指从指定的某一点v开始,求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。
    设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所最短路径(即用迪杰斯特拉算法),以及从任意场所到达所有场所的最短路径(即用弗洛伊德算法)。 功能要求:
    (1)输出顶点信息:将校园内各景点输出。
    (2)输出边的信息:将校园内每两个位置(若两个位置之间有直接路径)的距离输出。
    (3)修改:修改两个位置(若两个位置之间有直接路径)的距离,并重新输出每两个位置(若两个位置之间有直接路径)的距离;
    (4)求最短路径:输出给定两点之间的最短路径的长度及途经的地点,输出任意一点与其他各点的最短路径。

    三 . 校园导航系统模块图

    //迪杰斯特拉算法流程图

    在这里插入图片描述

    //弗洛伊德算法流程图

    在这里插入图片描述

    四、编码实现

    1.结点结构体
    typedef struct
    {
    char name[30]; //结点名称int num; //结点编号
    }VEXTYPE;
    typedef struct
    {
    VEXTYPE vexs[LENGTH];//结点value arcs[LENGTH][LENGTH];//弧
    int vexnum,arcnum ;//结点数和最大路径
    }MGraph;//邻接矩阵

    2.输出学校内各地点
    void PutOutVex(MGraph *G) // 功能 1 输出学校内各地点
    {
    for(int i=0;ivexnum;i++) cout<vexs[i].name<<" " <<endl;
    }

    利用for循环,将数组中的数据输出

    3.输出每两个直接相连地点的距离
    void PutOutArc(MGraph *G) // 功能 2 输出每两个直接相连地点的距离
    {
    for(int i=0;ivexnum;i++)
    for(int j=0;jvexnum;j++) if(G->arcs[i][j]<MAX)
    {
    cout <vexs[i].name<<"------>"<vexs[j].name<<" 的距离为 " <arcs[i][j]<<endl;
    }
    }

    利用两个for循环,将数据输出。利用MAX,可将不相邻顶点设置为距离无穷大 。

    4.修改两个地址距离
    void Change(MGraph *G) // 功能 3 修改:修改两个地址距离
    {
    int v0,v1,length;
    cout<<" 修改:请输入起始顶点 :\n"; cin>>v0;
    if(v0<0||v0>G->vexnum)
    {
    cout<<" 此点不存在 ! 请重新输入顶点 :"; cin>>v0;
    }
    cout<<" 请输入结束顶点 :\n"; cin>>v1;
    if(v1<0||v1>G->vexnum)
    {
    cout<<" 此点不存在 ! 请重新输入顶点 :"; cin>>v1;
    }

    cout<<" 输入距离 :"; cin>>length;
    G->arcs[v0][v1]=G->arcs[v1][v0]=length;
    }

    利用if语句,判断输入结点位置是否符合要求,同时保存两结点双向位置

    5.使用 Dijkstra 算法求解最短路径
    void Dijkstra(MGraph * G) // 功能 4. 求最短路径 输出两地点之间最短路径 使用 Dijkstra 算法求解最短路径
    {
    int v,w,i,min,t=0,x,v0,v1;
    int final[20], D[20], p[20][20]; cout<<" 请输入起始顶点 :\n"; cin>>v0;
    if(v0<0||v0>G->vexnum)
    {
    cout<<" 此点不存在 ! 请重新输入顶点 :"; cin>>v0;
    }
    cout<<" 请输入结束顶点 :\n"; cin>>v1;
    if(v1<0||v1>G->vexnum)
    {
    cout<<" 此点不存在 ! 请重新输入顶点 :"; cin>>v1;
    }
    for(v=0;vvexnum;v++)
    {
    final[v]=0;
    D[v]=G->arcs[v0][v]; for(w=0;wvexnum;w++) p[v][w]=0;
    if(D[v]<MAX)
    {
    p[v][v0]=1;p[v][v]=1;
    }
    }
    D[v0]=0;final[v0]=1; for(i=1;ivexnum;i++)
    {
    min=MAX;
    for(w=0;wvexnum;w++) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=1;
    for(w=0;wvexnum;w++) if(!final[w]&&(min+G->arcs[v][w]<D[w]))
    {
    D[w]=min+G->arcs[v][w]; for(x=0;xvexnum;x++)
    p[w][x]=p[v][x]; p[w][w]=1;
    }
    }
    cout<<" 从 “<vexs[v0].name<<” 到 “<vexs[v1].name<<” 的最短路径长度为 :
    “<<D[v1]<<endl;
    cout<<” 途经的景点 : "<<endl; for(int j=0;jvexnum;j++)
    {
    if(p[v1][j]==1)
    cout<vexs[j].name<<endl;
    }
    }

    (1)初始化:先找处从源点V0到各终点V1的直达路径(V0,V1),即通过一条弧到达的路 径。
    (2)选择:从这些路径中找出一条长度最短的路径(V0,x)。
    (3)更新:然后对其余各条路径进行适当的调整:
    若在图中存在弧(x,V1),且(x,V1)+(V0,x)<(V0,V1),则以路径(V0,x,V1)代替
    (V0,V1)。
    (4)在调整后的各条路径中,再找长度最短的路径,以此类推。

    五、实验结果与分析

    1.页面展示

    在这里插入图片描述

    2.输出学校内各地点
    在这里插入图片描述

    3.输出每两个直接相连地点的距离

    在这里插入图片描述
    4.修改两个地点距离

    在这里插入图片描述
    在这里插入图片描述

    (当输入的顶点不符合要求时)
    在这里插入图片描述

    5.两地点之间最短路径
    在这里插入图片描述

    校门–>13公寓 20
    13公寓–>操场 70
    操场–>大活 70
    大活–>篮球场 70 20+70*3=230

    六、总结
    本次课设对于我本人来说还是有些难度,编写过程遇到了很多问题,算法功能也有不足之处,尤其是在输出最短路径输出时总是输出空白。通过询问老师与同学,解决了这些问题。通过本次课程设 计,锻炼了自己的耐心,确实有些问题很难修改,但改出来很有成就感,希望后面加以总结,并继续学习下去。

    展开全文
  • 《算法和数据结构》从语言到算法的过渡篇

    万次阅读 多人点赞 2021-09-22 07:47:08
    《算法和数据结构》学习路线总纲
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    图是一种很重要的数据结构解释。
  • 文章目录第一节 地理空间及其表达第二节 空间数据采集第三节 属性数据采集第四节 空间数据格式转换第五节 空间数据质量 第一节 地理空间及其表达 1.1 地理空间 地理空间上至大气电离层,下至地幔莫霍面,是生命过程...
  • 数据结构课设之校园导航系统(迪杰斯特拉算法)

    千次阅读 多人点赞 2021-06-02 16:47:17
    根据设计要求确定导航系统中建立学校平面图的图形数据结构,查询给定建筑信息,找出任意起始点与终点的最佳路径等基本功能实现的方案,画出流程图,并对各部分功能进行说明。 3.程序设计 设计一个校园导航系统,...
  • 数据结构课程设计~校园导航问题

    千次阅读 多人点赞 2019-01-12 16:15:31
    下边发一下数据结构的课程设计:校园导航问题。 设计内容 (1)设计学校的平面图(至少包括10个以上的场所)。每两个场所间可以有不同的路径,且路长也可能不同(图形结构要求通过键盘输入数据后采用创建图的算法...
  • 问题处理涉及图模型、单源最短路径问题的Dijkstra算法、旅行商问题的回溯和分支限界算法以及相关数据在文件中的存储和使用,是对相关内容的综合利用和整合。设计过程基于构建相关问题模型并围绕软件生存周期展开,从...
  • 半边数据结构讲解

    万次阅读 多人点赞 2017-11-15 19:16:40
    在介绍半边数据结构之前,必须先要科普一下计算机图形学中,模型的几何表达。 对于一般的几何模型,在计算机图形学上早已有相关的数学模型来表达,而且这些表达已经标准化了。 例如对于机械行业的CAD来说,模型...
  • 数据结构作业--西邮校园导航

    千次阅读 2018-04-24 19:51:43
    介绍学习了数据结构课程中的一些简单的数据结构之后,用C语言和数据结构中的一些知识实现一个简易的学校的导航系统。 基本上的功能如下:数据结构采用图来存储信息,根据百度地图抽象出图的结构使用的是邻接矩阵,...
  • 关系数据数据之间有包含关系、层级关系、分流情况、联结关系等; 地理型数据包含地理型信息的数据,如国家、省份、城市、行政区、经纬度等。 1、区间型数据可视化 通过阅读资料可知,区间型数据大致分为...
  • 本人是某大学计算机的菜鸡,在数据结构上机课作业完成过程中,曾上网找了很多类似代码寻找思路,但是网上的代码太繁琐,而且都不是很好理解,因此在自己完成以后就写了这么一个博客,提供一种比较简单的程序代码,...
  • 数据结构课程设计 题 目 校园导航 指导教师 设计起始日期 5.9~5.16 学 院 系 别 学生姓名 班级/学号 成 绩 需求分析 需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图设计要 ...
  • C语言数据结构课程设计-校园导游系统

    千次阅读 多人点赞 2019-04-25 09:47:14
    倾心原创,转载请备注原文地址,谢谢。 主要内容: ...1) 设计学校的校园平面图,所含景点少于10个。图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长...
  • 在这两种情况下,这些超平面均以非概率方式映射线性结构。 但是,通过采用内核技巧,我们可以将非线性数据集转换为线性数据集,从而使SVM可以应用于非线性问题。 SVM是功能强大的算法,已得到广泛普及。 这部分是...
  • 一般来说,这些数据结构在您可以根据构建它所需的步骤列表而不是平面值来表达特定构造的任何地方都很有用。 以这种方式看世界,你会得到一些好处。 首先,能够查看构造在其历史上的任何时间点的状态,而仅仅是其...
  • 校园导航 数据结构课程设计校园导航 数据结构
  • 数据结构-校园导航问题

    热门讨论 2009-05-13 17:16:38
    数据结构:用图来描述校园内各个单位,顶点包括名称和简介,边包括两个端点和距离。 结果形式:输入要查询的单位,显示单位简介。输入两个单位,计算两个单位地点间最短距离。 测试数据:校园单位可包括:前门、...
  • 可编程数据平面(论文阅读)

    千次阅读 2022-04-16 11:55:11
    可编程数据平面 原文 《A Survey on the Programmable Data Plane: Abstractions, Architectures, and Open Problems》 可编程交换机允许数据包处理行为应用于传输的数据包,包括处理操作的类型、顺序和语义,以...
  • 系统设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
  • SDN数据平面

    千次阅读 2019-05-08 18:03:09
    1.传统网络数据平面 1.1 数据包的处理流程 1.2 数据的转发处理的特点 2. SDN数据平面架构 2.1 OF交换机的转发模型 3. PISA架构 1.传统网络数据平面 传统网络交换设备的功能架构主要由控制平面数据平面组成...
  • 半边数据结构及其使用

    千次阅读 2015-09-04 09:53:15
    实体的B-rep表示模型是一非常复杂的模型,要求能够表达出多面体各几何元素之间完整的几何和拓扑关系,并且允许对这种几何和拓扑关系进行修改.在B-rep表示中,体、面、边和顶点是最基本的几何元素,在实体的拼合、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,795
精华内容 28,318
关键字:

关系数据结构包不包含平面数据

数据结构 订阅