首页 > 其他分享 >C语言基础(二十七)

C语言基础(二十七)

时间:2024-08-30 20:22:39浏览次数:11  
标签:temp int graph 基础 二十七 dest 顶点 C语言 节点

1、位字段(Bit-fields)也是一种数据结构,允许在结构体(struct)或联合体(union)中定义其成员占用特定的位数。对于需要精确控制内存布局或处理硬件寄存器映射等场景非常有用。位字段使得开发者能够定义小于一个字节的变量,从而更有效地利用内存空间。位字段的声明方式是在结构体或联合体的成员后面加上冒号和该成员所占的位数。

测试代码:

#include <stdio.h>  
// 温馨提示:本程序不能在实际的硬件环境中运行,仅做示例。
// 位字段 
// 硬件寄存器结构体  
struct hardware_registers {  
    unsigned int control: 1;  // 控制位  
    unsigned int mode: 2;     // 模式选择位
    unsigned int speed: 3;    // 速度控制位
    unsigned int : 0;         // 填充位,不占用空间  
    unsigned int status: 1;   // 状态位,只读  

    // 其他寄存器...  
    // unsigned int another_register: 8;  
};  
  
// 硬件寄存器地址(硬件的物理地址,代码无法直接运行,0x12345678不是一个有效的硬件地址。)   
volatile struct hardware_registers *hardware = (volatile struct hardware_registers *)0x12345678;  
  
// 写入硬件寄存器的函数  
void write_hardware_register(void) {  
    // 设置控制位为1,模式为2(从0开始计数),速度为4(同样从0开始)  
    hardware->control = 1;  
    hardware->mode = 2;  
    hardware->speed = 4;  
    // 检查写入是否成功(需要读取状态寄存器)  
    // check_hardware_status();  
}  
  
// 读取硬件状态并打印的函数  
void read_hardware_status(void) {  
    // 读取状态位 
    if (hardware->status) {  
        printf("Hardware is in active state.\n");  
    } else {  
        printf("Hardware is in inactive state.\n");  
    }  
}  
  
int main() {  
    // 写入硬件寄存器  
    write_hardware_register();  
  
    // 读取并打印硬件状态  
    read_hardware_status();  
  
    return 0;  
}  
 

.........................................................................................................................................................   

2、邻接表通过为每个顶点维护一个链表来存储与该顶点相邻的所有顶点,从而高效地存储和访问图中的边。 

测试代码:

#include "date.h" 
#include <stdio.h>  
#include <stdlib.h>   
#define MAX_VERTICES 100  
// AdjListNode 表示邻接表中的一个节点,包含目标顶点和指向下一个节点的指针。 
typedef struct AdjListNode {  
    int dest;  
    struct AdjListNode* next;  
} AdjListNode;  
// AdjList 包含一个指向邻接表头部的指针。 
typedef struct AdjList {  
    struct AdjListNode* head; 
} AdjList;  
//  Graph是一个结构体(struct),表示图论中的图。
// 结构体通常会包含顶点的数组(或指针数组)以及某种形式表示边(比如:邻接矩阵、邻接表等)。

// Graph 包含顶点数和一个指向邻接表数组的指针。
typedef struct Graph {  
    int V;  
    struct AdjList* array;  
} Graph;  
  
// 函数声明 
void addEdge(Graph* graph, int src, int dest);  
void printGraph(Graph* graph);  
void DFS(Graph* graph, int v, int visited[]);  
void BFS(Graph* graph, int s);  
  
