通过C语言实现“数据结构”课程中的链表，数据，数，图

news/2025/2/24 15:50:43

链表

链表是一种线性数据结构，其中元素不是存储在连续的内存位置，而是通过指针链接在一起。每个元素称为一个节点，包含数据部分和指向下一个节点的指针。

单向链表示例：

假设有一个链表包含三个节点：1 -> 2 -> 3 -> NULL

单向链表的C语言实现

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct Node {
    int data;           // 数据部分
    struct Node* next;  // 指向下一个节点的指针
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);  // 创建新节点
    newNode->next = *head;                  // 新节点指向原来的头节点
    *head = newNode;                        // 更新头节点为新节点
}

// 打印链表
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);     // 打印当前节点的数据
        current = current->next;            // 移动到下一个节点
    }
    printf("NULL\n");                       // 表示链表结束
}

int main() {
    struct Node* head = NULL;

    insertAtHead(&head, 3);                 // 插入节点3
    insertAtHead(&head, 2);                 // 插入节点2
    insertAtHead(&head, 1);                 // 插入节点1

    printf("链表: ");
    printList(head);

    // 记得释放内存
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

栈（基于链表）

栈是一种后进先出（LIFO）的数据结构。我们可以使用链表来实现栈，其中链表的头部作为栈顶。

栈示例：

假设有一个栈包含三个元素：10 -> 20 -> 30 （30是栈顶）

基于链表的栈的C语言实现

#include <stdio.h>
#include <stdlib.h>

// 定义栈节点结构
struct StackNode {
    int data;           // 数据部分
    struct StackNode* next;  // 指向下一个节点的指针
};

// 创建新节点
struct StackNode* createStackNode(int data) {
    struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 检查栈是否为空
int isEmpty(struct StackNode* root) {
    return !root;
}

// 入栈操作
void push(struct StackNode** root, int data) {
    struct StackNode* stackNode = createStackNode(data);  // 创建新节点
    stackNode->next = *root;                              // 新节点指向原来的栈顶
    *root = stackNode;                                    // 更新栈顶为新节点
    printf("%d 已入栈\n", data);
}

// 出栈操作
int pop(struct StackNode** root) {
    if (isEmpty(*root)) {
        printf("栈为空\n");
        return -1; // 返回一个特殊值表示错误
    }
    struct StackNode* temp = *root;
    *root = (*root)->next;                                // 更新栈顶为下一个节点
    int popped = temp->data;
    free(temp);                                             // 释放已弹出节点的内存
    return popped;
}

// 获取栈顶元素
int peek(struct StackNode* root) {
    if (isEmpty(root)) {
        printf("栈为空\n");
        return -1; // 返回一个特殊值表示错误
    }
    return root->data;
}

int main() {
    struct StackNode* root = NULL;

    push(&root, 10);                                      // 入栈10
    push(&root, 20);                                      // 入栈20
    push(&root, 30);                                      // 入栈30

    printf("栈顶元素是 %d\n", peek(root));                // 查看栈顶元素

    printf("%d 出栈\n", pop(&root));                      // 出栈30
    printf("%d 出栈\n", pop(&root));                      // 出栈20
    printf("%d 出栈\n", pop(&root));                      // 出栈10

    // 记得释放内存
    while (!isEmpty(root)) {
        pop(&root);
    }

    return 0;
}

树

树是一种非线性的数据结构，由节点组成，其中每个节点都有零个或多个子节点。根节点没有父节点，而其他每个节点恰好有一个父节点。

二叉搜索树示例：

假设有一棵二叉搜索树包含三个节点：5 -> (3, 7)

二叉搜索树的C语言实现

#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构
struct TreeNode {
    int data;               // 数据部分
    struct TreeNode* left;  // 指向左子节点的指针
    struct TreeNode* right; // 指向右子节点的指针
};

// 创建新节点
struct TreeNode* createTreeNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点到二叉搜索树
struct TreeNode* insertBST(struct TreeNode* node, int data) {
    if (node == NULL) {
        return createTreeNode(data);  // 如果节点为空，则创建新节点
    }
    if (data < node->data) {
        node->left = insertBST(node->left, data);   // 插入左子树
    } else if (data > node->data) {
        node->right = insertBST(node->right, data); // 插入右子树
    }
    return node;
}

// 中序遍历二叉搜索树
void inorderTraversal(struct TreeNode* node) {
    if (node != NULL) {
        inorderTraversal(node->left);               // 遍历左子树
        printf("%d -> ", node->data);             // 打印当前节点的数据
        inorderTraversal(node->right);              // 遍历右子树
    }
}

int main() {
    struct TreeNode* root = NULL;

    root = insertBST(root, 5);                    // 插入节点5
    insertBST(root, 3);                           // 插入节点3
    insertBST(root, 7);                           // 插入节点7

    printf("中序遍历结果: ");
    inorderTraversal(root);
    printf("NULL\n");

    // 记得释放内存
    // 这里为了简化，省略了具体的内存释放代码

    return 0;
}

图

图是一种非线性的数据结构，由一组节点（也称为顶点）及其之间的连接（边）组成。图可以是有向的也可以是无向的。

无向图（邻接表表示法）示例：

假设有一个无向图包含五个顶点和六条边：0-1, 0-4, 1-2, 1-3, 1-4, 2-3, 3-4

邻接表表示的无向图的C语言实现

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点
struct AdjListNode {
    int dest;                   // 目标顶点
    struct AdjListNode* next;   // 指向下一条边
};

// 定义邻接表
struct AdjList {
    struct AdjListNode* head;   // 邻接表的头节点
};

// 定义图
struct Graph {
    int V;                      // 顶点数量
    struct AdjList* array;      // 邻接表数组
};

// 创建邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 创建邻接表数组
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

    // 初始化每个邻接列表为空
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加边到图中
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加一条从src到dest的边
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 由于是无向图，再添加一条从dest到src的边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 打印图
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n顶点 %d 的邻居:\n 头 ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    // 创建一个包含5个顶点的图
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);                         // 添加边0-1
    addEdge(graph, 0, 4);                         // 添加边0-4
    addEdge(graph, 1, 2);                         // 添加边1-2
    addEdge(graph, 1, 3);                         // 添加边1-3
    addEdge(graph, 1, 4);                         // 添加边1-4
    addEdge(graph, 2, 3);                         // 添加边2-3
    addEdge(graph, 3, 4);                         // 添加边3-4

    // 打印图的内容
    printGraph(graph);

    // 记得释放内存
    for (int i = 0; i < V; ++i) {
        struct AdjListNode* adjListPtr = graph->array[i].head;
        while (adjListPtr) {
            struct AdjListNode* tmp = adjListPtr;
            adjListPtr = adjListPtr->next;
            free(tmp);
        }
    }
    free(graph->array);
    free(graph);

    return 0;
}

