当前位置: article > 正文

数据结构—C语言实现双向链表

作者：繁依Fanyi0 | 2024-05-28 07:38:17

踩

数据结构—C语言实现双向链表

3.7 insert()函数在pos之后插入

1.双向带头循环链表

结构：

2.自定义头文件：


#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
 
 
typedef int type;
 
struct List
{
	type val;
	struct List* pre;
	struct List* next;
};
 
typedef struct List List;
 
void init(List** st);
List* newnode(type x);
void pushback(List* st, type x);
void print(List* st);
void pushfront(List* st, type x);
void popback(List* st);
void popfront(List* st);
void insert(List* pos, type x);
void erase(List* pos);
List* find(List* st, type x);
void destory(List* st);
void menu();

双向链表中的结点具有pre和next指针，分别连向上一个结点和下一个结点，val用来存储值。

3.List.cpp 文件

代码：


#include"Sqlist.h"
 
 
void menu()
{
	printf("******************************\n");
	printf("***1.init        2.pushback***\n");
	printf("***3.pushfront      4.print***\n");
	printf("***5.popback     6.popfront***\n");
	printf("***7.insert         8.erase***\n");
	printf("***9.destory         0.exit***\n");
	printf("******************************\n");
}
 
void init(List** st)
{
	*st = newnode(-1);
}
List* newnode(type x)
{
	List* nnee = (List*)malloc(sizeof(List));
 
	if (nnee == NULL)
	{
		perror("malloc");
		exit(0);
	}
 
	nnee->val = x;
	nnee->next = nnee->pre = nnee;
 
	return nnee;
}
void pushback(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
 
	List* nnee = newnode(x);
 
	nnee->next = st;
	nnee->pre = st->pre;
	st->pre->next = nnee;
	st->pre = nnee;
 
 
}
 
 
void print(List* st)
{
	List* cur = st->next;
 
	while (cur != st)
	{
		cout << cur->val << ' ';
		cur = cur->next;
	}
	cout << endl;
	return;
}
 
 
void pushfront(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
 
	List* nnee = newnode(x);
 
	nnee->next = st->next;
	nnee->pre = st;
	st->next->pre = nnee;
	st->next = nnee;
 
}
 
 
void popback(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}
 
	List* cur = st->pre;
	cur->pre->next = st;
	st->pre = cur->pre;
 
	free(cur);
	cur = NULL;
 
}
void popfront(List* st)
{
 
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}
 
	List* del = st->next;
 
	st->next = del->next;
	del->next->pre = st;
	free(del);
	del = NULL;
 
}
 
 
void insert(List* pos, type x)//之后
{
	if (pos == NULL)
	{
		printf("NULL\n");
		return;
	}
	List* nnee = newnode(x);
 
	nnee->next = pos->next;
	nnee->pre = pos;
 
	pos->next->pre = nnee;
	pos->next = nnee;
}
void erase(List* pos)
{
	if (pos == NULL)
	{
		printf("pos is NULL\n");
		return;
	}
 
	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
	pos = NULL;
}
List* find(List* st, type x)
{
	List* cur = st->next;
	while (cur != st)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
void destory(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
 
	List* cur = st->next;
 
	while (cur != st)
	{
		List* ne = cur->next;
		free(cur);
		cur = ne;
	}
 
	free(st);
	st = NULL;
	cur = NULL;
 
}

3.1 newnode()函数讲解

代码：


List* newnode(type x)
{
	List* nnee = (List*)malloc(sizeof(List));
 
	if (nnee == NULL)
	{
		perror("malloc");
		exit(0);
	}
 
	nnee->val = x;
	nnee->next = nnee->pre = nnee;
 
	return nnee;
}

(1).使用malloc函数开辟一块空间，赋给nnee。

(2).再判断是否开辟成功。开辟成功后，将x赋值给nnee的val，并且把nnee的两个指针域都赋值为自己。最后返回该结点。

3.2 init() 函数初始化


void init(List** st)
{
	*st = newnode(-1);
}

(1).由于我们创建的是带头循环链表，所以初始化要将链表的最开始创建一个头结点。

3.3 pushback()函数尾插


void pushback(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
 
	List* nnee = newnode(x);
 
	nnee->next = st;
	nnee->pre = st->pre;
	st->pre->next = nnee;
	st->pre = nnee;
}

(1).先判断链表的地址是否为空。

(2).创建一个新结点。

(3).将新结点的next指针指向头结点，再将新结点的pre指针指向st的pre。

再将头结点的pre的next(链表最后一个结点)指向新结点，再将头结点的pre指向新结点。

3.4 pushfront()函数头插


void pushfront(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
 
	List* nnee = newnode(x);
 
	nnee->next = st->next;
	nnee->pre = st;
	st->next->pre = nnee;
	st->next = nnee;
 
}

(1).创建新结点。

(2).将新结点的next指向头结点的next，再将新结点的pre指向头结点。

(3).再将头结点的next的pre指向新结点。头结点的next指向新结点。

3.5 popback() 尾删


void popback(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}
 
	List* cur = st->pre;
	cur->pre->next = st;
	st->pre = cur->pre;
 
	free(cur);
	cur = NULL;
 
}

