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

发布于：2024-05-05 ⋅ 阅读:(33) ⋅ 点赞:(0)

目录

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 文件

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);

}

完. 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布