国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C++ > 正文

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

2020-05-23 13:57:48
字體:
來源:轉載
供稿:網友

1.概念

雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數據結點中都有兩個指針,分別指向直接后繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

結構圖如下所示:

  C++,雙鏈表操作

  C++,雙鏈表操作

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

  C++,雙鏈表操作

圖中假設了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賦給這個位置,所以此時,由CD的紅線斷裂,這個紅線目標變成了S,如下圖C節點的紅線
p->prior = s;     // 同理,p->prior也指向了S,即p->prior中addressC變成了addressS, D指向C的藍線斷裂。變成如下圖D節點指向S節點的藍線.

C++,雙鏈表操作

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


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 渭源县| 睢宁县| 且末县| 阳原县| 南召县| 武鸣县| 济宁市| 开阳县| 依兰县| 阳西县| 兴仁县| 府谷县| 洞头县| 融水| 临桂县| 绥化市| 卓资县| 新竹县| 防城港市| 龙川县| 福海县| 奈曼旗| 谷城县| 井研县| 洛川县| 环江| 平陆县| 崇义县| 曲阜市| 鞍山市| 襄汾县| 天镇县| 姚安县| 武宁县| 洮南市| 湖南省| 石河子市| 新昌县| 封丘县| 临颍县| 广东省|