数据结构c语言图的操作
(1)问题3:
i=LocateVex(*G，va)；
j=LocateVex(*G，VB)；
*G不是指针，是指针G指向的对象，是ALGraph类型。程序中很多地方都用到了变量g，但是在不同的地方，含义是不一样的。在void CreateGraph(ALGraph *G g)中，G是指针，所以用*G来指代它所指代的对象。在其他情况下，代数G，G不是指针。
(2)第一:为什么这个void DFS traverse (Algraphg，void (* print) (char *))不能像调用DFS函数一样直接调用print函数？可以，函数指针是用来在未来任意扩展输出程序，以满足不同的需求，并且可以作为参数传递。
(3)第二:FirstAdjVex(G，G.vertices)的数据结构图的基本运算需要C语言的完整代码！！ # includestdio.h
#定义n 6
#定义e 8
void creat graph()；
typedef char vextype
typedef float adjtype
typedef结构{
vextype vexs[n]；
adj type arcs[n][n]；
}图；
int main()
{
creat graph()；
Printf("创建成功！\ n ")；
}
void CREATGRAPH()
{
graph * ga
int i，j，k；
浮动w；
for(I = 0；在；我)
ga-vexs[I]= getchar()；
for(I = 0；在；我)
for(j = 0；jn；j)
ga-arcs[I][j]= 0；
for(k = 0；柯；k)
{
scanf("%d%d%f "，I，j，w)；
ga-arcs[I][j]= w；
ga-arcs[j][I]= w；
}
Printf("创建成功！\ n ")；
}
我还没写完，你自己补充吧！
数据结构代码(C语言)图的遍历操作 #includestring.h
# includectype.h
# includedmalloc.h/* malloc()等等*/
#includelimits.h /* INT_MAX等*/
# includesdio.h/* eof (= z或F6)，NULL */
#includestdlib.h /* atoi() */
#includeio.h /* eof() */
#includemath.h /* floor()、ceil()、abs() */
#includeprocess.h /* exit() */
/*函数结果状态代码*/
#定义正确1
#定义假0
#定义确定1
#定义错误0
#定义不可行-1
/* #define OVERFLOW -2因为OVERFLOW的值在math.h中已经定义为3，所以这行*/
typedef int状态；/* Status是函数的类型，其值是函数的结果状态码，如OK */
typedef int BooleanBoolean是值为TRUE或FALSE的布尔类型*/
/* .........................*/
#定义最大顶点数20
typedef enumGraphKind/* */
typedef结构ArcNode
{
int adjvex/*弧所指顶点的位置*/
struct ArcNode * nextarc/*指向下一条弧线的指针*/
InfoType * info/*网的重量指针)*/
} ArcNode/*表节点*/
typedef结构
{
VertexType数据；/*顶点信息*/
ArcNode * firstarc/*第一个表节点的地址，指针指向附在顶点上的第一条弧*/
}VNode，adj list[MAX _ VERTEX _ NUM]；/*头节点*/
typedef结构
{
AdjList顶点；
int vexnum，arcnum/*图形的当前顶点数和弧数*/
int类；/*图形的类型标记*/
} ALGraph
/* .........................*/
/* .........................*/
/*ALGraphAlgo.cpp图的邻接表存储(存储结构由ALGraphDef.h定义)的基本操作*/
int LocateVex(代数G，顶点类型u)
{/*初始条件:图G存在，U和G中的顶点具有相同的特征*/
/*运算结果:如果G中存在顶点U，则返回该顶点在图中的位置；否则，-1 */
int I；
for(I = 0；iG.vexnum我)
if(strcmp(u，G.vertices[i].数据)==0)
返回I；
return-1；
}
状态创建图(图G)
{/*利用邻接表存储结构，构造没有相关信息的图G(用一个函数构造四个图)*/
int i，j，k；
int w；/*重量*/
VertexType va，VB；
ArcNode * p；
Printf("请输入图的类型(有向图:0，有向网络:1，无向图:2，无向网络:3):")；
scanf("%d "，(g . kind))；
Printf("请输入图的顶点数和边数:")；
scanf("%d，%d "，(G.vexnum)，(g . arcnum))；
Printf("请输入%d个顶点的值(%d个字符):\n "，G.vexnum，MAX _ NAME)；
for(I = 0；iG.vexnumI) /*构造顶点向量*/
{
scanf("%s "，G.vertices[i].数据)；
顶点[i]。firstarc = NULL
}
if(g . kind = = 1 | | g . kind = = 3)/* net */
Printf("请依次输入每条弧(边)的权值、尾值和头值(以空格为间隔):\ n ")；
Else /* Figure */
Printf("请依次输入每个弧(边)的弧尾和弧头(以空格为间隔):\ n ")；
for(k = 0；kG.arcnumK) /*构造一个表节点列表*/
{
if(g . kind = = 1 | | g . kind = = 3)/* net */
scanf("%d%s%s "，w，va，VB)；
Else /* Figure */
scanf("%s%s "，va，VB)；
i=LocateVex(G，va)；/*弧尾*/
j=LocateVex(G，VB)；/*弧形头*/
p =(ArcNode *)malloc(sizeof(ArcNode))；
p-adj vex = j；
if(g . kind = = 1 | | g . kind = = 3)/* net */
{
p-info =(int *)malloc(sizeof(int))；
*(p-info)= w；
}
其他
p-info = NULL；/*图*/
p-nextarc=G.vertices[i]。firstarc/*插入标题*/
顶点[i]。first arc = p；
如果(G.kind=2) /*无向图或网，生成第二个表节点*/
{
p =(ArcNode *)malloc(sizeof(ArcNode))；
p-adj vex = I；
If(G.kind==3) /*无向网络*/
{
p-info =(int *)malloc(sizeof(int))；
*(p-info)= w；
}
其他
p-info = NULL；/*无向图*/
p-nextarc=G.vertices[j]。firstarc/*插入标题*/
顶点[j]。first arc = p；
}
}
退货OK；
}
无效销毁图(图G)
{/*初始条件:图G存在。操作结果:销毁图G */
int I；
ArcNode *p，* q；
g . vex num = 0；
g . arcnum = 0；
for(I = 0；iG.vexnum我)
{
p=G.vertices[i]。firstarc
while(p)
{
q = p-next arc；
If(G.kind%2) /* net */
免费(p-info)；
免费(p)；
p = q；
}
}
}
VertexType* GetVex(代数G，int v)
{/*初始条件:图G存在，V是G中一个顶点的序号运算结果:返回V的值*/
if(v=G.vexnum||v0)
退出(错误)；
返回g顶点[v]。数据；
}
int FirstAdjVex(代数G，顶点类型v)
{/*初始条件:图G存在，V是G中的一个顶点*/
/*运算结果:返回v的第一个相邻顶点的序号，返回-1 */
ArcNode * p；
int v1
v1=LocateVex(G，v)；/* v1是图G中顶点V的序号*/
p=G.vertices[v1]。firstarc
如果(p)
返回p-adj vex；
其他
return-1；
}
int NextAdjVex(代数G，顶点类型v，顶点类型w)
{/*初始条件:图G存在，V是G中的一个顶点，W是V的一个邻点*/
/*运算结果:返回V的下一个相邻顶点的序号(相对于W)。*/
/*如果W是V的最后一个相邻点，-1 */
ArcNode * p；
int v1，w1；
v1=LocateVex(G，v)；/* v1是图G中顶点V的序号*/
w1=LocateVex(G，w)；/* w1是图g中顶点w的序号*/
p=G.vertices[v1]。firstarc
而(pp-adjvex！=w1) /*指针p不为空，它所引用的表节点不是w */
p = p-next arc；
如果(！p||！P-nextarc) /* W未找到或W是最后一个邻接点*/
return-1；
else /* p-adjvex==w */
返回p-nextarc-adj vex；/*返回V的下一个相邻顶点的序号(相对于W) */
}
布尔访问了[最大顶点数]；/*访问标志数组(全局数量)*/
void(* visit func)(char * v)；/*函数变量(全局量)*/
void DFS(代数G，整数v)
{/*递归遍历图G，深度从第v个顶点开始。算法7.5 */
int w；
顶点类型v1，w1；
strcpy(v1，*GetVex(G，v))；
visited[v]= TRUE；/*将访问标志设置为TRUE */
VisitFunc(G.vertices[v].数据)；/*访问v顶点*/
for(w=FirstAdjVex(G，v1)；w = 0；w=NextAdjVex(G，v1，strcpy(w1，*GetVex(G，w))))
如果(！已访问[w])
DFS(G，w)；/*递归调用DFS */
}
void DFSTraverse(ALGraph G，void(*Visit)(char*))
{/*先深度遍历图G。算法7.4 */
int v；
VisitFunc = Visit/*使用全局变量VisitFunc，这样DFS就不必设置函数指针参数*/
for(v = 0；vG.vexnum五)
visited[v]= FALSE；/*访问标志数组初始化*/
for(v = 0；vG.vexnum五)
如果(！拜访过
DFS(G，v)；/*呼叫DFS */
printf(" \ n ")；
}
typedef int QElemType/*队列类型*/
#include"LinkQueueDef.h "
#包含" LinkQueueAlgo.h "
void BFSTraverse(ALGraph G，void(*Visit)(char*))
{/*先按广度非递归遍历图g。使用辅助队列q和访问标志数组。算法7.6 */
int v，u，w；
顶点类型u1，w1；
link queue Q；
for(v = 0；vG.vexnum五)
visited[v]= FALSE；/*初始值*/
init queue(Q)；/*空辅助队列Q */
for(v = 0；vG.vexnumV) /*如果是连通图，只有v=0遍历整个图*/
如果(！已访问[v]) /* v未访问*/
{
visited[v]= TRUE；
访问(G.vertices[v].数据)；
入队(Q，v)；/* v入队*/
而(！QueueEmpty(Q)) /*队列不为空*/
{
出列(Q，u)；/*团队领导元素出列并并列为u */
strcpy(u1，*GetVex(G，u))；
for(w=FirstAdjVex(G，u1)；w = 0；w=NextAdjVex(G，u1，strcpy(w1，*GetVex(G，w))))
如果(！已访问[w])/* w为u的相邻顶点未被访问*/
{
visited[w]= TRUE；
访问(G.vertices[w].数据)；
入队(Q，w)；/* w加入团队*/
}
}
}
printf(" \ n ")；
}
空显示(代数G)
{/*邻接矩阵G */
int I；
ArcNode * p；
开关(G.kind)
{case DG: printf("有向图\ n ")；打破；
Case DN: printf("定向网络\ n ")；打破；
Case AG: printf("无向图\ n ")；打破；
案例AN: printf("无向网络\ n ")；
}
Printf("%d顶点:\n "，g . vex num)；
for(I = 0；iG.vexnum我)
printf("%s "，G.vertices[i].数据)；
Printf("\n%d弧(边):\n "，g . arcnum)；
for(I = 0；iG.vexnum我)
{
p=G.vertices[i]。firstarc
while(p)
{
If(G.kind=1) /* directed */
{
printf("%s→%s "，G.vertices[i]。数据，g顶点[p-adjvex]。数据)；
If(G.kind==DN) /* net */
printf(":% d " ,*(p-info))；
}
Else /*无向(避免输出两次)*/
{
if(ip-adjvex)
{
printf("%s-%s "，G.vertices[i]。数据，g顶点[p-adjvex]。数据)；
If(G.kind==AN) /* net */
printf(":% d " ,*(p-info))；
}
}
p = p-next arc；
}
printf(" \ n ")；
}
}
/* .........................*/
/* .........................*/
#包含“pubuse.h”
#define MAX_NAME 3 /*顶点字符串1的最大长度*/
typedef int InfoType/*存储网络的重量*/
typedef char vertex type[MAX _ NAME]；/*字符串类型*/
#包含“ALGraphDef.h”
#包含“ALGraphAlgo.h”
无效打印(char *i)
{
printf("%s "，I)；
}
void main()
{
int i，j，k，n；
代数g；
VertexType v1，v2；
Printf("请选择有向图\ n ")；
创建图表(g)；
显示(g)；
Printf("深度优先搜索的结果:\ n ")；
DFSTraverse(g，print)；
Printf("广度优先搜索的结果:\ n ")；
BFSTraverse(g，print)；
销毁记录(克)；/*破坏图*/
}
最后更新于 2023-10-08 19:09:58 并被添加「」标签，已有 位童鞋阅读过。
本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处
相关文章