行业资讯

C语言单链表实例分析

发布时间：2022-04-11 15:28:32 作者：iii
来源：亿速云 阅读：157

C语言单链表实例分析

目录

  1. 引言
  2. 单链表的基本概念
  3. 单链表的实现
  4. 单链表的应用实例
  5. 单链表的优缺点
  6. 总结

引言

在计算机科学中，数据结构是组织和存储数据的方式，以便有效地访问和修改数据。链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表是链表的一种，它只有一个指向下一个节点的指针。本文将详细介绍单链表的基本概念、实现方法以及应用实例。

单链表的基本概念

2.1 单链表的定义

单链表是一种线性数据结构，它由一系列节点组成，每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。单链表的最后一个节点的指针域通常指向NULL，表示链表的结束。

2.2 单链表的结构

单链表的结构可以用以下伪代码表示：

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

2.3 单链表的操作

单链表的基本操作包括：

单链表的实现

3.1 单链表的节点定义

在C语言中，单链表的节点可以通过结构体来定义：

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

3.2 单链表的创建

创建一个单链表通常需要初始化一个头节点，头节点不存储数据，只用于指向链表的第一个节点。

struct Node* createLinkedList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    head->next = NULL;  // 初始化头节点的指针域为NULL
    return head;
}

3.3 单链表的插入

在单链表中插入节点可以分为以下几种情况：

  1. 在链表头部插入节点：

    void insertAtHead(struct Node* head, int data) {
   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   if (newNode == NULL) {
       printf("Memory allocation failed\n");
       return;
   }
   newNode->data = data;
   newNode->next = head->next;
   head->next = newNode;
}

  2. 在链表尾部插入节点：

    void insertAtTail(struct Node* head, int data) {
   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   if (newNode == NULL) {
       printf("Memory allocation failed\n");
       return;
   }
   newNode->data = data;
   newNode->next = NULL;


   struct Node* current = head;
   while (current->next != NULL) {
       current = current->next;
   }
   current->next = newNode;
}

  3. 在链表中间插入节点：

    void insertAfter(struct Node* prevNode, int data) {
   if (prevNode == NULL) {
       printf("Previous node cannot be NULL\n");
       return;
   }
   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   if (newNode == NULL) {
       printf("Memory allocation failed\n");
       return;
   }
   newNode->data = data;
   newNode->next = prevNode->next;
   prevNode->next = newNode;
}

3.4 单链表的删除

删除单链表中的节点可以分为以下几种情况：

  1. 删除链表头部节点：

    void deleteAtHead(struct Node* head) {
   if (head->next == NULL) {
       printf("List is empty\n");
       return;
   }
   struct Node* temp = head->next;
   head->next = temp->next;
   free(temp);
}

  2. 删除链表尾部节点：

    void deleteAtTail(struct Node* head) {
   if (head->next == NULL) {
       printf("List is empty\n");
       return;
   }
   struct Node* current = head;
   while (current->next->next != NULL) {
       current = current->next;
   }
   struct Node* temp = current->next;
   current->next = NULL;
   free(temp);
}

  3. 删除链表中间节点：

    void deleteNode(struct Node* head, int data) {
   struct Node* current = head;
   while (current->next != NULL && current->next->data != data) {
       current = current->next;
   }
   if (current->next == NULL) {
       printf("Node not found\n");
       return;
   }
   struct Node* temp = current->next;
   current->next = temp->next;
   free(temp);
}

3.5 单链表的遍历

遍历单链表是指访问链表中的每个节点，并执行某些操作（如打印节点数据）。

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

3.6 单链表的查找

在单链表中查找指定数据的节点，并返回该节点的指针。

