[数据结构与算法]C++实现双向链表

双向链表：两个指针域，一个指向前结点，一个指向后结点

list.h

#pragma once
#define OK 		1
#define ERROR 	0
#define TRUE 	1
#define FALSE 	0

typedef int Status;
typedef int ElemType;

typedef struct DNode
{
	struct DNode *prior;		//前结点指针域
	ElemType data;				//数据域
	struct DNode *next;			//后结点指针域
}DNode, *DLinkList;				//结点和指向结点的指针

bool InitDLinkList(DLinkList &L);						//双链表初始化
Status CreatDLinkList(DLinkList &L);					//尾插法创建链表，包含初始化功能
bool InsertNextDNode(DNode *p, DNode *s);				//结点s插入在结点p之后
Status DeleteNextDNode(DNode *p, ElemType &e);			//删除结点p的后继节点				
void ListTraverse(const DLinkList L);					//双链表的遍历
Status ListInsert(DLinkList &L, int i, ElemType e);		//指定位置插入元素
Status ListDelete(DLinkList &L, int i, ElemType &e);	//指定位置删除元素
DNode* GetElem(DLinkList L, int i);						//查找链表指定位置节点，返回的是结点
void DestoryList(DLinkList &L);							//销毁双链表,需要释放头结点

oper_func.cpp

#include <iostream>
#include"list.h"

bool InitDLinkList(DLinkList &L)
{
	//构建空的双链表，作为双链表的头结点，数据域为空
	L = new DNode;
	if (L == NULL)				//内存分配失败
		return FALSE;
	L->prior = NULL;			//头结点的前驱指针始终指向NULL	
	L->next = NULL;				//暂时指向NULL
	return TRUE;
}

Status CreatDLinkList(DLinkList &L)
{
	//利用InsertNextDNode函数来创建

	using std::cin;
	using std::cout;
	using std::endl;
	if (InitDLinkList(L))
	{
		DNode *s,*r = L;				//s为新建的新结点，用来存储数据，而r为尾指针，始终指向尾部节点
		int num;
		cout << "输入你需要创建的双链表的个数：";
		cin >> num;
		for (int i = 1; i <= num; i++)
		{
			s = new DNode;				//创建的新结点
			cout << "输入第" << i << "个元素：";
			cin >> s->data;				//输入数据
			s->next = NULL;
			InsertNextDNode(r,s);		//结点s插在尾部节点之后
			r = s;						//尾指针指向新的尾结点
		}
		return OK;
	}
	else
	{
		cout << "内存不够，单链表创建失败！" << endl;
		return ERROR;
	}
}

//结点s插入在结点p之后
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;
	return TRUE;
}

Status DeleteNextDNode(DNode *p, ElemType &e)
{
	if(p == NULL)
		return FALSE;			//非法参数
	DNode *q = p->next;			//找到p节点的后继节点
	if (q == NULL)				//节点p没有后继节点
	{
		return ERROR;
	}
	else
	{
		//有后继节点，但是p的后继节点为空
		p->next = q->next;
		e = q->data;
		if (q->next != NULL)
		{
			q->next->prior = p;
		}
		delete q;
		return OK;
	}
}

void ListTraverse(const DLinkList L)
{
	using std::cout;
	using std::endl;
	int i = 1;
	DNode *p = L->next;					//指向第一个元素
	if (p == NULL)
	{
		cout << "双链表为空，无法输出元素！" << endl;
		return;
	}
	while (p)
	{
		cout << "第" << i++ << "个元素为：" << p->data << endl;
		p = p->next;
	}
}

Status ListDelete(DLinkList &L, int i, ElemType &e)
{
	if (i < 1)		 		//位置不合理
		return ERROR;
	//寻找第i-1个结点
	DNode *p = GetElem(L, i - 1);
	//删除i-1结点的后面结点
	return DeleteNextDNode(p,e);
}

DNode* GetElem(DLinkList L, int i)
{
	DNode *p = L;
	int j = 0;				//表示p指向的当前结点的位置，此时为头结点
	while (p != NULL && j < i)
	{
		p = p->next;		//指向下一个结点
		j++;
	}
	return p;
}

void DestoryList(DLinkList &L)
{
	using std::cout;
	using std::endl;
	ElemType temp;
	int i = 1;
	while (L->next != NULL)
	{
		DeleteNextDNode(L,temp);
		cout << "第" << i++ << "个删除的元素为：" << temp << endl;
	}
	cout << "双链表全部数据销毁成功！" << endl;
	delete L;
	cout << "头结点销毁，整个双链表销毁成功！" << endl;
	L = NULL;				//头指针指向NULL
}

Status ListInsert(DLinkList &L, int i, ElemType e)
{
	if (i < 1)
		return FALSE;
	//寻找第i-1个结点
	DNode *p = GetElem(L, i - 1);
	//直接在i-1结点的后面插入元素即可
	DNode *s = new DNode;		//新建节点
	s->data = e;
	s->next = NULL;
	s->prior = NULL;
	return InsertNextDNode(p,s);
}

main.cpp

/* 双向链表：带头结点，且头结点的prior指针时钟指向为NULL

1、双链表的初始化
2、双链表的创建
3、双链表的结点插入（相当于后插操作）：（结点s插入结点p之后）需要考虑p结点是不是最后一个结点
	如果想前插操作，则找到该节点的i-1节点，然后实行后插操作也是一样
4、双链表的结点删除（相当于后删操作）：（删除p节点的后序节点q）需要考虑p结点是不是最后一个结点
	也要考虑q节点是不是最后一个结点
5、双链表的删除：
6、双链表的遍历：
7、双链表的销毁：需要回收头结点

*/

#include <iostream>
#include"list.h"

void showMenu()
{
	using std::cout;
	using std::cin;
	using std::endl;
	cout << "*********************************************************" << endl;
	cout << "*** 1.指定位置插入元素			2.删除指定位置元素 ***" << endl;
	cout << "*** 3.遍历单链表			0.销毁双链表并退出 ***" << endl;
	cout << "*********************************************************" << endl;
}

int main()
{
	using std::cout;
	using std::cin;
	using std::endl;
	int select = 0, flag = -1;			//输入的选择

	DLinkList L;				//L表示头指针，始终指向表头

	if (CreatDLinkList(L))		//尾插法创建单链表
	{
		cout << "双链表创建成功！" << endl;
	}
	else
		cout << "双链表创建失败！" << endl;

	while (true)
	{
		showMenu();
		cout << "输入你的选择：";
		cin >> select;
		switch (select)
		{
		case 1: {		//指定位置插入元素
			int position = 0, elem = 0;
			cout << "输入插入的位置和元素:";
			cin >> position >> elem;
			if (ListInsert(L, position, elem))
				cout << "指定位置插入元素成功！" << endl;
			else
				cout << "内存分配失败或者插入位置越界，插入失败！" << endl;
		}
				break;
		case 2: {		//删除指定位置节点
			int position = 0, elem = 0;
			cout << "输入指定位置:";
			cin >> position;
			if (ListDelete(L, position, elem))
			{
				cout << "删除指定位置元素成功！元素为：" << elem << endl;
			}
			else
			{
				cout << "单链表为空或者删除位置不合理！" << endl;
			}
		}
				break;
		case 3: {
			ListTraverse(L);
		}
				break;
		case 0: {
			DestoryList(L);
			system("pause");
			return 0;
		}
		break;
		}
	}
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