单链表之无头链表(C语言版)-阿里云开发者社区

单链表之无头链表(C语言版)

2024-10-14 10

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本文详细介绍了使用C语言实现无头单链表的方法，包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除，以及链表的打印等功能。文章通过具体的代码示例，展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除，以及如何清空和销毁链表。

单链表之无头链表

在这里插入图片描述
1. 定义节点结构

NODE为节点类型
LPNODE 为节点指针类型

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

//定义节点结构
typedef struct Node_tlg{
    int data;         //数据域
    struct Node_tlg* next; //指针域
}NODE,*LPNODE;

节点结构

2. 定义链表结构

size 当前节点个数
frontNode 首元节点指针
tailNode 尾节点指针
List 链表数据类型

//定义链表结构
typedef struct List_tlg{
    int   size;        //当前节点个数
    NODE* frontNode;   //首元节点(头节点)指针
    //LPNODE frontNode;  也可
    NODE* tailNode;    //尾节点指针
}List;

3. 创建链表

//创建链表
List* createList()
{
    List* list = (List*)malloc(sizeof(List));
    if (NULL == list)
    {
        printf("链表空间申请失败!\n");
        return NULL;
    }
    //初始化链表数据
    list->size = 0;
    list->frontNode = NULL;
    list->tailNode = NULL;
    return list;
}

4. 创建节点

