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

2020-01-26 14:21:49

字體：大中小

供稿：網(wǎng)友

1.概念

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問(wè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;    }  }}//求鏈表長(zhǎng)度int DoubleList::GetDouListLength(pDoubleListNode &head){  int length = 0;  if (head == NULL)  {    printf("鏈表不存在，請(qǐng)先初始化!/n");  }  else  {    pDoubleListNode p = head->next;    while (p)    {      length++;      p = p->next;    }  }  return length;}//判斷鏈表是否為空bool DoubleList::IsDouListEmpty(pDoubleListNode &head){  if (head == NULL)  {    printf("鏈表不存在，請(qǐng)先初始化!/n");    return true;  }  else if (head->next == NULL)  {    printf("鏈表為空!/n");    return true;  }    return false;}//把雙向鏈表置空void DoubleList::ClearDouList(pDoubleListNode &head){  if (head == NULL)  {    printf("鏈表不存在，請(qǐng)先初始化!/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("請(qǐng)輸入要插入的元素和位置:/n");  scanf_s("%d%d", &data, &pos, 100);  if (head == NULL)  {    printf("鏈表不存在，請(qǐng)先初始化!/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("請(qǐng)輸入要插入的元素和位置:/n");  scanf_s("%d%d", &data, &pos, 100);  if (head == NULL)  {    printf("鏈表不存在，請(qǐng)先初始化!/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("請(qǐng)輸入要?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 oncetypedef 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);  //求鏈表長(zhǎng)度  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.對(duì)鏈表插入節(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));　　// 申請(qǐng)一段內(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)線.