安科网

数据结构C语言实现----图

lebronchen

lebronchen

2020-07-28

关注 关注

 邻接表储存结构

/*邻接表的边*/
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *next;
}ArcNode;
/*邻接表的结点*/
typedef struct VNode
{
    char date;
    ArcNode *firstarc;
}VNode;

创建一个邻接表储存结构的图

//创建一个邻接表类型的图
void CreatArcGraph(int count , VNode G[])
{
    ArcNode *p , *q;
    char c; //储存结点内数据
    int number; //储存要连接的结点
    printf("请输入各个结点的数据：\n");
    for (size_t i = 0; i < count; i++)  //初始化数组，输入各结点数据
    {
        fflush(stdin);
        printf("请输入第%d个结点内存入的字符：" , i);
        c = getchar();
        G[i].date = c;
        G[i].firstarc = NULL;
    }

图的遍历（1）-----深度优先搜索

//深度优先搜索一个连通图
void DFS(VNode G[] , int v)
{
    int w;
    printf("%c" , G[v].date); //访问当前结点
    printfed[v] = 1;
    w = FirstAdj(G , v);
    while (w!=-1)
    {
        if (printfed[w]==0)
        DFS(G,w);
        w = NextAdj(G , v);
    }
}
//对图G = （V，E）进行深度优化搜索的主算法
void Travel_DFS(VNode G[] , int n)
{
    for (size_t i = 0; i < n; i++)
    {
        printfed[i] = 0;
    }
    for (size_t i = 0; i < n; i++)
    {
        if (printfed[i]==0)
        {
            DFS(G,i);
        }
    }
}

深度优先搜索实例

#include<stdio.h>
#include<stdlib.h>
/*邻接表的边*/
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *next;
}ArcNode;
/*邻接表的结点*/
typedef struct VNode
{
    char date;
    ArcNode *firstarc;
}VNode;

//创建一个邻接表类型的图
void CreatArcGraph(int count , VNode G[])
{
    ArcNode *p , *q;
    char c; //储存结点内数据
    int number; //储存要连接的结点
    printf("请输入各个结点的数据：\n");
    for (size_t i = 0; i < count; i++)  //初始化数组，输入各结点数据
    {
        fflush(stdin);
        printf("请输入第%d个结点内存入的字符：" , i);
        c = getchar();
        G[i].date = c;
        G[i].firstarc = NULL;
        //putchar(‘\n‘);
    }
    for (size_t i = 0; i < count; i++)      //创建边
    {
        printf("请输入第%d个结点要连接的结点(各个结点以空格隔开）：",i);
        scanf("%d" , &number);
        while (number!=-1)
        {
            p = (ArcNode*)malloc(sizeof(ArcNode));
            p->next = NULL;
            p->adjvex = number;
            if (G[i].firstarc == NULL)
            {
                G[i].firstarc = p;
            }else
            {
                q->next = p;
            }
            q = p;
            scanf("%d" , &number);
        }
    }
}
int printfed[3];
//寻找第一个邻接点
int FirstAdj(VNode G[] , int v)
{
    return G[v].firstarc->adjvex;
}
//寻找下一个邻接点
int NextAdj(VNode G[] , int v)
{
    ArcNode *p;
    p = G[v].firstarc->next;
    while (p->next!=NULL )
    {
        p = p->next;
        if (printfed[p->adjvex]==0)
        {
            return p->adjvex;
        }
    }
    return -1;
}
//深度优先搜索一个连通图
void DFS(VNode G[] , int v)
{
    int w;
    printf("%c" , G[v].date); //访问当前结点
    printfed[v] = 1;
    w = FirstAdj(G , v);
    while (w!=-1)
    {
        if (printfed[w]==0)
        DFS(G,w);
        w = NextAdj(G , v);
    }
}
//对图G = （V，E）进行深度优化搜索的主算法
void Travel_DFS(VNode G[] , int n)
{
    for (size_t i = 0; i < n; i++)
    {
        printfed[i] = 0;
    }
    for (size_t i = 0; i < n; i++)
    {
        if (printfed[i]==0)
        {
            DFS(G,i);
        }
    }
}
#define MAXG 100
int main()
{
    int count;
    VNode G[MAXG];
    printf("请输入要创建的图的结点数:");
    scanf("%d",&count);
    CreatArcGraph(count , G);
    Travel_DFS(G,count);
    return 0;
}

