数据结构关于数据查找的代码（用C语言）
（1）创建图的邻接矩阵和邻接表
（2）验证图的深度优先、广度优先遍历算法
（3）验证最短路径问题
问题太多了，每个小问题，都可以写不少代码
下面是问题1的代码，其他的问题，网上也很容易找到
// 邻接矩阵表示 :
#include iostream.h
#include stdlib.h
#define INFINITY 0
#define MAX_VERTEX_NUM 10 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
typedef enum Graphkind;
typedef char VertexType; //顶点数据类型
typedef struct ArcCell
{
int adj; //无权图，1或0表示相邻否；带权图则是权值。
//int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数。
Graphkind kind;
}MGraph;
int LocateVex(MGraph G,VertexType v1)
{
int i;
for(i=0;iG.vexnum;i++)
if(G.vexs[i]==v1)
return i;
return -1;
}
int CreatUDN(MGraph G)
// 采用数组表示法，构造无向网 G
{
VertexType v1,v2;
int w,j;
cout”输入图的顶点数”endl;
cinG.vexnum;
cout”输入图的弧数”endl;
cinG.arcnum;
for(int i=0;iG.vexnum;i++)
{
cout”输入顶点向量”endl;
cinG.vexs[i];
}
for(i=0;iG.vexnum;i++)
for(j=0;jG.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
}
for(int k=0;kG.arcnum;++k) //构造邻接矩阵
{
cout”输入边依附的两个顶点”endl;
cinv1v2;
cout”输入此边的权值”endl;
cinw;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
return 1;
}
void dispMGraph(MGraph G)
{
cout”图的邻接矩阵图是：”endl;
for(int i=0;iG.vexnum;i++)
{
for(int j=0;jG.vexnum;j++)
cout” “G.arcs[i][j].adj;
coutendl;
}
}
void main()
{
MGraph G;
CreatUDN(G);
dispMGraph(G);
}
// 邻接表 表示:
#include iostream.h
#include stdlib.h
#define MAX_VERTEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
int visited[ MAX_VERTEX_NUM];
typedef int VertexType ; //顶点数据类型
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph G)
{
int i,j,k;
ArcNode *p;
cout”创建一个图:”endl;
cout”顶点数:”; cinG.vexnum;coutendl;
cout”边数:”; cinG.arcnum; coutendl;
for(i=0;iG.vexnum;i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=0;kG.arcnum;k++)
{
cout”请输入第”k+1″条边:”;
cinij;
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=j;
p-nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}
void Disp(ALGraph G)
{
int i,j;
ArcNode *p;
cout”输出图为:”endl;
for(i=0;iG.vexnum;i++)
{
p=G.vertices[i].firstarc;
j=0;
while(p!=NULL)
{
cout”(“i”,”p-adjvex”)”;
p=p-nextarc;
j=1;
}
if(j==1)
coutendl;
}
}
void dfs(ALGraph G,int v) //深度优先遍历
{
ArcNode *p;
coutv” “;
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!=NULL)
{ if(!visited[p-adjvex])
dfs(G,p-adjvex);
p=p-nextarc;
}
return ;
}
void dfs1(ALGraph G)
{
int i;
for(i=0;iG.vexnum;i++)
if(visited[i]==0)
dfs(G,i);
}
void main()
{
ALGraph G;
CreateDG(G);
int v;
Disp(G);
cout”输入顶点:”;
cinv;
cout”深度优先序列:”;
dfs1(G);
coutendl;
}
补充：
c和c＋＋本来就差不了多少
只需要把#include iostream.h换成#include stdio.h
把cout换成printf，把cin换成scanf
就能把上述c＋＋的代码变化成c的啊
c语言深度优先搜索。代码
#include stdlib.h
#include stdio.h
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode-vertex = to; /* 建立顶点内容 */
newnode-nextnode = NULL; /* 设定指标初值 */
ptr = (head[from]); /* 顶点位置 */
while ( ptr-nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr-nextnode; /* 下一个顶点 */
ptr-nextnode = newnode; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf(“vertex[%d]\n”,current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr-vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr-vertex); /* 递回遍历呼叫 */
ptr = ptr-nextnode; /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
//clrscr();
for ( i = 1; i = 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf(“Content of the gragh’s ADlist is:\n”);
for ( i = 1; i = 8; i++ )
{
printf(“vertex%d -“,head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(” %d “,ptr-vertex); /* 印出顶点内容 */
ptr = ptr-nextnode; /* 下一个顶点 */
}
printf(“\n”); /* 换行 */
}
printf(“\nThe end of the dfs are:\n”);
dfs(1); /* 打印输出遍历过程 */
printf(“\n”); /* 换行 */
puts(” Press any key to quit…”);
// getch();
}
c语言BFS、DFS函数代码
这个没有固定的形式
根据具体的情况来写
关键是思想
bfs是先扩展节点再增加深度
dfs是先增加深度,到底后返回再扩展节点
一个是使用大量空间 另一个则是遍历所有路径,相对的更费时间
c语言，用二维数组解决迷宫问题。来段完整的代码吧。
好的，以下是使用二维数组解决迷宫问题的C语言代码示例：
Copy code
#include stdio.h
#define ROW 6 // 迷宫行数
#define COL 6 // 迷宫列数
int maze[ROW][COL] = { // 迷宫地图 1表示障碍，0表示通路
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1},
};
int result[ROW][COL]; // 存放走迷宫的结果
int dfs(int row, int col) {
if (row == ROW – 1 col == COL – 1) { // 到达终点
result[row][col] = 1;
return 1;
}
if (maze[row][col] == 0) { // 当前位置是通路
result[row][col] = 1;
if (row ROW – 1 dfs(row + 1, col)) { // 向下走有解
return 1;
}
if (col COL – 1 dfs(row, col + 1)) { // 向右走有解
return 1;
}
result[row][col] = 0; // 标记走过的路
}
return 0; // 返回无解
}
void print_result() {
printf(“走迷宫的结果：\n”);
for (int i = 0; i ROW; i++) {
for (int j = 0; j COL; j++) {
printf(“%d “, result[i][j]);
}
printf(“\n”);
}
}
int main() {
if (dfs(0, 0)) { // 从起点开始走迷宫
print_result();
} else {
printf(“无法走出迷宫！\n”);
}
return 0;
}
上述代码中，我们使用了一个二维数组 maze 来表示迷宫地图，其中 1 表示障碍，0 表示通路；另一个二维数组 result 用来存储走迷宫的结果，其中 1 表示该位置走通了， 0 表示该位置没有走通。
我们使用 dfs 函数来进行深度优先搜索，从起点 (0, 0) 开始往下、往右走，直到走到终点 (ROW-1, COL-1)，如果存在通路，则将路径标记在 result 数组中，并返回 1，否则返回 0 表示无解。
最后，我们在 main 函数中调用 dfs 函数，判断是否能从起点走出迷宫，如果有解，则输出走迷宫的结果；否则，输出 “无法走出迷宫” 的提示。
C语言DFS八皇后问题，输出结果重复
重复输出是因为
for(int
i
=
0;
i
n;
i
++)
dfs(0,i);
由于在dfs内部，已经对当前行进行过遍历，在主函数只需用调用一次dfs(0,0)即可
而当5的时候，为什么会出错，具体原因不清楚
但根据调试发现，无法处理对角线间隔多行的情况，特别是第二个输出就错了，问题在往上返回的过程中，左下角位置本来是-1，变成了0，这种情况应该是在恢复地图时错误
这是一个C语言搜索的问题。求大神给我讲解下这段代码。
#includestdio.h
#define max(a,b) ab?a:b //判断a、b的大小，返回大的
int a[25],n,m,s=0;
void dfs(int num,int sum)//函数功能大概是找出输入的n个数里面，小于等于m 的数中最大的数
{
if(numn)return;//如果num 大于输入的 n 结束
if(sum=m)//如果sum 小于 输入的m 进入
{
s=max(s,sum); //将s赋值为s和sum里最大的
}
dfs(num+1,sum);//递归n次,将num变到n-1的值,结束执行下一句
dfs(num+1,sum+a[num]);//进入函数判断
}
int main()
{
int i;
scanf(“%d%d”,n,m);//输入两个数 n , m
for(i=0;in;i++)
scanf(“%d”,a[i]);//循环读入n 个数
dfs(0,0);
printf(“%d”,s);//输出
}
粗略观察，欢迎追问
微信扫一扫 
支付宝扫一扫 
