C语言实现线性表—链式存储（普通单链表）

1.定义结构体

typedef struct LNode
{
    int date;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;     //定义了2个别名LNode（用于一般的结构体定义）和*LinkList（用于结构体指针的定义）

 2.InitList初始化链表（初始化链表就是创立头结点）

LinkList InitList()
{
    LinkList L = (LNode *)malloc(sizeof(LNode)); 
    L->next = NULL;
    return L;
}

3.List_HeadInsert头插入-建立单链表

bool List_HeadInsert(LinkList L)
{
    int x;    //插入数字大小
    LNode *s; //指向结点的指针
    printf("请输入要插入的数字，输入999则表示结束插入\n");
    scanf("%d", &x);
    while (x != 999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->date = x;
        s->next = L->next;
        L->next = s;
        printf("请输入要插入的数字，输入999则表示结束插入\n");
        scanf("%d", &x);
    }
    return true;
}

4.List_TailInsert尾插入-建立单链表

bool List_TailInsert(LinkList L)
{
    int x;        //插入的数字大小
    LNode *s;     //指向结点的指针
    LNode *l = L; //尾指针
    printf("请输入要插入到数字，输入999则表示结束输入\n");
    scanf("%d", &x);
    while (x != 999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->date = x;
        l->next = s;
        s->next = NULL; //可以写在while循环外，因为只有最后一个结点的next才需要NULL
        l = s;
        printf("请输入要插入到数字，输入999则表示结束输入\n");
        scanf("%d", &x);
    }
    return true;
}

5.GetElem按序号查找结点

LNode *GetElem(LNode *L, int x) //返回一个结构体指针
{
    int s = 1;
    if (x < 0)
        return NULL;
    LNode *p = L->next;
    while (p != NULL && s != x) //不满足一个条件就退出
    {
        p = p->next;
        s++;
    }
    return p;
}

6.LocateElem按值查找结点

LNode *LocateElem(LNode *L, int x)
{
    int s = 0; //定义按值查找元素在链表中的位置
    LNode *p = L->next;
    while (p != NULL && p->date != x)
    {
        p = p->next;
        s++; //对s范围进行处理，也可以输出
    }
    return p;
}

7.ListInsert插入链表

void ListInsert(LNode *L, int x, int m)
{
    LNode *p = GetElem(L, x - 1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->date = m;
    s->next = p->next;
    p->next = s;
}

8.ListDelect删除链表

void ListDelect(LNode *L, int x, int *a)
{
    LNode *p = GetElem(L, x - 1);
    LNode *q = p->next;
    *a = q->date;
    p->next = q->next;
}

9.Length求表长

int Length(LNode *L)
{
    int s = 0;
    LNode *p = L->next;
    while (p != NULL)
    {
        p = p->next;
        s++;
    }
    return s;
}

10.DestroyList销毁链表

void DestroyList(LNode *L)
{
    LNode *p = L;
    while (p->next != NULL)
    {
        LNode *a = p;
        p = p->next;
        free(a);
    }
    free(p);
    L = NULL;
}

11.PrintList输出单链表（普通单链表只能从“表头”开始输出）

bool PrintList(LinkList L)
{
    LNode *s = L;
    if (L->next == NULL)
        return false;
    printf("链表输出结果为：");
    while (s->next != NULL)
    {
        s = s->next;
        printf("%d ", s->date);
    }
    printf("\n");
    return true;
}

完整代码：

//线性表-链式存储（普通单链表）

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

//定义结构体
typedef struct LNode
{
    int date;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;     //定义了2个别名LNode（用于一般的结构体定义）和*LinkList（用于结构体指针的定义）

// InitList初始化链表（初始化链表就是创立头结点）
LinkList InitList()
{
    LinkList L = (LNode *)malloc(sizeof(LNode)); 
    L->next = NULL;
    return L;
}

// List_HeadInsert头插入-建立单链表
// bool List_HeadInsert(LinkList L)
// {
//     int x;    //插入数字大小
//     LNode *s; //指向结点的指针
//     printf("请输入要插入的数字，输入999则表示结束插入\n");
//     scanf("%d", &x);
//     while (x != 999)
//     {
//         s = (LNode *)malloc(sizeof(LNode));
//         s->date = x;
//         s->next = L->next;
//         L->next = s;
//         printf("请输入要插入的数字，输入999则表示结束插入\n");
//         scanf("%d", &x);
//     }
//     return true;
// }

// List_TailInsert尾插入-建立单链表
bool List_TailInsert(LinkList L)
{
    int x;        //插入的数字大小
    LNode *s;     //指向结点的指针
    LNode *l = L; //尾指针
    printf("请输入要插入到数字，输入999则表示结束输入\n");
    scanf("%d", &x);
    while (x != 999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->date = x;
        l->next = s;
        s->next = NULL; //可以写在while循环外，因为只有最后一个结点的next才需要NULL
        l = s;
        printf("请输入要插入到数字，输入999则表示结束输入\n");
        scanf("%d", &x);
    }
    return true;
}

// GetElem按序号查找结点
LNode *GetElem(LNode *L, int x) //返回一个结构体指针
{
    int s = 1;
    if (x < 0)
        return NULL;
    LNode *p = L->next;
    while (p != NULL && s != x) //不满足一个条件就退出
    {
        p = p->next;
        s++;
    }
    return p;
}

// LocateElem按值查找结点
LNode *LocateElem(LNode *L, int x)
{
    int s = 0; //定义按值查找元素在链表中的位置
    LNode *p = L->next;
    while (p != NULL && p->date != x)
    {
        p = p->next;
        s++; //对s范围进行处理，也可以输出
    }
    return p;
}

// ListInsert插入链表
void ListInsert(LNode *L, int x, int m)
{
    LNode *p = GetElem(L, x - 1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->date = m;
    s->next = p->next;
    p->next = s;
}

// ListDelect删除链表
void ListDelect(LNode *L, int x, int *a)
{
    LNode *p = GetElem(L, x - 1);
    LNode *q = p->next;
    *a = q->date;
    p->next = q->next;
}

// Length求表长
int Length(LNode *L)
{
    int s = 0;
    LNode *p = L->next;
    while (p != NULL)
    {
        p = p->next;
        s++;
    }
    return s;
}

// DestroyList销毁链表
void DestroyList(LNode *L)
{
    LNode *p = L;
    while (p->next != NULL)
    {
        LNode *a = p;
        p = p->next;
        free(a);
    }
    free(p);
    L = NULL;
}

// PrintList输出单链表（普通单链表只能从“表头”开始输出）
bool PrintList(LinkList L)
{
    LNode *s = L;
    if (L->next == NULL)
        return false;
    printf("链表输出结果为：");
    while (s->next != NULL)
    {
        s = s->next;
        printf("%d ", s->date);
    }
    printf("\n");
    return true;
}

int main()
{
    //定义结构体指针（注意此时L只是一个指向结构体的指针，他的地址需要建立头结点之后才会得到）
    LinkList L = InitList(); //这里的L就是头指针
    // List_HeadInsert(L);       //头插入建立单链表
    List_TailInsert(L);       //尾插入建立单链表
    LNode *E = GetElem(L, 5); //按序号查找第5个元素，返回地址
    printf("按序号查找的元素date值为：%d\n", E->date);
    LNode *x = LocateElem(L, 3); //按值查找数值为3的结点，返回序号值
    printf("按值查找的元素date值为：%d\n", x->date);
    ListInsert(L, 5, 666); //在第5个位置插入666
    int l1 = Length(L);    //链表长度
    printf("链表长度为：%d\n", l1);
    PrintList(L); //输出单链表

    int a;                // a是要删除元素的值-它是由第ListDelect()中的指针修改可得a的值
    ListDelect(L, 2, &a); //删除链表中位置为2的结点，并赋值删除元素
    printf("删除元素为%d\n", a);

    int l2 = Length(L); //链表长度
    printf("链表长度为：%d\n", l2);
    PrintList(L); //输出单链表

    DestroyList(L); //销毁链表

    return 0;
}

运行结果：

注：如有错误之处，请大佬指正