[数据结构与算法] 【数据结构】1.3线性表的链式表示（双链表）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】1.3线性表的链式表示（双链表） -> 正文阅读

[数据结构与算法]【数据结构】1.3线性表的链式表示（双链表）

结点定义

//带头结点的双链表 
//在单链表的基础上加个指向前一结点的指针prior 
//结点定义 
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
	struct DNode *r; //尾结点 
}DNode,*DLinklist;

初始化

//初始化
bool InitDLinkList(DLinklist &L){
	L=(DNode*)malloc(sizeof(DNode));//分配一个头结点
	if(L==NULL){
		return false;
	} 
	L->prior=NULL;//头结点的prior永远指向NULL；
	L->next=NULL;//空表，因此头结点之后暂时没有结点
	return true;	 
}

求长度

//求长度 （带头结点 ） 
int Length(DLinklist L){
	int len=0;
	DNode *p=L;
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
	return len;
}

判断是否为空

//判断是否为空
bool Empty(DLinklist &L){
	if(L->next==NULL){
		printf("双链表为NULL！\n"); 
		return true;
	}else{
		printf("双链表不为NULL，长度为：%d\n",Length(L));
		return false;
	}
}

双链表创建

头插法（倒序）

//头插构建 （反向） 
//头插法的重要作用：链表的逆置 
DLinklist DList_HeadInsert(DLinklist &L){
	printf("头插法构建双链表：(以空格间隔、9999结束)\n"); 
	DNode *s;
	int x;
	L=(DLinklist)malloc(sizeof(DNode));//创建头结点 
	L->next=NULL;//初始为空链表（！！！！！！！必须得加 ） 
	scanf("%d",&x);//输入结点的值 
	while(x!=9999){//输入9999 表示结束 
		s=(DNode*)malloc(sizeof(DNode));//创建新结点（由系统生成一个LNode型的结点，同时将该节点的起始位置赋给指针变量s） 
		s->data=x;
		if(L->next==NULL){//如果链表只有头结点 
			L->next=s;
			s->prior=L;
			s->next=NULL;
			L->r=s;//记录尾结点 
		} else{
			s->next=L->next;
			s->next->prior=s;
			L->next=s;
			s->prior=L;
		}
		scanf("%d",&x);
	}
	return L;
}

尾插法（顺序）

//尾插构建,正向 
DLinklist DList_TailInsert(DLinklist &L){
	printf("尾插法构建双链表：(以空格间隔、9999结束)\n"); 
	int x;
	L=(DLinklist)malloc(sizeof(DNode));//创建头结点 
	L->next=NULL;//初始为空链表（！！！！！！！必须得加 ） 
	DNode *s,*r=L;//r为表尾指针 
	scanf("%d",&x);//输入结点的值 
	while(x!=9999){//输入9999 表示结束 
		s=(DNode*)malloc(sizeof(DNode));//创建新结点（由系统生成一个LNode型的结点，同时将该节点的起始位置赋给指针变量s） 
		s->data=x;
		r->next=s;
		s->prior=r;
		r=s;//r指向新的表尾结点 
		scanf("%d",&x);
	}
	r->next=NULL;//尾结点指针置空，即为最后结点，下一结点为空 
	L->r=r;
	return L;
}

插入

指定结点前插入

//前插，在p结点之前插入s 
bool InsertPriorNode(DNode *p,DNode *s){
	if(p==NULL||s==NULL){//非法参数 
		return false; 
	}
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
}

指定结点后插入

//后插，在p结点之后插入s 
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL||s==NULL){//非法参数 
		return false; 
	}
	s->next=p->next;
	if(p->next!=NULL){//p有后继结点 
		p->next->prior=s;
	}
	s->prior=p;
	p->next=s;
}

遍历

从前往后

//从前往后遍历
void Head_PrintList(DLinklist &L){
	printf("【从前向后遍历】\n");
	DNode *p;
	p=L->next;
	while(p!=NULL){
		printf("%d\n",p->data);
		p=p->next;
	}
}

从后往前

//从后往前遍历 
void Tail_PrintList(DLinklist &L){
	printf("【从后向前遍历】\n");
	DNode *p;
	p=L->r;
	while(p!=L){
		printf("%d\n",p->data);
		p=p->prior;
	}
}

删除结点

//删除,删除p的后继结点 
bool DeleteNextDNode(DNode *p){
	if(p==NULL){//非法参数 
		return false;
	} 
	DNode *q=p->next;
	if(q==NULL){//p没有后继结点 
		return false;
	} 
	p->next=q->next;
	if(q->next!=NULL){//q有后继结点 
		q->next->prior=p;
	}
	free(q);//释放结点空间 
	return true; 
}

销毁双链表

//销毁
void DestoryList(DLinklist &L){
	printf("DestoryList"); 
	while(L->next!=NULL){//循环释放各个节点 
		DeleteNextDNode(L);
	}	
	free(L);//释放头结点
	L=NULL;//头指针指向NULL
	printf("双链表已销毁！"); 
}

完整代码及运行结果

代码

#include<stdlib.h>
#include<stdio.h>
//带头结点的双链表 
//在单链表的基础上加个指向前一结点的指针prior 
//结点定义 
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
	struct DNode *r; //尾结点 
}DNode,*DLinklist;

//初始化
bool InitDLinkList(DLinklist &L){
	L=(DNode*)malloc(sizeof(DNode));//分配一个头结点
	if(L==NULL){
		return false;
	} 
	L->prior=NULL;//头结点的prior永远指向NULL；
	L->next=NULL;//空表，因此头结点之后暂时没有结点
	return true;	 
}

