当前位置： 首页 > article >正文

数据结构 - 链表

article 2025/1/19 13:08:56

0.链表的定义

1.单链表

        单链表一个结点 = data + next(指针) ，所以其存储结构是随机存储结构

2.双链表

        双链表一个结点 = prior(指针) + data + next(指针) ，所以其存储结构是随机存储结构

一.单链表

1.单链表的结构

        单链表一个结点 = data + next(指针)

2.单链表结构体的定义

typedef int datatype;

typedef struct node
{
    datatype data;
    struct node *next; 
}listnode;

3.创建一个空的单链表

/**
 * @description:            创建一个空的单链表
*/
listnode *list_create(void)
{
    listnode *p = NULL;

    /* 1.申请空间 */
    p = (listnode *)malloc(sizeof(listnode));
    if(NULL == p)
    {
        printf("create list faild\n");
        return NULL;
    }

    /* 2.初始化头结点 */
    p->data = 0;
    p->next = NULL;

    return p;
}

4.使用键盘输入创建并初始化单链表

/**
 * @description:            键盘输入创建单链表
 * @param       :           无
 * @return      :           指向链表的指针
*/
listnode *list_create_init(void)
{
    /* h指向头结点，r指向尾结点,q指向新结点 */
    listnode *h,*r,*q;
    datatype value;     //接收键盘输入的值

    /* 1.申请空间 */
    h = (listnode *)malloc(sizeof(listnode));
    if(NULL == h)
    {
        printf("create list faild\n");
        return NULL;
    }
    r = h;                  //初始情况，尾结点就是首结点

    /* 2.初始化头结点 */
    h->data = 0;
    h->next = NULL;

    /* 3.利用尾插，循环插入新的结点 */
    while(1)
    {
        printf("input new node ->\n");
        printf("input -1 : exit\n");
        scanf("%d",&value);
        if(-1 == value)
        {
            break;
        }

        /* 3.创建新的结点 */
        q = (listnode *)malloc(sizeof(listnode));
        if(NULL == q)
        {
            printf("create list faild\n");
            return NULL;
        }

        q->data = value;
        q->next = NULL;
        r->next = q;        //尾结点的next的字段指向新的结点
        r = q;              //尾结点指针向后移动
    }

    return h;
}

5.向单链表中头插

/**
 * @description:            向单链表中使用头插，插入一个结点
 * @param - h       :       要操作的链表的首结点的指针
 * @param - x       :       要插入的结点的data字段数据
 * @return          :       0 成功，其他 失败
*/
int insert_head_list(listnode *h , datatype value)
{
    listnode *p = list_create();
    if(NULL == p)
    {
        printf("insert into linklist faild!\n");
        return -1;
    }

    p->data = value;
    p->next = h->next;
    h->next = p;

    return 0;
}

6.向单链表中尾插

7.打印单链表所有的结点

/**
 * @description:            打印链表全部的结点
 * @param - h       :       要操作的单链表
 * @return          :       无
*/
void list_show(listnode *h)
{
    /* 循环打印，直到某个结点的指针为NULL，则表示是最后一个结点 */
    while(h->next)
    {
        printf("%d ",h->next->data);
        h = h->next;                    //结点指向向后移动
    }

    printf("\n");
}

8.按序号查找结点

/**
 * @description:            按照序号查找链表中的结点
 * @param - h       :       要操作的链表
 * @param - pos     :       结点的序号
 * @return          :       查找到的结点的指针,若为NULL，则查找失败
*/
listnode *Get_Linklist(listnode *h,int pos)
{
    listnode *p = h;        //记录当前结点位置
    int j = -1;      

    /* 结点序号必须大于等于0 */
    if(0 > pos)
        return NULL;   

    /* 遍历链表，直到 j = pos （成功找到指定序号的结点）|| （当前结点位置已经到了最后一个结点） */
    while(p->next && j < pos)
    {
        p = p->next;        //结点向后移动一个位置
        j++;
    }

    /* 若以指定序号找到了结点,则返回找到的结点的指针 */
    if(j == pos)      
    {
        return p;
    }

    /* 若没有找到，则返回NULL */
    else
        return NULL;

    return NULL;
}

9.按结点的数据查找结点

/**
 * @description:            按照指定结点的数据查找结点
 * @param - h       :       要操作的链表的头结点
 * @param - value   :       指定要查找的值
 * @return          :       查找到的结点的指针,若返回NULL则为失败
*/
listnode *List_Locate(listnode *h,datatype value)
{
    listnode *p = h;        //记录当前结点位置

    /* 遍历链表，直到 （结点位置已经到了最后一个结点）||（查找到了指定的结点） */
    while((p->next) && (p->data != value))
    {
        p = p->next;
    }

    /* 若当前结点的data字段 == value */
    if(p->data == value)
        return p;

    else
        return NULL;

    return NULL;
}

