關於雙向鏈表的增刪改查和排序的C++完成

關於雙向鏈表的增刪改查和排序的C++完成。本站提示廣大學習愛好者：（關於雙向鏈表的增刪改查和排序的C++完成）文章只能為提供參考，不一定能成為您想要的結果。以下是關於雙向鏈表的增刪改查和排序的C++完成正文

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

由於雙向鏈表可以方便地完成正序和逆序兩個方向的拔出、查找等功用，在很多算法中常常被運用，

這裡用C＋＋結構了一個雙向鏈表，提供了對雙向鏈表的拔出、查找、刪除節點、排序等功用，其中排序提供了拔出排序和冒泡排序兩種方式

#include<iostream>

using namespace std;

class Node     //組成雙向鏈表的節點
{
public:
  int data;
  Node * pNext;
  Node * pLast;
};

class List   //結構一個雙向鏈表
{
private:
  Node * pHead;
  Node * pTail;
  int length;
public:
  List(int length)　　　　//創立雙向鏈表
  {
    this->length=length;
    pHead=new Node();
    pHead->pLast=NULL;
    pTail=pHead;
    for(int i=0;i<length;i++)
    {
      Node * temp=new Node();
      cout<<"please enter the no"<<i+1<<" Node's data:";
      cin>>temp->data;
      temp->pNext=NULL;
      temp->pLast=pTail;
      pTail->pNext=temp;
      pTail=temp;
    }
  }
  
  void traverseList()　　　　//正向遍歷
  {
    Node * p=pHead->pNext;
    while(p!=NULL)
    {
      cout<<p->data<<endl;
      p=p->pNext;
    }
  }
  
  void traverseListReturn()　　　　//逆向遍歷
  {
    Node * p=pTail;
    while(p->pLast!=NULL)
    {
      cout<<p->data<<endl;
      p=p->pLast;
    }
  }
  
  void sortList()   //冒泡排序
  {
    Node * p=new Node();
    Node * q=new Node();
    int temp;
    for(p=pHead->pNext;p->pNext!=NULL;p=p->pNext)
    {
      for(q=p->pNext;q!=NULL;q=q->pNext)
      {
        if(q->data<p->data)
        {
          temp=q->data;
          q->data=p->data;
          p->data=temp;
        }
      }
    }
  }
  
  void sortListByInsertWay()    //拔出排序
  {
    if(pHead->pNext==NULL||pHead->pNext->pNext==NULL)
    {
      return;
    }
    Node * p2=pHead->pNext->pNext;
    Node * p1=pHead;
    pHead->pNext->pNext=NULL;
    while(p2)
    {
      Node * pN=p2->pNext;
      while(p1->pNext)
      {
        if(p2->data<p1->pNext->data)
        {
          p2->pNext=p1->pNext;
          p2->pLast=p1;
          p1->pNext->pLast=p2;
          p1->pNext=p2;
          break;
        }
        p1=p1->pNext;
      }
      if(p1->pNext==NULL)
      {
        p2->pNext=NULL;
        p2->pLast=p1;
        p1->pNext=p2;
      }
      p2=pN;
    }
    
    //重新查找pTail的地位
    Node * pt=pHead;
    while(pt->pNext)
    {
      pt=pt->pNext;
    }
    pTail=pt;
  }
  
  void changeList(int num,int position)　　　　//修正鏈表中指定地位的節點
  {
    Node * p=pHead->pNext;
    if(position>length||position<=0)
    {
      cout<<"over stack !"<<endl;
      return;
    }
    for(int i=0;i<position-1;i++)
    {
      p=p->pNext;
    }
    p->data=num;
  }
  
  void insertList(int num,int position)　　　　//拔出數據
  {
    Node * p=pHead->pNext;
    if(position>length||position<=0)
    {
      cout<<"over stack !"<<endl;
      return;
    }
    for(int i=0;i<position-1;i++)
    {
      p=p->pNext;
    }
    Node * temp=new Node();
    temp->data=num;
    temp->pNext=p;
    temp->pLast=p->pLast;
    p->pLast->pNext=temp;
    p->pLast=temp;
    length++;
  }
  
  void clearList()　　　　　　//清空
  {
    Node * q;
    Node * p=pHead->pNext;
    while(p!=NULL)
    {
      q=p;
      p=p->pNext;
      delete q;
    }
    p=NULL;
    q=NULL;
  }
  
  void deleteList(int position)　　　//刪除指定地位的節點
  {
    Node * p=pHead->pNext;
    if(position>length||position<=0)
    {
      cout<<"over stack !"<<endl;
      return;
    }
    for(int i=0;i<position-1;i++)
    {
      p=p->pNext;
    }
    p->pLast->pNext=p->pNext;
    p->pNext->pLast=p->pLast;
    delete p;
    length--;
  }
  
  int getItemInList(int position)　　　　　　//查找指定地位的節點
  {
    Node * p=pHead->pNext;
    if(position>length||position<=0)
    {
      cout<<"over stack !"<<endl;
      return 0;
    }
    for(int i=0;i<position-1;i++)
    {
      p=p->pNext;
    }
    return p->data;
  }
  
  ~List()
  {
    Node * q;
    Node * p=pHead->pNext;
    while(p!=NULL)
    {
      q=p;
      p=p->pNext;
      delete q;
    }
    p=NULL;
    q=NULL;
  }
  
};

int main()
{
  List l(3);
  l.traverseList();
  cout<<"AFTER SORT------------------------------------------------------"<<endl;
//  l.sortList();       //冒泡排序
  l.sortListByInsertWay();  //拔出排序
  l.traverseList();
  cout<<"AFTER INSERT-----------------------------------------------------"<<endl;
  l.insertList(55,1);
  l.traverseList();
  cout<<"AFTER DELETE-----------------------------------------------------"<<endl;
  l.deleteList(1);
  l.traverseList();
  cout<<"Return Traverse---------------------------------------------"<<endl;
  l.traverseListReturn();
  cout<<"Find the Second Node's data:"<<l.getItemInList(2)<<endl;
  return 0;
}

以上這篇關於雙向鏈表的增刪改查和排序的C++完成就是分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持。