http://www.niftyadmin.cn/n/5864553.html

相关文章

maven模块化管理

maven模块化管理

将一个大项目拆分成若干个子模块&#xff0c;方便项目管理维护、扩展&#xff0c;也方便模块间的相互引用&#xff0c;资源共享 具体步骤 先创建一个空项目&#xff08;父项目&#xff09;即下图的sky-take-out,然后打开项目结构的模块&#xff0c;选中父模块&#xff0c;再点…
阅读更多...
支持向量机（SVM）在 NLP 中的使用场景

支持向量机（SVM）在 NLP 中的使用场景

支持向量机（Support Vector Machine, SVM）是一种强大的监督学习算法，广泛应用于分类任务中。由于其出色的分类性能和高效的计算特点，SVM 已经成为自然语言处理（NLP）领域中的一种经典模型。SVM 在 NLP 中的应用非常广泛，尤其在文本分类任务中，表现出色。 本文将探讨 SV…
阅读更多...
深度解析：大模型在多显卡服务器下的通信机制与分布式训练——以DeepSeek、Ollama和vLLM为例

深度解析：大模型在多显卡服务器下的通信机制与分布式训练——以DeepSeek、Ollama和vLLM为例

一、引言&#xff1a;大模型与多显卡的必然结合 随着大模型参数规模突破千亿级&#xff08;如GPT-4、DeepSeek&#xff09;&#xff0c;单显卡的显存容量与算力已无法满足需求。多显卡并行计算成为训练与推理的核心技术&#xff0c;其核心挑战在于高效通信与负载均衡。本文以国…
阅读更多...
《论多源数据集成及应用》审题技巧 - 系统架构设计师

《论多源数据集成及应用》审题技巧 - 系统架构设计师

论多源数据集成及应用写作框架 一、考点概述 本论题“论多源数据集成及应用”主要考察的是计算机软件测试工程师在数据管理和集成方面的专业知识与实践能力。论题聚焦于信息爆炸时代企业、组织和个人所面临的数据挑战&#xff0c;特别是如何有效地收集、整理和清洗来自不同渠…
阅读更多...
Spring Security+JWT+Redis实现项目级前后端分离认证授权

Spring Security+JWT+Redis实现项目级前后端分离认证授权

1. 整体概述 权限管理包括用户身份认证和授权两部分&#xff0c;简称认证授权。对于需要访问控制到资源&#xff0c;用户首先经过身份认证&#xff0c;认证通过后用户具有该资源的访问权限方可访问。 1.1 认证概述 认证是确认用户身份的过程&#xff0c;确保用户是谁。 1.1.1 …
阅读更多...
【STM32 基于PID的闭环电机控制系统】

【STM32 基于PID的闭环电机控制系统】

STM32 基于PID的闭环电机控制系统 目录 STM32 基于PID的闭环电机控制系统一、PID算法在STM32F103C8T6中的实现思路二、代码实现与解释三、PID算法的调试与优化四、总结 一、PID算法在STM32F103C8T6中的实现思路 基本概念 • 目标 &#xff1a;通过PID算法调节电机的转速&#…
阅读更多...
`sh` 与 `bash` 的区别详解

`sh` 与 `bash` 的区别详解

sh 与 bash 的区别详解 1. 历史背景 sh (Bourne Shell)&#xff1a; 由 Stephen Bourne 在 1977 年开发&#xff0c;是 Unix 系统的默认 Shell。语法简洁&#xff0c;但功能有限。 bash (Bourne Again Shell)&#xff1a; 由 Brian Fox 在 1989 年开发&#xff0c;是 sh 的扩…
阅读更多...
第15届 蓝桥杯 C++编程青少组中/高级选拔赛 202401 真题答案及解析

第15届 蓝桥杯 C++编程青少组中/高级选拔赛 202401 真题答案及解析

第 1 题 【 单选题 】 表达式117 % 16 的结果是（ ）。 A：0 B：5 C：7 D：10 解析： % 是取模运算符，用于计算两个数相除后的余数。 计算 117 / 16，结果是 7，余数是 5。因此，117 % 16 = 5。答案： B 第 2 题 【 单选题 】 下列选项中，字符数组定义正确的是（ …
阅读更多...
最新文章

Copyright @ 2022~2023