10.向单链表中某个结点前插入一个结点

/**
 * @description:            向单链表的某个结点前插入一个结点
 * @param - h       :       要操作的链表的头结点指针
*/
int Insert_Linklist_before(listnode *h,datatype value,int pos)
{
    listnode *p,*q;

    /* 位置必须大于等于0 */
    if(0 > pos)
    {
        return -1;
    }

    /* 1.申请一个新结点填充数据 */
    p = list_create();
    p->data = value;
    p->next = NULL;

    if(pos == 0)       //若为0,则直接在首结点头插
    {
        p->next = h->next;
        h->next = p;
        return 0;
    }

    /* 2.找到要插入的结点的前驱结点 */
    q = Get_Linklist(h,pos-1);
    if(NULL == q)               //若没有找到指定结点的前驱结点
        return -1;

    /* 3.将该结点,插入到指定结点s的前驱结点的后面 */
    p->next = q->next;
    q->next = p;

    return 0;
}

11.删除指定序号的结点

/**
 * @description:            删除指定序号的结点
 * @param - h       :       要操作的链表的首结点指针
 * @param - pos     :       指定的结点的序号
 * @return          :       0 成功;其他 失败
*/
int Delete_Linklist_bypos(listnode *h,int pos)
{
    listnode *p,*q;         //q用来指向要删除的结点，p用来指向要删除结点的前驱结点

    /* 序号必须 >= 0 */
    if(0 > pos)
        return -1;

    if(0 == pos)            //要删除第 0 个结点
    {
        q = h->next;            //q指向第 0 个结点
        h->next = q->next;      //首结点的指针字段指向第 1 个结点 
        free(q);                //删除第 0 个结点
    }
    /* 删除其他的结点 */
    else
    {
        p = Get_Linklist(h,pos-1);      //p指向前驱结点     a(i-1)
        q = p->next;                    //q指向要删除的结点  a(i)
        /* 若没有前驱结点 || 没有指定的结点 */
        if(NULL == p || NULL == q)
            return -1;

        p->next = q->next;              //结点 a(i-1) 的指针字段指向结点 a(i+1)
        free(q);                        //删除结点 a(i)
    }

    return 0;
}

12.删除指定数值的结点

/**
 * @description:            删除指定 value 的结点
 * @param - h       :       要操作的链表的头结点指针
 * @param - value   :       指定的结点 data 字段的数据
 * @return          :       0为成功 ; 其他为失败
*/
int Delete_Linklist_byvalue(listnode *h,datatype value)
{
    listnode *p,*q;             // p 指向要删除结点的前驱结点，q 指向要删除的结点

    p = h;
    
    /* 找到指定结点的前驱结点 p , p->next->data 就是指定结点的数据段的值*/
    while(p->next->next && (p->next->data != value))
    {
        p = p->next;
    }

    if(p->next->data == value)          //p->next是指定结点       
    {
        q = p->next;                    //q 指向指定结点
    }
    else
        return -1;

    p->next = q->next;

    free(q);

    return 0;
}

13.单链表倒置

/**
 * @descritpion:            倒置链表
 * @param - h       :       要操作的链表头结点指针
 * @return          :       0为成功;其他为失败
*/
void Reverse_Linklist(listnode *h)
{
    listnode *p,*q;                 

    p = h->next;            //p 指向 a(0) 结点
    h->next = NULL;

    while(p != NULL)
    {
        q = p;
        p = p->next;
        q->next = h->next;
        h->next = q;
    }
}

14.单链表的有序插入

/**
 * @description:            向单链表中有序插入一个结点
 * @param - h       :       要操作的链表首结点指针
 * @param - value   :       要插入的结点的值
*/
int Insert_order_Linklist(listnode *h,datatype value)
{
    listnode *p,*q;

    /* 为新结点申请空间 */
    p = (listnode *)malloc(sizeof(listnode));
    if(NULL == p)
    {
        return -1;
    }
    p->next = NULL;
    p->data = value;

    q = h;
    /* 遍历查找比新结点 data 字段大的结点(q->next)，找到了就头插在该结点前 */
    while(q->next && q->next->data <= value)       
    {
        q = q->next;
    }
    if(NULL == q->next)             //所有的结点的 data 字段都 <= 新结点的 data 字段
    {
        q->next = p;
    }
    else if(q->next->data > value)
    {
        p->next = q->next;
        q->next = p;
    }

    return 0;
}

