C++代码实现双向链表
时间：2022-10-12 10:04:49|栏目：C代码|点击： 次
本文实例为大家分享了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;
}
