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

2020-01-26 14:21:49

字體：大中小

來源：轉載

供稿：網友

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 oncetypedef 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