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

day20 双向链表

news 2025/7/26 6:43:26

双向链表的函数功能

注意事项 

1.双向链表还需要关注到前指针的指向

2.函数都需要判断逻辑

3.函数的增删都要关注到len的变化

4.函数的改查功能都需要遍历结束的标志NULL

5.注意p->next->prio时，p->next是否指向NULL

创建双向链表头节点

Node_ptr list_create()

函数功能：申请一个头结点并初始化len

参数：无

返回值：头结点地址

    //指针接收申请的空间地址Node_ptr L=(Node_ptr)malloc(sizeof(Node));	//判断逻辑if(L==NULL){printf("申请空间失败\n");return NULL;}//初始化逻辑L->len=0;L->prio=NULL;L->next=NULL;//返回逻辑return L;

判空函数

int list_empty(Node_ptr head)

函数功能：判断双向链表是否为空
参数：头结点地址
返回值：链表为空返回1，非空返回0 

return L->next==NULL;

节点封装函数

Node_ptr list_node_apply(datatype e)

函数功能：申请一个新节点并初始化数据域为e
参数：待封装的数据e
返回值：新节点地址

    //申请空间Node_ptr p=(Node_ptr)malloc(sizeof(Node));//判断逻辑if(p==NULL){printf("节点空间申请失败\n");return NULL;}//初始化逻辑p->data=e;p->prio=NULL;p->next=NULL;//返回逻辑return p;

头插函数

int list_insert_head(Node_ptr head, datatype e)

函数功能：在链表头部插入新节点
参数：头结点地址，待插入数据e
返回值：成功返回1，失败返回0

    //节点申请Node_ptr p=list_node_apply(e);//头插逻辑if(list_empty(L)){//链表为空L->next=p;p->prio=L;//长度自增L->len++;return 0;}else{    //链表不为空//先确定尾指针的指向p->next=L->next;L->next=p;//再确定头指针的指向p->prio=L;p->next->prio=p;//长度自增L->len++;//返回逻辑printf("头插成功\n");return 0;}

尾插函数 

int list_insert_tail(Node_ptr head,datatype e);

函数功能：在链表尾部插入新节点
参数：头结点地址，待插入数据e
返回值：成功返回1，失败返回0

    //节点申请Node_ptr p=list_node_apply(e);if(p==NULL){printf("尾插失败\n");return -1;}//遍历逻辑Node_ptr q=L->next;while(q->next!=NULL) //遍历到最后一个节点{q=q->next;}//插入逻辑p->next=q->next;q->next=p;p->prio=q;//长度自增L->len++;

 

遍历函数

void list_show(Node_ptr head)

函数功能：打印双向链表所有节点的数据
参数：头结点地址
返回值：无

按位置查找节点

Node_ptr list_search_post(Node_ptr head, int post)

函数功能：查找链表中指定位置的节点
参数：头结点地址，位置pos（从1开始）
返回值：找到返回节点地址，失败返回NULL

任意位置插入

int list_insert_post(Node_ptr head, int post, datatype e)

函数功能：在指定位置插入新节点
参数：头结点地址，位置post，待插入数据e
返回值：成功返回1，失败返回0

判断逻辑

申请空间

插入逻辑 

表长变化

返回逻辑

    //申请空间Node_ptr q=list_node_apply(e);if(q==NULL){printf("插入失败1\n");return -1;}//post位置查找Node_ptr post_ptr=list_search_post(L,post);//插入逻辑//继承post节点的指向q->prio=post_ptr->prio;q->prio->next=q;//完善链接q的指向q->next=post_ptr;post_ptr->prio=q;//表长变化L->len++;//返回逻辑return 0;

头删函数

int list_delete_head(Node_ptr head)

函数功能：删除链表首元素节点
参数：头结点地址
返回值：成功返回1，失败返回0

    Node_ptr p=L->next;//删除逻辑L->next=p->next;if(L->next!=NULL)L->next->prio=L;//释放节点，置空free(p);p=NULL;//len自减逻辑L->len--;

