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

单向循环链表的概念+单向循环链表的结点插入+单向循环链表的结点删除+程序设计与笔试题分析

article 2025/1/30 1:23:18

  1. 单向循环链表的原理与应用

思考：对于单向链表而言，想要遍历链表，则必须从链表的首结点开始进行遍历，请问有没有更简单的方案实现链表中的数据的增删改查？

回答：是有的，可以使用单向循环的链表进行设计，单向循环的链表的使用规则和普通的单向链表没有较大的区别，需要注意：单向循环链表的尾结点的指针域中必须指向链表的首结点的地址，由于带头结点的单向循环链表更加容易进行管理，所以教学以带头结点的为例：

上图所示的就是一个典型的单向循环链表的结构，可以发现单向循环链表的结构属于环形结构，链表中的最后一个结点的指针域中存储的是链表的第一个结点的地址。

为了管理单向循环链表，需要构造头结点的数据类型以及构造有效结点的数据类型，如下：

  1. 创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！

  1. 创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：

  1. 根据情况把新结点插入到链表中，此时可以分为尾部插入、头部插入、指定位置插入：

  • 头插

  • 尾插

  • 中插

  1. 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定元素删除：

  • 头删

  • 尾删

  • 中删

  1. 双向链表的原理与应用

如果想要提高单向链表或者单向循环链表的访问速度，则可以在链表中的结点中再添加一个指针域，让新添加的指针域指向当前结点的直接前驱的地址，也就意味着一个结点中有两个指针域（prev + next），也被称为双向链表（Double Linked List）。

由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向不循环的链表。

  1. 创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！

  3. 创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：

  5. 根据情况可以从链表中插入新结点，此时可以分为尾部插入、头部插入、指定位置插入：

  • 头插

  • 尾插

  • 中插
  • （略）
  1. 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定结点删除：

  • 头删

  • //利用头删法实现结点删除