15.单链表的排序（直接插入排序）

/**
 * @description:            单链表排序（直接插入排序）
 * @param - h       :       要操作的链表
 * @return          :       无
*/
void Linklist_Sort(listnode *h)
{
    listnode *p,*q,*r;

    p = h->next;            //指向 a(0)
    h->next = NULL;         //把头结点从链表上分开

    while(p)
    {
        q = p;              // q、p 指向 a(0) 结点
        p = p->next;        //p往后移动

        r = h;
        while(r->next && r->next->data <= q->data)
        {
            r = r->next;
        }
        q->next = r->next;
        r->next = q;
    }
}

二.单向循环链表

1.单向循环链表的结构

        单链表的最后一个结点的 *next 字段为 NULL。单向循环链表的最后一个结点的 *next 字段为首结点的指针。

三.双向循环链表

1.双向循环链表的结构

2.双向链表的结构体定义

typedef int data_t;

/* 双向链表结构体 */
typedef struct double_linklist
{
    data_t data;
    struct double_linklist *prior,*next;
}dlinklist;

3.使用键盘输入创建一个双向循环链表

注意：当只有头结点时，其


/**
 * @description:            用户输入创建一个循环双链表
 * @param -         :       无
 * @return          :       创建的双链表的首结点指针
*/
dlinklist * dlist_create(void)
{
    dlinklist *h,*r,*p;     // h 为头结点的指针，r 指向链表的最后一个结点，p 指向新创建的结点 
    int num = 0;

    /* 1.创建一个头结点 */
    h = (dlinklist *)malloc(sizeof(dlinklist));
    if(NULL == h)
    {
        printf("dlinklist create failed\n");
        return NULL;
    }

    /* 2.头结点初始化，next 和 prior 都指向自己 */
    h->prior = h;
    h->next = h;
    r = h->prior;

    /* 3.键盘输入要创建的结点的 data 段数据 */
    while(1)
    {
        printf("input node data:\n");
        printf("input -1 break!\n");
        scanf("%d",&num);
        if(-1 == num)
        {
            break;
        }

        else
        {
            /* 创建一个新的结点 p */
            p = (dlinklist *)malloc(sizeof(dlinklist));
            if(NULL == p)
            {
                printf("dlinklist create failed!\n");
                return -1;
            }
            p->data = num;
            
            /* 对尾结点进行尾插 */
            p->prior = r;
            p->next = r->next;
            r->next = p;
            h->prior = p;
            r = p;
        }
    }

    return h;
}

4.打印双向循环链表

