C++ 雙鏈表的根本操作(詳解)

C++ 雙鏈表的根本操作(詳解)。本站提示廣大學習愛好者：（C++ 雙鏈表的根本操作(詳解)）文章只能為提供參考，不一定能成為您想要的結果。以下是C++ 雙鏈表的根本操作(詳解)正文

---

1.概念

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，辨別指向直接後繼和直接前驅。所以，從雙向鏈表中的恣意一個結點開端，都可以很方便地訪問它的前驅結點和後繼結點。普通我們都結構雙向循環鏈表。

構造圖如下所示：

　　

　　

2.根本操作實例

DoubleList.cpp

#include "stdafx.h"
#include "DoubleList.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
DoubleList::DoubleList()
{
    pDoubleListNode pDouList = NULL;
    // 創立雙鏈表
    CreateDouList(pDouList);
    PrintDouList(pDouList);
    // 打印逆序鏈表
    PrintDouReverseList(pDouList);
    // 節點後拔出節點
    InsertNodeAfter(pDouList);
    PrintDouList(pDouList);
    // 節點前拔出節點
    InsertNodeBefore(pDouList);
    PrintDouList(pDouList);
    // 刪除節點
    DeleteNode(pDouList);
    PrintDouList(pDouList);
    // 刪除鏈表
    DeleteDouList(pDouList);
    PrintDouList(pDouList);
    system("PAUSE");
}
DoubleList::~DoubleList()
{
}
//創立雙向鏈表
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);  //清空輸出緩沖區
  x = getchar();
  while (x != 'q')
  {
    s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
    s->data = x - '0'; // 失掉的是輸出字符的ASCII碼，減去30H就變成想要的數字
    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打印出雙向鏈表數據為：\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打印出逆序雙向鏈表數據為：\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;            // 新結點的後結點指向原head的後結點 
      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;       //數據
  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.對鏈表拔出節點的了解

例如在節點i前拔出一個新的節點(即下面代碼中的InsertNodeBefore函數):

鏈表構造體為：

typedef struct DoubleListNode
{
  int data;       // 數據
  struct DoubleListNode *prior; // 前驅
  struct DoubleListNode *next; // 後繼
}DoubleListNode, *pDoubleListNode;

假定該鏈表由五個節點構成,辨別為A,B,C,D,E

　　

圖中假定了A,B,C,D,E的地址辨別為:addressA,addressB,addressC,addressD,addressE。

上面將剖析鏈表的前插的例子:

雙鏈表的前插，上面這是在節點"D"前拔出一個新的節點"S"的代碼和剖析

s = (pDoubleListNode)malloc(sizeof(DoubleListNode));　　// 請求一段內存空間，指針指向首地址為addressS s->data = data;　　　　 // 給節點S的數據賦值data s->prior = p->prior;　　// p指向D節點, p->prior表示addressC，將它賦給s->prior,則s->prior外面的值是addressC，從而指向addressC這個地址即節點C，如下圖S節點的藍線 s->next = p;　　　　　 // p是addressD，將它賦給s->next，s->next中的值為addressD，也即s->next指向了D，如下圖S節點的紅線 p->prior->next = s;　　// p->prior 是addressC，即節點C，所以p->prior->next相當於沒拔出S之前的addressD，拔出S後，將S的首地址即addressS賦給這個地位，所以此時，由C 到D的紅線斷裂，這個紅線目的變成了S，如下圖C節點的紅線 p->prior = s;　　　　　// 同理，p->prior也指向了S，即p->prior中addressC變成了addressS, D指向C的藍線斷裂。變成如下圖D節點指向S節點的藍線.

以上這篇C++ 雙鏈表的根本操作(詳解)就是分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持。