当前位置:网站首页>使用C语言实现双向链表(带头结点)
使用C语言实现双向链表(带头结点)
2022-08-09 08:58:00 【Keep_Trying_Go】
目录
1.双链表
相对于单链表来说就是多一个前驱的指针prior,指向前一个节点(主要是为了方便删除和插入)。
注:由于之前的实现的单链表总是会遇到一种情况就是,如果要删除当前的节点p的话,那么只能通过一种技巧的方式计算交换值;但是如果是需要进行更加复杂的操作的话,就会比较麻烦,可能还需要辅助的指针r来指向当前节点的前驱,这会给程序写起来和理解起来带来不便,所以为了实现当前节点能够访问前驱节点,那么提出了双链表的概念。
2.双链表的相关操作
(1)数据结构的定义
#include<stdlib.h>
#include<stdio.h>
#define MAXSIZE 10
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode*prior,*next;
}DNode,*DLinkList;
//清单列表
void MenuLinkList(){
printf("-------------1.插入操作-------------\n");
printf("-------------2.定位插入操作---------\n");
printf("-------------3.按序查找操作---------\n");
printf("-------------4.按值查找操作---------\n");
printf("-------------5.定位删除操作---------\n");
printf("-------------6.按值删除元素---------\n");
printf("-------------7.删除整个表元素节点---\n");
printf("-------------8.表的长度-------------\n");
printf("-------------9.打印操作-------------\n");
printf("-------------10.结束操作-------------\n");
}
(2)初始化和销毁
//初始化操作
void InitDLinkList(DLinkList&L){
L=(DNode*)malloc(sizeof(DNode));
if(L==NULL){
printf("申请空间失败!\n");
return ;
}
L->prior=NULL;
L->next=NULL;
printf("申请空间成功!\n");
}
//销毁表(头节点不销毁)
DNode* DestryDLinkList(DNode*p,DLinkList&L,int flag=9){
//从尾部开始删除节点
DNode*r=p;
while(r!=L){
DNode*s=r;
r=r->prior;
r->next=s->next;
free(s);
}
//如果是结束操作的话,直接将头节点释放
if(flag==10){
free(L);
L=NULL;
}
return r;
}
这里的销毁操作主要是从最后节点开始进行删除,更加的方便,如果从头结点开始删除的话,需要判断的条件更多,相对麻烦一点,所以采用这种方法。读者自己可以实现从前往后的删除操作。
(3)判断空和表的长度
//判空
bool Empty(DLinkList L){
if(L->next==NULL){
return true;
}else{
return false;
}
}
//表的长度
int DLinkListLength(DLinkList L){
int len=0;
DNode*p=L->next;
while(p!=NULL){
len++;
p=p->next;
}
return len;
}
(4)节点的后插操作
//节点的插入操作(后插)
DNode* InsertDLinkList(DNode*p,ElemType e){
if(p==NULL){
printf("插入的节点不合法!\n");
return NULL;
}
DNode*s=(DNode*)malloc(sizeof(DNode));
s->data=e;
s->next=p->next;
p->next=s;
s->prior=p;
printf("插入节点成功!\n");
return s;
}
//在第i个位置插入节点
void InsertIDLinkList(DLinkList&L,int i,ElemType e){
DNode*p=FindDNode(L,i);
//如果是插入到尾节点
if(p->next==NULL){
InsertDLinkList(p,e);
return ;
}
//插入到中间的节点
if(p!=NULL){
DNode*s=(DNode*)malloc(sizeof(DNode));
s->data=e;
s->next=p->next;
p->next->prior=s;
p->next=s;
s->prior=p;
printf("插入节点成功!\n");
return ;
}
}
(5)按序查找第i个节点和按值查找节点
//查找第i个位序的节点
DNode*FindDNode(DLinkList L,int i){
if(L==NULL){
printf("表为空!\n");
return NULL;
}
if(i<0||i>DLinkListLength(L)){
printf("查找的位置不正确!\n");
return NULL;
}
int j=1;
DNode*p=L->next;
while(p!=NULL&&j<i){
p=p->next;
j++;
}
return p;
}
//按值查找操作
DNode*FindDElem(DLinkList L,ElemType e){
if(L==NULL){
printf("表为空!\n");
return NULL;
}
DNode*p=L->next;
while(p->data!=e){
p=p->next;
}
return p;
}
(6)定位删除和按序删除
//定位删除节点
void DeleteDLNode(DLinkList&L,int i,ElemType&e){
DNode*p=FindDNode(L,i);
e=p->data;
//如果是尾节点直接删除
if(p->next==NULL){
p->prior->next=p->next;
free(p);
return ;
}
if(p!=NULL){
DNode*s=p;
p->prior->next=s->next;
p->next->prior=s->prior;
free(s);
return ;
}
}
//按值删除
void DeleteDElem(DLinkList&L,ElemType e){
DNode*p=FindDElem(L,e);
//如果是尾节点直接删除
if(p->next==NULL){
p->prior->next=p->next;
free(p);
return ;
}
if(p!=NULL){
DNode*s=p;
p->prior->next=s->next;
p->next->prior=s->prior;
free(s);
return ;
}
}
(7)打印操作
//打印
void PrintDLinkList(DLinkList L){
DNode*p=L->next;
while(p!=NULL){
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}
(8)主函数
int main(){
DLinkList L;
InitDLinkList(L);
//对顺序表进行插入操作
ElemType x;
int flag=-1;
DNode*p=L;
//各种操作
while(1) {
int i=0;
ElemType e=0;
MenuLinkList();
printf("请输入操作: ");
scanf("%d",&flag);
int len=0;
DNode*s;
switch(flag){
case 1:
printf("请输入元素(-1_end): ");
scanf("%d",&x);
while(x!=-1) {
p=InsertDLinkList(p,x);
printf("请输入元素(-1_end): ");
scanf("%d",&x);
}
break;
case 2:
printf("请输入元素插入位置: \n");
scanf("%d",&i);
printf("请输入元素: ");
scanf("%d",&x);
InsertIDLinkList(L,i,x);
break;
case 3:
printf("请输入查找元素位置: ");
scanf("%d",&i);
s=FindDNode(L,i);
if(s!=NULL){
printf("查找的元素为 = %d\n",s->data);
}
break;
case 4:
printf("请输入要查找的值: ");
scanf("%d",&x);
s=FindDElem(L,x);
if(s!=NULL){
printf("查找的元素存在!\n");
}else{
printf("查找的元素不存在!\n");
}
break;
case 5:
printf("请输入删除的定位位置: ");
scanf("%d",&i);
DeleteDLNode(L,i,e);
printf("删除的元素为 = %d\n",e);
break;
case 6:
printf("请输入要删除的元素: ");
scanf("%d",&e);
DeleteDElem(L,e);
break;
case 7:
p=DestryDLinkList(p,L);
printf("删除成功!\n");
break;
case 8:
len=DLinkListLength(L);
printf("表的长度 = %d\n",len);
break;
case 9:
PrintDLinkList(L);
break;
default:
DestryDLinkList(p,L,flag);
printf("结束操作\n");
}
if(flag==10){
break;
}
}
return 0;
}
(9)测试
边栏推荐
猜你喜欢
随机推荐
elder blind date
ctf misc picture questions knowledge points
【场景化解决方案】OA审批与用友U9数据集成
网络层协议介绍
零搜索量的关键词,你需要布局吗?
ASP.net中的数据库应用
大学四年不努力,出社会后浑浑噩噩深感无力,辞去工作,从头开始
Redis redis 】 【 the expiration of listening
基于 JSch 实现服务的自定义监控解决方案
The 5th Blue Cap Cup preliminary misc reappears after the game
NodeMCU(ESP8266) 接入阿里云物联网平台 踩坑之旅
leetcode 37. 解数独 (困难)
Makefile中patsubst、wildcard、notdir的使用
权限管理模型 ---- ACL、RBAC和ABAC(详解)
ctfshow-web入门 文件上传篇部分题解
Makefile中的%标记和系统通配符*的区别
深度学习时代的视频理解综述
gin清晰简化版curd接口例子
[漏洞复现]CVE-2018-7490(路径遍历)
第1讲 Verilog基础知识