// newAdjListNode 函数:创建一个新的邻接表节点,其中 dest 参数表示目标顶点。
// 使用动态内存分配分配一个新的节点,并将目标顶点赋值给新节点的 dest 字段,
// 并将 next 字段设为 NULL。最后返回新节点的指针。
// 函数定义开始,接收一个整型参数dest,返回一个指向AdjListNode类型的指针  
AdjListNode* newAdjListNode(int dest) {  
    // 使用malloc函数动态分配内存给一个新的AdjListNode结构体实例  
    // sizeof(AdjListNode)计算AdjListNode结构体所需的总字节数  
    // (AdjListNode*)类型转换,将void*类型的malloc返回值转换为AdjListNode*类型  
    // 分配的内存地址被存储在newNode指针中  
    AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));  

    // 将传入的dest参数赋值给新节点的dest成员变量  
    // dest成员变量通常用于存储与该节点相关联的顶点或边的信息  
    newNode->dest = dest;  
  
    // 初始化新节点的next指针为NULL  
    // next指针用于指向链表中的下一个节点,初始时为NULL表示链表结束  
    newNode->next = NULL;  
  
    // 返回新创建的节点指针  
    return newNode;  
} 
// createGraph 函数:创建一个新的图,其中 vertices 参数表示图中顶点的数量。
// 首先分配一个 Graph 结构体的空间,然后设置顶点的数量。
// 然后再分配一个邻接表数组的空间,并对每个邻接表头部进行初始化。
// 最后返回创建的图的指针。
// vertices 作为参数,表示图中顶点的数量。函数返回一个指向 Graph 类型的指针。 
Graph* createGraph(int vertices) {  
    // 为 Graph 结构体分配内存,并将返回的指针存储在 graph 变量中。(Graph*) 类型转换,将 void* 转换(Graph*) 指针类型。 
    Graph* graph = (Graph*) malloc(sizeof(Graph)); 
    
	// 将图的顶点数(vertices)存储在 graph 结构的 V 成员中。 
    graph->V = vertices;  
    // 为AdjList 类型的数组分配内存,数组的大小与图的顶点数相同。
	// 每个 AdjList 元素(为一个链表头,每个链表包含从该顶点出发的所有边的目标顶点)对应于图中的一个顶点。 
    graph->array = (AdjList*) malloc(vertices * sizeof(AdjList));  
    // 遍历邻接表数组,将每个 AdjList 的 head 成员初始化为 NULL。
	// 创建图时,没有任何边存在(每个顶点的邻接链表都是空的)。
    for (int i = 0; i < vertices; ++i) 
    
        graph->array[i].head = NULL;  
  
    return graph;  
}
// addEdge 函数:向图中添加一条边,从顶点 src 到 dest。
// 首先创建一个新的邻接表节点,然后将该节点插入到 src 对应的邻接表中,
// 由于图是无向图,需要在 dest 对应的邻接表中插入一条边从 dest 指向 src。
void addEdge(Graph* graph, int src, int dest) {  
    // 将 dest 成员设置为给定的参数值,然后返回指向该节点的指针,创建一个新节点,
    // 该节点的 dest 成员被设置为当前边的目标顶点 dest。
    AdjListNode* newNode = newAdjListNode(dest);  
    // 将新节点的 next 指针设置为源顶点 src 当前邻接链表的头节点。
	// 将源顶点 src 的邻接链表头指针 head 更新为新节点,从而将该新节点添加到链表的开头。
	// 表示从源顶点 src 到目标顶点 dest 有一条边。
    newNode->next = graph->array[src].head;  
    graph->array[src].head = newNode;  
  
    // 将新节点添加到目标顶点 dest 的邻接链表中。
	// 表示从目标顶点 dest 到源顶点 src 也有一条边,无向图的特性。 
    newNode = newAdjListNode(src);  
    newNode->next = graph->array[dest].head;  
    graph->array[dest].head = newNode;  
}
//  DFS 函数:深度优先搜索。
// 从给定的起始顶点 v 开始,递归地遍历与它相邻的顶点,直到没有未访问的相邻顶点。
// 递归函数将递归访问每个相邻顶点,并用 visited 数组跟踪已访问的顶点。
void DFS(Graph* graph, int v, int visited[]) {  
    // 将整数数组 visited 中索引为 v 的元素设置为 1,表示顶点 v 已经被访问过。
    visited[v] = 1;  
    // 打印当前正在访问的顶点 v 的值
    printf("%d", v);  
    // 获取图中顶点 v 的邻接链表的头节点,并将其地址存储在指针 temp 中。 
    AdjListNode* temp = graph->array[v].head;  
    //  while 循环遍历顶点 v 的所有邻接顶点。
	// 循环继续执行,直到 temp 变为 NULL,遍历完所有邻接顶点。 
    while (temp) {  
        // 获取当前邻接链表节点 temp 的目标顶点 next。
        int next = temp->dest;  
        // 检查该顶点是否已经被访问过(即 visited[next] 是否为 0)。
        if (!visited[next])  
        // 如果 next 顶点尚未被访问,则递归调用 DFS 函数,以 next 为新的起始顶点继续搜索。 
            DFS(graph, next, visited);  
        // 将 temp 更新为当前节点的下一个节点,以下一次循环迭代中处理。
		// 确保能够遍历完顶点 v 的所有邻接顶点。
            temp = temp->next;  
    } 
	// 当 temp 变为 NULL 时,while 循环结束,表示顶点 v 的所有邻接顶点都已经被检查并已经被递归访问过。 
}  
// BFS 函数:广度优先搜索。
// 从给定的起始顶点 s 开始,利用队列依次访问和处理与起始顶点相邻的顶点,直到队列为空。
// while循环,函数将访问起始顶点的相邻顶点,并将们添加到队列中,同时使用 visited 数组跟踪已访问的顶点。 
void BFS(Graph* graph, int s) {  
     // 声明整数数组 visited,其大小为图的顶点数 graph->V。用于跟踪哪些顶点已经被访问过。
    int visited[graph->V];  
    // 循环遍历 visited 数组,将所有元素初始化为 0,表示开始时没有顶点被访问过。
    for (int i = 0; i < graph->V; i++)  
        visited[i] = 1;  
    // 声明整数数组 queue 作为队列,用于存储待访问的顶点。
	// 声明两个整数 front 和 rear 分别作为队列的前端和尾端索引,初始时都设为 0。
    int queue[graph->V], front = 0, rear = 0;  
    // 将起始顶点 s 标记为已访问(将 visited[s] 设置为 1)。
	// 将起始顶点 s 加入队列的尾部(通过增加 rear 索引并将 s 赋值给 queue[rear])。
    visited[s] = 1;  
    queue[rear++] = s;  
    // 循环持续进行,直到队列为空(即 front 等于 rear)。
	// 在队列不为空的情况下,执行循环体内的代码。
    while (front < rear) { 
	    // 从队列的前端取出一个顶点 s(通过增加 front 索引并读取 queue[front] 的值),并打印出来。表示顶点 s 已经被访问。 
        s = queue[front++];
		  
        printf("%d", s);  
        // 对于每个邻接顶点,如果未被访问(即 visited[temp->dest] 为 0),则将其标记为已访问,并将其加入队列的尾部。
		// 通过遍历 s 的邻接链表(由 graph->array[s].head 指向)实现,其中 temp 是指向邻接链表节点的指针。
        AdjListNode* temp = graph->array[s].head;  
        while (temp) {  
            if (!visited[temp->dest]) {  
                visited[temp->dest] = 1;  
                queue[rear++] = temp->dest;  
            }  
            temp = temp->next;  
        }  
    }  
}