尾删函数

 int list_delete_tail(Node_ptr L)

函数功能：删除链表尾元素节点
参数：头结点地址
返回值：成功返回1，失败返回0

    //遍历逻辑Node_ptr p=L->next;while(p->next!=NULL) //遍历到最后一个节点{p=p->next;}//删除逻辑p->prio->next=NULL; //倒数第二个节点置空//长度自减L->len--;

 

任意位置删除

int list_delete_post(Node_ptr head, int post)

函数功能：删除指定位置的节点
参数：头结点地址，位置pos
返回值：成功返回1，失败返回0

    //查找逻辑Node_ptr p=list_search_post(L,post);//删除逻辑//最后一个节点只执行一条p->prio->next=p->next;if(p->next!=NULL){   //如果不为最后一个节点p->next->prio=p->prio;}//自减L->len--;//释放节点，置空free(p);p=NULL;

任意位置修改

int list_updata_post(Node_ptr head, int post, datatype e)

函数功能：修改指定位置节点的数据
参数：头结点地址，位置pos，新数据e
返回值：成功返回1，失败返回0

    //查找逻辑Node_ptr p=list_search_post(L,post);//修改逻辑p->data=e;

销毁链表

int list_free(Node_ptr head)

函数功能：释放双向链表所有节点内存
参数：头结点地址
返回值：成功返回1，失败返回0

    //删除逻辑//结点删除 Node_ptr p=L->next;while(!list_empty(L)){list_delete_head(L);	}//头节点删除free(L);L=NULL;

链表与顺序表的比较

存储：1.顺序表是一段连续空间存储，链表不一定连续的空间

           2.顺序表是静态分配空间，链表是动态分配空间        (创建时体现)

           3.顺序表存在存满的情况，链表不存在

           4.顺序表需要提前预估空间，链表不需要

时间复杂度
增删改查
顺序表O(n)      其他数据元素后移O(1)        对应的元素修改即可
链表           O(1)      只需改变指针指向O(n)        需要遍历到其位置

因此：增删链表，改查顺序表

完整代码

Dlink.h

#ifndef _Dlink_H
#define _Dlink_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char datatype;//定义数据类型
//双向链表
typedef struct Node
{   //数据域union{datatype data;int len;};//指针域struct Node *prio;   //前指针struct Node *next;   //后指针
}Node,*Node_ptr;   //创建双向链表头节点
Node_ptr list_create();//判空
int list_empty(Node_ptr );//节点封装函数
Node_ptr list_node_apply(datatype e);//头插
int list_insert_head(Node_ptr ,datatype );//尾插
int list_insert_tail(Node_ptr,datatype);
//遍历
void list_show(Node_ptr );//按位置查找返回节点(位置从1开始)
Node_ptr list_search_post(Node_ptr ,int);//任意位置插入数据
int list_insert_post(Node_ptr ,int ,datatype);//头删
int list_delete_head(Node_ptr );
//尾删
int list_delete_tail(Node_ptr );
//任意位置删除
int list_delete_post(Node_ptr ,int );//任意位置修改
int list_updata_post(Node_ptr ,int ,datatype);//销毁双向链表
int list_free(Node_ptr );
#endif

Dlink.c

