C语言怎么实现线性动态单向链表

发布时间:2022-05-16 13:44:27 作者:iii
来源:亿速云 阅读:189

C语言怎么实现线性动态单向链表

链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。与数组不同,链表的内存空间是动态分配的,因此可以灵活地增加或删除节点。本文将介绍如何使用C语言实现一个线性动态单向链表。

1. 链表的基本概念

1.1 节点结构

链表的每个节点通常包含两个部分: - 数据域:存储节点的数据。 - 指针域:指向下一个节点的指针。

在C语言中,我们可以使用结构体来定义一个节点:

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

1.2 链表的头指针

链表的头指针指向链表的第一个节点。如果链表为空,头指针为NULL

struct Node* head = NULL;  // 初始化头指针为空

2. 链表的操作

2.1 创建节点

创建一个新节点并初始化其数据域和指针域。

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

2.2 插入节点

在链表中插入节点有多种方式,常见的有: - 在链表头部插入 - 在链表尾部插入 - 在指定位置插入

2.2.1 在链表头部插入

将新节点插入到链表的头部,使其成为新的头节点。

void insertAtHead(int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    head = newNode;
}

2.2.2 在链表尾部插入

将新节点插入到链表的尾部。

void insertAtTail(int data) {
    struct Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        return;
    }
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

2.2.3 在指定位置插入

在链表的指定位置插入新节点。

void insertAtPosition(int data, int position) {
    if (position < 1) {
        printf("无效的位置\n");
        return;
    }
    if (position == 1) {
        insertAtHead(data);
        return;
    }
    struct Node* newNode = createNode(data);
    struct Node* temp = head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("位置超出链表长度\n");
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

2.3 删除节点

删除链表中的节点也有多种方式: - 删除头节点 - 删除尾节点 - 删除指定位置的节点

2.3.1 删除头节点

删除链表的头节点。

void deleteAtHead() {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    struct Node* temp = head;
    head = head->next;
    free(temp);
}

2.3.2 删除尾节点

删除链表的尾节点。

void deleteAtTail() {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

2.3.3 删除指定位置的节点

删除链表中指定位置的节点。

void deleteAtPosition(int position) {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    if (position < 1) {
        printf("无效的位置\n");
        return;
    }
    if (position == 1) {
        deleteAtHead();
        return;
    }
    struct Node* temp = head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {
        printf("位置超出链表长度\n");
        return;
    }
    struct Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;
    free(nodeToDelete);
}

2.4 遍历链表

遍历链表并打印每个节点的数据。

void printList() {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

2.5 释放链表

释放链表占用的内存,防止内存泄漏。

void freeList() {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

3. 完整示例代码

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* head = NULL;

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

void insertAtHead(int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    head = newNode;
}

void insertAtTail(int data) {
    struct Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
        return;
    }
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void insertAtPosition(int data, int position) {
    if (position < 1) {
        printf("无效的位置\n");
        return;
    }
    if (position == 1) {
        insertAtHead(data);
        return;
    }
    struct Node* newNode = createNode(data);
    struct Node* temp = head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("位置超出链表长度\n");
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void deleteAtHead() {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    struct Node* temp = head;
    head = head->next;
    free(temp);
}

void deleteAtTail() {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

void deleteAtPosition(int position) {
    if (head == NULL) {
        printf("链表为空,无法删除\n");
        return;
    }
    if (position < 1) {
        printf("无效的位置\n");
        return;
    }
    if (position == 1) {
        deleteAtHead();
        return;
    }
    struct Node* temp = head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {
        printf("位置超出链表长度\n");
        return;
    }
    struct Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;
    free(nodeToDelete);
}

void printList() {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

void freeList() {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    insertAtHead(10);
    insertAtHead(20);
    insertAtTail(30);
    insertAtPosition(15, 2);
    printList();  // 输出: 20 -> 15 -> 10 -> 30 -> NULL

    deleteAtHead();
    deleteAtTail();
    deleteAtPosition(2);
    printList();  // 输出: 15 -> 10 -> NULL

    freeList();
    return 0;
}

4. 总结

本文介绍了如何使用C语言实现一个线性动态单向链表,包括节点的创建、插入、删除、遍历和释放等操作。链表是一种灵活的数据结构,适用于需要频繁插入和删除操作的场景。通过掌握链表的基本操作,可以更好地理解和应用其他复杂的数据结构。

推荐阅读:
  1. 单向链表 c语言实现
  2. C语言之字符单向链表

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言

上一篇:​​​​​​​Spring多租户数据源管理AbstractRoutingDataSource怎么用

下一篇:python怎么给内存和cpu使用量设置限制

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》