C语言版:双向链表的建立以及基本操作

2021年6月26日 8点热度 0条评论 来源: 路飞QAQw

C语言版数据结构:双向链表的实现,以及增删改查等基本操作, 本篇文章是介绍如何建立,插入,删除。查找,修改与单链表,循环链表一样,遍历即可。

文章目录

双向链表

数据结构最常规的链表:单链表,循环链表,双向链表。双向链表解决了时间复杂度的问题,单链表和循环链表在进行修改和查找的过程,从查找直接后继为O(1),但是查找直接前驱O(n), 面对大量数据时,降低了执行效率。

一、基本操作

如果思想不是特别清晰的同学,要么是指针理解不够透彻,要么就是链表思想理解不够, 个人推荐去某站看王卓老师的数据结构于算法,从中会受益多多。

二、使用步骤

1.引入库

代码如下(示例):

#include<stdio.h> //调用基本输入/输出库文件
#include<stdlib.h> //调用标准库头文件,malloc函数在这个头文件中
#include<process.h> //使用系统库文件,暂停一下,看到执行结果

2.删除

代码如下(示例):


//删除操作,本次采用的按值操作
void Du_delete(RDuNode *node, int value)    //表示第几个位置
{ 
	RDuNode* p = initnode();       //生成一个新结点
	node = node->next;
	while (node->data != value)
	{ 
		node = node->next;
	}
	node->prior->next = node->next;
	node->next->prior = node->prior;
	p = node;
	delete p;
}

3.插入

//插入方式:为前插法
void front_insert(RDuNode* head, int x)
{ 
	RDuNode* p = initnode();
	p->data = x;
	if (head->next == NULL && head->prior == NULL)  //代表是一个空链表
	{ 
		head->next = p;
		head->prior = p;   //指向同一个地方
		p->next = head;
		p->prior = head; 
	}
	else
	{ 
		p->prior = head;
		p->next = head->next;
		head->next->prior = p;			//这才是代码的灵魂
		head->next = p;
	}
}

总结

无论是删除还是插入,都是交换指针指向对象的问题,我个人推荐还是需要手画过程,这样写出的代码会大大提高,加油各位!!!

代码实现

本次采用的是前插法构建双向链表, 也是一种插入。
#include<stdio.h>
#include<stdlib.h>
#include<process.h>


//双向链表的删,插入操作
typedef struct DuNode
{ 
	int data;
	struct DuNode* next;		//后继指针
	struct DuNode	*prior;   //前驱指针
}RDuNode;

RDuNode* initnode()
{ 
	RDuNode* node;
	node = (struct DuNode*)malloc(sizeof(struct DuNode));
	node->data = 0;
	node->prior = NULL;
	node->next = NULL;
	return node;
}

//创建只有一个头结点的双向链表
RDuNode* createDulink_list()
{ 
	RDuNode* head;
	head = initnode();
	return head;
}

//插入(前插法)构建的链表
void front_insert(RDuNode* head, int x)
{ 
	RDuNode* p = initnode();
	p->data = x;
	if (head->next == NULL && head->prior == NULL)  //代表是一个空链表
	{ 
		head->next = p;
		head->prior = p;   //指向同一个地方
		p->next = head;
		p->prior = head; 
	}
	else
	{ 
		p->prior = head;
		p->next = head->next;
		head->next->prior = p;
		head->next = p;
	}
}

void Du_delete(RDuNode *node, int value)    //表示第几个位置
{ 
	RDuNode* p = initnode();       //生成一个新结点
	node = node->next;
	while (node->data != value)
	{ 
		node = node->next;
	}
	node->prior->next = node->next;
	node->next->prior = node->prior;
	p = node;
	delete p;
}

//打印函数flag 表示需要正序打印, 或者逆序打印
void display(RDuNode* head, int flag)
{ 
	if (flag > 0)
	{ 
		RDuNode* p = head->next;
		while (p->next != head) { 
			printf("%d->", p->data);
			p = p->next;
		}
		printf("%d", p->data);
	}
	else if (flag < 0)
	{ 
		RDuNode* p = head->prior;
		while (p->prior != head) { 
			printf("%d->", p->data);
			p = p->prior;
		}
		printf("%d", p->data);
	}
	else
	{ 
		printf("位置非法!!!");
		exit(0);
	}
	
}
int main()
{ 
	RDuNode* Dulink_list;
	Dulink_list = createDulink_list();    //创立了一个链表
	for (int i = 8; i > 1; i--)
	{ 
		front_insert(Dulink_list, i);
	}
	//正数正序
	printf("\n利用后继进行遍历:\n");
	display(Dulink_list, 1);
	//负数逆序
	printf("\n利用前驱指针遍历:\n");
	display(Dulink_list, -1);
	Du_delete(Dulink_list, 2);
	printf("\n删除元素值为2的双向链表:\n");
	display(Dulink_list, 1);
	Du_delete(Dulink_list, 5);
	printf("\n删除元素值为4的双向链表:\n");
	display(Dulink_list, 1);
	return 0;
}

结果测试
利用后继进行遍历:
2->3->4->5->6->7->8
利用前驱指针遍历:
8->7->6->5->4->3->2
删除元素值为2的双向链表:
3->4->5->6->7->8
删除元素值为4的双向链表:
3->4->6->7->8
    原文作者:路飞QAQw
    原文地址: https://blog.csdn.net/m0_53318344/article/details/118252357
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。