关于双向链表的增删改查和排序的C++实现
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
由于双向链表可以方便地实现正序和逆序两个方向的插入、查找等功能，在很多算法中经常被使用，
这里用C＋＋构造了一个双向链表，提供了对双向链表的插入、查找、删除节点、排序等功能，其中排序提供了插入排序和冒泡排序两种方式
#include<iostream>
usingnamespacestd;
classNode//组成双向链表的节点
{
public:
intdata;
Node*pNext;
Node*pLast;
};
classList//构造一个双向链表
{
private:
Node*pHead;
Node*pTail;
intlength;
public:
List(intlength)//创建双向链表
{
this->length=length;
pHead=newNode();
pHead->pLast=NULL;
pTail=pHead;
for(inti=0;i<length;i++)
{
Node*temp=newNode();
cout<<"pleaseentertheno"<<i+1<<"Node'sdata:";
cin>>temp->data;
temp->pNext=NULL;
temp->pLast=pTail;
pTail->pNext=temp;
pTail=temp;
}
}
voidtraverseList()//正向遍历
{
Node*p=pHead->pNext;
while(p!=NULL)
{
cout<<p->data<<endl;
p=p->pNext;
}
}
voidtraverseListReturn()//逆向遍历
{
Node*p=pTail;
while(p->pLast!=NULL)
{
cout<<p->data<<endl;
p=p->pLast;
}
}
voidsortList()//冒泡排序
{
Node*p=newNode();
Node*q=newNode();
inttemp;
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;
}
}
}
}
voidsortListByInsertWay()//插入排序
{
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;
}
voidchangeList(intnum,intposition)//修改链表中指定位置的节点
{
Node*p=pHead->pNext;
if(position>length||position<=0)
{
cout<<"overstack!"<<endl;
return;
}
for(inti=0;i<position-1;i++)
{
p=p->pNext;
}
p->data=num;
}
voidinsertList(intnum,intposition)//插入数据
{
Node*p=pHead->pNext;
if(position>length||position<=0)
{
cout<<"overstack!"<<endl;
return;
}
for(inti=0;i<position-1;i++)
{
p=p->pNext;
}
Node*temp=newNode();
temp->data=num;
temp->pNext=p;
temp->pLast=p->pLast;
p->pLast->pNext=temp;
p->pLast=temp;
length++;
}
voidclearList()//清空
{
Node*q;
Node*p=pHead->pNext;
while(p!=NULL)
{
q=p;
p=p->pNext;
deleteq;
}
p=NULL;
q=NULL;
}
voiddeleteList(intposition)//删除指定位置的节点
{
Node*p=pHead->pNext;
if(position>length||position<=0)
{
cout<<"overstack!"<<endl;
return;
}
for(inti=0;i<position-1;i++)
{
p=p->pNext;
}
p->pLast->pNext=p->pNext;
p->pNext->pLast=p->pLast;
deletep;
length--;
}
intgetItemInList(intposition)//查找指定位置的节点
{
Node*p=pHead->pNext;
if(position>length||position<=0)
{
cout<<"overstack!"<<endl;
return0;
}
for(inti=0;i<position-1;i++)
{
p=p->pNext;
}
returnp->data;
}
~List()
{
Node*q;
Node*p=pHead->pNext;
while(p!=NULL)
{
q=p;
p=p->pNext;
deleteq;
}
p=NULL;
q=NULL;
}
};
intmain()
{
Listl(3);
l.traverseList();
cout<<"AFTERSORT------------------------------------------------------"<<endl;
//l.sortList();//冒泡排序
l.sortListByInsertWay();//插入排序
l.traverseList();
cout<<"AFTERINSERT-----------------------------------------------------"<<endl;
l.insertList(55,1);
l.traverseList();
cout<<"AFTERDELETE-----------------------------------------------------"<<endl;
l.deleteList(1);
l.traverseList();
cout<<"ReturnTraverse---------------------------------------------"<<endl;
l.traverseListReturn();
cout<<"FindtheSecondNode'sdata:"<<l.getItemInList(2)<<endl;
return0;
}
以上这篇关于双向链表的增删改查和排序的C++实现就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。