struct Node* searchNode(struct Node* head, int data) {
    struct Node* current = head->next;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

3.7 单链表的销毁

销毁单链表是指释放链表占用的所有内存。

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

单链表的应用实例

4.1 学生信息管理系统

假设我们需要实现一个简单的学生信息管理系统，每个学生信息包括学号和姓名。我们可以使用单链表来存储学生信息。

struct Student {
    int id;
    char name[50];
    struct Student* next;
};

struct Student* createStudent(int id, const char* name) {
    struct Student* student = (struct Student*)malloc(sizeof(struct Student));
    if (student == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    student->id = id;
    strcpy(student->name, name);
    student->next = NULL;
    return student;
}

void insertStudent(struct Student** head, int id, const char* name) {
    struct Student* newStudent = createStudent(id, name);
    if (*head == NULL) {
        *head = newStudent;
    } else {
        struct Student* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newStudent;
    }
}

void printStudents(struct Student* head) {
    struct Student* current = head;
    while (current != NULL) {
        printf("ID: %d, Name: %s\n", current->id, current->name);
        current = current->next;
    }
}

void deleteStudent(struct Student** head, int id) {
    struct Student* current = *head;
    struct Student* prev = NULL;
    while (current != NULL && current->id != id) {
        prev = current;
        current = current->next;
    }
    if (current == NULL) {
        printf("Student not found\n");
        return;
    }
    if (prev == NULL) {
        *head = current->next;
    } else {
        prev->next = current->next;
    }
    free(current);
}

void destroyStudents(struct Student* head) {
    struct Student* current = head;
    while (current != NULL) {
        struct Student* temp = current;
        current = current->next;
        free(temp);
    }
}

4.2 多项式相加

假设我们需要实现两个多项式的相加操作，每个多项式可以用单链表表示，每个节点存储一个项的系数和指数。

struct Term {
    int coefficient;
    int exponent;
    struct Term* next;
};

struct Term* createTerm(int coefficient, int exponent) {
    struct Term* term = (struct Term*)malloc(sizeof(struct Term));
    if (term == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    term->coefficient = coefficient;
    term->exponent = exponent;
    term->next = NULL;
    return term;
}

void insertTerm(struct Term** head, int coefficient, int exponent) {
    struct Term* newTerm = createTerm(coefficient, exponent);
    if (*head == NULL) {
        *head = newTerm;
    } else {
        struct Term* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newTerm;
    }
}

struct Term* addPolynomials(struct Term* poly1, struct Term* poly2) {
    struct Term* result = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exponent > poly2->exponent) {
            insertTerm(&result, poly1->coefficient, poly1->exponent);
            poly1 = poly1->next;
        } else if (poly1->exponent < poly2->exponent) {
            insertTerm(&result, poly2->coefficient, poly2->exponent);
            poly2 = poly2->next;
        } else {
            int sum = poly1->coefficient + poly2->coefficient;
            if (sum != 0) {
                insertTerm(&result, sum, poly1->exponent);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    while (poly1 != NULL) {
        insertTerm(&result, poly1->coefficient, poly1->exponent);
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        insertTerm(&result, poly2->coefficient, poly2->exponent);
        poly2 = poly2->next;
    }
    return result;
}

void printPolynomial(struct Term* head) {
    struct Term* current = head;
    while (current != NULL) {
        printf("%dx^%d", current->coefficient, current->exponent);
        if (current->next != NULL) {
            printf(" + ");
        }
        current = current->next;
    }
    printf("\n");
}

void destroyPolynomial(struct Term* head) {
    struct Term* current = head;
    while (current != NULL) {
        struct Term* temp = current;
        current = current->next;
        free(temp);
    }
}

单链表的优缺点

5.1 优点

5.2 缺点

总结

单链表是一种简单而灵活的数据结构，适用于需要频繁插入和删除操作的场景。通过本文的介绍，我们了解了单链表的基本概念、实现方法以及应用实例。虽然单链表在某些方面存在不足，但它在许多实际应用中仍然具有重要的价值。希望本文能够帮助读者更好地理解和应用单链表。

推荐阅读：
  1. 【C语言数据结构】单链表
  2. [c语言]单链表的实现

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

c语言

上一篇：vue如何实现纯前端表格滚动分页加载

下一篇：PostgreSQL聚合函数的分组排序怎么使用

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号