C++ 雙鏈表的基本操作(詳解)
更新時間：2016年12月18日 12:40:39 投稿：jingxian
下面小編就為大家?guī)硪黄狢++ 雙鏈表的基本操作(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
1.概念
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。
結構圖如下所示：
2.基本操作實例
DoubleList.cpp
#include "stdafx.h"
#include "DoubleList.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
DoubleList::DoubleList()
{
pDoubleListNode pDouList = NULL;
// 創(chuàng)建雙鏈表
CreateDouList(pDouList);
PrintDouList(pDouList);
// 打印逆序鏈表
PrintDouReverseList(pDouList);
// 節(jié)點后插入節(jié)點
InsertNodeAfter(pDouList);
PrintDouList(pDouList);
// 節(jié)點前插入節(jié)點
InsertNodeBefore(pDouList);
PrintDouList(pDouList);
// 刪除節(jié)點
DeleteNode(pDouList);
PrintDouList(pDouList);
// 刪除鏈表
DeleteDouList(pDouList);
PrintDouList(pDouList);
system("PAUSE");
}
DoubleList::~DoubleList()
{
}
//創(chuàng)建雙向鏈表
void DoubleList::CreateDouList(pDoubleListNode &head)
{
char x; // 定義成char型是用于輸入'q'時可以退出，其實定義成int也能退出
pDoubleListNode p, s;
head = (pDoubleListNode)malloc(sizeof(DoubleListNode));
head->next = NULL;
head->prior = NULL; // 構造頭結點p
p = head;
printf("\n輸入雙向鏈表的元素，每輸入一個元素后按回車，輸入q表示結束.\n");
fflush(stdin); //清空輸入緩沖區(qū)
x = getchar();
while (x != 'q')
{
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = x - '0'; // 得到的是輸入字符的ASCII碼，減去30H就變成想要的數(shù)字
s->next = NULL;
s->prior = p;
p->next = s;
p = s;
fflush(stdin);
x = getchar();
}
if (x == 'q')
{
printf("雙向鏈表構造完畢!\n");
}
}
//打印雙向鏈表
void DoubleList::PrintDouList(pDoubleListNode &head)
{
pDoubleListNode p;
printf("\n打印出雙向鏈表數(shù)據(jù)為：\n");
if (!IsDouListEmpty(head))
{
p = head->next;
while (p)
{
printf("%d\n", p->data);
p = p->next;
}
}
}
//逆序打印雙向鏈表
void DoubleList::PrintDouReverseList(pDoubleListNode &head)
{
pDoubleListNode p;
printf("\n打印出逆序雙向鏈表數(shù)據(jù)為：\n");
if (!IsDouListEmpty(head))
{
p = head->next;
while (p->next)
{
p = p->next;
}
while (p->prior)
{
printf("%d \n", p->data);
p = p->prior;
}
}
}
//求鏈表長度
int DoubleList::GetDouListLength(pDoubleListNode &head)
{
int length = 0;
if (head == NULL)
{
printf("鏈表不存在，請先初始化!\n");
}
else
{
pDoubleListNode p = head->next;
while (p)
{
length++;
p = p->next;
}
}
return length;
}
//判斷鏈表是否為空
bool DoubleList::IsDouListEmpty(pDoubleListNode &head)
{
if (head == NULL)
{
printf("鏈表不存在，請先初始化!\n");
return true;
}
else if (head->next == NULL)
{
printf("鏈表為空!\n");
return true;
}
return false;
}
//把雙向鏈表置空
void DoubleList::ClearDouList(pDoubleListNode &head)
{
if (head == NULL)
{
printf("鏈表不存在，請先初始化!\n");
}
else
{
pDoubleListNode p, q;
p = q = head->next; //是p、q指向第一個元素
head->next = NULL;
while (p) //逐個釋放元素所占內存
{
p = p->next;
free(q);
q = p;
}
}
}
// 刪除雙向鏈表
void DoubleList::DeleteDouList(pDoubleListNode &head)
{
printf("\n刪除雙向鏈表\n");
ClearDouList(head);
free(head);
head = NULL;
}
// 在雙向鏈表中第i個位置后面插入元素
void DoubleList::InsertNodeAfter(pDoubleListNode &head)
{
int data, pos;
pDoubleListNode p, s;
p = head;
int i = 0;
printf("\n在雙向鏈表中第i個位置后面插入元素\n");
printf("請輸入要插入的元素和位置:\n");
scanf_s("%d%d", &data, &pos, 100);
if (head == NULL)
{
printf("鏈表不存在，請先初始化!\n");
}
else if (head->next == NULL)
{
printf("鏈表為空，插入第一個元素!\n");
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
s->prior = NULL;
s->next = NULL;
head->next = s; // 將新結點插入head后
}
else if (pos<1 || pos>GetDouListLength(head) + 1)
{
printf("插入位置錯誤!\n");
}
else
{
while (i < pos)
{
p = p->next;
i++;
}
if (i == GetDouListLength(head)) //如果在最后一個元素后面插入data
{
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
s->next = NULL;
s->prior = p;
p->next = s;
}
else
{
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
}
}
}
// 在雙向鏈表中第i個位置前面插入元素
void DoubleList::InsertNodeBefore(pDoubleListNode &head)
{
int data, pos;
pDoubleListNode p, s;
p = head;
int i = 0;
printf("\n在雙向鏈表中第i個位置前面插入元素\n");
printf("請輸入要插入的元素和位置:\n");
scanf_s("%d%d", &data, &pos, 100);
if (head == NULL)
{
printf("鏈表不存在，請先初始化!\n");
}
else if (head->next == NULL)
{
printf("鏈表為空，插入第一個元素!\n");
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
s->prior = NULL;
s->next = NULL;
head->next = s; // 將新結點插入head后
}
else if (pos<1 || pos>GetDouListLength(head) + 1)
{
printf("插入位置錯誤!\n");
}
else
{
while (i < pos)
{
p = p->next;
i++;
}
if (i == 1) // 如果在第一個元素前面插入data
{
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
head->next = s; // 將新結點插入head后
s->prior = head; // 新結點的前結點指向頭結點
s->next = p; // 新結點的后結點指向原h(huán)ead的后結點
p->prior = s ; // 原第一個結點的前結點指向新結點
}
else
{
s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
s->data = data;
s->prior = p->prior;
s->next = p;
p->prior->next = s;
p->prior = s;
}
}
}
//刪除雙向鏈表中的第i個元素
void DoubleList::DeleteNode(pDoubleListNode &head)
{
int pos;
int i = 0;
pDoubleListNode p = head;
printf("\n在雙向鏈表中刪除第i個位置的元素\n");
printf("請輸入要刪除的位置:");
scanf_s("%d", &pos, 100);
if (IsDouListEmpty(head))
{
return;
}
else if (pos<1 || pos>GetDouListLength(head))
{
printf("刪除的位置不存在!\n");
}
else
{
while (i < pos)
{
p = p->next;
i++;
}
if (i == GetDouListLength(head))
{
p->prior->next = NULL;
free(p);
}
else
{
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
}
}
}
DoubleList.h
#pragma once
typedef struct DoubleListNode
{
int data; //數(shù)據(jù)
struct DoubleListNode *prior; //前驅
struct DoubleListNode *next; //后繼
}DoubleListNode, *pDoubleListNode;
class DoubleList
{
public:
DoubleList();
~DoubleList();
//初始化雙向鏈表
void DoubleList::CreateDouList(pDoubleListNode &head);
//打印雙向鏈表
void DoubleList::PrintDouList(pDoubleListNode &head);
//逆序打印雙向鏈表
void DoubleList::PrintDouReverseList(pDoubleListNode &head);
//求鏈表長度
int DoubleList::GetDouListLength(pDoubleListNode &head);
//判斷鏈表是否為空
bool DoubleList::IsDouListEmpty(pDoubleListNode &head);
//把雙向鏈表置空
void DoubleList::ClearDouList(pDoubleListNode &head);
//刪除雙向鏈表
void DoubleList::DeleteDouList(pDoubleListNode &head);
//在雙向鏈表中第i個位置后面插入元素m
void DoubleList::InsertNodeAfter(pDoubleListNode &head);
// 在雙向鏈表中第i個位置前面插入元素
void DoubleList::InsertNodeBefore(pDoubleListNode &head);
//刪除雙向鏈表中的第i個元素
void DoubleList::DeleteNode(pDoubleListNode &head);
};
3.對鏈表插入節(jié)點的理解
例如在節(jié)點i前插入一個新的節(jié)點(即上面代碼中的InsertNodeBefore函數(shù)):
鏈表結構體為：
typedef struct DoubleListNode
{
int data; // 數(shù)據(jù)
struct DoubleListNode *prior; // 前驅
struct DoubleListNode *next; // 后繼
}DoubleListNode, *pDoubleListNode;
假設該鏈表由五個節(jié)點構成,分別為A,B,C,D,E
圖中假設了A,B,C,D,E的地址分別為:addressA,addressB,addressC,addressD,addressE。
下面將分析鏈表的前插的例子:
雙鏈表的前插，下面這是在節(jié)點"D"前插入一個新的節(jié)點"S"的代碼和分析
s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); // 申請一段內存空間，指針指向首地址為addressS
s->data = data; // 給節(jié)點S的數(shù)據(jù)賦值data
s->prior = p->prior; // p指向D節(jié)點, p->prior表示addressC，將它賦給s->prior,則s->prior里面的值是addressC，從而指向addressC這個地址即節(jié)點C，如下圖S節(jié)點的藍線
s->next = p; // p是addressD，將它賦給s->next，s->next中的值為addressD，也即s->next指向了D，如下圖S節(jié)點的紅線
p->prior->next = s; // p->prior 是addressC，即節(jié)點C，所以p->prior->next相當于沒插入S之前的addressD，插入S后，將S的首地址即addressS賦給這個位置，所以此時，由C 到D的紅線斷裂，這個紅線目標變成了S，如下圖C節(jié)點的紅線
p->prior = s; // 同理，p->prior也指向了S，即p->prior中addressC變成了addressS, D指向C的藍線斷裂。變成如下圖D節(jié)點指向S節(jié)點的藍線.
以上這篇C++ 雙鏈表的基本操作(詳解)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
高效實現(xiàn)整型數(shù)字轉字符串int2str的方法
下面小編就為大家?guī)硪黄咝崿F(xiàn)整型數(shù)字轉字符串int2str的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
這篇文章主要介紹了C++淺拷貝與深拷貝及引用計數(shù)分析的相關資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C++構造函數(shù)拋出異常需要注意的地方，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
詳解C++編程中用數(shù)組名作函數(shù)參數(shù)的方法
這篇文章主要介紹了詳解C++編程中用數(shù)組名作函數(shù)參數(shù)的方法,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
在C++中，每一個對象都能通過this指針來訪問自己的地址。this?指針是所有成員函數(shù)的隱含參數(shù)。因此，在成員函數(shù)內部，它可以用來指向調用對象2022-05-05
C++數(shù)據(jù)結構二叉搜索樹的實現(xiàn)應用與分析
從這篇博客開始，我就要和大家介紹有關二叉搜索樹的知識，它還衍生出了兩棵樹——AVL樹和紅黑樹，在后面兩篇博客我都會介紹。今天先從二叉搜索樹開始引入2022-02-02
C++實現(xiàn)LeetCode(109.將有序鏈表轉為二叉搜索樹)
這篇文章主要介紹了C++實現(xiàn)LeetCode(109.將有序鏈表轉為二叉搜索樹),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
今天小編就為大家分享一篇opencv3/C++視頻中疊加透明圖片的實現(xiàn)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要介紹了C++11標準庫互斥鎖 <mutex> 的相關知識,使用call_once()的時候,需要一個once_flag作為call_once()的傳入?yún)?shù),本文給大家介紹的非常詳細,感興趣的朋友一起看看吧2024-07-07
這篇文章主要介紹了如何用C++制作LeetCode刷題小技巧-錯題記錄本的方法,需要的朋友可以參考下2021-04-04