C语言单向链表实现

此文章距离最后一次更新已有 478 天, 文章内容可能已经过时.

前言

代码为博主无聊时自己敲的，作为学习笔记，仅供学习参考，未进行系统性测试，不保证其可用性

学习版

此代码思路来源于网络，写于学习链表时

优点：可以很好的操作所有节点，无需在主函数内执行额外操作
缺点：需要实例化一个节点作为头结点并且不能对其进行操作

#include <stdio.h>
#include <stdlib.h>
// 定义链表结构
typedef struct Basic_LinkList
{
    int data, id;
    Basic_LinkList *next;

} LinkList;

// 函数声明
LinkList *Creat(int n);
void PrintLinkList(LinkList *head);
void Change(LinkList *head);
void DeleteLinkList(LinkList *head);
void HeadInsertLinkList(LinkList *head);
void FootInsertLinkList(LinkList *h);
// 结束声明

int main()
{
    int n;
    scanf("%d", &n);
    LinkList *head = Creat(n); // 创建链表
    // getchar();
    PrintLinkList(head);
    // Change(head);
    // DeleteLinkList(head);
    // HeadInsertLinkList(head);
    FootInsertLinkList(head);
    PrintLinkList(head);
    getchar();
}

LinkList *Creat(int n) // 创建链表函数实现
{
    LinkList *head, *node, *end;
    head = (LinkList *)malloc(sizeof(LinkList)); // head仅使用指针指向node，所以为head单独申请空间
    end = head;                                  // end为中间用于连接链表的工具
    for (int i = 0; i < n; i++)
    {
        node = (LinkList *)malloc(sizeof(LinkList)); // 为节点申请空间
        scanf("%d", &node->data);
        node->id = i + 1;
        end->next = node; // 将end（上一级）的next指针指向新创建的node（连接链表）
        end = node;       // 将end指向新创建的node（代替head，成为上一级）
    }
    end->next = NULL; // 结尾链接
    return head;
}

void Change(LinkList *head) // 修改链表节点值
{
    int n;
    printf("\n请输入需要修改的节点序号:");
    scanf("%d", &n);
    LinkList *h = head;                      // 重新定义一个指针避免对后续操作产生影响(虽然根本没有后续操作了)
    for (int i = 0; i < n && h != NULL; i++) // 将指针移动至指定位置
    {
        h = h->next;
    }
    if (h != NULL)
    {
        printf("\n请输入需要修改的值:");
        scanf("%d", &h->data);
    }
    else
    {
        printf("\n节点不存在");
    }
}

void DeleteLinkList(LinkList *head) // 删除链表节点
{
    int n;
    printf("\n请输入要删除的节点序号:");
    scanf("%d", &n);
    LinkList *h = head, *last;               // 重新定义一个指针避免对后续操作产生影响(虽然根本没有后续操作了)
    for (int i = 0; i < n && h != NULL; i++) // 将指针移动至指定位置
    {
        last = h;
        h = h->next;
    }
    if (h != NULL)
    {
        last->next = h->next; // 将上层node的next指针指向下一层node的地址
        free(h);              // 释放被删除node的内存
    }
    else
    {
        printf("\n节点不存在");
    }
}

void HeadInsertLinkList(LinkList *head) // 向前插入节点
{
    int n, data1;
    printf("\n请输入需要插入的的节点序号（向前插入）:");
    scanf("%d", &n);
    printf("请输入要插入的值:");
    scanf("%d", &data1);
    LinkList *h = head, *last, *mid;
    mid = (LinkList *)malloc(sizeof(LinkList));
    mid->data = data1;
    for (int i = 0; i < n && h != NULL; i++) // 将指针移动至指定位置
    {
        last = h;
        h = h->next;
    }
    if (h != NULL)
    {
        last->next = mid; // 将上层node的next指针指向插入的node地址
        mid->next = h;    // 将插入node的next指针指向下一层地址
    }
    else
    {
        printf("\n节点不存在");
    }
}

void FootInsertLinkList(LinkList *head) // 向后插入节点
{
    int n, data1;
    printf("\n请输入需要插入的节点序号（向后插入）:");
    scanf("%d", &n);
    printf("请输入需要插入的数据:");
    scanf("%d", &data1);
    LinkList *foot, *h, *mid;
    h = head;
    mid = (LinkList *)malloc(sizeof(LinkList));
    mid->data = data1;
    for (int i = 0; i < n && h != NULL; i++) // 将指针移动至指定位置
    {
        h = h->next;
    }
    if (h != NULL)
    {
        foot = h->next;   // 将foot指向h的下一个node地址
        mid->next = foot; // 将插入node的next指针指向foot
        h->next = mid;    // 将h的next指针指向mid
    }
    else
    {
        printf("\n节点不存在");
    }
}