// 释放链表中所有节点  
void freeAdjList(AdjList* adjList) {  
    // 指向AdjListNode类型的指针temp。用于临时存储链表中当前要释放的节点的地址。
    AdjListNode* temp;
	// 邻接表的头节点不为空(即链表中还有节点未被释放),循环继续执行。  
    while (adjList->head != NULL) {  
        // 将adjList->head(即当前链表的头节点)的地址赋值给temp。
		// temp指向当前要释放的节点。
        temp = adjList->head;  
        // adjList->head更新为adjList->head->next,让头节点指向下一个节点。 
        adjList->head = adjList->head->next;  
        // 释放temp所指向的内存 
        free(temp);  
    }  
}  
  
// 释放图占用的所有内存  
void freeGraph(Graph* graph) {  
    // 释放每个顶点的邻接表  
    for (int i = 0; i < graph->V; i++) {  
        freeAdjList(&graph->array[i]);  
    }  
  
    // 释放顶点数组  
    free(graph->array);  
  
    // 释放图结构本身  
    free(graph);  
}  
  
int main() {  
    int time = getTime();
    int V = 4; // 图的顶点数  
    Graph* graph = createGraph(V);  
  
    printf("Adding edges:\n");  
    addEdge(graph, 0, 1);  
    addEdge(graph, 0, 2);  
    addEdge(graph, 1, 2);  
    addEdge(graph, 2, 0); // 冗余,无向图已经通过addEdge添加了从0到2和从2到0的边。 
    addEdge(graph, 2, 3);  
    addEdge(graph, 3, 3); // 添加一个自环。 
	
  
    printf("\nGraph created. Following is Depth First Traversal (DFS):\n");  
    
    int* visited = (int*)malloc(V * sizeof(int));  
    if (visited == NULL) {  
        fprintf(stderr, "Memory allocation failed\n");  
        exit(EXIT_FAILURE);  
    }  

    for (int i = 0; i < V; i++)  
        if (visited[i] == 0)  
            DFS(graph, i, visited); // 从每个未访问的顶点开始DFS  
  
    // 重置visited数组进行BFS  
    for (int i = 0; i < V; i++)  
        visited[i] = 0;  
  
    printf("\nFollowing is Breadth First Traversal (BFS), starting from vertex 2:\n");  
    BFS(graph, 2); // 从顶点2开始BFS  
  
    // 清理分配的内存  
    freeGraph(graph);  
    
    return 0;  
}

