我要去跳楼
，我是没办法了，谁会看看
，下面的程序，按深度优先搜索打印不了完整的图：
#include <stdio.h>
#include <stdlib.h>
#define N 20
typedef struct arc
{
int index; /* 弧头结点在图数组中的序号 */
struct arc *nextarc;
}*Arc;
typedef struct
{
int info; /* 顶点的信息 */
Arc firstarc; /* 每个顶点的第一条边 */
}Graph;
static void CreateGraph(Graph g[]); /* 创建图 */
static int LocateNode(Graph g[], int v, int n); /* 查找顶点在图数组中的序号 */
static void PrintGraph(Graph g[], int n); /* 打印图 */
static void DepthFirstSearch(Graph g[], int i, int temp[]); /* 深度优先搜索 */
static void OutputGraph(Graph g[], int n);
int main(void)
{
Graph g[N];
CreateGraph(g);
return 0;
}
static void CreateGraph(Graph g[])
{
int i, j, k, n, e, v1, v2; /* n, e 分别代表顶点的数量和边的数量 */
Arc p, q;
printf("Enter n and e: ");
scanf("%d %d", &n, &e); /* 读取顶点的数量和边的数量 */
printf("Enter every node information: ");
for (k = 0; k < n; k++)
{
scanf("%d", &g[k].info); /* 读取每个顶点的信息 */
g[k].firstarc = NULL; /* 初始化每个顶点的头指针 */
}
printf("Enter every edge: \n");
for (k = 0; k < e; k++)
{
scanf("%d %d", &v1, &v2); /* 读取组成每条边的两个顶点 */
i = LocateNode(g, v1, n);
j = LocateNode(g, v2, n); /* 查找这两个顶点在图数组中的序号 */
if ((p = (Arc)malloc(sizeof(struct arc))) == NULL)
{
exit(1);
}
p -> index = j; /* 指向弧头结点在数组中的序号 */
p -> nextarc = g[i].firstarc; /* 指向弧尾 */
g[i].firstarc = p;
if ((q = (Arc)malloc(sizeof(struct arc))) == NULL)
{
exit(1);
}
q -> index = i;
q -> nextarc = g[j].firstarc;
g[j].firstarc = q;
}
OutputGraph(g, n);
PrintGraph(g, n); /* 打印图，按深度优先搜索 */
}
static int LocateNode(Graph g[], int v, int n)
{
int i;
for (i = 0; i < n; i++)
{
if (g[i].info == v)
{
return i;
}
}
}
static void OutputGraph(Graph g[], int n) /* 按顶点在数组中的顺序打印图 */
{
int i;
Arc p;
for (i = 0; i < n; i++)
{
printf("info = %d: arc", g[i].info);
p = g[i].firstarc;
while (p)
{
printf("-> %d", p -> index);
p = p -> nextarc;
}
putchar('\n');
}
}
static void PrintGraph(Graph g[], int n) /* 主要就是下面两个函数 */
{
int temp[N], i;
for (i = 0; i < n; i++)
{
temp[i] = 0; /* 初始化辅助数组 */
}
printf("The Depth First Search Order: ");
for (i = 0; i < n; i++)
{
if (temp[i] == 0)
{
DepthFirstSearch(g, i, temp); /* i 代表下标 */
}
}
putchar('\n');
}
static void DepthFirstSearch(Graph g[], int i, int temp[])
{
int k;
Arc p;
temp[i] = 1; /* 以访问过设置成 1 */
printf("%d ", g[i].info); /* 打印顶点信息 */
p = g[i].firstarc; /* p 指向当前顶点链表的头结点 */
k = p -> index;
while (p)
{
if (temp[k] == 0)
{
DepthFirstSearch(g, k, temp);
}
p = p -> nextarc;
k = p -> index;
}
}
下面是输入输出数据：
Enter n and e: 8 10
Enter every node information: 1 2 3 4 5 6 7 8
Enter every edge:
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 8
7 8
info = 1: arc-> 2-> 1
info = 2: arc-> 4-> 3-> 0
info = 3: arc-> 6-> 5-> 0
info = 4: arc-> 7-> 1
info = 5: arc-> 7-> 1
info = 6: arc-> 7-> 2
info = 7: arc-> 7-> 2
info = 8: arc-> 6-> 5-> 4-> 3
The Depth First Search Order: 1 3 7 8 6 Press any key to continue...
贴子别给我转走，你要敢转到数据结构
，我．．．．
不懂，数据结构刚看到线性表和广义表，连树都没到，更别说图了．哎！
，那里人少，不好解决
