什么是单向链表？

链表是线性表的一种，通过指针实现线性逻辑关系。链表可以动态地进行存储分配，根据需要开辟内存单元。

链表有带头结点和不带头结点之分。

单链表 vs 顺序表

单向链表指针操作底层原理

单向链表结构体声明

typedef struct linklist{
    data_t data;//数据域
    //LINK *next;//错误声明
    struct linklist *next;//指针域，指向下一个节点
}LINK, *LINKLIST;

LINK等价于struct linklist

LINKLIST等价于LINK*

注意：结构体成员中不能有自身类型定义的结构体，会导致无穷的递归定义。但结构体的成员可以是有自身类型定义的指针，通过这个指针来引用自身类型的结构体。

链表的操作

基本操作：创建、插入（头插/尾插）、删除、遍历（打印）、查找、修改等。

创建一个头结点

LINK *createHeadNode(void)
{
    LINK *h = (LINK *)malloc(sizeof(LINK));
    h->next = NULL;
    return h;
}

头结点的指针域指向第一个数据结点，如果没有数据结点则指向NULL

头结点的数据域没有数据

创建一个数据结点

LINK *createDataNode(data_t val)
{
    LINK *node = (LINK *)malloc(sizeof(LINK));
    node->data = val;
    node->next = NULL;
    return node;
}

头插法插入一个数据结点

void insertNode(LINK *h,data_t val)
{
    LINK *node = createDataNode(val);
    node->next = h->next;
    h->next = node;
}

1、创建一个数据结点

2、修改头结点和数据结点的指针指向

怎么修改指针？

思路：

1、指针是谁的 ["箭头"的名字]

2、指针指向谁

头插法插入一串数据结点

void insertNodes(LINKLIST h)
{
    int val;
    scanf("%d",&val);
    while(val != -1)//结束输入标志
    {
        insertNode(h,val);
        scanf("%d",&val);
    }
}

尾插法插入一个数据结点

void tailInsertNode(LINK *h,data_t val)
{
    LINK *node = createDataNode(val);
    while(h->next!=NULL)
        h = h->next;
    h->next = node;
}

遍历定位到最后一个结点

头删法删除一个数据结点

void deleteHeadNode(LINKLIST h)
{
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    LINKLIST p = h->next;
    h->next = p->next;
    free(p);
}

先判空，后修改指针

尾删法删除一个数据结点

void deleteTailNode(LINKLIST h)
{
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    LINKLIST p = h;
    while(p->next->next!=NULL)
        p = p->next;
    free(p->next);
    p->next = NULL;
}

先判空，后遍历定位到最后一个结点的前驱结点，再删除最后一个结点

根据给定数据修改数据

void updataBydata(LINKLIST h,data_t data,data_t val)
{
    int flag=0;
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    while(h->next!=NULL)
    {
        h=h->next;
        if(h->data == data)
        {
            h->data = val;
            flag = 1;
        }
    }
    if(!flag)
        printf("链表中没有数据%d\n",data);
}

查询的基础是遍历的过程

插入数据并排序

void inserdAndSort(LINKLIST h)
{
    int val;
    scanf("%d",&val);
    while(val!=-1)
    {
        LINKLIST p = h;
        LINKLIST node = createDataNode(val);
        while(p->next!=NULL && p->next->data<val)
        {
            p=p->next;
        }
        node->next = p->next;
        p->next = node;
        scanf("%d",&val);
    }
}

插入数据：需要创建一个数据结点

排序：遍历的过程中比较数据的大小

结束遍历的时候，头插法插入

链表逆序翻转

void reverseLink(LINKLIST h)
{
    LINKLIST p = h->next;//交换
    LINKLIST t = h->next;//遍历
    h->next = NULL;//“砍”头
    while(t!=NULL)
    {
        t = p->next;
        p->next = h->next;
        h->next = p;
        p = t;
    }
}

1、先断开头结点与链表的联系

2、将链表的第一个结点头插法插入到头结点后面

3、依次将剩余的结点按头插法插入

遍历（打印）

