数据结构双向链表,实现增删改查

这篇具有很好参考价值的文章主要介绍了数据结构双向链表,实现增删改查。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、双向链表的描述

        在单链表中,查找直接后继结点的执行时间为O(1),而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点,可以用双向链表

        在双向链表的结点中有两个指针域,一个指向直接后继,另一个指向直接前驱。

数据结构双向链表,实现增删改查,数据结构练习,# 数据结构练习(7月19),数据结构,链表文章来源地址https://www.toymoban.com/news/detail-597333.html

二、双向链表的存储结构

typedef char ElemType[20];  //重定义数据域的数据类型
typedef struct LNode  //定义双向链表存储结构
{
	ElemType data;
	struct LNode *next;
	struct LNode *prev;
}*DoubleLink;

三、双向链表的操作

2.1 双向链表结点创建

DoubleLink Request_space()  //在堆区申请一个结点空间
{
	DoubleLink node=(DoubleLink)malloc(sizeof(struct LNode));
	if(NULL==node)
		return NULL;
	strcpy(node->data,"");
	node->next=node->prev=NULL;
	return node;
}

2.2 双向链表遍历

int Output(DoubleLink L_list)  //实现输出
{
	if(NULL==L_list)
		return -1;
	DoubleLink p=L_list;
	do
	{
		printf("%s ",p->data);
		p=p->next;
	}while(p!=NULL);
	puts("");
	return 0;
}

2.3 双向链表头插

DoubleLink insert_head(DoubleLink L_list,ElemType value)  //实现头插
{
	DoubleLink node=Request_space();
	if(NULL==node)
		return L_list;  
	strcpy(node->data,value);
	if(NULL!=L_list)
	{
		node->next=L_list;
		L_list->prev=node;
	}
	L_list=node;
	return L_list;
}

2.4 双向链表尾插

DoubleLink insert_rear(DoubleLink L_list,ElemType value)  //实现尾插
{
	DoubleLink node=Request_space();
	strcpy(node->data,value);
	if(NULL==L_list)
		L_list=node;
	else
	{
		DoubleLink rear=L_list;
		while(rear->next!=NULL)
			rear=rear->next;
		rear->next=node;
		node->prev=rear;
	}
	return L_list;
}

2.5 双向链表头删

DoubleLink delete_head(DoubleLink L_list)  //实现头删
{
	if(NULL==L_list)
		return NULL;
	if(L_list->next==NULL)
	{
		free(L_list);
		L_list=NULL;
	}
	else
	{
		DoubleLink p=L_list->next;
		strcpy(L_list->data,p->data);
		L_list->next=p->next;
		if(p->next!=NULL)
			p->next->prev=L_list;
		free(p);
		p=NULL;
	}
	return L_list;
}

2.6 双向链表尾删

DoubleLink delete_rear(DoubleLink L_list)  //实现尾删
{
	if(NULL==L_list)
		return NULL;
	if(L_list->next==NULL)
	{
		free(L_list);
		L_list=NULL;
	}
	else
	{
		DoubleLink rear=L_list;
		while(rear->next!=NULL)
			rear=rear->next;
		rear->prev->next=NULL;
		free(rear);
		rear=NULL;
	}
	return L_list;
}

2.7 计算双向链表长度

int len_Llist(DoubleLink L_list)  //计算双向链表长度
{
	int count=0;
	if(NULL==L_list)
		return -1;
	while(L_list!=NULL)
	{
		count++;
		L_list=L_list->next;
	}
	return count;
}

2.8 双向链表逆置

DoubleLink rev_list(DoubleLink L_list)  //双向链表逆置
{
	if(NULL==L_list||L_list->next==NULL)
		return L_list;
	int len=len_Llist(L_list)-1;
	DoubleLink p=L_list->next;
	L_list->next=NULL;
    L_list->prev=L_list->next;
	for(int i=0;i<len;i++)
	{
		DoubleLink q=p;
		p=p->next;
		q->prev=q->next;
		q->next=L_list;
		L_list=q;
	}
	return L_list;
}

四、多文件编辑实现双向链表操作

头文件 head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char ElemType[20];  //重定义数据域的数据类型
typedef struct LNode  //定义双向链表存储结构
{
	ElemType data;
	struct LNode *next;
	struct LNode *prev;
}*DoubleLink;

DoubleLink Request_space();  //在堆区申请一个结点空间
int Output(DoubleLink L_list);  //实现输出
DoubleLink insert_head(DoubleLink L_list,ElemType value);  //实现头插
DoubleLink insert_rear(DoubleLink L_list,ElemType value);  //实现尾插
DoubleLink delete_head(DoubleLink L_list);  //实现头删
DoubleLink delete_rear(DoubleLink L_list);  //实现尾删
DoubleLink rev_list(DoubleLink L_list);  //双向链表逆置

#endif

自定义函数 fun.c

#include "head.h"
DoubleLink Request_space()  //在堆区申请一个结点空间
{
	DoubleLink node=(DoubleLink)malloc(sizeof(struct LNode));
	if(NULL==node)
		return NULL;
	strcpy(node->data,"");
	node->next=node->prev=NULL;
	return node;
}
int Output(DoubleLink L_list)  //实现输出
{
	if(NULL==L_list)
		return -1;
	DoubleLink p=L_list;
	do
	{
		printf("%s ",p->data);
		p=p->next;
	}while(p!=NULL);
	puts("");
	return 0;
}

