当前位置：首页 > article >正文

初学者入门C语言指针与链表

article 2024/11/21 1:26:33

什么是链表？

链表是一种数据结构，用于在内存中存储一系列元素。与数组不同，链表中的元素可以不必顺序存储，而是通过指针链接在一起。链表的最简单形式是单向链表，其中每个节点包含一个值和一个指向下一个节点的指针。

以下是一个简单的单向链表结构的定义：

typedef struct Node {
    int value;
    struct Node* next;
} Node;

什么是指针？

指针是一个变量，它存储了一个内存地址。通过指针，我们可以访问该内存地址中存储的数据。在C语言中，可以通过使用取地址运算符`&`获取变量的地址，并使用解引用运算符`*`来访问该地址中存储的值。

以下是一个示例，演示了如何使用指针来交换两个整数的值：

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    int x = 5, y = 10;
    printf("Before swap: x = %d, y = %d\n", x, y);
    swap(&x, &y);
    printf("After swap: x = %d, y = %d\n", x, y);
    return 0;
}

在上面的代码中，`swap`函数接受两个整数指针作为参数，并使用解引用运算符来访问这些指针所指向的值。在`main`函数中，我们声明了两个整数变量`x`和`y`，并在调用`swap`函数时传递它们的地址。

如何使用指针来操作链表？

链表中的每个节点都有一个指向下一个节点的指针。因此，我们可以使用指针来遍历链表，并访问每个节点中存储的值。

以下是一个示例，演示了如何创建一个简单的链表并遍历它：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node* next;
} Node;
void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }
    printf("\n");
}
int main() {
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
    // allocate 3 nodes in the heap
    head = (Node*)malloc(sizeof(Node));
    second = (Node*)malloc(sizeof(Node));
   third = (Node*)malloc(sizeof(Node));
    head->value = 1;      // assign values to the first node
    head->next = second;  // link the first node to the second node
    second->value = 2;    // assign values to the second node
    second->next = third; // link the second node to the third node
    third->value = 3;     // assign values to the third node
    third->next = NULL;   // mark the end of the list
    print_list(head);     // print the list
    // free the nodes
    free(head);
    free(second);
    free(third);
    return 0;
}

在上面的代码中，我们首先定义了一个`print_list`函数，它接受一个指向链表头的指针，并使用一个`while`循环来遍历链表并打印每个节点中的值。

在`main`函数中，我们创建了三个节点，并为每个节点分配了内存。我们然后将这些节点链接在一起，并将链表的头指针指向第一个节点。最后，我们调用`print_list`函数来打印整个链表，并释放了我们分配的所有内存。

如何在链表中插入和删除节点？

在链表中插入和删除节点是一个常见的操作。为了在链表中插入一个新节点，我们需要将新节点的`next`指针链接到链表中的下一个节点，并将链表中前一个节点的`next`指针链接到新节点。删除一个节点时，我们需要将前一个节点的`next`指针链接到下一个节点，并释放被删除节点的内存。

以下是一个示例，演示如何在链表中插入和删除节点：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node* next;
} Node;
void print_list(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }
    printf("\n");
}
void insert_node(Node* head, int value) {
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->value = value;
    new_node->next = NULL;
    current->next = new_node;
}
void delete_node(Node* head, int value) {
    Node* current = head;
    Node* previous = NULL;
    while (current != NULL && current->value != value) {
        previous = current;
        current = current->next;
    }
    if (current == NULL) {
        return; // value not found in list
    }
    if (previous == NULL) {
        head = current->next;//The list is empty
    } else {
        previous->next = current->next;
    }
    free(current);
}
int main() {
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
    // allocate 3 nodes in the heap
    head = (Node*)malloc(sizeof(Node));
    second = (Node*)malloc(sizeof(Node));
    third = (Node*)malloc(sizeof(Node));
    head->value = 1;      // assign
    head->next = second;  // link the first node to the second node
    second->value = 2;    // assign values to the second node
    second->next = third; // link the second node to the third node
    third->value = 3;     // assign values to the third node
    third->next = NULL;   // mark the end of the list
    print_list(head);     // print the list

    insert_node(head, 4); // insert a new node with value 4
    print_list(head);     // print the updated list

    delete_node(head, 2); // delete the node with value 2
    print_list(head);     // print the updated list
    // free the nodes
    free(head);
    free(second);
    free(third);
    return 0;
}

在上面的代码中，我们添加了两个新的函数，`insert_node`和`delete_node`。`insert_node`函数将创建一个新的节点，并将其添加到链表的末尾。`delete_node`函数将搜索链表，找到包含特定值的节点，并从链表中删除该节点。

在`main`函数中，我们首先创建了一个具有三个节点的链表，并打印了该链表。然后我们插入了一个新节点并再次打印了更新后的链表。接下来，我们删除了一个节点并再次打印了更新后的链表。最后，我们释放了所有分配的内存。

指针的使用

指针是 C 语言中的一个重要概念。一个指针是一个变量，它存储了一个内存地址。指针可以用于访问内存中的数据，也可以用于动态地分配内存。在链表中，我们使用指针来链接节点。

以下是一些关于指针的基本操作：

int main() {
    int x = 5;
    int* p = &x;  // declare a pointer to x
    printf("The value of x is %d\n", x);
    printf("The address of x is %p\n", &x);
    printf("The value of p is %p\n", p);
    printf("The value that p points to is %d\n", *p);
    int* q = (int*)malloc(sizeof(int)); // dynamically allocate memory
    *q = 10;                             // assign a value to the memory location
    printf("The value that q points to is %d\n", *q);
    free(q);  // free the memory
    return 0;
}

在上面的代码中，我们首先定义了一个变量`x`，并将其值设置为`5`。然后，我们声明了一个指向`x`的指针`p`，并将其初始化为`&x`，这是`x`的内存地址。我们可以使用`&`运算符获取一个变量的内存地址。

我们使用`printf`函数打印了`x`的值、`x`的内存地址、`p`的值（即指向`x`的内存地址）以及`p`指向的值（即`x`的值）。在 C 语言中，使用`*`运算符可以访问指针指向的值。

接下来，我们使用`malloc`函数动态分配了一个`int`类型的内存空间，并将其地址存储在指针`q`中。我们可以使用`*`运算符将值`10`分配给`q`所指向的内存地址。最后，我们使用`free`函数释放了动态分配的内存空间。