(1).首先判断链表是否有头结点，还要判断链表是否已经为空，为空则 st->next == st，头结点自己指向自己时

(2).创建一个指针cur，令cur指向链表最后一个结点，再令最后一个节点的pre(倒数第二个结点)的next指向头结点，再令头节点的pre指向cur的pre(倒数第二个指针)。

3.6 popfront() 函数头删


void popfront(List* st)
{
 
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}
 
	List* del = st->next;
 
	st->next = del->next;
	del->next->pre = st;
	free(del);
	del = NULL;
 
}

(1).首先判断链表是否有头结点，还要判断链表是否已经为空，为空则 st->next == st，头结点自己指向自己时

(2).创建一个指针del，令del指向头结点的next(头结点的下一个结点)，再将头结点的next指向del的next，再将del的next的pre指向头结点。

3.7 insert()函数在pos之后插入


void insert(List* pos, type x)//之后
{
	if (pos == NULL)
	{
		printf("NULL\n");
		return;
	}
	List* nnee = newnode(x);
 
	nnee->next = pos->next;
	nnee->pre = pos;
 
	pos->next->pre = nnee;
	pos->next = nnee;
}

(1).创建一个新结点，令新结点的next指向pos的next。再将新结点的pre指向pos。

(2).再将pos的next的pre(pos下一个结点的pre指针)指向新结点；pos的next指向新结点。

3.8 popback()函数删除


void erase(List* pos)
{
	if (pos == NULL)
	{
		printf("pos is NULL\n");
		return;
	}
 
	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
	pos = NULL;
}

(1).将pos的pre的next(pos的前一个节点的next指针)指向pos的next(pos的下一个节点)。

(2).再将pos的next的pre(pos的下一个节点的pre指针)指向pos的pre(pos的前一个指针)

3.9 find() 函数查找


List* find(List* st, type x)
{
	List* cur = st->next;
	while (cur != st)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

(1).直接遍历链表即可，当遇到当前节点的val与x相同时，直接返回地址。

(2).若遍历完后还没有找到，则最后返回空。

3.10 print()函数打印


void print(List* st)
{
	List* cur = st->next;
 
	while (cur != st)
	{
		cout << cur->val << ' ';
		cur = cur->next;
	}
	cout << endl;
	return;
}

(1).直接遍历链表即可，依次打印节点的每个值。

4.test.cpp 文件

代码：


#include"Sqlist.h"
 
 
int main()
{
	List* head;
	List* pos=NULL;
	type x;
	int op;
	int n;
	type y;
	init(&head);
	do
	{
		menu();
		printf("input optio\n");
		cin >> op;
 
		switch (op)
		{
		case 1:
			init(&head);
			break;
		case 2:
			printf("input you want push number\n");
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				cin >> x;
				pushback(head, x);
			}
			break;
		case 3:
			printf("input you want push number\n");
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				cin >> x;
				pushfront(head, x);
			}
			break;
		case 4:
			print(head);
			break;
		case 5:
			popback(head);
			break;
		case 6:
			popfront(head);
			break;
		case 7:
			printf("input you pos and val\n");
			cin >> y >> x;
			pos = find(head,y);
			if (pos == NULL)
			{
				printf("pos is not save\n");
			}
			else
			{
				insert(pos, x);
			}
			break;
		case 8:
			printf("input you pos \n");
			cin >> y;
			pos = find(head, y);
			if (pos == NULL)
			{
				printf("pos is not save\n");
			}
			else
			{
				erase(pos);
			}
			break;
		case 9:
			destory(head);
			break;
		case 0:
			break;
 
 
		default:
			printf("piease input correct option\n");
			break;
		}
	} while (op);
 
}

完.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/636284

数据结构—C语言实现双向链表

1.双向带头循环链表

2.自定义头文件：

3.List.cpp 文件

3.1 newnode()函数讲解

3.2 init() 函数 初始化

3.3 pushback()函数 尾插

3.4 pushfront()函数 头插

3.5 popback() 尾删

3.6 popfront() 函数 头删

3.7 insert()函数 在pos之后插入

3.8 popback()函数 删除

3.9 find() 函数 查找

3.10 print()函数 打印

4.test.cpp 文件

3.2 init() 函数初始化

3.3 pushback()函数尾插

3.4 pushfront()函数头插

3.6 popfront() 函数头删

3.7 insert()函数在pos之后插入

3.8 popback()函数删除

3.9 find() 函数查找

3.10 print()函数打印