//求长度 （带头结点 ） 
int Length(DLinklist L){
	int len=0;
	DNode *p=L;
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
	return len;
}

//判断是否为空
bool Empty(DLinklist &L){
	if(L->next==NULL){
		printf("双链表为NULL！\n"); 
		return true;
	}else{
		printf("双链表不为NULL，长度为：%d\n",Length(L));
		return false;
	}
} 
 
 
//头插构建 （反向） 
//头插法的重要作用：链表的逆置 
DLinklist DList_HeadInsert(DLinklist &L){
	printf("头插法构建双链表：(以空格间隔、9999结束)\n"); 
	DNode *s;
	int x;
	L=(DLinklist)malloc(sizeof(DNode));//创建头结点 
	L->next=NULL;//初始为空链表（！！！！！！！必须得加 ） 
	scanf("%d",&x);//输入结点的值 
	while(x!=9999){//输入9999 表示结束 
		s=(DNode*)malloc(sizeof(DNode));//创建新结点（由系统生成一个LNode型的结点，同时将该节点的起始位置赋给指针变量s） 
		s->data=x;
		if(L->next==NULL){//如果链表只有头结点 
			L->next=s;
			s->prior=L;
			s->next=NULL;
			L->r=s;//记录尾结点 
		} else{
			s->next=L->next;
			s->next->prior=s;
			L->next=s;
			s->prior=L;
		}
		scanf("%d",&x);
	}
	return L;
}

//尾插构建,正向 
DLinklist DList_TailInsert(DLinklist &L){
	printf("尾插法构建双链表：(以空格间隔、9999结束)\n"); 
	int x;
	L=(DLinklist)malloc(sizeof(DNode));//创建头结点 
	L->next=NULL;//初始为空链表（！！！！！！！必须得加 ） 
	DNode *s,*r=L;//r为表尾指针 
	scanf("%d",&x);//输入结点的值 
	while(x!=9999){//输入9999 表示结束 
		s=(DNode*)malloc(sizeof(DNode));//创建新结点（由系统生成一个LNode型的结点，同时将该节点的起始位置赋给指针变量s） 
		s->data=x;
		r->next=s;
		s->prior=r;
		r=s;//r指向新的表尾结点 
		scanf("%d",&x);
	}
	r->next=NULL;//尾结点指针置空，即为最后结点，下一结点为空 
	L->r=r;
	return L;
} 
 

//后插，在p结点之后插入s 
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL||s==NULL){//非法参数 
		return false; 
	}
	s->next=p->next;
	if(p->next!=NULL){//p有后继结点 
		p->next->prior=s;
	}
	s->prior=p;
	p->next=s;
} 

//前插，在p结点之前插入s 
bool InsertPriorNode(DNode *p,DNode *s){
	if(p==NULL||s==NULL){//非法参数 
		return false; 
	}
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
} 


//删除,删除p的后继结点 
bool DeleteNextDNode(DNode *p){
	if(p==NULL){//非法参数 
		return false;
	} 
	DNode *q=p->next;
	if(q==NULL){//p没有后继结点 
		return false;
	} 
	p->next=q->next;
	if(q->next!=NULL){//q有后继结点 
		q->next->prior=p;
	}
	free(q);//释放结点空间 
	return true; 
}

//销毁
void DestoryList(DLinklist &L){
	printf("DestoryList"); 
	while(L->next!=NULL){//循环释放各个节点 
		DeleteNextDNode(L);
	}	
	free(L);//释放头结点
	L=NULL;//头指针指向NULL
	printf("双链表已销毁！"); 
}


//从后往前遍历 
void Tail_PrintList(DLinklist &L){
	printf("【从后向前遍历】\n");
	DNode *p;
	p=L->r;
	while(p!=L){
		printf("%d\n",p->data);
		p=p->prior;
	}
}

//从前往后遍历
void Head_PrintList(DLinklist &L){
	printf("【从前向后遍历】\n");
	DNode *p;
	p=L->next;
	while(p!=NULL){
		printf("%d\n",p->data);
		p=p->next;
	}
} 

int main(){
	DLinklist L1,L2;
	InitDLinkList(L1); //初始化双链表
	Empty(L1);//判断是否为空表 
	DList_HeadInsert(L1);//头插法创建 
	Empty(L1); //判断是否为空表
	Head_PrintList(L1); //从前往后遍历 
	Tail_PrintList(L1);//从后往前遍历 
	DList_TailInsert(L2);//尾插法创建 
	Empty(L2);//判断是否为空表
	Head_PrintList(L2);//从前往后遍历 
	Tail_PrintList(L2);//从后往前遍历 
	DestoryList(L2);//销毁双链表 
}

运行结果

双链表为NULL！
头插法构建双链表：(以空格间隔、9999结束)
1 2 3 4 5 6 9999
双链表不为NULL，长度为：6
【从前向后遍历】
6
5
4
3
2
1
【从后向前遍历】
1
2
3
4
5
6
尾插法构建双链表：(以空格间隔、9999结束)
1 2 3 4 5 6 9999
双链表不为NULL，长度为：6
【从前向后遍历】
1
2
3
4
5
6
【从后向前遍历】
6
5
4
3
2
1
DestoryList双链表已销毁！

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2022-04-01 23:38:43 更:2022-04-01 23:40:09

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 9:50:34-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码