快捷導(dǎo)航

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

更新時(shí)間：2016年12月18日 12:40:39 投稿：jingxian

下面小編就為大家?guī)硪黄狢++ 雙鏈表的基本操作(詳解)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

1.概念

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。

結(jié)構(gòu)圖如下所示：

2.基本操作實(shí)例

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é)點(diǎn)后插入節(jié)點(diǎn)
    InsertNodeAfter(pDouList);
    PrintDouList(pDouList);
    // 節(jié)點(diǎn)前插入節(jié)點(diǎn)
    InsertNodeBefore(pDouList);
    PrintDouList(pDouList);
    // 刪除節(jié)點(diǎn)
    DeleteNode(pDouList);
    PrintDouList(pDouList);
    // 刪除鏈表
    DeleteDouList(pDouList);
    PrintDouList(pDouList);
    system("PAUSE");
}
DoubleList::~DoubleList()
{
}
//創(chuàng)建雙向鏈表
void DoubleList::CreateDouList(pDoubleListNode &head)
{
  char x;     // 定義成char型是用于輸入'q'時(shí)可以退出，其實(shí)定義成int也能退出
  pDoubleListNode p, s;
  head = (pDoubleListNode)malloc(sizeof(DoubleListNode));
  head->next = NULL;
  head->prior = NULL;    // 構(gòu)造頭結(jié)點(diǎn)p
  p = head;
  printf("\n輸入雙向鏈表的元素，每輸入一個(gè)元素后按回車，輸入q表示結(jié)束.\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("雙向鏈表構(gòu)造完畢!\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指向第一個(gè)元素
    head->next = NULL;
    while (p)     //逐個(gè)釋放元素所占內(nèi)存
    {
      p = p->next;
      free(q);
      q = p;
    }
  }
}
// 刪除雙向鏈表
void DoubleList::DeleteDouList(pDoubleListNode &head)
{
  printf("\n刪除雙向鏈表\n");
  ClearDouList(head);
  free(head);
  head = NULL;
}
// 在雙向鏈表中第i個(gè)位置后面插入元素
void DoubleList::InsertNodeAfter(pDoubleListNode &head)
{
  int data, pos;
  pDoubleListNode p, s;
  p = head;
  int i = 0;
  printf("\n在雙向鏈表中第i個(gè)位置后面插入元素\n");
  printf("請輸入要插入的元素和位置:\n");
  scanf_s("%d%d", &data, &pos, 100);
  if (head == NULL)
  {
    printf("鏈表不存在，請先初始化!\n");
  }
  else if (head->next == NULL)
  {
    printf("鏈表為空，插入第一個(gè)元素!\n");
    s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
    s->data = data;
    s->prior = NULL;  
    s->next = NULL;
    head->next = s;    // 將新結(jié)點(diǎn)插入head后 
  }
  else if (pos<1 || pos>GetDouListLength(head) + 1)
  {
    printf("插入位置錯(cuò)誤!\n");
  }
  else
  {
    while (i < pos)
    {
      p = p->next;
      i++;
    }
    if (i == GetDouListLength(head))   //如果在最后一個(gè)元素后面插入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個(gè)位置前面插入元素
void DoubleList::InsertNodeBefore(pDoubleListNode &head)
{
  int data, pos;
  pDoubleListNode p, s;
  p = head;
  int i = 0;
  printf("\n在雙向鏈表中第i個(gè)位置前面插入元素\n");
  printf("請輸入要插入的元素和位置:\n");
  scanf_s("%d%d", &data, &pos, 100);
  if (head == NULL)
  {
    printf("鏈表不存在，請先初始化!\n");
  }
  else if (head->next == NULL)
  {
    printf("鏈表為空，插入第一個(gè)元素!\n");
    s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
    s->data = data;
    s->prior = NULL;
    s->next = NULL;
    head->next = s;    // 將新結(jié)點(diǎn)插入head后 
  }
  else if (pos<1 || pos>GetDouListLength(head) + 1)
  {
    printf("插入位置錯(cuò)誤!\n");
  }
  else
  {
    while (i < pos)
    {
      p = p->next;
      i++;
    }
    if (i == 1)   // 如果在第一個(gè)元素前面插入data
    {
      s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
      s->data = data;
      head->next = s;    // 將新結(jié)點(diǎn)插入head后 
      s->prior = head;    // 新結(jié)點(diǎn)的前結(jié)點(diǎn)指向頭結(jié)點(diǎn) 
      s->next = p;            // 新結(jié)點(diǎn)的后結(jié)點(diǎn)指向原h(huán)ead的后結(jié)點(diǎn) 
      p->prior = s ;          // 原第一個(gè)結(jié)點(diǎn)的前結(jié)點(diǎn)指向新結(jié)點(diǎn) 
    }
    else
    {
      s = (pDoubleListNode)malloc(sizeof(DoubleListNode));
      s->data = data;
      s->prior = p->prior;
      s->next = p;
      p->prior->next = s;
      p->prior = s;
    }
  }
}
//刪除雙向鏈表中的第i個(gè)元素
void DoubleList::DeleteNode(pDoubleListNode &head)
{
  int pos;
  int i = 0;
  pDoubleListNode p = head;
  printf("\n在雙向鏈表中刪除第i個(gè)位置的元素\n");
  printf("請輸入要?jiǎng)h除的位置:");
  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; //前驅(qū)
  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個(gè)位置后面插入元素m
  void DoubleList::InsertNodeAfter(pDoubleListNode &head);
  // 在雙向鏈表中第i個(gè)位置前面插入元素
  void DoubleList::InsertNodeBefore(pDoubleListNode &head);
  //刪除雙向鏈表中的第i個(gè)元素
  void DoubleList::DeleteNode(pDoubleListNode &head);
};

3.對鏈表插入節(jié)點(diǎn)的理解

例如在節(jié)點(diǎn)i前插入一個(gè)新的節(jié)點(diǎn)(即上面代碼中的InsertNodeBefore函數(shù)):

鏈表結(jié)構(gòu)體為：

typedef struct DoubleListNode
{
  int data;       // 數(shù)據(jù)
  struct DoubleListNode *prior; // 前驅(qū)
  struct DoubleListNode *next; // 后繼
}DoubleListNode, *pDoubleListNode;

假設(shè)該鏈表由五個(gè)節(jié)點(diǎn)構(gòu)成,分別為A,B,C,D,E

圖中假設(shè)了A,B,C,D,E的地址分別為:addressA,addressB,addressC,addressD,addressE。

下面將分析鏈表的前插的例子:

雙鏈表的前插，下面這是在節(jié)點(diǎn)"D"前插入一個(gè)新的節(jié)點(diǎn)"S"的代碼和分析

s = (pDoubleListNode)malloc(sizeof(DoubleListNode));　　// 申請一段內(nèi)存空間，指針指向首地址為addressS

s->data = data;　　　　 // 給節(jié)點(diǎn)S的數(shù)據(jù)賦值data

s->prior = p->prior;　　// p指向D節(jié)點(diǎn), p->prior表示addressC，將它賦給s->prior,則s->prior里面的值是addressC，從而指向addressC這個(gè)地址即節(jié)點(diǎn)C，如下圖S節(jié)點(diǎn)的藍(lán)線

s->next = p;　　　　　 // p是addressD，將它賦給s->next，s->next中的值為addressD，也即s->next指向了D，如下圖S節(jié)點(diǎn)的紅線

p->prior->next = s;　　// p->prior 是addressC，即節(jié)點(diǎn)C，所以p->prior->next相當(dāng)于沒插入S之前的addressD，插入S后，將S的首地址即addressS賦給這個(gè)位置，所以此時(shí)，由C 到D的紅線斷裂，這個(gè)紅線目標(biāo)變成了S，如下圖C節(jié)點(diǎn)的紅線

p->prior = s;　　　　　// 同理，p->prior也指向了S，即p->prior中addressC變成了addressS, D指向C的藍(lán)線斷裂。變成如下圖D節(jié)點(diǎn)指向S節(jié)點(diǎn)的藍(lán)線.