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;
}

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