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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持源码搜藏网。