頂點存儲

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

思路：

1. 用vector建立鄰接表

2. 計算每個點的入度

3. 如果是偏序無環的，一定存在入度為0的點，輸出並且刪除它，同時刪除它出發的邊，更新其他點的入度

4. 循環直到移除所有點，輸出順序就是拓撲排序
   

*/

#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是什麼意思

1. typedef char VertexType[MAX_NAME];

2. 。。。。。

3. 2. typedef struct

4. 3. {

5. 4. VertexType vexs[MAX_VERTEX_NUM]; // 頂點向量

6. 5. AdjMatrix arcs; // 鄰接矩陣

7. 6. int vexnum,arcnum; // 圖的當前頂點數和弧數

8. 7. GraphKind kind; // 圖的種類標志

9. 8. } MGraph;

10. 。。。。。。

11. 9.

12. 10. VertexType *GetVex(MGraph G,int v)

13. 11. {

14. 12. // 初始條件: 圖G存在，v是G中某個頂點的序號。操作結果: 返回v的值

15. 13. if(v>=G.vexnum||v<0)

16. 14. exit(ERROR);

17. 15. return G.vexs[v];

18. 16. }

19. 17. int main()

20. 18. {

21. 19. .

22. 20. printf("%s ",*GetVex(G,v));

23. 21. ..

24. 22. }

25. 編譯執行時，提示「15行：warning: function returns address of local variable」，執行時到這個函數就卡住了，問一下怎麼修改？