bool SencdList_Head_Delete(Node_t *HeadPointer)
{
     //备份头结点的地址
    Node_t *p =HeadPointer;

    //检查参数有效性
    if (HeadPointer == NULL)
    { 
        fprintf(stderr,"SencdList HeadPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }
    //检查链表是否为空
    if (p->Next == NULL)
    {
       fprintf(stderr,"SencdList is Empty,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

    //链表不为空，分两种情况，第一种只有一个结点，另一种有多个结点
    //只有一个结点
    if (p->Next->Next == NULL)
    {
        free(p->Next);
        p->Next = NULL;
        return true;
    }
    //有多个结点
    else
    {
        p->Next = p->Next->Next;        //头结点的next指向新首结点
        p->Next->perv->Next = NULL;     //原首结点的next指向null

        //释放要删除的结点空间
        free(p->Next->perv);

        //更新新首结点的prev
        p->Next->perv = NULL;

        printf("Delete is  OK\n");

        return true;
    

    }

}

  • 尾删

  • //利用尾删法删除结点
bool SencdList_Tail_Delete(Node_t *TailPointer)
{
     //备份头结点的地址
    Node_t *p =TailPointer;

    //检查参数有效性
    if (TailPointer == NULL)
    { 
        fprintf(stderr,"SencdList TailPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

     
     
     //检查链表是否为空
      if (p->Next == NULL)
    {
        fprintf(stderr,"SencdList TailPointer is Empty,errno = %d,%s\n",
                                            errno,strerror(errno));
       
        return false;
    }
    

     //如果链表不为空,有两种情况，一种为只有一个结点，另一种有多个结点
     //只有一个结点
     if (p->Next->Next == NULL)  //判断首结点的next是否指向null
     {
        free(p->Next);              //释放首结点的内存空间
        p->Next = NULL;             //更新头结点的指针域
        return true;
     }
     

     //有多个结点
     else
     {
        while (p->Next != NULL)
        {
            p = p->Next; //p往后移
        }

    //循环结束p指向尾结点
    p->perv->Next = NULL; //新尾结点的next指向null
    p->perv = NULL;       //原尾结点的prev指向null

    //释放尾结点空间
    free(p);

    return true;


     }
    





}

  • 中删
  • （略）

三、双向循环链表的原理与应用

双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。

由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向循环的链表。

// 5.结构体、联合体、枚举的定义。
typedef int Data_Type_t;

//结构体用来装链表的
typedef struct CirularSencdListNode
{
  struct CirularSencdListNode    *perv; //链表的perv指针域，指向结点的直接前驱
  Data_Type_t              Data; //链表的数据域
  struct CirularSencdListNode    *Next; //链表的next指针域,指向结点的直接后继

}Node_t;

  1. 创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！

  2. //创建新的链表（头结点）
Node_t* CirularSencdList_Create(void)
{
    //为链表申请堆空间
     Node_t *Pragmar = (Node_t*)calloc(1,sizeof(Node_t));

    //检查参数有效性
    if (Pragmar == NULL)
    {
        fprintf(stderr,"CirularSencdList Create is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        exit(-1);
    }

    //链表的初始化

    Pragmar->Next = Pragmar; //记录next指针域
    Pragmar->perv = Pragmar; //记录prev指针域
    
    printf("CirularSencdList Create is OK\n");
    return Pragmar;

}

  1. 创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：

  2. //创建新的结点
Node_t* CirularSencdList_NewNode(Data_Type_t Data )
{
     //为链表申请堆空间
     Node_t *NewNode = (Node_t*)calloc(1,sizeof(Node_t));
     //检查参数有效性
      if (NewNode == NULL)
    {
        fprintf(stderr,"CirularSencdList Create is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        exit(-1);
    }
    //链表的初始化
    NewNode->Data = Data; //记录数据域
    NewNode->Next = NewNode; //记录next指针域
    NewNode->perv = NewNode; //记录prev指针域
    
    printf("NewNode Create is OK\n");
    return NewNode;

}

  1. 根据情况可以从链表中插入新结点，此时可以分为尾部插入、头部插入、指定位置插入：

  2. 头插

//头插法为链表插入结点
bool CirularSencdList_HeadInsert(Node_t *HeadPointer,Data_Type_t Data)
{
    //备份头结点的地址
    Node_t *p =HeadPointer;
     Node_t *p_cur =HeadPointer->Next;

    //检查参数有效性
    if (HeadPointer == NULL)
    { 
        fprintf(stderr,"CirularSencdList HeadPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

    //创建新结点并初始化
    Node_t * NewNode = CirularSencdList_NewNode(Data);

   

    //检查链表是否为空
    if (p->Next == HeadPointer)
    {
        p->Next = NewNode;
       printf("insert is ok\n");
        return true;
    }
    
    //如果链表不为空
    p->Next->perv->Next = NewNode;  //尾结点的next指向新结点
    NewNode->perv  = p->Next->perv; //新结点的prev指向尾结点
    NewNode->Next =p->Next;         //新结点的next指向原首结点
    p->Next->perv = NewNode;        //原首结点的prev指向新结点
    p->Next = NewNode;              //更新头结点的指针域


   

    return true;


}

  1. 尾插

  2. //尾插法为链表插入结点
bool CirularSencdList_Tail_Insert(Node_t *TailPointer,Data_Type_t Data)
{
    //备份头结点的地址
    Node_t *p =TailPointer;

    //检查参数有效性
    if (TailPointer == NULL)
    { 
        fprintf(stderr,"CirularSencdList TailPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

    //创建新结点并初始化
    Node_t * NewNode = CirularSencdList_NewNode(Data);

   

    //检查链表是否为空
    if (p->Next == TailPointer)
    {
        p->Next = NewNode;
       
        return true;
    }
    
    //如果链表不为空
   p->Next->perv->Next = NewNode; //原尾结点的next指向新结点
   NewNode->perv =p->Next->perv;  //新结点的prev指向原尾结点
   NewNode->Next = p->Next;       //新结点的next指向首结点
   p->Next->perv = NewNode;       //首结点的prev指向新结点


    return true;


}

  3. 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定结点删除：

  4. 头删

  5. //利用头删法实现结点删除
bool CirularSencdList_Head_Delete(Node_t *HeadPointer)
{
     //备份头结点的地址
    Node_t *p =HeadPointer;

    //检查参数有效性
    if (HeadPointer == NULL)
    { 
        fprintf(stderr,"CirularSencdList HeadPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }
    //检查链表是否为空
    if (p->Next == HeadPointer)
    {
       fprintf(stderr,"CirularSencdList is Empty,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

    //链表不为空有两种情况，一种为只有一个结点，另一种有多个结点
    //只有一个结点
    if (p->Next->Next == p->Next)  //判断首结点的next是否指向首结点本身
    {
        p->Next->Next = NULL;     //首结点的next指向null

        p->Next->perv = NULL;     //首结点的prev指向null
        free(p->Next);            //释放首结点
        p->Next = HeadPointer;    //更新头结点的指针域
        return true;
    }
    else
    {
        p->Next = p->Next->Next;             //更新头结点的指针域
        p->Next->perv = p->Next->perv->perv; //新首结点的prev指向尾结点
        p->Next->perv->Next->Next = NULL;    //原首结点的next指向null
        p->Next->perv->Next->perv = NULL;    //原首结点的prev指向null

        //释放原首结点的内存空间
        free(p->Next->perv->Next);
        p->Next->perv->Next = p->Next;       //尾结点的next指向新首结点







    }


    printf("Delete is  OK\n");

    return true;
    

}

    尾删

  6. //利用尾删法删除结点
bool CirularSencdList_Tail_Delete(Node_t *TailPointer)
{
     //备份头结点的地址
    Node_t *p =TailPointer;

    //检查参数有效性
    if (TailPointer == NULL)
    { 
        fprintf(stderr,"CirularSencdList TailPointer is error,errno = %d,%s\n",
                                            errno,strerror(errno));
        return false;
    }

     //检查链表是否为空
    if (p->Next == TailPointer)
    {
        fprintf(stderr,"CirularSencdList TailPointer is Empty,errno = %d,%s\n",
                                            errno,strerror(errno));
       
        return false;
    }
    
    //如果链表不为空,有两种情况，第一种是只有一个结点，另一种是有多个结点
    //只有一个结点
    if (p->Next->Next == p->Next)  //判断首结点的next是否指向自身
    {
        p->Next->Next = NULL;      //首结点的next指向null
        p->Next->perv = NULL;      //首结点的prev指向null

        //释放首结点的内存空间
        free(p->Next); 

        //更新头结点的指针域            
        p->Next = TailPointer;
        return true;
    }
    

    //有多个结点    
    p->Next->perv =p->Next->perv->perv;
    p->Next->perv->Next->Next = NULL;
    p->Next->perv->Next->perv = NULL;

    //释放尾结点空间
    free(p->Next->perv->Next);

    p->Next->perv->Next = p->Next;

    return true;





}

练习：

练习：

练习：

练习：

练习：

练习：

练习：


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

相关文章：

  • 7. 马科维茨资产组合模型+金融研报AI长文本智能体(Qwen-Long)增强方案（理论+Python实战）
  • SVG 矩形：深入理解与实际应用
  • 元素的显示与隐藏
  • 【Rust自学】16.3. 共享状态的并发
  • 实战 | 域环境下通过anydesk进入生产网
  • 共享内存 shm
  • 构建可靠的时间序列预测模型：数据泄露检测、前瞻性偏差消除与因果关系验证
  • Kafka 深入客户端 — 分区分配策略与协调器
  • Luzmo 专为SaaS公司设计的嵌入式数据分析平台
  • 【Validator】字段验证器struct与多层级验证，go案例
  • ReentrantLock锁江湖：一柄寒刃镇并发纷争
  • ts 基础核心
  • 2025-01-28 - 通用人工智能技术 - RAG - 本地安装 DeepSeek-R1对话系统 - 流雨声
  • 拟合损失函数
  • C语言练习（29）
  • PWM频率测量方法
  • langchain基础（二）
  • 【数据结构】_链表经典算法OJ：分割链表（力扣—中等）
  • 信息学奥赛一本通 1390：食物链【NOI2001】| 洛谷 P2024 [NOI2001] 食物链
  • 通过 NAudio 控制电脑操作系统音量
  • 8638 直接插入排序
  • 9.7 打造你的专属智能助手：基于 GPT Builder 定制化 ChatGPT 应用全指南
  • 智能客服系统：结合 AI 模型与数据库实现对话与知识检索
  • FastAPI + GraphQL + SQLAlchemy 实现博客系统
  • DearMom婴儿车：书籍点亮希望，为乡村留守儿童架起知识桥梁
  • 【1.安装ubuntu22.04】