顶点存储
A. 爬升,下降顶点存储形式
你的问题不大清楚,下降怎么有顶点.从飞行性能上飞机有升限,跟位置无关,航线飞行的高度根据调配来的呀
B. 求一段c语言代码,题目:建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中
代码
/*输入:先输入两个数,代表点的数量和边的数量,
再输入各个边,起点编号 > 终点编号,编号从0开始
例子:
6 10
0 3
0 4
1 4
1 3
3 5
0 1
4 5
5 2
4 2
4 3
输出:
0 1 4 3 5 2
思路:
用vector建立邻接表
计算每个点的入度
如果是偏序无环的,一定存在入度为0的点,输出并且删除它,同时删除它出发的边,更新其他点的入度
循环直到移除所有点,输出顺序就是拓扑排序
*/
#include<iostream>
#include<vector>
using namespace std;
int main() {
freopen("in.txt","r",stdin);//重定向输入流//in.txt 建在程序所在的文件夹里
int M,N;
scanf("%d%d",&M,&N);//M个点,N条边
vector<int> maps[M];
int innode[M]={0};//入度
for(int i=0;i<N;i++)
{
int tx,ty;
scanf("%d%d",&tx,&ty);
maps[tx].push_back(ty);
++innode[ty];
}
for(int time=0;time<M;time++)
for(int i=0;i<M;i++)
{
if(innode[i]==0)
{
printf("%d ",i);
for(vector<int>::iterator it = maps[i].begin(); it != maps[i].end(); ++it)
{
--innode[*it];
}
innode[i]=-1;
break;
}
}
}
C. 如何用文件保存图的顶点,编号,描述和边等信息(C语言代码)
#define Infinity 1000
#define MaxVertexNum 35
#define MAX 40
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<iostream.h>
typedef struct arcell //边的权值信息
{
int adj; //权值
}arcell,adjmatrix[MaxVertexNum][MaxVertexNum]; //图的邻接矩阵类型
typedef struct vexsinfo //顶点信息
{
int position; //景点的编号
char name[32]; //景点的名称
char introction[256]; //景点的介绍
}vexsinfo;
typedef struct mgraph //图结构信息
{
vexsinfo vexs[MaxVertexNum]; //顶点向量(数组)
adjmatrix arcs; //邻接矩阵
int vexnum,arcnum; //分别指定顶点数和边数
}mgraph;
//全局变量
int visited[35]; //用于标志是否已经访问过
int d[35]; //用于存放权值或存储路径顶点编号
mgraph campus; //图变量(大学校园)
// (1) 对图初始化
mgraph initgraph()
{
int i=0,j=0;
mgraph c;
c.vexnum =28; //顶点个数
c.arcnum =39; //边的个数
for(i=0;i<c.vexnum ;i++) //依次设置顶点编号
c.vexs[i].position =i;
//依次输入顶点信息
strcpy(c.vexs[0].name ,"小西南门");
strcpy(c.vexs[0].introction ,"离公交站近");
strcpy(c.vexs[1].name ,"学校南正门");
strcpy(c.vexs[1].introction ,"学校大门、学校班车进出口");
strcpy(c.vexs[2].name ,"语言文化职业学院");
strcpy(c.vexs[2].introction ,"语言文化职业学院办公楼,楼高6层");
strcpy(c.vexs[3].name ,"艺术学院");
strcpy(c.vexs[3].introction ,"音乐系、美术系,楼高4层");
strcpy(c.vexs[4].name ,"行政楼");
strcpy(c.vexs[4].introction ,"行政办公大楼,楼高5层");
strcpy(c.vexs[5].name,"文学院");
strcpy(c.vexs[5].introction ,"文学院,楼高6层");
strcpy(c.vexs[6].name ,"体育场");
strcpy(c.vexs[6].introction ,"室外标准田径场");
strcpy(c.vexs[7].name,"教育科学学院");
strcpy(c.vexs[7].introction ,"教心系、经管系,楼高5层");
strcpy(c.vexs[8].name ,"南区学生宿舍");
strcpy(c.vexs[8].introction ,"离西南门近");
strcpy(c.vexs[9].name, "数学与经济管理学院");
strcpy(c.vexs[9].introction , "数学与经济管理学院大楼,楼高4层");
strcpy(c.vexs[10].name ,"中区学生宿舍");
strcpy(c.vexs[10].introction ,"若干栋,离学生1、2食堂近");
strcpy(c.vexs[11].name ,"职业学院教学大楼");
strcpy(c.vexs[11].introction ,"职业学院教学大楼,楼高5层");
strcpy(c.vexs[12].name ,"体育系");
strcpy(c.vexs[12].introction ,"体育系,楼高5层");
strcpy(c.vexs[13].name ,"游泳馆");
strcpy(c.vexs[13].introction ,"室内小型游泳馆");
strcpy(c.vexs[14].name ,"报告厅、阶梯教室");
strcpy(c.vexs[14].introction ,"可举办中、大型学术会议。有大小报告厅1-6个、阶梯教室1-6个");
strcpy(c.vexs[15].name ,"大礼堂、体育馆");
strcpy(c.vexs[15].introction ,"文艺演出所在地、室内运动场");
strcpy(c.vexs[16].name ,"1食堂");
strcpy(c.vexs[16].introction ,"教工食堂及学生1食堂在此");
strcpy(c.vexs[17].name ,"新图书馆");
strcpy(c.vexs[17].introction ,"建筑面积46000平方米");
strcpy(c.vexs[18].name ,"2食堂");
strcpy(c.vexs[18].introction ,"学校东区,学生食堂");
strcpy(c.vexs[19].name ,"东区学生宿舍");
strcpy(c.vexs[19].introction ,"离学生2食堂近");
strcpy(c.vexs[20].name ,"计算机学院");
strcpy(c.vexs[20].introction ,"计算机学院大楼,楼高5层");
strcpy(c.vexs[21].name ,"教工宿舍");
strcpy(c.vexs[21].introction ,"学校青年教职工租住地");
strcpy(c.vexs[22].name ,"西区学生宿舍");
strcpy(c.vexs[22].introction ,"离学生3、4食堂近");
strcpy(c.vexs[23].name ,"3食堂");
strcpy(c.vexs[23].introction ,"学校西区,学生食堂");
strcpy(c.vexs[24].name ,"外国语学院");
strcpy(c.vexs[24].introction ,"外国语学院大楼,楼高5层");
strcpy(c.vexs[25].name ,"4食堂");
strcpy(c.vexs[25].introction ,"学校西区,学生食堂,人气较高");
strcpy(c.vexs[26].name ,"校医院");
strcpy(c.vexs[26].introction ,"看小病的地方");
strcpy(c.vexs[27].name ,"实验楼");
strcpy(c.vexs[27].introction ,"物电学院、化学与生命科学学院、机电系、建材系所在地,机房及多媒体教室若干");
//依次输入边上的权值信息
for(i=0;i<c.vexnum ;i++)
for(j=0;j<c.vexnum ;j++)
c.arcs [i][j].adj =Infinity; //先初始化图的邻接矩阵
//部分弧长
c.arcs[0][2].adj=50; c.arcs[0][3].adj=60;
c.arcs[1][4].adj=90;
c.arcs[2][3].adj=60; c.arcs[2][8].adj=40;
c.arcs[3][4].adj=60; c.arcs[3][6].adj=40;
c.arcs[4][5].adj=70; c.arcs[4][9].adj=70; c.arcs[4][10].adj=80; c.arcs[4][17].adj=200;
c.arcs[5][7].adj=70;
c.arcs[6][9].adj=40;
c.arcs[7][18].adj=190;
c.arcs[8][11].adj=50;
c.arcs[9][12].adj=40;
c.arcs[10][18].adj=70;
c.arcs[11][12].adj=60; c.arcs[11][14].adj=50; c.arcs[11][15].adj=50;
c.arcs[12][16].adj=50;
c.arcs[13][14].adj=40; c.arcs[13][22].adj=60;
c.arcs[14][15].adj=50; c.arcs[14][20].adj=90;
c.arcs[15][16].adj=60; c.arcs[15][21].adj=40;
c.arcs[16][17].adj=60;
c.arcs[17][18].adj=80;
c.arcs[18][19].adj=60;
c.arcs[20][21].adj=60; c.arcs[20][24].adj=80;
c.arcs[22][23].adj=60; c.arcs[22][25].adj=80;
c.arcs[23][24].adj=60;
c.arcs[24][26].adj=100; c.arcs[24][27].adj=100;
c.arcs[25][26].adj=90;
c.arcs[26][27].adj=90;
for(i=0;i<c.vexnum ;i++) //邻接矩阵是对称矩阵,对称赋值
for(j=0;j<c.vexnum ;j++)
c.arcs[j][i].adj =c.arcs[i][j].adj ;
return c;
}//initgraph
// (2) 查找景点在图中的序号
int locatevex(mgraph c,int v)
{
int i;
for(i=0;i<c.vexnum ;i++)
if(v==c.vexs[i].position)
return i; //找到,返回顶点序号i
return -1; //否则,返回-1
}
//(3) 、(4) 求两景点间的所有路径
// (3) 打印序号为m,n景点间的长度不超过8个景点的路径
void path(mgraph c, int m,int n,int k)
{
int s,x=0;
int t=k+1; //t 记载路径上下一个中间顶点在d[]数组中的下标
if(d[k]==n && k<8) //d[k]存储路径顶点。若d[k]是终点n且景点个数<=8,则输出该路径
{ //递归出口,找到一条路径
for(s=0;s<k;s++)
printf("%s--->",c.vexs[d[s]].name); //输出该路径。s=0 时为起点m
printf("%s",c.vexs[d[s]].name); //输出最后一个景点名(即顶点n的名字,此时s==k)
printf("\n\n");
}
else
{
s=0;
while(s<c.vexnum) //从第m个顶点,试探至所有顶点是否有路径
{
if((c.arcs[d[k]][s].adj<Infinity) && (visited[s]==0)) //初态:顶点m到顶点s有边,且未被访问
{
visited[s]=1;
d[k+1]=s; //存储顶点编号s 至d[k+1]中
path(c,m,n,t); //求从下标为t=k+1的第d[t]个顶点开始的路径(递归调用),同时打印出一条m至n的路径
visited[s]=0; //将找到的路径上顶点的访问标志重新设置为0,以用于试探新的路径
}
s++; //试探从下一个顶点 s 开始是否有到终点的路径
}//endwhile
}//endelse
}//endpath
//(4) 打印两景点间的景点个数不超过8的所有路径。调用(3)
int allpath(mgraph c)
{
int k,i,j,m,n;
printf("\n\n请输入你要查询的两个景点编号:\n\n");
scanf("%d%d",&i,&j);
printf("\n\n");
m=locatevex(c,i); //调用(2),确定该顶点是否存在。若存在,返回该顶点编号
n=locatevex(c,j);
d[0]=m; //存储路径起点m (int d[]数组是全局变量)
for(k=0;k<c.vexnum;k++) //全部顶点访问标志初值设为0
visited[k]=0;
visited[m]=1; //第m个顶点访问标志设置为1
path(c,m,n,0); //调用(3)。k=0,对应起点d[0]==m。k为d[]数组下标
return 1;
}
// (5) 用迪杰斯特拉算法,求出一个景点到其他景点间的最短路径,并打印
void shortestpath_dij(mgraph c)
{
//迪杰斯特拉算法,求从顶点v0到其余顶点的最短路经及其带权长度d[v]
//若p[v][w]为1,则w是从v0到v的最短路经上的顶点
//final[v]类型用于设置访问标志
int v,w,i,min,t=0,x,flag=1,v0; //vo为起始景点的编号
int final[35],d[35],p[35][35];
printf("\n请输入一个起始景点的编号:");
scanf("%d",&v0);
printf("\n\n");
while(v0<0||v0>c.vexnum)
{
printf("\n你所输入的景点编号不存在\n");
printf("请重新输入:");
scanf("%d",&v0);
}//while
for(v=0;v<c.vexnum ;v++)
{
final[v]=0; //初始化各顶点访问标志
d[v]=c.arcs[v0][v].adj; //v0 到各顶点 v 的权值赋值给d[v]
for(w=0;w<c.vexnum ;w++) //初始化p[][]数组,各顶点间的路径全部设置为空路径0
p[v][w]=0;
if(d[v]<Infinity) //v0 到v 有边相连,修改p[v][v0]的值为1
{
p[v][v0]=1;
p[v][v]=1; //各顶点自己到自己要连通
}
}//for
d[v0]=0; //自己到自己的权值设为0
final[v0]=1; //v0的访问标志设为1,v 属于 s 集
for(i=1;i<c.vexnum ;i++) //对其余c.vexnum-1个顶点w,依次求 v 到 w 的最短路径
{
min=Infinity;
for(w=0;w<c.vexnum ;w++) //在未被访问的顶点中,查找与 v0 最近的顶点v
if(!final[w])
if(d[w]<min) //v0 到 w (有边)的权值<min
{
v=w;
min=d[w];
}//if
final[v]=1; //v 的访问标志设置为1,v 属于s集
for(w=0;w<c.vexnum ;w++) //修改v0 到其余各顶点w 的最短路径权值d[w]
if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不属于s,且v 到w 有边相连
{
d[w]=min+c.arcs[v][w].adj; //修改v0 到w 的权值d[w]
for(x=0;x<c.vexnum ;x++) //所有v0 到v 的最短路径上的顶点x,都是v0 到w 的最短路径上的顶点
p[w][x]=p[v][x];
p[w][w]=1;
}//if
}//for
for(v=0;v<c.vexnum ;v++) //输出v0 到其它顶点v 的最短路径
{
if(v!=v0)
printf("%s",c.vexs[v0].name); //输出景点v0 的景点名
for(w=0;w<c.vexnum ;w++) //对图中每个顶点w,试探w 是否是v0 到v 的最短路径上的顶点
{
if(p[v][w] && w!=v0 && w!=v) //若w 是且w 不等于v0,则输出该景点
printf("--->%s",c.vexs[w].name);
}
printf("---->%s",c.vexs[v].name);
printf("\n总路线长为%d米\n\n",d[v]);
}//for
}//shortestpath
//(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边
//(6) 构造图的邻接矩阵
int creatgragh(mgraph &c) //建图。以图的邻接矩阵存储图
{
int i,j,m,n;
int v0,v1;
int distance;
printf("请输入图的顶点数和边数: \n");
scanf("%d %d",&c.vexnum ,&c.arcnum );
printf("下面请输入景点的信息:\n");
for(i=0;i<c.vexnum ;i++) //构造顶点向量(数组)
{
printf("请输入景点的编号:");
scanf("%d",c.vexs[i].position );
printf("\n请输入景点的名称:");
scanf("%s",c.vexs[i].name );
printf("\n请输入景点的简介:");
scanf("%s",c.vexs[i].introction );
}
for(i=0;i<c.arcnum ;i++) //初始化邻接矩阵
for(j=0;j<c.arcnum ;j++)
c.arcs[i][j].adj =Infinity;
printf("下面请输入图的边的信息:\n");
for(i=1;i<=c.arcnum ;i++) //构造邻接矩阵
{
printf("\n第%d条边的起点 终点 长度为:",i);//输入一条边的起点、终点及权值
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0 && n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//creatgragh
// (7) 更新图的部分信息。返回值: 1
int newgraph(mgraph &c)
{
int changenum; //计数。用于记录要修改的对象的个数
int i,m,n,t,distance,v0,v1;
printf("\n下面请输入你要修改的景点的个数:\n");
scanf("%d",&changenum);
while(changenum<0||changenum>c.vexnum )
{
printf("\n输入错误!请重新输入");
scanf("%d",&changenum);
}
for(i=0;i<changenum;i++)
{
printf("\n请输入景点的编号:");
scanf("%d",&m);
t=locatevex(c,m);
printf("\n请输入景点的名称:");
scanf("%s",c.vexs[t].name );
printf("\n请输入景点的简介:");
scanf("%s",c.vexs[t].introction );
}
printf("\n下面请输入你要更新的边数");
scanf("%d",&changenum);
while(changenum<0||changenum>c.arcnum )
{
printf("\n输入错误!请重新输入");
scanf("%d",&changenum);
}
printf("\n下面请输入更新边的信息:\n");
for(i=1;i<=changenum ;i++)
{
printf("\n修改的第%d条边的起点 终点 长度为:",i);
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0&&n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//newgraph
D. 【数据结构】计算顶点数目超大(达千万级别)的无向图的连通分量数,如何用文本文件存储
第一行存储顶点个数
从第二行开始,每一行存两个定点编号代表一条边(例如:329 744 这就代表329号顶点到744号顶点的一条边)
这些边可以按照第一个顶点编号来进行排序这样便于索引,利用二分搜索可以很快找到相应的边
E. 数据结构:城市导游咨询系统
呵呵,工作太忙,没法给你详细代码。
首先:你把你的这个系统中所有涉及到得数据都提取出来,看看都是什么类型的数据,然后根据数据之间的逻辑依存关系,去设计自己的数据结构。
其次:看看数据之间的流动、交互,通过这样的分析,来设计自己的方法函数。
这样一步步的分析下来,我想你基本就明白了。
希望能帮到你。
F. 急~~~opengl顶点缓冲和顶点数组有什么关系
顶点数组的顶点数据是存储在内存中的
glEnableClientState(GL_VERTEX_ARRAY);
glVertexPointer(3, GL_FLOAT, 0, m_VertexArray);
glDrawElements(GL_TRIANGLES, m_FaceNum * 3, GL_UNSIGNED_INT, m_FaceArray);
VBO(Vertex Buffer Object)即顶点缓冲对象,它的数据是存在显存中的。
glBindBuffer(GL_ARRAY_BUFFER, m_VBOVertices);
glVertexPointer(3, GL_FLOAT, 0, NULL);
glEnableClientState(GL_VERTEX_ARRAY);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m_VBOIndices);
glDrawElements(GL_TRIANGLES, m_FaceNum * 3, GL_UNSIGNED_INT, NULL);
VBO通过构建缓冲数据将所有数据存储到显存中(存不下则放到内存中)
glGenBuffers(1, &m_VBOVertices);
glBindBuffer(GL_ARRAY_BUFFER, m_VBOVertices);
glBufferData(GL_ARRAY_BUFFER, sizeof(float) * vertexNum * 3, vertexArray, GL_STREAM_DRAW);
顶点数组渲染时候数据从内存送入渲染管线,而VBO则从显存送入渲染管线,后者效率更高
如你所说的情况,可以在运行期间动态修改索引缓冲。索引数组的话直接修改数组数据以及渲染时指定的索引数组大小。VBO当中可以使用glBufferSubData对缓冲进行局部修改
G. 图的存储结构——所存储的信息有哪些
一、邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。
设G=(V,E)是具有n(n>0)个顶点的图,顶点的顺序依次为0~n-1,则G的邻接矩阵A是n阶方阵,其定义如下:
(1)如果G是无向图,则:
A[i][j]=1:若(i,j)∈E(G) 0:其他
(2)如果G是有向图,则:
A[i][j]=1:若<i,j>∈E(G) 0:其他
(3)如果G是带权无向图,则:
A[i][j]= wij :若i≠j且(i,j)∈E(G) 0:i=j ∞:其他
(4)如果G是带权有向图,则:
A[i][j]= wij :若i≠j且<i,j>∈E(G) 0:i=j∞:其他
注意:带权图和不带权图表示的元素类型不同。
带权图(不论有向还是无向图)A[i][j]用double表示,不带权图(不论有向还是无向图)A[i][j]用int表示。
用一维数组G[ ]存储有4个顶点的无向图如:G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
如:
邻接矩阵的特点如下:
(1)图的邻接矩阵表示是唯一的。
(2)无向图的邻接矩阵一定是一个对称矩阵。因此,按照压缩存储的思想,在具体存放邻接矩阵时只需存放上(或下)三角形阵的元素即可。
(3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此,当图的顶点较多时,可以采用三元组表的方法存储邻接矩阵。
(4)对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度。
(5)对于有向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度(或入度)。
(6)用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
邻接矩阵的数据类型定义如下:
#define MAXV <最大顶点个数>
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数,弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵表示类型
二、 邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点i的边(对有向图是以顶点i为尾的边)。每个单链表上附设一个表头节点。
其中,表节点由三个域组成,adjvex指示与顶点i邻接的点在图中的位置,nextarc指示下一条边或弧的节点,info存储与边或弧相关的信息,如权值等。
表头节点由两个域组成,data存储顶点i的名称或其他信息,firstarc指向链表中第一个节点。
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息
} ArcNode; //边表节点类型
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //完整的图邻接表类型
邻接表的特点如下:
(1)邻接表表示不唯一。这是因为在每个顶点对应的单链表中,各边节点的链接次序可以是任意的,取决于建立邻接表的算法以及边的输入次序。
(2)对于有n个顶点和e条边的无向图,其邻接表有n个顶点节点和2e个边节点。显然,在总的边数小于n(n-1)/2的情况下,邻接表比邻接矩阵要节省空间。
(3)对于无向图,邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
(4)对于有向图,邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
例, 给定一个具有n个节点的无向图的邻接矩阵和邻接表。
(1)设计一个将邻接矩阵转换为邻接表的算法;
(2)设计一个将邻接表转换为邻接矩阵的算法;
(3)分析上述两个算法的时间复杂度。
解:
(1)在邻接矩阵上查找值不为0的元素,找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。
void MatToList(MGraph g,ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{ int i,j,n=g.n; ArcNode *p; //n为顶点数
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //给所有头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//创建节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//将*p链到链表头
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
(2)在邻接表上查找相邻节点,找到后修改相应邻接矩阵元素的值。
void ListToMat(ALGraph *G,MGraph &g)
{ int i,j,n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
(3)算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e),其中e为图的边数。
H. 对于有n个顶点的无向图,怎样存储可以省一半空间
原则上的确是n的平方,不过由于无向图的邻接矩阵是一个对称矩阵,只需要存储下三角或者上三角的元素,个数就是从1加到n,就是n(n+1)/ 2,不过题目问错了,这是压缩存储,是用一维数组存放,一般好像不叫矩阵
其实更精确地说,上面的数字个数是普通对称矩阵的,这个邻接矩阵的对角线一定为0,所以,只需要存储1 加到n-1,也就是n(n-1)/2就可以了
I. 灵活顶点格式是啥意思
“灵活顶点格式”是Direct3D在使用三角形来描述物体模型时的一种描述方式。
Direct3D应用程序可以用几种不同的方式定义灵活顶点格式。灵活顶点格式使应用程序只使用它需要的顶点数据,排除那些它不需要的组成成分。这样,应用程序可以节省内存空间,减少系统带宽。
通过D3DFVF的组合,可以描述图元顶点的格式。灵活顶点格式指定的格式包括点的大小,用D3DFVF_PSIZE指定,该大小在投影机空间用来表示未经变换的顶点,在设备空间用来表示经过变换的顶点。
(9)顶点存储扩展阅读:
定义顶点格式
structCustomerVertex
{
FLOATx,y,z,rhw;
DWORDcolor;
};
注: RHW表示投影空间中顶点所在的齐次点(x,y,z,w)(homogeneous point)的w坐标的导数(reciprocal),
注意的是,D3DFVF_XYZRHW和D3DFVF_XYZ、D3DFVF_NORMAL不能共存,因为后两个标志与前一个矛盾。在使用这种顶点时,系统需要顶点的位置已经经过变换了。
在定义完顶点格式以后,就要开辟一块顶点缓冲区:
g_pd3dDevice->CreateVertexBuffer(3*sizeof(CUSTOMVERTEX),
0,
D3DFVF_CUSTOMVERTEX,
D3DPOOL_DEFAULT,
&g_pVB,NULL)
开辟缓冲区后,就需要对这个缓冲区进行填写,那么填写的数据呢,也需要先指定出来:
CUSTOMVERTEXvertices[]=
{
{100.0f,400.0f,0.5f,1.0f,0xffff0000,},
{300.0f,50.0f,0.5f,1.0f,0xff00ff00,},
{500.0f,400.0f,0.5f,1.0f,0xff0000ff,},
};
然后将数据写入缓冲区:
VOID*pVertices;
if(FAILED(g_pVB->Lock(0,sizeof(vertices),(void**)&pVertices,0)))
returnE_FAIL;
memcpy(pVertices,vertices,sizeof(vertices));
g_pVB->Unlock();
这里写入的过程用的是Lock函数得到的缓冲区的地址,然后用memcpy函数将自己写好的数据写进去。到这里,顶点就算是创建好了。
J. 邻接矩阵vex是什么意思
typedef char VertexType[MAX_NAME];
。。。。。
2. typedef struct
3. {
4. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
5. AdjMatrix arcs; // 邻接矩阵
6. int vexnum,arcnum; // 图的当前顶点数和弧数
7. GraphKind kind; // 图的种类标志
8. } MGraph;
。。。。。。
9.
10. VertexType *GetVex(MGraph G,int v)
11. {
12. // 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值
13. if(v>=G.vexnum||v<0)
14. exit(ERROR);
15. return G.vexs[v];
16. }
17. int main()
18. {
19. .
20. printf("%s ",*GetVex(G,v));
21. ..
22. }
编译执行时,提示“15行:warning: function returns address of local variable”,执行时到这个函数就卡住了,问一下怎么修改?