C语言数据结构与算法之链表(一)

欢迎阅读本篇文章,本文将为大家详细讲解C语言中数据结构与算法之链表。接下来,将从以下几个方面为大家讲述:

  1. 链表的定义
  2. 链表的特点
  3. 链表的分类
  4. 单向链表的实现及应用
  5. 双向链表的实现及应用
  6. 示例说明

1. 链表的定义

链表是由一系列节点组合而成的数据结构,每个节点都包含了一个数据域和一个指向下一个节点的指针域。其中,链表的头结点为第一个节点,而尾节点为最后一个节点。链表通过指针连接各个节点,形成链式的数据存储结构。

2. 链表的特点

链表具有以下特点:

  1. 以节点为单位存储数据,节点之间通过指向下一个节点的指针相连。
  2. 链表的大小可动态变化,可以随时在链表中添加或删除节点。
  3. 链表可以高效地插入和删除元素,时间复杂度为O(1)。

3. 链表的分类

链表可以分为以下两种类型:

  1. 单向链表
    单向链表中的节点只含有一个指针域,指向下一个节点。

  2. 双向链表
    双向链表中的节点含有两个指针域,一个指向下一个节点,另一个指向前一个节点。

4. 单向链表的实现及应用

单向链表的实现比较简单,其中一个简单的实现方式是:

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

typedef struct node {
    int data;            // 数据域
    struct node *next;   // 指针域,指向下一个节点
} Node;

int main() {
    Node *head = (Node*) malloc(sizeof(Node));    // 头结点
    head -> next = NULL;                           // 初始化

    // 创建链表
    for(int i = 0; i < 5; i++) {
        Node *newNode = (Node*) malloc(sizeof(Node));
        newNode -> data = i;
        newNode -> next = head -> next;
        head -> next = newNode;
    }

    // 遍历链表并输出
    Node *p = head -> next;
    while(p != NULL) {
        printf("%d ", p -> data);
        p = p -> next;
    }
    printf("\n");

    return 0;
}

单向链表的应用比较广泛,比如实现队列、链式栈和图等数据结构,甚至在一些算法题中也会用到。

5. 双向链表的实现及应用

双向链表相比单向链表,多出了一个指针来指向前面的节点。因此,双向链表有以下的实现方式:

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

typedef struct node {
    int data;            // 数据域
    struct node *prev;   // 指针域,指向前一个节点
    struct node *next;   // 指针域,指向下一个节点
} Node;

int main() {
    Node *head = (Node*) malloc(sizeof(Node));    // 头结点
    head -> prev = NULL;
    head -> next = NULL;

    // 创建链表
    Node *prev = head, *p = NULL;
    for(int i = 0; i < 5; i++) {
        p = (Node*) malloc(sizeof(Node));
        p -> data = i;
        p -> prev = prev;
        p -> next = NULL;
        prev -> next = p;
        prev = p;
    }

    // 遍历链表并输出
    p = head -> next;
    while(p != NULL) {
        printf("%d ", p -> data);
        p = p -> next;
    }
    printf("\n");

    return 0;
}

双向链表可以在单向链表的基础上,更方便地进行双向遍历以及双向查找。

6. 示例说明

下面,我们来看两个示例。

示例一:使用链表实现栈

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

typedef struct node {
    int data;            // 数据域
    struct node *next;   // 指针域,指向下一个节点
} Node;

typedef struct stack {
    Node *top;    // 栈顶指针
} Stack;

void InitStack(Stack *s) {
    s -> top = (Node*) malloc(sizeof(Node));    // 头结点
    s -> top -> next = NULL;
}

int IsEmpty(Stack *s) {
    return s -> top -> next == NULL;
}

void Push(Stack *s, int x) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode -> data = x;
    newNode -> next = s -> top -> next;
    s -> top -> next = newNode;
}

void Pop(Stack *s) {
    if(IsEmpty(s)) {
        printf("Error: Stack is empty!\n");
        return;
    }
    Node *temp = s -> top -> next;
    s -> top -> next = temp -> next;
    free(temp);
}

int Top(Stack *s) {
    if(IsEmpty(s)) {
        printf("Error: Stack is empty!\n");
        return -1;
    }
    return s -> top -> next -> data;
}

int main() {
    Stack s;
    InitStack(&s);
    Push(&s, 1);
    Push(&s, 2);
    Push(&s, 3);
    Pop(&s);
    Push(&s, 4);
    printf("%d\n", Top(&s));
    return 0;
}

以上代码使用单向链表实现了栈的基本操作,满足了栈的后进先出原则。

示例二:使用链表实现图

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

#define MAXVEX 100

typedef struct EdgeNode {
    int adjvex;                 // 邻接顶点在顶点数组中下标
    struct EdgeNode *next;      // 指向下一个邻接点
    int weight;                 // 边权值
} EdgeNode;

typedef struct VertexNode {
    int data;                   // 顶点信息
    EdgeNode *firstedge;        // 指向第一个邻接点
} VertexNode, AdjList[MAXVEX];

typedef struct GraphAdjList {
    AdjList adjList;            // 邻接表
    int numNodes, numEdges;     // 顶点数和边数
} GraphAdjList;