/**
 * @description:            打印循环双链表的内容
 * @param - h       :       要操作的双链表的首结点指针
 * @return          :       无
*/
void dlist_show(dlinklist *h)
{
    dlinklist *p;
    
    p = h->next;
    if(p == h)
    {
        printf("the linklist is empty!\n");
        return ;
    }

    while(p != h)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

5.按序号查找双向循环链表的结点

/**
 * @description:            按序号查找双向循环链表的结点
 * @param - h       :       要操作的双向循环链表的首结点指针
 * @param - pos     :       指定结点的序号
*/
dlinklist *Dlinklist_Get_Bypos(dlinklist *h,int pos)
{
    dlinklist *p = h;           //指向当前的结点
    int i = -1;             //从首结点出发

    if(pos < 0)
    {
        printf("the pos is invalid!\n");
        return NULL;
    }

    while(i < pos)
    {
        p = p->next;
        i++;

        /* 若遍历到了最后的一个结点 */
        if(p == h)
            return NULL;
    }
    if(i == pos)
    {
        return p;
    }

}

6. 按值查找双向循环链表中的结点

/**
 * @description:                按值查找双向循环链表中的结点
 * @param - h       :           要操作的链表的首结点指针
 * @param - value   :           要查找的结点的值
 * @return          :           找到的结点的指针
*/
dlinklist *Dlinklist_Get_Byvalue(dlinklist *h,data_t value)
{
    dlinklist *p = h->next;

    /* 遍历链表 */
    while(value != p->data)
    {
        p = p->next;

        /* 若遍历完了 */
        if(p == h)
            return NULL;
    }
    if(p->data == value)
        return p;
}

7.在指定位置结点前插入新结点

/**
 * @description:            在指定位置的结点前插入一个新的结点
 * @param - h       :       要操作的链表的首结点指针
 * @param - pos     :       指定在哪个结点前插入
 * @param - value   :       要插入的结点的值
 * @return          :       0 为成功 ; 其他 为失败
*/
int Dlinklist_insert_before(dlinklist *h,int pos,int value)
{
    dlinklist *p,*q;

    p = Dlinklist_Get_Bypos(h,pos);
    if(NULL == p)
    {
        return -1;
    }

    /* 创建一个新的结点 */
    q = (dlinklist *)malloc(sizeof(dlinklist));
    if(NULL == q)
    {
        return -1;
    }
    q->data = value;

    q->prior = p->prior;
    q->next = p;
    p->prior->next = q;
    p->prior = q;

    return 0;
}

8.双向循环链表的删除

/**
 * @description:                指定序号，删除循环双链表中的结点
 * @param - h       :           要操作的链表的首结点指针
 * @param - pos     :           指定删除的结点的序号
 * @return          :           0 为成功 ; 其他为失败
*/
int Dlinklist_Delete_Bypos(dlinklist *h,int pos)
{
    dlinklist *p;

    p = Dlinklist_Get_Bypos(h,pos);
    /* 没找到指定序号的结点则退出，并返回错误信息 */
    if(NULL == p)
    {
        return -1;
    }

    p->prior->next = p->next;
    p->next->prior = p->prior;

    free(p);

    return 0;
}

9.删除指定数值的结点

/**
 * @description:                指定序号，删除循环双链表中的结点
 * @param - h       :           要操作的链表的首结点指针
 * @param - pos     :           指定删除的结点的序号
 * @return          :           0 为成功 ; 其他为失败
*/
int Dlinklist_Delete_Bypos(dlinklist *h,int pos)
{
    dlinklist *p;

    /* 1.获取要删除的结点的指针 */
    p = Dlinklist_Get_Bypos(h,pos);

    /* 没找到指定序号的结点则退出，并返回错误信息 */
    if(NULL == p)
    {
        return -1;
    }

    /* 2.删除指定的结点 p */
    p->prior->next = p->next;
    p->next->prior = p->prior;

    free(p);

    return 0;
}

10.倒置双向循环链表

/**
 * @description:                双向循环链表的倒置
 * @param - h       :           要操作的链表的首结点指针
 * @return          :           无
*/
void Dlinklist_Reverse(dlinklist *h)
{
    dlinklist *p,*q,*r;            //,r 指向首结点的下一个结点 a(0), p 指向当前要头插的结点，q 指向下一个结点，防止链表丢失

    /* 1.先把链表分成两部分 */
    r = h->next;
    p = r->next;
    h->prior = r;
    r->next = h;

    /* 从 a(1) 开始遍历 */
    while(p != h)
    {
        /* 2.依次提取 a(1),a(2),a(3)... */
        q = p;
        p = p->next;

        /* 3.将 q 指向的结点，头插到 a(0) 前 */
        q->prior = h;
        q->next = r;
        h->next = q;
        r->prior = q;
        
        /* 4.将 r 指向 q 的结点 */
        r = q;
    }


}


http://www.kler.cn/a/300704.html

相关文章：

  • Spring Web MVC综合案例
  • Python毕业设计选题：基于django+vue的智能租房系统的设计与实现
  • 从AI生成内容到虚拟现实：娱乐体验的新边界
  • PL/SQL语言的语法糖
  • 细说STM32F407单片机窗口看门狗WWDG的原理及使用方法
  • 单片机存储器和C程序编译过程
  • 数据分析-19-时间序列预测之时间窗口数据的划分
  • 总结——薄基础_Android开发_简易计算器__非教程
  • Nestjs微服务简单案例
  • List＜Map＜String, Object＞＞汇总统计排序
  • paddle模型转onnx介绍（以utc-mini为例）
  • shell脚本编程-进阶部分
  • 作为负责招聘的HR，如何解决职位吸引力不足的问题
  • 【STM32】OLED
  • 部署后端WebSocket服务到AWS云服务器
  • C++与QML的数据交互
  • 数字证书学习
  • MySQL——DCL
  • C#的属性和方法
  • opencv羊群计数，动态目标检测跟踪
  • List集合特点，遍历方式，ArrayList（去重原理，增长因子论，LinkedList)
  • 【Kubernetes】常见面试题汇总（十一）
  • milvus的二进制文件集群部署
  • 区块链当前发展和未来展望
  • 【微服务】⭐️华为云obs功能抽取到公共服务，供所有项目使用
  • 【机器学习】马尔可夫随机场的基本概念、和贝叶斯网络的联系与对比以及在python中的实例