用C++实现双向链表

#include "StdAfx.h" #include "LList.h" CLList::CLList(void) { phead=NULL; ptail=NULL; NumberOfNode=0; } CLList::~CLList(void) { } void CLList::InsertNode(int InsertItem) { CNode* NewNode=new CNode; NewNode->Item=InsertItem; if (GetNumberOfNode()==0)//链表还没有创建 { phead=ptail=NewNode; NewNode->prenode=NULL; NewNode->nextnode=NULL; SetNumberOfNode(1); return; } if (GetNumberOfNode()==1) { if (InsertItem<=phead->Item)//该元素应该插入到链表首 { NewNode->nextnode=phead; NewNode->prenode=NULL; phead->prenode=NewNode; phead=phead->prenode; } else//该元素应该插入到链表末 { NewNode->nextnode=NULL; NewNode->prenode=ptail; ptail->nextnode=NewNode; ptail=ptail->nextnode; } SetNumberOfNode(GetNumberOfNode()+1); return; } //链表中至少有两个元素的情况 CNode* ptemp;//用于记录当前的指针位置 ptemp=phead;//初始化为链表头 while (ptemp!=ptail) { if (InsertItem<=ptemp->Item) { if (ptemp==phead)//插入链表头 { NewNode->nextnode=phead; NewNode->prenode=NULL; phead->prenode=NewNode; phead=phead->prenode; } else//插入链表中间 { NewNode->nextnode=ptemp; NewNode->prenode=ptemp->prenode; ptemp->prenode->nextnode=NewNode; ptemp->prenode=NewNode; } break; } ptemp=ptemp->nextnode; } if (ptemp==ptail) { if (InsertItem<=ptemp->Item)//插入最后一个元素之前 { NewNode->nextnode=ptemp; NewNode->prenode=ptemp->prenode; ptemp->prenode->nextnode=NewNode; ptemp->prenode=NewNode; } else//插入链表末 { NewNode->nextnode=NULL; NewNode->prenode=ptail; ptail->nextnode=NewNode; ptail=ptail->nextnode; } } SetNumberOfNode(GetNumberOfNode()+1); NewNode=NULL; return; } void CLList::DeleteNode(int DeleteItem) { if (GetNumberOfNode()==0) { cout<<"链表中没有元素!"<<endl; getchar(); return; } CNode* ptemp=phead; while(ptemp!=ptail) { if (ptemp->Item==DeleteItem) { if (ptemp==phead)//删除头节点 { phead=phead->nextnode; phead->nextnode->prenode=NULL; ptemp->nextnode=NULL; free(ptemp); ptemp=NULL; } else//删除中间节点 { ptemp->prenode->nextnode=ptemp->nextnode; ptemp->nextnode->prenode=ptemp->prenode; ptemp->prenode=NULL; ptemp->nextnode=NULL; free(ptemp); ptemp=NULL; } SetNumberOfNode(GetNumberOfNode()-1); break; } ptemp=ptemp->nextnode; } if (ptemp==ptail) { if (ptemp->Item==DeleteItem)//删除末节点 { ptemp->prenode->nextnode=NULL; ptail=ptemp->prenode; ptemp->prenode=NULL; free(ptemp); ptemp=NULL; SetNumberOfNode(GetNumberOfNode()-1); } else { cout<<"您要删除的元素不存在!!"<<endl; getchar(); } } return; } void CLList::ShowList() { if (GetNumberOfNode()==0) { cout<<"链表为空！！"<<endl; getchar(); return; } CNode* ptemp=phead; while(ptemp!=ptail) { cout<<ptemp->Item<<" "; ptemp=ptemp->nextnode; } cout<<ptemp->Item<<endl; cout<<"链表中共有"<<GetNumberOfNode()<<"个元素！"<<endl; }