void CreateGraph(GraphAdjList *G) {
    int i, j, k, w;
    printf("Enter the number of nodes and edges: \n");
    scanf("%d%d", &G -> numNodes, &G -> numEdges);
    for(i = 0; i < G -> numNodes; i++) {
        printf("Enter vertex[%d] data: \n", i);
        scanf("%d", &G -> adjList[i].data);
        G -> adjList[i].firstedge = NULL;
    }
    for(k = 0; k < G -> numEdges; k++) {
        printf("Enter edge[%d] direction(i, j) and weight(w): \n", k);
        scanf("%d%d%d", &i, &j, &w);
        EdgeNode *e = (EdgeNode*) malloc(sizeof(EdgeNode));
        e -> adjvex = j;
        e -> weight = w;
        e -> next = G -> adjList[i].firstedge;
        G -> adjList[i].firstedge = e;
    }
}

void Print(GraphAdjList *G) {
    int i;
    EdgeNode *p;
    for(i = 0; i < G -> numNodes; i++) {
        printf("vertex[%d]: data=%d, edge=%d->", i, G -> adjList[i].data, i);
        p = G -> adjList[i].firstedge;
        while(p != NULL) {
            printf("%d(%d) ", p -> adjvex, p -> weight);
            p = p -> next;
        }
        printf("\n");
    }
}

int main() {
    GraphAdjList G;
    CreateGraph(&G);
    Print(&G);
    return 0;
}

以上代码使用单向链表实现了图的存储,并实现了基本的创建和输出操作。其中,每个顶点通过一个边链表来存储与之相邻接的顶点。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言数据结构与算法之链表(一) - Python技术站

(0)
上一篇 2023年5月17日
下一篇 2023年5月17日

相关文章

  • Java集合和数据结构排序实例详解

    Java集合和数据结构排序实例详解 作为Java程序员,集合和数据结构是我们经常会用到的工具,其中排序是其中非常重要的一环。本文将为大家详细介绍Java中集合和数据结构排序的实例。 Java集合排序 在Java中,集合排序通常使用Collections工具类来完成。Collections提供了多种排序算法,包括插入排序、选择排序、归并排序等等。例如,下面的示…

    数据结构 2023年5月17日
    00
  • Raft协议及伪码解析

    目录 节点的状态转换 follower candidate leader 伪码部分 节点初始化(Initialazation) 选举时其他节点的视角 回到candidate选举时的视角 消息如何广播复制 重要的反复出现的ReplicateLog 节点收到了LogRequest 节点如何追加log,Appendentries 再次回到leader, 如何处理L…

    算法与数据结构 2023年4月17日
    00
  • 2021最新Android笔试题总结美团Android岗职能要求

    2021最新Android笔试题总结和美团Android岗职能要求 简介 本文主要介绍了2021最新的Android笔试题总结和美团Android岗职能要求,旨在为正在面试美团Android岗位的面试者提供参考。 笔试题总结 下面是近期美团Android面试中出现的一些笔试题目: 1. 请描述Android中BroadcastReceiver的生命周期。 安…

    数据结构 2023年5月17日
    00
  • java实现数据结构单链表示例(java单链表)

    下面是 Java 实现数据结构单链表的完整攻略。 简介 单链表是数据结构中的一种,用于存储一组有序的元素。单链表中,每个元素都由一个结点表示,结点中包含了一个指向下一个结点的指针。单链表的结构更加灵活,支持插入、删除等操作。 实现步骤 1. 定义节点类ListNode 单链表的每一个节点包含两个属性,分别是节点值 val 和指向下一个节点的指针 next,所…

    数据结构 2023年5月17日
    00
  • C++深入分析讲解链表

    C++深入分析讲解链表 链表概述 链表是数据结构中最基本和重要的一种,它的实现可以分为链表的节点和链表的指针。每个节点都记录着链表中的一个元素,并带有一个指向下一个节点的指针,这样就可以通过遍历指针,达到遍历链表的目的。 链表数据结构 在C++中,链表可以通过结构体或者类来实现,比如以下这个结构体实现的单向链表: struct Node { int data…

    数据结构 2023年5月17日
    00
  • 多维度深入分析Redis的5种基本数据结构

    多维度深入分析Redis的5种基本数据结构 Redis是一种高性能、内存数据存储系统,它支持多种数据结构,包括字符串、哈希表、列表、集合和有序集合。其中,每种数据结构都具有不同的特性和用途,本文将对这五种基本数据结构进行深入分析。 1. 字符串(string) 字符串是最基本的数据结构,一个字符串可以存储任意二进制数据,例如一个jpg图片或者一个序列化的对象…

    数据结构 2023年5月17日
    00
  • C语言数据结构算法基础之循环队列示例

    标题:C语言数据结构算法基础之循环队列示例 1. 简介 循环队列是一种常见的数据结构,它采用固定大小的数组来模拟队列的数据结构,可以高效地处理队列的进出操作。本文将会讲解循环队列的实现原理和示例代码。 2. 循环队列基本原理 循环队列通过两个指针front和rear来实现队列的添加和删除操作。在初始化时,front和rear的初始值都为0。每当数据进入队列时…

    数据结构 2023年5月17日
    00
  • JavaScript数据结构之链表的实现

    JavaScript数据结构之链表的实现 什么是链表 链表是一种线性数据结构,其中的元素在内存中不连续地存储,每个元素通常由一个存储元素本身的节点和一个指向下一个元素的引用组成。相比较于数组,链表具有如下优缺点: 优点:动态地添加或删除元素时,无需移动其它元素。(数组则需要移动其它元素) 缺点:不能随机地访问某个元素,必须从头开始顺序遍历。(而数组可以通过索…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部