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;
}
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。