运行结果如下:

 

标签:temp,int,graph,基础,二十七,dest,顶点,C语言,节点
From: https://blog.csdn.net/wehpd/article/details/141726501

相关文章

  • 11.2 C语言文件的读写操作
    11.2C语言文件的读写操作11.2文件的读写操作11.2文件的读写操作文件的读写是文件处理中的核心操作,C语言提供了多种函数来实现从文件读取数据和向文件写入数据。文件的写操作写字符:fputc(c,fp);//将字符c写入文件写字符串:fputs(str,fp);//将字符......
  • js基础学习
    1.js是动态语言,变量类型是可变的。varx=10;varx='pink';2.八进制(0开头)、十六进制(0x开头)3.字符串多个嵌套时,外双内单/外单内双。模版字符串:为了简化字符串拼接。`我今年${age}了`转义字符:4.typeof变量 可以检测类型---控制台颜色也可以检测类型5.转成字符串......
  • 【C语言】内存函数
    文章目录前言一、memcpy的使用和模拟实现1.memcpy的使用2.模拟实现memcpy函数二、memmove的使用和模拟实现1.memmove的使用2.模拟实现memmove函数三、memset函数的使用四、memcmp函数的使用前言`内存函数的头文件都是<string.h>介绍了memcpy、memmove、memset......
  • C语言深度复习【数组和指针】
    目录一.数组和指针1.1数组指针1.2指针数组1.3函数指针1.4const和指针1.5sizeof和指针和数组1.6strlen和字符数组一.数组和指针1.1数组指针一个数组指针实际上是指指向数组的指针。当你有一个数组类型作为函数参数时,它在函数内部被当作一个指针来处理。例......
  • 信息安全数学基础(3)整数的表示
    前言    在信息安全数学基础中,整数的表示是一个核心且基础的概念。整数的表示不仅涉及到其数值的存储方式,还关系到整数在计算机中的运算和处理。以下是对整数表示的详细阐述:一、整数的定义与分类    整数包括正整数、零和负整数,通常表示为…,-3,-2,-1,0,......
  • 什么是激活函数?零基础扫盲~
    我刚开始学习深度学习的时候,看到了这么一段话:作者把非线性激活函数(ReLU)用在了模型里,发现训练速度显著提高,原因在于传统用的是饱和非线性激活函数,例如tanh,训练时如果进入到饱和区域,那么会因为梯度变化过小而难以训练;而ReLU是一种非饱和非线性激活函数,接受阈是0~∞∞,不存在tan......
  • Linux操作文件和文件夹的常用基础命令
    文件和文件夹的查看ls:列出当前目录中的文件和文件夹。ls-l:以长格式列出文件信息,包括权限、所有者、大小、修改时间等。ls-a:显示隐藏文件(以.开头的文件)。ls-h:以人类可读的格式显示文件大小。文件和文件夹的创建touchfilename:创建一个新的空文件。mkdirdirname:......
  • VS Code 代码片段指南: 从基础到高级技巧
    前言“系列首发于公众号『非同质前端札记』,若不想错过更多精彩内容,请“星标”一下,敬请关注公众号最新消息。今天咱们来聊聊VSCode里的自定义代码片段。这玩意儿简直是提升编码效率的神器,用好了能让你敲代码更方便!不管你是刚入行的菜鸟还是身经百战的老兵,这篇攻略都......
  • VS Code 代码片段指南: 从基础到高级技巧
    前言“系列首发于公众号『非同质前端札记』,若不想错过更多精彩内容,请“星标”一下,敬请关注公众号最新消息。今天咱们来聊聊VSCode里的自定义代码片段。这玩意儿简直是提升编码效率的神器,用好了能让你敲代码更方便!不管你是刚入行的菜鸟还是身经百战的老兵,这篇攻略都......
  • Mysql基础练习题 595.大的国家 (力扣)
            如果一个国家满足下述两个条件之一,则认为该国是大国:面积至少为300万平方公里(即,3000000km2),或者人口至少为2500万(即25000000)编写解决方案找出大国的国家名称、人口和面积,以任意顺序返回结果表。建表插入数据:CreatetableIfNotExistsWorld......