运行结果

数据结构C语言实现----图

图的遍历（2）-------广度优先搜索

//广度优先搜索一个连通图
void BFS(VNode G[] , int v)
{
    initQueue(&q);
    //首先访问当前结点
    printf("%c" , G[v].date);
    visited[v] = 1;     //访问标记
    EnQueue(&q , v);     //入队列
    //
    int w;
    while (q.front==q.rear)
    {
        DeQueue(&q , &v);
        w = Firstadj(G , v);
        while (w!=-1)
        {
            if (visited[w]==0)
            {
                printf("%c",G[w].date);
                EnQueue(&q , w);
                visited[w] = 1;
            }
            w = Nextadj(G,v);
        }
    }
}
//广度优先搜索的主算法
void Travel_BFS(VNode G[] , int v)
{
    for (size_t i = 0; i < v; i++)
    {
        visited[i] = 0;
    }
    for (size_t i = 0; i < v; i++)
    {
        BFS(G , i);
    }
}

广度优先搜索实例

如图：

数据结构C语言实现----图

#include<stdio.h>
#include<stdlib.h>
//////////////////////////////////////////////////////////////////////////////
//储存类型定义
//图边
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *next;
}ArcNode;
//图结点
typedef struct VNode
{
    char date;
    ArcNode *firstarc;
}VNode;
//队列结点
typedef struct QNode
{
    int date;
    struct QNode *next;
}QNode , *QueuePtr;
//队列指针
typedef struct 
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
////////////////////////////////////////////////////////////////////////////////
//队列操作
//创建队列
void initQueue(LinkQueue *q)
{
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!q->front) exit(0);
    q->front->next = NULL;
}
//入队列
void EnQueue(LinkQueue *q , int v )
{
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!q->front) exit(0);
    p->date = v;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}
//出队列
void DeQueue(LinkQueue *q , int *v)
{
    if (q->front==q->rear)
    {
        exit(0);
    }
    QueuePtr p;
    p = q->front->next;
    *v = p->date;
    q->front->next = p->next;
    if (q->rear==p)
    {
        q->front = q->rear =NULL;
    }
    free(p);
}
/////////////////////////////////////////////////////////////////////////////////////
//图操作
//创建一个图（邻接表）
void CreatArcNode(VNode G[] , int count)
{
    //为结点数组输入数据
    char c;
    printf("请输入要在各个结点存入的字符...");
    for (size_t i = 0; i < count; i++)
    {
        fflush(stdin);
        printf("请输入在第%d个结点存入的数据：",i);
        c = getchar();
        G[i].date = c;
        G[i].firstarc = NULL;
    }
    //创建几条单链表连接在数组后面（创建边）
    int number;
    ArcNode *p , *q;
    for (size_t i = 0; i < count; i++)
    {
        printf("请输入结点%d要指向的结点：",i);
        scanf("%d",&number);
        while (number!=-1)
        {
            p = (ArcNode*)malloc(sizeof(ArcNode));
            p->adjvex = number;
            p->next = NULL;
    
            if (G[i].firstarc==NULL)
            {
                G[i].firstarc = p;
            }else
            {
                q->next = p;
            }
            q = p;
            scanf("%d",&number);
        }   
    }
}
/***********************************全局变量****************************************/
int visited[100];
LinkQueue q;


