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

首頁(yè) > 編程 > C++ > 正文

關(guān)于雙向鏈表的增刪改查和排序的C++實(shí)現(xiàn)

2020-05-23 13:57:45
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個(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)鏈表

由于雙向鏈表可以方便地實(shí)現(xiàn)正序和逆序兩個(gè)方向的插入、查找等功能,在很多算法中經(jīng)常被使用,

這里用C++構(gòu)造了一個(gè)雙向鏈表,提供了對(duì)雙向鏈表的插入、查找、刪除節(jié)點(diǎn)、排序等功能,其中排序提供了插入排序和冒泡排序兩種方式

#include<iostream>using namespace std;class Node     //組成雙向鏈表的節(jié)點(diǎn){public:  int data;  Node * pNext;  Node * pLast;};class List   //構(gòu)造一個(gè)雙向鏈表{private:  Node * pHead;  Node * pTail;  int length;public:  List(int length)    //創(chuàng)建雙向鏈表  {    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)    //修改鏈表中指定位置的節(jié)點(diǎn)  {    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)    //插入數(shù)據(jù)  {    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)   //刪除指定位置的節(jié)點(diǎn)  {    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)      //查找指定位置的節(jié)點(diǎn)  {    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;}

以上這篇關(guān)于雙向鏈表的增刪改查和排序的C++實(shí)現(xiàn)就是小編分享給大家的全部?jī)?nèi)容了,希望能給大家一個(gè)參考,也希望大家多多支持VEVB武林網(wǎng)。


發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 吉林省| 夏津县| 蓝田县| 文山县| 如东县| 讷河市| 泽州县| 河池市| 稷山县| 济源市| 厦门市| 建昌县| 汨罗市| 信宜市| 永宁县| 通江县| 鄂温| 山阴县| 康保县| 常熟市| 平南县| 资源县| 云浮市| 璧山县| 临桂县| 通城县| 门头沟区| 涞水县| 沅陵县| 高青县| 保德县| 克拉玛依市| 阿拉善右旗| 利辛县| 临邑县| 通江县| 康定县| 甘谷县| 凉山| 武平县| 名山县|