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的出边的另一个顶点。