A. 一道數據結構的題目跪求大神解題: 畫出下面二叉樹的中序線索二叉樹的存儲結構圖（含附加的頭節點）。
中序線索二叉樹 先根，在左子樹，然後右子樹。
左線索指向前一個結點，左線索指向後一個結點。
中序遍歷 ABCDEFGHI.
化成為森林，這個看一下書
B. 數據結構實現圖的基本操作
對鄰接表存儲的圖進行深度優先搜索演算法：
#include "stdio.h"
#define MAXVER 10 /* 最多頂點數 */
typedef char ElemType; /* 頂點元素類型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 邊或弧的結點類型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 頂點信息結構 */
int vex,edge,tag; /* 存放頂點數、邊數和圖的類型 */
}adjlist; /* 鄰接表存儲結構類型名 */
/* 建立圖的鄰接表存儲表示。 */
void cregraph(adjlist *G,int n,int m) /* 建立鄰接表. n為頂點數，m為圖的類型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化鄰接表 */
printf("Input edges(x-->y):"); /* 用大寫字母表示頂點 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 輸入邊或弧，遇空格符結束 */
{ e++; /* 統計邊或弧和數目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成結點插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立無向圖的鄰接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 輸出用鄰接表存儲表示的圖 */
void list(adjlist *G) /* 輸出鄰接表 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 對鄰接表存儲的圖進行深度優先搜索演算法 */
int visited[MAXVER+1]; /* 頂點的訪問標記數組 */
dfs(adjlist *G,int v) /* v是訪問的起始點的下標 */
{ slink *p;
visited[v]=1;
printf("%3c",G->ve[v].vertex);
p=G->ve[v].first;
while(p)
{ if(visited[p->num]==0) /* 從V的未訪問過的鄰接點出發 */
dfs(G,p->num);
p=p->next; /* 找V的下一個鄰接點 */
}
}
void dfsgraph(adjlist *G)
{ int i;
for(i=0;i<G->vex;i++) if(!visited[i]) dfs(G,i);
}
main()
{ adjlist g;
int n=8;
cregraph(&g,n,0);
dfsgraph(&g);
}
對一個採用鄰接表作存儲結構的圖進行廣度優先遍歷：
/*鄰接表結構*/
#include "stdio.h"
#define MAXVER 10 /* 最多頂點數 */
typedef char ElemType; /* 頂點元素類型 */
typedef struct node
{ int num;
struct node *next;
}slink; /* 邊或弧的結點類型 */
typedef struct
{ struct
{ ElemType vertex;
slink *first;
}ve[MAXVER]; /* 頂點信息結構 */
int vex,edge,tag; /* 存放頂點數、邊數和圖的類型 */
}adjlist; /* 鄰接表存儲結構類型名 */
/*建立鄰接表*/
void cregraph(adjlist *G,int n,int m) /* n為頂點數，m為圖的類型 */
{ int i,e=0;slink *p,*q,*s;char x,y;
G->vex=n; G->tag=m;
for(i=0;i<n;i++)
{ G->ve[i].vertex=i+'A'; G->ve[i].first=NULL;} /* 初始化鄰接表 */
printf("Input edges(x-->y):"); /* 用大寫字母表示頂點 */
scanf("%c%c",&x,&y);
while(x!=' '&&y!=' ') /* 輸入邊或弧，遇空格符結束 */
{ e++; /* 統計邊或弧和數目 */
s=(slink *)malloc(sizeof(slink));
s->num=y-'A'; /* 生成結點插入 */
if(G->ve[x-'A'].first==NULL)
{ G->ve[x-'A'].first=s;
s->next=NULL;
}
else
{ p=G->ve[x-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) {p=q;q=q->next;}
p->next=s;s->next=q;
}
if(!G->tag) /* m=0表示建立無向圖的鄰接表 */
{ s=(slink *)malloc(sizeof(slink));
s->num=x-'A';
if(G->ve[y-'A'].first==NULL)
{ G->ve[y-'A'].first=s;s->next=NULL;}
else
{ p=G->ve[y-'A'].first;q=p->next;
while(q!=NULL&&s->num>q->num) { p=q;q=q->next;}
p->next=s;s->next=q;
}
}
scanf("%c%c",&x,&y);
}
G->edge=e;
}
/* 輸出鄰接表 */
void list(adjlist *G) /* 輸出用鄰接表表示的圖 */
{ int i; slink *p;
for(i=0;i<G->vex;i++)
{ printf("%d:%c--->",i,G->ve[i].vertex);
p=G->ve[i].first;
while(p)
{ printf("%3d",p->num);
p=p->next;
}
printf("\n");
}
}
/* 對一個採用鄰接表作存儲結構的圖進行廣度優先遍歷 */
int visited[MAXVER];
void bfs(adjlist *G,int v)
{ int queue[MAXVER],front,rear,i;/* 定義一個分離隊列 */
slink *p;
front=rear=0; /* 隊列初始化為空 */
queue[rear++]=v; /* 初始頂點入隊列 */
while(front!=rear) /* 隊列不空 */
{ v=queue[front++]; /* 出隊列訪問 */
printf("%c->",G->ve[v].vertex);
visited[v]=1; /* 入訪問表 */
p=G->ve[v].first;
while(p!=NULL)
{ for(i=0;i<rear;i++)
if(p->num==queue[i]) break;
if(i>=rear)
queue[rear++]=p->num; /* 該鄰接點即沒被訪問過，也不在隊列中，則入隊列 */
p=p->next; /* 找V的下一個鄰接點 */
}
}
}
void bfsgraph(adjlist *G) /* 若還有不連通的部分，則跳過去訪問之 */
{ int i;
for(i=0;i<G->vex;i++)
if(!visited[i]) bfs(G,i);
}
main()
{ adjlist G;
cregraph(&G,8,0);
bfsgraph(&G);
}
最小生成樹的演算法：
/*求最小生成樹的Kruskal演算法描述*/
#define MAXE 10
struct edges
{ int bv,tv,w;}; /* 邊集類型，存儲一條邊的起始點bv終止頂點tv和權w */
typedef struct edges edgeset[MAXE+1];
int seeks(int set[],int v)
{ int i=v;
while(set[i]>0)
i=set[i];
return i;
}
kruskal(edgeset ge,int n,int e) /* ge表示的圖是按權值從小到大排列的 */
{ int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0; /* 給set中的每個元素賦初值 */
i=1; /* i表示待獲取的生成樹中的邊數，初值為1 */
j=1; /* j表示ge中的下標，初值為1 */
while(j<n &&i<=e) /* 按邊權遞增順序，逐邊檢查該邊是否應加入到生成樹中 */
{ v1=seeks(set,ge[i].bv); /* 確定頂點v所在的邊通集 */
v2=seeks(set,ge[i].tv);
if(v1!=v2) /* 當v1,v2不在同一頂點集合，確定該邊應當選入生成樹 */
{ printf(" (%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{ edgeset e={{0,0,0},{4,5,2},{3,5,3},{1,4,5},{1,2,6},{2,4,7},{2,5,8},{1,3,9},{3,4,9},{1,5,13},{2,3,14}};
kruskal(e,5,10);
}
最短路徑的演算法：
#define Max 10 /* 預設最多頂點數 */
#define INFINITY 1000 /* 最大值 */
typedef struct
{ int vexnum,arcnum; /* 頂點數及邊或弧的數目 */
char vex[Max]; /* 存頂點信息的一維數組 */
int arc[Max][Max]; /* 存邊信息的二維數組 */
}AdjMatrix;
/* 建立有向圖的鄰接矩陣表示 */
void Creadjm(AdjMatrix *G)
{ int i,j,k,w;
printf("Input vex&arc:");
scanf("%d%d%*c",&G->vexnum,&G->arcnum);/*輸入頂點數和邊數，並讀掉回車符*/
printf("Input Vexinfo:");
for(k=0;k<G->vexnum;k++)
scanf("%c",&G->vex[k]); /* 輸入代表頂點的字元 */
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arc[i][j]=INFINITY; /* 初始化鄰接矩陣 */
printf("Input %d edges:\n",G->arcnum);
for(k=0;k<G->arcnum;k++)
{ scanf("%d%d%d",&i,&j,&w); /* 輸入邊或弧 */
G->arc[i][j]=w;
}
}
/* 輸出用鄰接矩陣表示的有向圖 */
void list(AdjMatrix *G)
{ int i,j;
for(i=0;i<G->vexnum;i++)
{ printf("%6c----",G->vex[i]); /* 先輸出頂點信息 */
for(j=0;j<G->vexnum;j++)
printf("%4d",G->arc[i][j]); /* 再輸出與該頂點有關聯的邊或弧的信息 */
printf("\n");
}
}
/* 計算從頂點v0到其餘各點最短路徑演算法 */
void dijkstra(AdjMatrix *G,int n,int v0,int d[]) /* d數組存放各頂點最短路徑 */
{ int s[Max] ; /* s數組存放頂點是否找到最短路徑 */
int i,j,u,mindis;
for(i=0;i<n;i++)
{ d[i]=G->arc[v0][i];s[i]=0;}
s[v0]=1;
for(i=1;i<n;i++)
{ mindis=INFINITY;
for(j=0;j<n;j++)
if(s[j]==0 && d[j]<mindis) { u=j; mindis=d[j];}
s[u]=1; /* 頂點u已找到最短路徑 */
for(j=1;j<=n;j++) /* 修改j的最短路徑 */
if(s[j]==0&&d[j]>d[u]+G->arc[u][j]) d[j]=d[u]+G->arc[u][j];
}
}
main()
{ AdjMatrix G;
int d[Max],i;
Creadjm(&G);
list(&G);
dijkstra(&G,6,0,d);
for(i=0;i<G.vexnum;i++)
printf("%4d",d[i]);
}
C. 數據結構：畫出下圖的鄰接矩陣存儲結構
我定義一個int型二維數組 G[5][5].
點a，b,c,d分別定義編號為1,2,3,4
G[u][v]的值為零 則有向邊(u,v)不聯通
若值為1則有向邊(u,v)聯通
又因為在c,c ,java中 數組的范圍是從0開始的
為了使用方便 我們不使用下標為0的數組元素
因為有四個點 所以我們定義一個5x5的二維數組
矩陣數據如下
00000
00110
00000
00001
01000
其中 G[1][2] G[1][3]G[3][4]G[4][1]的值為一
D. 數據結構圖的存儲
圖的存儲有兩種方式：鄰接矩陣，鄰接表。
圖的深度優先和廣度優先遍歷的復雜度：
1、鄰接矩陣：矩陣包含n n個元素，在演算法中，共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為 O(n n)
2、鄰接表：包含n個頭節點和e個表節點，演算法中對所有節點都要遍歷一次，所以時間復雜度為O(n+e)
E. 數據結構 - 圖
前面我們學習了線性表，棧、隊列和樹。前面三者都屬於線性表范疇，它的的數據元素是被串起來的，僅有線性關系，每個元素僅有一個直接前驅和一個直接後繼，是屬於一對一關系。在樹裡面，每個元素之間存在著明顯的層次關系，每一層的元素可能和下一層的多個元素相關，但只能和上一層的一個元素相關，屬於一對多的關系。而圖是一種較線性表和樹更為復雜的數據結構，在圖的結構中，節點和節點的關系是任意的，圖中任意兩個數據元素都可能相關。
定義 ：圖（ Graph ）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。
在圖中需要注意的是：
（1）線性表中我們把數據元素叫元素，樹中將數據元素叫結點，在圖中數據元素，我們則稱之為頂點（Vertex）。
（2）線性表可以沒有元素，稱為空表；樹中可以沒有節點，稱為空樹；但是，在圖中不允許沒有頂點（有窮非空性）。
（3）線性表中的各元素是線性關系，樹中的各元素是層次關系，而圖中各頂點的關系是用邊來表示（邊集可以為空）。
頂點Vi的度（Degree）是指在圖中與Vi相關聯的邊的條數。對於有向圖來說，有入度（In-degree）和出度（Out-degree）之分，有向圖頂點的度等於該頂點的入度和出度之和。
①若無向圖中的兩個頂點V1和V2存在一條邊(V1,V2)，則稱頂點V1和V2鄰接（Adjacent）；
②若有向圖中存在一條邊<V3,V2>，則稱頂點V3與頂點V2鄰接，且是V3鄰接到V2或V2鄰接直V3；
注意：無向圖中的邊使用小括弧「()」表示，而有向圖中的邊使用尖括弧「<>」表示。
在無向圖中，若從頂點Vi出發有一組邊可到達頂點Vj，則稱頂點Vi到頂點Vj的頂點序列為從頂點Vi到頂點Vj的路徑（Path）。
若從Vi到Vj有路徑可通，則稱頂點Vi和頂點Vj是連通（Connected）的。
圖的存儲結構除了要存儲圖中的各個頂點本身的信息之外，還要存儲頂點與頂點之間的關系，因此，圖的結構也比較復雜。常用的圖的存儲結構有鄰接矩陣和鄰接表等。
我們再來看一個有向圖樣例，如下圖所示的左邊。頂點數組為vertex[4]={v0,v1,v2,v3}，弧數組arc[4][4]為下圖右邊這樣的一個矩陣。主對角線上數值依然為0。但因為是有向圖，所以此矩陣並不對稱，比如由v1到v0有弧，得到arc[1][0]=1，而v到v沒有弧，因此arc[0][1]=0。
註：由於存在n個頂點的圖需要n*n個數組元素進行存儲，當圖為稀疏圖時，使用鄰接矩陣存儲方法將會出現大量0元素，這會造成極大的空間浪費。這時，可以考慮使用鄰接表表示法來存儲圖中的數據。
首先，回憶我們在線性表時談到， 順序存儲結構 就存在預先分配內存可能造成存儲空間浪費的問題，於是引出了 鏈式存儲 的結構。同樣的，我們也可以考慮對邊或弧使用鏈式存儲的方式來避免空間浪費的問題。
鄰接表 由表頭節點和表節點兩部分組成，圖中每個頂點均對應一個存儲在數組中的表頭節點。如果這個表頭節點所對應的頂點存在鄰接節點，則把鄰接節點依次存放於表頭節點所指向的單向鏈表中。
上面的圖G1包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7條邊。
上圖右邊的矩陣是G1在內存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點的鄰接點的序號"。例如，第2個頂點(頂點C)包含的鏈表所包含的節點的數據分別是"0,1,3"；而這"0,1,3"分別對應"A,B,D"的序號，"A,B,D"都是C的鄰接點。就是通過這種方式記錄圖的信息的。
鄰接表有向圖是指通過鄰接表表示的有向圖。
上面的圖G2包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9條邊。
上圖右邊的矩陣是G2在內存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點所對應的出邊的另一個頂點的序號"。例如，第1個頂點(頂點B)包含的鏈表所包含的節點的數據分別是"2,4,5"；而這"2,4,5"分別對應"C,E,F"的序號，"C,E,F"都屬於B的出邊的另一個頂點。