void printLink(LINK *h)
{
    while(h->next!=NULL)
    {
        h = h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}

示例

#include <stdio.h>
#include <stdlib.h>
typedef int data_t; 
typedef struct linklist{
    data_t data;//数据域
    //LINK *next;//错误声明
    struct linklist *next;//指针域，指向下一个节点
}LINK, *LINKLIST;
LINK *createHeadNode(void);
LINK *createDataNode(data_t val);
void insertNode(LINK *h,data_t val);
void insertNodes(LINKLIST h);
void tailInsertNode(LINK *h,data_t val);
void deleteHeadNode(LINKLIST h);
void deleteTailNode(LINKLIST h);
void updataBydata(LINKLIST h,data_t data,data_t val);
void inserdAndSort(LINKLIST h);
void reverseLink(LINKLIST h);
void printLink(LINK *h);
int main(int argc, const char *argv[])
{
    LINK *h = createHeadNode();
    inserdAndSort(h);//从小到大排序插入
    printLink(h);   
    insertNode(h,1);//头插法插入一个数据节点
    insertNode(h,2);
    printLink(h);
    insertNodes(h);//连续头插一串数据
    printLink(h);
    deleteHeadNode(h);//删除第一个数据节点
    printLink(h);
    deleteTailNode(h);//删除最后一个数据节点
    printLink(h);
    updataBydata(h,6,666);//修改一个数据6为666
    printLink(h);
    inserdAndSort(h);
    printLink(h);
    reverseLink(h);//链表逆序翻转
    printLink(h);
    return 0;
}
//创建一个头节点
LINK *createHeadNode(void)
{
    LINK *h = (LINK *)malloc(sizeof(LINK));
    h->next = NULL;
    return h;
}
//创建一个数据节点
LINK *createDataNode(data_t val)
{
    LINK *node = (LINK *)malloc(sizeof(LINK));
    node->data = val;
    node->next = NULL;
    return node;
}
//头插法插入一个数据节点
void insertNode(LINK *h,data_t val)
{
    LINK *node = createDataNode(val);
    node->next = h->next;
    h->next = node;
}
//头插法插入一串数据节点
void insertNodes(LINKLIST h)
{
    int val;
    scanf("%d",&val);
    while(val != -1)
    {
        insertNode(h,val);
        scanf("%d",&val);
    }
}
//尾插法插入一个数据节点
void tailInsertNode(LINK *h,data_t val)
{
    LINK *node = createDataNode(val);
    while(h->next!=NULL)
        h = h->next;
    h->next = node;
}
//头删法删除一个数据节点
void deleteHeadNode(LINKLIST h)
{
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    LINKLIST p = h->next;
    h->next = p->next;
    free(p);
}
//尾删法删除一个数据节点
void deleteTailNode(LINKLIST h)
{
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    LINKLIST p = h;
    while(p->next->next!=NULL)
        p = p->next;
    free(p->next);
    p->next = NULL;
}
//根据数据修改数据
void updataBydata(LINKLIST h,data_t data,data_t val)
{
    int flag=0;
    if(h->next==NULL)
    {
        printf("表空\n");
        return;
    }
    while(h->next!=NULL)
    {
        h=h->next;
        if(h->data == data)
        {
            h->data = val;
            flag = 1;
        }
    }
    if(!flag)
        printf("链表中没有数据%d\n",data);
}
//插入数据自带排序功能
void inserdAndSort(LINKLIST h)
{
    int val;
    scanf("%d",&val);
    while(val!=-1)
    {
        LINKLIST p = h;
        LINKLIST node = createDataNode(val);
        while(p->next!=NULL && p->next->data<val)
        {
            p=p->next;
        }
        node->next = p->next;
        p->next = node;
        scanf("%d",&val);
    }
}
//链表逆序翻转
void reverseLink(LINKLIST h)
{
    LINKLIST p = h->next;//交换
    LINKLIST t = h->next;//遍历
    h->next = NULL;
    while(t!=NULL)
    {
        t = p->next;
        p->next = h->next;
        h->next = p;
        p = t;
    }
}
//打印
void printLink(LINK *h)
{
    while(h->next!=NULL)
    {
        h = h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}

结果

9 8 7 6 -1
6 7 8 9
2 1 6 7 8 9
55 11 22 77 -1
77 22 11 55 2 1 6 7 8 9
22 11 55 2 1 6 7 8 9
22 11 55 2 1 6 7 8
22 11 55 2 1 666 7 8
3 33 -1
3 22 11 33 55 2 1 666 7 8
8 7 666 1 2 55 33 11 22 3

本文链接：https://shengto.top/data_structure/136.html

转载时须注明出处及本声明

Last modification：2021 年 03 月 28 日 16 : 05 : 15
© 允许规范转载