void PrintLinkList(LinkList *head) // 链表的遍历
{
    while (head->next != NULL)
    {
        head = head->next; // 移动指针并跳过第一个head
        printf("%d ", head->data);
    }
}

巩固版

此代码则由自己独立完成

优点：不浪费一个节点（？），封装性好
缺点：无法对头节点进行删除、向前插入操作，需要主函数内有额外操作

#include <stdio.h>
#include <stdlib.h>
/*
    Tips: 本文件内函数的位置参数起始点均为0
*/
// 结构体声明
typedef struct Point_node
{
    int data;
    struct Point_node *next;

} LinkList;
// 函数声明
LinkList *Creat(int n);                                       // 创建链表函数并返回首节点指针
void Display(LinkList *head);                                 // 遍历链表函数
LinkList *Find(LinkList *head, int pos);                      // 查找链表数据并返回该节点的指针
LinkList *Change(LinkList *head, int pos, int data);          // 修改节点数据并返回该节点的指针
int Delete(LinkList *head, int pos);                          // 删除节点(无法用于删除首节点)并返回该节点值
LinkList *Insert_Backward(LinkList *head, int pos, int data); // 插入节点(向后)并返回该节点的指针
LinkList *Insert_Forward(LinkList *head, int pos, int data);  // 插入节点(向前)并返回该节点的指针
//
int main()
{
    int n;
    printf("请输入节点数：");
    scanf("%d", &n);
    LinkList *head = Creat(n);

    Display(head);

    int position = 0, data = 0;
    // printf("\n请输入需要查询的节点位置：");
    // scanf("%d", &position);
    // printf("%d", Find(head, position - 1)->data);

    // printf("\n请输入需要修改的节点位置：");
    // scanf("%d", &position);
    // printf("\n请输入需要修改的值：");
    // scanf("%d", &data);
    // printf("%d", Change(head, position - 1, data)->data);

    // printf("\n请输入需要删除的节点位置：");
    // scanf("%d", &position);
    // printf("%d", Delete(head, position - 1));

    // printf("\n请输入需要插入节点的位置与值(向后)：");
    // scanf("%d %d", &position, &data);
    // printf("%d", Insert_Backward(head, position - 1, data)->data);

    printf("\n请输入需要插入节点的位置与值(向前)：");
    scanf("%d %d", &position, &data);
    printf("%d", Insert_Forward(head, position - 1, data)->data);
    getchar();
}

LinkList *Creat(int n) // 创建链表
{
    LinkList *head = NULL, *end = NULL, *node = NULL;
    printf("请输入节点数据：");
    for (int i = 0; i < n; i++)
    {
        if (head == NULL)
        {
            head = (LinkList *)malloc(sizeof(LinkList));
            head->next = NULL;
            end = head;
            scanf("%d", &end->data);
        }
        else
        {
            node = (LinkList *)malloc(sizeof(LinkList));
            node->next = NULL;
            scanf("%d", &node->data);
            end->next = node;
            end = node;
        }
    }
    return head;
}

void Display(LinkList *head)
{
    while (1)
    {
        if (head == NULL)
        {
            break;
        }
        else
        {
            printf("%d ", head->data);
            head = head->next;
        }
    }
}

LinkList *Find(LinkList *head, int pos)
{
    if (head == NULL)
    {
        printf("\n节点为空");
        return NULL;
    }
    if (pos < 0)
    {
        printf("\n非法位置！");
        return NULL;
    }
    int i;
    for (i = 0; i < pos; i++)
    {
        head = head->next;
        if (head == NULL)
        {
            printf("\n位置越界！");
            return NULL;
        }
    }
    return head;
}
LinkList *Change(LinkList *head, int pos, int data)
{
    LinkList *p = Find(head, pos);
    p->data = data;
    return p;
}
int Delete(LinkList *head, int pos)
{
    int data = NULL;
    LinkList *p = Find(head, pos - 1), *temp;

    if (p == NULL)
    {
        printf("\n删除失败！");
        return NULL;
    }
    temp = p->next;
    p->next = temp->next;
    data = temp->data;
    free(temp);
    return data;
}

LinkList *Insert_Backward(LinkList *head, int pos, int data)
{
    LinkList *p = Find(head, pos);
    if (p == NULL)
    {
        printf("\n插入失败！");
        return NULL;
    }
    // 初始化新的节点
    LinkList *node = (LinkList *)malloc(sizeof(LinkList));
    node->data = data;
    node->next = p->next;
    p->next = node;
    return node;
}

LinkList *Insert_Forward(LinkList *head, int pos, int data)
{
    LinkList *p = Find(head, pos - 1);

    if (p == NULL)
    {
        printf("\n插入失败！");
        return NULL;
    }
    // 初始化新的节点
    LinkList *node = (LinkList *)malloc(sizeof(LinkList));
    node->data = data;
    node->next = p->next;
    p->next = node;
    return node;
}