//创建节点
LPNODE createNode(int data)
{
    LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
    if (NULL == newNode)
    {
        printf("节点空间申请失败!\n");
        return NULL;
    }
    //初始化节点数据
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

5. 求链表长度

//求链表长度大小
int listSize(List* list)
{
    return list->size;
}

6. 判断链表是否为空

//求链表是否为空
int empty(List* list)
{
    return list->size == 0;
}

7. 头插法插入数据

为空直接插入即可

   1. 头节点指针(frontNode),尾节点指针(tailNode)均指向新节点

不为空头插法插入数据

 1. 新节点(newNode)指针域指向首元节点
 2. frontNode(链表首元节点)指针移动到新节点(newNode)

//头部插入
void insertFront(List* list, int data)
{
    //创建一个节点
    LPNODE newNode = createNode(data);
    //表为空直接插入
    if (empty(list))
    {
        //头指针尾指针均指向创建的新节点
        list->frontNode = newNode;
        list->tailNode = newNode;
    }
    //头插,移动头节点指针
    else{
        newNode->next = list->frontNode;
        list->frontNode = newNode;
    }
    list->size++;
}

头插法插入数据

8. 尾插法插入数据

为空直接插入即可

   1. 头节点指针,尾节点指针均指向新节点

不为空头插法插入数据

 1. 尾节点(tailNode)的next域指向新节点(newNode)
 2. tailNode(链表尾节点)指针移动到新节点(newNode)

//尾部插入
void insertTail(List* list, int data)
{
    //创建一个节点
    LPNODE newNode = createNode(data);
    //为空直接插入
    if (empty(list))
    {
        list->frontNode = newNode;
        list->tailNode = newNode;
    }
    //插入节点到尾部,移动尾指针
    else{
        list->tailNode->next = newNode;
        list->tailNode = newNode;  
    }
    list->size++;
}

尾插法插入数据

9. 自定义位置插入数据

//自定义位置插入
void insertAppoint(List* list, int data, int pos)
{
    //创建一个节点
    LPNODE newNode = createNode(data);
    LPNODE curNode = list->frontNode;
    LPNODE beforeNode = NULL;
    if (pos > list->size || pos <= 0)
    {
        printf("插入的位置有误!\n");
        return;
    }
    if (pos == 1)   //头插
    {
        insertFront(list, data);
        return;
    }
    while (--pos && curNode->next!=NULL)
    {
        beforeNode = curNode;
        curNode = curNode->next;
    }
    newNode->next = curNode;
    beforeNode->next = newNode;
    list->size++;
}

指定位置插入数据

10. 头删法删除数据

只有一个节点

     1. 直接删除
     2. 将首元节点指针(frontNode),尾节点指针(tailNode)置空即可

头删法删除

   1. 保存要删除的节点(定义一个节点保存首元节点)
   2. 首元节点指针(frontNode)指向首元节点(或要删除节点)下一个节点
   3. 删除保存的节点

//头部删除
void deleteFront(List* list)
{
    if (empty(list))
    {
        printf("表为空,无元素可删!\n");
        return;
    }
    if (listSize(list) == 1)
    {
        LPNODE delNode = list->frontNode;
        free(delNode);
        delNode = NULL;
        list->frontNode = NULL;
        list->tailNode = NULL;
    }
    else{
        LPNODE delNode = list->frontNode;
        list->frontNode = delNode->next;
        free(delNode);
        delNode = NULL;
    }
    list->size--;
}

头删法删除节点

11. 尾删法删除数据

只有一个节点

    1. 直接删除
    2. 将首元节点指针(frontNode),尾节点指针(tailNode)置空即可

尾删法删除

   1. 保存要删除的节点(定义一个节点保存最后一个节点delNode)
   2. 定义一个节点去保存需要删除节点的前一个节点(curNode)
   3. 尾节点指针(tailNode)指向curNode节点
   4. 删除保存的节点(delNode)

//尾部删除
void deleteTail(List* list)
{
    if (empty(list))
    {
        printf("表为空,无元素可删!\n");
        return;
    }
    if (listSize(list) == 1)
    {
        LPNODE delNode = list->tailNode;
        free(delNode);
        delNode = NULL;
        list->frontNode = NULL;
        list->tailNode = NULL;
    }
    else
    {
        LPNODE delNode = list->tailNode;
        LPNODE curNode = list->frontNode;  //保存删除节点的前一个节点
        while (curNode->next->next != NULL)
        {
            curNode = curNode->next;
        }
        list->tailNode = curNode;
        free(delNode);
        delNode = NULL;
        curNode->next = NULL;
    }
    list->size--;
}

尾删法删除节点

12. 自定义位置删除数据

//自定义位置删除
void deleteAppoint(List* list, int pos)
{
    if (empty(list))
    {
        printf("表为空,无元素可删!\n");
        return;
    }
    LPNODE delNode = list->frontNode;
    LPNODE curNode = NULL;
    if (pos == 1)   //pos为1直接头删
    {
        deleteFront(list);
        return;
    }
    while (--pos > 0 && delNode->next != NULL)
    {
        curNode = delNode;
        delNode = delNode->next;
    }
    if (curNode == NULL)
    {
        printf("节点删除失败!可能位置有误哦!\n");
        return;
    }
    curNode->next = delNode->next;
    free(delNode);
    delNode = NULL;
    list->size--;
}

13. 删除指定数据

//指定数据删除
void deleteByData(List* list, int data)
{
   //判断链表中是否有用户想要删除的数据的标志
    bool flag = false;
    if (empty(list))
    {
        printf("表为空,无元素可删!\n");
        return;
    }
    LPNODE delNode = list->frontNode;
    LPNODE curNode = NULL;
    while (delNode->next!=NULL)
    {
        curNode = delNode;
        delNode = delNode->next;
        if (delNode->data == data)
        {
        //找到数据,标志置为true,退出循环
            flag = true;  
            break;
        }
    }
    //节点删除
    if (flag){
        curNode->next = delNode->next;
        free(delNode);
        delNode = NULL;
        list->size--;
    }
    else
    {
        printf("表中没有你想要删除的数据!\n");
        return;
    }
}

14. 清空链表

//清空链表
void clearList(List* list)
{
    int n = listSize(list);
    while (n--)
    {
        //头删删除链表中的节点
        deleteFront(list);
    }
    if (list->size == 0)
    {
        printf("链表已清空!\n");
        return;
    }
    else{
        printf("链表未清空!\n");
        clearList(list);
    }
}

15. 销毁链表

//销毁链表
//注意改变指针指向需要传入二级指针
void destoryList(List** plist)
{
    if ((*plist)->size >= 0)
    {
        clearList(*plist);
    }
    free(*plist);
    *plist = NULL;
    printf("链表已经销毁!\n");
}

16. 打印链表

//打印链表
void showList(List* list,char* str)
{
    printf("%s\n", str);
    if (listSize(list) == 0 || list == NULL)
    {
        printf("链表为空,无法打印!\n");
        return;
    }
    LPNODE curNode = list->frontNode;
    while (curNode != NULL)
    {
        printf("%d\t", curNode->data);
        curNode = curNode->next;
    }
    //打印当前链表长度
    printf("\n当前链表长度: %d", list->size);
    putchar('\n');
    putchar('\n');
}

17.链表功能测试

int main()
{
    system("color 0B");
    //创建无头链表
    List* mylist = createList();
    //头插
    for (int i = 0; i < 10; i++)
    {
        insertFront(mylist, 520 + i);
    }
    showList(mylist,"头插: ");
    //尾插
    for (int i = 0; i < 5; i++)
    {
        insertTail(mylist, 580 + i);
    }
    showList(mylist,"尾插: ");
    //头删
    deleteFront(mylist);
    showList(mylist,"头删: ");
    //尾删
    deleteTail(mylist);
    showList(mylist,"尾删: ");
    //自定义位置插入
    insertAppoint(mylist,1314,2);
    showList(mylist,"自定义位置插入: ");
    //自定义位置删除
    deleteAppoint(mylist, 2);
    showList(mylist,"自定义位置删除: ");
    //指定数据删除
    deleteByData(mylist, 1000);
    showList(mylist, "指定数据删除: ");
    //清空链表
    clearList(mylist);
    //销毁链表
    destoryList(&mylist);  //二级指针传入改变指针指向

    system("pause");
    return 0;
}

测试数据

单链表之无头链表(C语言版)

单链表之无头链表

热门文章

最新文章

相关课程

相关电子书