/////////////////////////////////////////////////////////////////////////////////
//广度优先搜索操作
//寻找第一个邻接点
int Firstadj(VNode G[] , int v)
{
    return G[v].firstarc->adjvex;
}
//寻找下一个邻接点
int Nextadj(VNode G[] , int v)
{
    ArcNode *p;
    p = G[v].firstarc->next;
    while (!p->next)
    {
        p = p->next;
        if (visited[p->adjvex]==0)
        {
            return p->adjvex;
        }
    }
    return -1;
}
//广度优先搜索一个连通图
void BFS(VNode G[] , int v)
{
    initQueue(&q);
    //首先访问当前结点
    printf("%c" , G[v].date);
    visited[v] = 1;     //访问标记
    EnQueue(&q , v);     //入队列
    //
    int w;
    while (q.front==q.rear)
    {
        DeQueue(&q , &v);
        w = Firstadj(G , v);
        while (w!=-1)
        {
            if (visited[w]==0)
            {
                printf("%c",G[w].date);
                EnQueue(&q , w);
                visited[w] = 1;
            }
            w = Nextadj(G,v);
        }
    }
}
//广度优先搜索的主算法
void Travel_BFS(VNode G[] , int v)
{
    for (size_t i = 0; i < v; i++)
    {
        visited[i] = 0;
    }
    for (size_t i = 0; i < v; i++)
    {
        BFS(G , i);
    }
}


int main()
{
    //创建一个图
    int count;
    printf("请输入创建的图有几个结点：");
    scanf("%d" , &count);
    VNode G[count];
    CreatArcNode(G,count);
    //打印邻接表
    for (size_t i = 0; i < count; i++)
    {
        ArcNode *p;
        p = G[i].firstarc;
        printf("第%d个结点：%c",i,G[i].date);
        do
        {
            if(p!=NULL)
            {
                printf("----<%d,%c>",p->adjvex,G[p->adjvex].date);
                p = p->next;
            }
        }while(p!=NULL);
        putchar(‘\n‘);
    }
    //广度优先搜索
    Travel_BFS(G , count);
    getchar();
    return 0;
}

运行结果：

数据结构C语言实现----图

数据结构 c语言 typedef

lebronchen

lebronchen

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

学c++需要先学c语言吗？

看需求，如果是底层开发，就必须学习C语言。如果只是应用开发，可以直接从C++开始学习。实际上这两个语言是平等的，只是在语法上C++尽量与C兼容，但仍然有很多不同的地方。1) C++不是C的超集。2) 如果你选择了一本好书，学C++之前完全没有必要学C，即使

shenwenjie 2020-09-24

数据结构C语言实现----入队列操作

New_node = malloc;//创建一个队列元素的结点

ding0 2020-07-18

详解Redis数据结构之跳跃表

我们先不谈Redis，来看一下跳表。还要支持输入道具名称的精确查询和不输入名称的全量查询。拍卖行商品列表是线性的，最容易表达线性结构的是数组和链表。每个元素均关联一个double类型的score，Redis 根据score进行从小到大排序；这个是 Redi

koushr 2020-11-12

数据结构之利用PHP实现二分搜索树

二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。二叉树不一定是满的，可能只有左儿子或又儿子。

KAIrving 2020-10-25

泛型和元编程的模型：Java, Go, Rust, Swift, D等

在程序设计的时候，我们通常希望使用同样的数据结构或算法，就可以处理许多不同类型的元素，比如通用的List或只需要实现compare函数的排序算法。在本文中，我将带你领略不同语言中的泛型系统以及它们是如何实现的。我将从C这样的不具备泛型系统的语言如何解决这个

zhangxiafll 2020-11-13

万能Python的秘诀：操纵数据的内置工具

本文转载自公众号“读芯术”。Python可谓是如今最流行的编程语言，甚至孩子们也可以从它开始学习趣味编程。Python类似英语的简单语法使它成为一种通用语言，已在全世界各个领域被广泛使用。Python的万能之处正在于其内置的数据结构，它使编码变得简单，不受

kikaylee 2020-10-31

Java实现单链表、栈、队列三种数据结构

它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap等等的底层都是用链表实现的。添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将

范范 2020-10-28

Map和Set两种数据结构在ES6的作用

什么又是字典呢？每个元素有一个称作key 的域，不同元素的key 各不相同。它们之间又有什么区别呢？大多数主流编程语言都有多种内置的数据集合。然而 JavaScript 直到ES6的发布之前，只拥有数组和对象这两个内建的数据集合。Set中的元素只会出现一次

MILemon 2020-10-22

「算法与数据结构」带你看回溯算法之美

