雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。

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

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

#include<iostream> using namespace std;class Node //組成雙向鏈表的節(jié)點 { public:int data;Node * pNext;Node * pLast; };class List //構(gòu)造一個雙向鏈表 { 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é)點{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()　　　　　　//清空{(diào)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é)點{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é)點{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; }

總結(jié)

以上是生活随笔為你收集整理的基于双向链表的增删改查和排序（C++实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。