DoubleLink insert_head(DoubleLink L_list,ElemType value)  //实现头插
{
	DoubleLink node=Request_space();
	if(NULL==node)
		return L_list;  
	strcpy(node->data,value);
	if(NULL!=L_list)
	{
		node->next=L_list;
		L_list->prev=node;
	}
	L_list=node;
	return L_list;
}

DoubleLink insert_rear(DoubleLink L_list,ElemType value)  //实现尾插
{
	DoubleLink node=Request_space();
	strcpy(node->data,value);
	if(NULL==L_list)
		L_list=node;
	else
	{
		DoubleLink rear=L_list;
		while(rear->next!=NULL)
			rear=rear->next;
		rear->next=node;
		node->prev=rear;
	}
	return L_list;
}

DoubleLink delete_head(DoubleLink L_list)  //实现头删
{
	if(NULL==L_list)
		return NULL;
	if(L_list->next==NULL)
	{
		free(L_list);
		L_list=NULL;
	}
	else
	{
		DoubleLink p=L_list->next;
		strcpy(L_list->data,p->data);
		L_list->next=p->next;
		if(p->next!=NULL)
			p->next->prev=L_list;
		free(p);
		p=NULL;
	}
	return L_list;
}

DoubleLink delete_rear(DoubleLink L_list)  //实现尾删
{
	if(NULL==L_list)
		return NULL;
	if(L_list->next==NULL)
	{
		free(L_list);
		L_list=NULL;
	}
	else
	{
		DoubleLink rear=L_list;
		while(rear->next!=NULL)
			rear=rear->next;
		rear->prev->next=NULL;
		free(rear);
		rear=NULL;
	}
	return L_list;
}
int len_Llist(DoubleLink L_list)  //计算双向链表长度
{
	int count=0;
	if(NULL==L_list)
		return -1;
	while(L_list!=NULL)
	{
		count++;
		L_list=L_list->next;
	}
	return count;
}
DoubleLink rev_list(DoubleLink L_list)  //双向链表逆置
{
	if(NULL==L_list||L_list->next==NULL)
		return L_list;
	int len=len_Llist(L_list)-1;
	DoubleLink p=L_list->next;
	L_list->next=NULL;
	for(int i=0;i<len;i++)
	{
		DoubleLink q=p;
		p=p->next;
		q->prev=q->next;
		q->next=L_list;
		L_list=q;
	}
	return L_list;
}

主函数 main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	DoubleLink L_list=NULL;  //定义头指针变量,注意定义时一定要指向NULL
	int n;            //定义循环输入次数
	ElemType value;   //定义数据域元素
	int seat;  //定义元素位置

	printf("please enter n:");
	scanf("%d",&n);

 	for(int i=0;i<n;i++)  //头插
	{
		printf("please enter a value:");
		scanf("%s",value);
		L_list=insert_head(L_list,value);
	}
	
	for(int i=0;i<n;i++)  //尾插
	{	
		printf("please enter a value:");
		scanf("%s",value);
		L_list=insert_rear(L_list,value);
	}

	L_list=delete_head(L_list);  //头删
	L_list=delete_rear(L_list);  //尾删
	Output(L_list);


	L_list=rev_list(L_list);  //双向链表逆置
	Output(L_list);

	return 0;
}

到了这里,关于数据结构双向链表,实现增删改查的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——双向链表的实现

    注意: 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点,实际为“ 哨兵位 ”,哨兵位节点不存储任何有效元素,只

    2024年02月06日
    浏览(48)
  • 【(数据结构)— 双向链表的实现】

    注意: 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念,实际前面的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点,实际为 “哨兵位” ,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(46)
  • 双向链表--C语言实现数据结构

    本期带大家一起用C语言实现双向链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;简单来说,线性表的链式存储结构生成的表,称作“链表”。 每个元素本身由两部分组成: 1、本身的信息,称

    2024年02月04日
    浏览(59)
  • 数据结构:双向链表的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 本篇博客,将要实现的是 带头双向循环链表 ,该结构实现尾插,尾删只需要O(1)的时间复杂度。 其结构如下所示: 既然要实现的链表是双向循环的,那么对于指针域,我们就需要 指向节点上一个的指针 和 指向节点

    2024年02月14日
    浏览(52)
  • 数据结构之List(双向链表)的实现

    方法名 参数 功能 返回 find const T val, int n, listNode * p 区间查找 从p往前数n个节点 指针或NULL const T val, listNode * p 区间查找 从p往前到首节点 const T val 查找 Size void 链表规模 size empty void 判空 bool first void 返回首节点 首节点指针 clear void 清空链表 void insertAsFirst const T val 作为首节

    2024年02月16日
    浏览(47)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • 【数据结构】—C语言实现双向链表(超详细!)

                                          食用指南:本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了:C语言                                     🍀 双向链表 前 置知识 :单链表      

    2024年02月13日
    浏览(50)
  • 数据结构 —— 双向链表(超详细图解 & 接口函数实现)

    数据结构 —— 顺序表 数据结构 —— 单链表 数据结构 —— 双向链表 数据结构 —— 队列 数据结构 —— 栈 数据结构 —— 堆 数据结构 —— 二叉树 数据结构 —— 八大排序 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元

    2024年02月11日
    浏览(42)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 【数据结构】C语言实现双向链表(带头结点、循环)

    结点定义: 接口定义: 我们将申请结点的代码封装成函数,方便后续使用 由于是带头结点的双向链表,因此在使用链表前,我们需要对链表进行初始化。 遍历链表,值得说的是,带头结点的双向链表的循环结束条件是 cur != phead 尾插时,需要先找到尾结点,然后将新结点插

    2024年02月03日
    浏览(72)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包