关于双向链表的增删改查和排序的C++实现
更新时间:2020年4月25日 17:33 点击:2077
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
由于双向链表可以方便地实现正序和逆序两个方向的插入、查找等功能,在很多算法中经常被使用,
这里用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++实现就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
下一篇: 原码, 反码与补码基础知识详细介绍
相关文章
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- c# n个数排序实现代...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要为大家详细介绍了JavaScript数据结构之双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-03-07
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
- 这篇文章主要介绍了C#使用linq对数组进行筛选排序的方法,实例分析了C#实用linq扩展进行数组排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 冒泡排序即是对数组每次轮循出最大数或最小数放在队尾,这里我们来看一下C#实现冒泡排序算法的代码示例,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了jQuery实现对无序列表的排序功能,涉及jQuery与javascript常见的文本操作函数与sort排序函数的相关使用方法,具有一定参考借鉴价值,需要的朋友可以参考下...2016-07-01
- 但是,我们在使用中就会发现问题,这里的数组排序方法并不是按照我们想像中的数字大小来排序的,而是按照字符串测试结果改变原先的数据。这并不是我们想要的。那么如何才可以得到我们想要的按照我们思维中的数字大小来排序...2014-05-31
- 这篇文章主要介绍了C++ 字符串去重排序实例代码的相关资料,需要的朋友可以参考下...2020-04-25
Redis快速表、压缩表和双向链表(重点介绍quicklist)
这篇文章主要介绍了Redis快速表、压缩表和双向链表(重点介绍quicklist),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-06- 排序是我们在日常开发中经常遇到的一个功能,下面这篇文章主要给大家介绍了利用JavaScript对中文(汉字)进行排序的相关资料,文中通过示例代码介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面跟着小编一起来看看吧。...2017-06-24
- 这篇文章主要介绍了C++ STL关联式容器自定义排序规则的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-04
- 这篇文章主要介绍了 C语言开发之归并排序详解及实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25