C语言单链表实现

C语言单链表实现

简单的实现一些功能:

1. 定义节点结构
2. 创建头节点
3. 创建普通节点
4. 头删
5. 尾删
6. 头插
7. 尾插
8. 指定位置插入
9. 指定位置删除
10. 清空链表
11. 销毁链表
12. 打印链表数据

有头单链表实际就是创建一个头节点,不存放数据,然后做一系列的操作

1.定义节点结构

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

typedef struct Node_tlg
{
    int data;
    struct Node_tlg* next;
}NODE,*LPNODE;

数据域存放当前节点的数据,指针域存放下一个节点

2.创建头节点(头节点不存储数据)

LPNODE createHeadNode()
{
    LPNODE head = (LPNODE)malloc(sizeof(NODE));
    if (NULL == head)
    {
        printf("头节点空间申请失败!\n");
        return NULL;
    }
    head->next = NULL;
    return head;
}

3.创建普通节点

LPNODE createNewNode(int data)
{
    LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
    if (NULL == newNode)
    {
        printf("新节点内存申请失败!\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

4.头删

删掉head(头节点后面的第一个节点(首元节点))

void deleteFrontNode(LPNODE head)
{
    if (NULL == head->next)
    {
        printf("表为空,无节点可删!\n");
    }
    else
    {
        LPNODE delNode = head->next;
        head->next = delNode->next;
        free(delNode);          //释放节点内存空间
        delNode = NULL;
    }
}

5.1 尾删法1

void deleteTailNode(LPNODE head)
{
    if (NULL == head->next)
    {
        printf("表为空,无节点可删!\n");
    }
    else{
        LPNODE curNode = head;
        while (curNode->next->next != NULL)
        {
            curNode = curNode->next;
        }
        LPNODE delNode = curNode->next;
        curNode->next = NULL;
        free(delNode);
        delNode = NULL;
    }
}

因为需要将删除节点的前一个节点的next域置为NULL,因此需要保存删除节点的前一个节点,然后将其的next域置为空

5.1 尾删法二

void deleteTailNode2(LPNODE head)
{
    if (NULL == head->next)
    {
        printf("表为空,无节点可删!\n");
    }
    else{
        LPNODE curNode = NULL;   //删除节点的前一个节点
        LPNODE delNode = head;
        while (delNode->next != NULL)
        {
            curNode = delNode;
            delNode = delNode->next;
        }
        curNode->next = NULL;
        free(delNode);
        delNode = NULL;
    }
}

6.头插

void insertFrontNode(LPNODE head,int data)
{
    //创建一个新节点
    LPNODE newNode = createNewNode(data);
    if (head->next == NULL)  //表空直接插入
    {
        head->next = newNode;
    }
    else
    {
        newNode->next = head->next;
        head->next = newNode;
    }
}

先让newNode的next域指向head的next是为了防止head后节点的丢失,因此,先连接后面,然后再连接前面

7.尾插

void insertTailNode(LPNODE head,int data)
{
    //创建一个新节点
    LPNODE newNode = createNewNode(data);
    //直接找到最后一个节点插入即可
    LPNODE curNode = head;
    while (curNode->next != NULL)
    {
        curNode = curNode->next;
    }
    curNode->next = newNode;
}

直接找到最后一个节点,将newNode连接到后面即可

8.指定位置插入

void insertNodeByPos(LPNODE head,int data,int pos)
{
    LPNODE newNode = createNewNode(data);
    LPNODE curNode = head;
    //防止pos位置大于链表的长度,处理为直接插入到表尾
    while (--pos > 0 && curNode->next != NULL)
    {
        curNode = curNode->next;
    }
    newNode->next = curNode->next;
    curNode->next = newNode;
}

9.指定位置删除

void deleteNodeByPos(LPNODE head,int pos)
{
    LPNODE curNode = head->next;
    --pos;                      //curNode为删除节点的前一个节点,因此减掉一次后移
    while (--pos > 0 && curNode->next->next != NULL)
    {
        curNode = curNode->next;
    }
    LPNODE delNode = curNode->next;
    curNode->next = delNode->next;
    free(delNode);
    delNode = NULL;
}

10.清空链表

void cleanList(LPNODE head)
{
    while (head->next != NULL)
    {
        deleteFrontNode(head);
    }
}

11.销毁链表

void destoryList(LPNODE** phead)  //因为需要改变指针的指向,因此传二级指针
{
    cleanList(*phead);
    free(*phead);
    *phead = NULL;
    if (*phead == NULL)
    {
        printf("销毁成功!\n");
    }
}

12.打印链表数据

void printListData(LPNODE head)
{
    if (head->next == NULL)
    {
        printf("链表为空!\n");
    }
    else{
        LPNODE curNode = head->next;
        while (curNode != NULL)
        {
            printf("%d\t", curNode->data);
            curNode = curNode->next;  //节点向后移动
        }
    }
    putchar('\n');
}

13.手动连接测试

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

//中间省略

int main()
{
    system("color 0B");
    //创建头节点
    LPNODE head = createHeadNode();

    //手动连接法
    NODE Node1, Node2, Node3;
    Node1.data = 520;
    Node2.data = 521;
    Node3.data = 522;
    //连接
    head->next = &Node1;
    Node1.next = &Node2;
    Node2.next = &Node3;
    Node3.next = NULL;
    //打印
    printListData(head);

    system("pause");
    return 0;
}

14.自动连接测试

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

//中间省略

int main()
{
    system("color 0B");
    //创建头节点
    LPNODE head = createHeadNode();

    printf("头插:\n");
    for (int i = 0; i < 5; i++)
    {
        insertFrontNode(head, i + 500);
    }
    printListData(head);

    printf("尾插:\n");
    for (int i = 0; i < 5; i++)
    {
        insertTailNode(head, i + 1000);
    }
    printListData(head);

    //    头删
    printf("头删:\n");
    deleteFrontNode(head);
    printListData(head);

    //    尾删1
    printf("尾删1:\n");
    deleteTailNode(head);
    printListData(head);

    //尾删2
    printf("尾删2:\n");
    deleteTailNode2(head);
    printListData(head);

    //    指定位置插入
    printf("指定位置5插入:\n");
    insertNodeByPos(head, 1314, 5);
    printListData(head);

    //    指定位置删除
    printf("指定位置5删除:\n");
    deleteNodeByPos(head, 5);
    printListData(head);

    //    清空链表
    printf("清空链表:\n");
    cleanList(head);
    printListData(head);

    //    销毁链表
    printf("销毁链表:\n");
    destoryList(&head);
    putchar("\n");

    system("pause");
    return 0;
}

~很短暂很喜欢很遗憾~