#include"Dlink.h"//创建双向链表
Node_ptr list_create()
{   //指针接收申请的空间地址Node_ptr L=(Node_ptr)malloc(sizeof(Node));	//判断逻辑if(L==NULL){printf("申请空间失败\n");return NULL;}//初始化逻辑L->len=0;L->prio=NULL;L->next=NULL;//返回逻辑return L;
}
//判空
//空返回1,非空返回0,非法返回-1
int list_empty(Node_ptr L)
{   //判断逻辑if(L==NULL){printf("非法地址\n");return -1;}return L->next==NULL;
}
//节点封装函数
Node_ptr list_node_apply(datatype e)
{//申请空间Node_ptr p=(Node_ptr)malloc(sizeof(Node));//判断逻辑if(p==NULL){printf("节点空间申请失败\n");return NULL;}//初始化逻辑p->data=e;p->prio=NULL;p->next=NULL;//返回逻辑return p;
}//头插
//成功返回0，失败返回-1
int list_insert_head(Node_ptr L,datatype e)
{//判断逻辑if(L==NULL){printf("非法地址\n");return -1;}//节点申请Node_ptr p=list_node_apply(e);//头插逻辑if(list_empty(L)){//链表为空L->next=p;p->prio=L;printf("插入成功\n");//长度自增L->len++;return 0;}else{//先确定尾指针的指向p->next=L->next;L->next=p;//再确定头指针的指向p->prio=L;p->next->prio=p;//长度自增L->len++;//返回逻辑printf("头插成功\n");return 0;}
}
//尾插
int list_insert_tail(Node_ptr L,datatype e)
{//判断逻辑if(L==NULL){printf("尾插失败\n");return -1;}//节点申请Node_ptr p=list_node_apply(e);if(p==NULL){printf("尾插失败\n");return -1;}//遍历逻辑Node_ptr q=L->next;while(q->next!=NULL) //遍历到最后一个节点{q=q->next;}//插入逻辑p->next=q->next;q->next=p;p->prio=q;//长度自增L->len++;//返回逻辑return 0;
}//遍历
void list_show(Node_ptr L)
{//判断逻辑if(L==NULL){printf("非法地址\n");}//遍历逻辑Node_ptr p=L->next; //定义遍历指针while(p!=NULL){printf("%-4c",p->data); //访问数据域p=p->next;//指针移到下一个节点}putchar(10);
}//按位置查找返回节点(位置从1开始)
Node_ptr list_search_post(Node_ptr L,int post)
{//判断逻辑if(list_empty(L)||post<1||post>L->len){printf("post不合理\n");return NULL;}//查找逻辑Node_ptr p=L->next;for (int i=1; i<post; i++){p=p->next;}return p;
}
//任意位置插入数据
int list_insert_post(Node_ptr L,int post,datatype e)
{//判断逻辑if(post<1||post>L->len+1){printf("插入位置不合理\n");return -1;}//申请空间Node_ptr q=list_node_apply(e);if(q==NULL){printf("插入失败1\n");return -1;}//post位置查找Node_ptr post_ptr=list_search_post(L,post);//插入逻辑//继承post节点的指向q->prio=post_ptr->prio;q->prio->next=q;//完善链接q的指向q->next=post_ptr;post_ptr->prio=q;//表长变化L->len++;//返回逻辑return 0;		
}//头删
int list_delete_head(Node_ptr L)
{//判断逻辑if(list_empty(L)){printf("头删失败\n");return -1;}Node_ptr p=L->next;//删除逻辑L->next=p->next;if(L->next!=NULL)L->next->prio=L;//释放节点，置空free(p);p=NULL;//len自减逻辑L->len--;//返回逻辑return 0;
}
//尾删
int list_delete_tail(Node_ptr L)
{//判断逻辑if(L==NULL||list_empty(L)){printf("尾删失败\n");return -1;}//遍历逻辑Node_ptr p=L->next;while(p->next!=NULL) //遍历到最后一个节点{p=p->next;}//删除逻辑p->prio->next=NULL; //倒数第二个节点置空//长度自减L->len--;//返回逻辑printf("尾删成功\n");return 0;}
//任意位置删除
int list_delete_post(Node_ptr L,int post )
{//判断逻辑if(list_empty(L)||post<1||post>L->len){printf("位置删除失败\n");return -1;}//查找逻辑Node_ptr p=list_search_post(L,post);//删除逻辑//最后一个节点只执行一条p->prio->next=p->next;if(p->next!=NULL){   //如果不为最后一个节点p->next->prio=p->prio;}//自减L->len--;//释放节点，置空free(p);p=NULL;//返回逻辑return 0;
}
//任意位置修改
int list_updata_post(Node_ptr L ,int post ,datatype e)
{//判断逻辑if(list_empty(L)||post<1||post>L->len){printf("修改位置不合理\n");return -1;}//查找逻辑Node_ptr p=list_search_post(L,post);//修改逻辑p->data=e;//返回逻辑return 0;
}
//销毁双向链表
int list_free(Node_ptr L)
{//判断逻辑if(L==NULL){printf("销毁失败\n");return -1;}//删除逻辑//结点删除 Node_ptr p=L->next;while(!list_empty(L)){list_delete_head(L);	}//头节点删除free(L);L=NULL;//返回逻辑printf("销毁成功\n");return 0;
}

 Dmain.c

#include"Dlink.h"
int main(int argc, const char *argv[])
{		//接收申请的空间Node_ptr x=list_create();if(x==NULL){printf("申请失败\n");return -1;}printf("申请成功\n");//头插printf("-----------头插-----------\n");list_insert_head(x,'a');list_insert_head(x,'b');list_insert_head(x,'c');list_insert_head(x,'d');list_insert_head(x,'e');list_insert_head(x,'f');list_insert_head(x,'p');list_insert_head(x,'q');printf("-----------遍历------------\n");list_show(x);printf("------按位置查找-----------\n");Node_ptr q=list_search_post(x,3);printf("%c\n",q->data);//按位置插入printf("--------位置插入-----------\n");list_insert_post(x,3,'x');list_insert_post(x,x->len,'z');list_show(x);//头删printf("----------头删-------------\n");list_delete_head(x);list_delete_head(x);list_show(x);//尾删printf("----------尾删-------------\n");list_delete_tail(x);list_delete_tail(x);list_show(x);//尾插printf("----------尾插-------------\n");list_insert_tail(x,'D');list_insert_tail(x,'O');list_show(x);//任意位置删除printf("-------位置删除------------\n");list_delete_post(x,x->len);list_delete_post(x,2);list_show(x);//任意位置修改printf("-------位置修改------------\n");list_updata_post(x,x->len,'G');list_show(x);printf("-------链表销毁------------\n");list_free(x);return 0;
}

http://www.xdnf.cn/news/1177039.html

相关文章：

  • MAC包头、IP包头 、UDP包头中的长度含义是啥？三者之间有啥区别？
  • 【SpringAI实战】提示词工程实现哄哄模拟器
  • 中小企业安全落地：低成本漏洞管理与攻击防御方案
  • SpringCache
  • 双紫擒龙紫紫红黄安装使用攻略，2025通达信指标源码，擒龙追踪源码公式学习
  • 遨游三防平板|国产芯片鸿蒙系统单北斗三防平板，安全高效
  • 算法调试技巧
  • 《使用Qt Quick从零构建AI螺丝瑕疵检测系统》——4. 前后端联动：打通QML与C++的任督二脉
  • 【基础】go基础学习笔记
  • 极客大挑战2019-HTTP
  • 基于Odoo的微信小程序全栈开发探索分析
  • 探索复杂列表开发：从基础到高级的全面指南
  • SSE与Websocket有什么区别？
  • 如何在 conda 中删除环境
  • rust-结构体使用示例
  • Elasticsearch 的聚合（Aggregations）操作详解
  • 使用phpstudy极简快速安装mysql
  • Java 大视界 -- Java 大数据在智能家居能源管理与节能优化中的深度应用（361）
  • API安全监测工具：数字经济的免疫哨兵
  • 五、Vue项目开发流程
  • LeetCode 2563.统计公平数对的数目
  • Effective Python 第16条：用get处理字典缺失键，避免in与KeyError的陷阱
  • 【低空经济之无人集群】
  • runc源码解读(一)——runc create
  • C++右值引用与移动语义详解
  • QML 模型
  • git更新内核补丁完整指南
  • Android LiveData 全面解析：原理、使用与最佳实践
  • 【智能协同云图库】智能协同云图库第六弹：空间模块开发
  • 飞腾D3000麒麟信安系统下配置intel I210 MAC