我对回溯算法有一定理解：回溯算法建立在DFS基础之上的，但不同的是在搜索的过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索，因此我们可以这样子理解，回溯算法与DFS的区别就是有无状态重置。如果你还不了解什么是回溯算法，或者知道一些，但是对于它具体是如

hugebawu 2020-10-12

比较JavaScript中的数据结构（数组与对象）

在编程中，如果你想继续深入，数据结构是我们必须要懂的一块， 学习/理解数据结构的动机可能会有所不同，一方面可能是为了面试，一方面可能单单是为了提高自己的技能或者是项目需要。无论动机是什么，如果不知道什么是数组结构及何时使用应用字们，那学数据结构是一项繁琐

LauraRan 2020-09-28

动图演示：手撸堆栈的两种实现方法！

正式开始之前，先和各位朋友聊聊公众号后期的一些打算，后面的文章计划写一些关于数据结构和算法的内容，原因很简单「底层结构决定上层建筑嘛」，对于框架满天飞的今天，我们不止要学习如何使用框架，更要了解它的原理以及底层数据结构，只有这样我们才能更好的应用它。当然，

omyrobin 2020-09-23

技术人员思维和认知升级

今天这篇文章准备整理下我原来谈过的和技术人员相关的思维方面的话题，整个内容实际上包括两个方面。其一是我们可以从开发和技术中借鉴哪些思维方式；其二是技术人员本身不要受限于技术中，而应该跳出盒子培养价值驱动下的经营思维。结构化思维是架构思维必须具备的，最常用的

guangcheng 2020-09-22

python的链表基础知识点

python中的链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表有两种类型：单链表和双链表。一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中，相反，你可以通过一个节点指向另外一个

qiangde 2020-09-13

数据结构 4

//顺序表的插入操作 bool ListInsert { if//判断i的范围是否合法 return false if//存储空间是否满了 return false; //开始插入元素 for{ L.data[j] = L.dat

hanyujianke 2020-08-18

HBase/TiDB都在用的数据结构：LSM Tree，不得了解一下？

LSM Tree广泛应用在HBase，TiDB等诸多数据库和存储引擎上，我们先来看一下它的一些应用：。这么牛X的名单，你不想了解下LSM Tree吗？装X之前，我们先来了解一些基本概念。设计数据存储系统可能需要考虑的一些问题有：ACID，RUM。读性能体现

晨曦之星 2020-08-14

编写更简洁的Python代码的5个技巧

许多人刚开始学习编程时会选择Python。Python确实是初学者友好的。当您按照其官方网站上的下载和安装说明进行操作时，很快就可以编写" Hello World"程序。当您了解更多关于Python的知识时，您可能会着迷于它使用不同方

xiesheng 2020-08-06

盘点 Python 10 大常用数据结构（下篇）

上篇文章中4种数据结构相信大家都已经比较熟悉，因此我言简意赅的介绍一遍。接下来再详细的介绍下面6种数据结构及各自使用场景，会列举更多的例子。基本用法 deque 双端队列，基于list优化了列表两端的增删数据操作。实现原理：cpython实现deque使用

KAIrving 2020-08-02

盘点 Python 10 大常用数据结构（上篇）

如果你还处于Python入门阶段，通常只需掌握list、tuple、set、dict这类数据结构，做到灵活使用即可。因为相比于list, tuple实例更加节省内存，这点尤其重要。并且set内允许增删元素，且效率很高。但是值得注意，dict占用字节数是li

xiesheng 2020-08-02

图解！24张图彻底弄懂九大常见数据结构！ 原创 Amazing10 业余码农 5月24日

数据结构想必大家都不会陌生，对于一个成熟的程序员而言，熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合，特殊的结构在不同的应用场景中往往会带来不一样的处理效率。常用的数据结构可根据数据访问的特点分为线性结

范范 2020-07-30

什么是hash?

这个特定的算法就叫hash算法，hash算法并不是一个固定不变的算法。只要是能达到这个目的的算法都可以说hash算法。例如MD5,SHA，String.hashcode()都是hash算法。另外不同的输入可能会得出相同的hash值，那么这种现象称为hash

chenfei0 2020-07-30
lebronchen

lebronchen

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号