C++双向链表

求一个双向链表的示例代码

补充：少说了，是双循环链表

答案：#include <iostream>
using namespace std;
struct Data 
{
 Data()
 {
  no=0;
 }
 Data(int _no)
 {
  no=_no;
 }
 friend ostream & operator << (ostream & os,const Data & d){
  os<<d.no;
  return os;
 }
 int no;
};
struct Node
{
 Node()
 {
  pNext=NULL;
  prior=NULL;
 }
 Data data;
 Node *pNext;
 Node *prior;
 
};
struct Link
{
 Link()
 {
  pHead=NULL;
 }
 bool insert(const Data & data)
 {
  if (pHead==NULL)
  {
   pHead=new Node;
   pHead->data=data;
   pHead->pNext=pHead;
   pHead->prior=pHead;
   return true;
  }
  if (pHead->data.no>data.no)
  {
   Node *pNew=new Node;
   pNew->data=data;
   pNew->prior=pHead->prior;
   pHead->prior->pNext=pNew;
   pHead->prior=pNew;
   pNew->pNext=pHead;
   pHead=pNew;
   return true;
  }
  Node *p=pHead;
  do
  {
   if (p->data.no<data.no&&p->pNext==pHead)
   {
    Node *pNew=new Node;
    pNew->data=data;
    pNew->pNext=p->pNext;
    pNew->prior=p;
    p->pNext=pNew;
    pHead->prior=pNew;
    return true;
   }else
    if(p->data.no<data.no&&p->pNext->data.no>data.no)
    {
     Node *pNew = new Node;
     pNew->data=data;
     pNew->pNext=p->pNext;
     pNew->prior=p;
     p->pNext->prior=pNew;
     p->pNext->prior=pNew;
     p->pNext=pNew;
     return true;
    }
   p=p->pNext;
  }while(p!=pHead);
  return false;
 }
 void print()
 {
  Node *p=pHead;
  do 
  {
   cout<<p->data<<endl;
   p=p->pNext;
  } while (p!=pHead);
 }
 Node *pHead;
};
void main()
{
 Link link;
 link.insert(Data(7));
 link.insert(Data(6));
 link.insert(Data(2));
 link.insert(Data(4));
 link.insert(Data(3));
 link.insert(Data(0));
 link.print();
 system("pause");
}emplate ＜class Type＞ class newtype
{
public:
Type data;
Node＜newtype＞ *link;
} 
　　当你派生双向链表时，这样写template ＜calss Type＞ class DblList : public List＜newtype＜Type＞ ＞，注意连续的两个"＞"之间要有空格。或者根本不定义这样的结构，直接拿Node类型来做，例如我下面给出的。但是，请注意要完成"=="的重载，否则，你又要重写Find函数，并且其他的某些操作也不方便。
　　在开始完成你的从单链表派生出来的双向链表之前，要在单链表这个基类中添加修改当前指针和当前前驱指针的接口，如下所示：
protected:
void Put(Node＜Type＞ *p)//尽量不用，双向链表将使用这个完成向前移动
{
current = p;
}
void PutPrior(Node＜Type＞ *p)//尽量不用，原因同上
{
prior = p;
} 
　　因为这个接口很危险，而且几乎用不到，所以我在前面并没有给出，但要完成双向链表最"杰出"的优点--向前移动当前指针，必须要使用。另外说的是，我从前也从来没计划从单链表派生双链表，下面你将看到，这个过程很让人烦人，甚至不如重写一个来的省事，执行效率也不是很好，这种费力不讨好的事做它有什么意思呢？的确，我也觉得我在钻牛角尖。
　　定义和实现
#ifndef DblList_H
#define DblList_H
#include "List.h"
template ＜class Type＞ class DblList : public List＜ Node＜Type＞ ＞
{
public:
Type *Get()
{
if (pGet() != NULL) return &pGet()-＞data.data;
else return NULL;
}
Type *Next()
{
pNext();
return Get();
}
Type *Prior()
{
if (pGetPrior != NULL)
{
Put(pGetPrior());
PutPrior( (Node＜ Node＜Type＞ ＞*)pGet()-＞data.link);
return Get();
}
return NULL;
}
void Insert(const Type &value)
{
Node＜Type＞ newdata(value, (Node＜Type＞*)pGet());
List＜ Node＜Type＞ ＞::Insert(newdata);
if (pGetNext()-＞link != NULL) 
pGetNext()-＞link-＞data.link = (Node＜Type＞*)pGetNext();
}
BOOL Remove()
{
if (List＜ Node＜Type＞ ＞::Remove())
{
pGet()-＞data.link = (Node＜Type＞*)pGetPrior();
return TURE;
}
return FALSE;
}
};
#endif 
　　【说明】只完成了最重要的Insert和Remove函数和最具特点的Prior()函数，其他的没有重新实现。所以，你在这里使用单链表的其他方法，我不保证一定正确。并且，这里的指针类型转换依赖于编译器实现，我也不能肯定其他的编译器编译出来也能正确。对于让不让Prior返回头节点的data，我考虑再三，反正用First();Get();这样的组合也能返回，所以就不在乎他了，所以要是用Prior遍历直到返回NULL，就会将头节点的data输出来了。
　　【补充】至于双向循环链表，也可以从这个双向链表派生（仿照派生循环链表的方法）；或者从循环链表派生（仿照派生双向链表的方法），就不一一举例了（再这样下去，我就真闹心的要易做图了）。至此，可以得出一个结论，链表的各种结构都是能从单链表派生出来的。换句话说，单链表是根本所在，如果研究透了单链表，各种链式结构都不难。
　　一小段测试程序
void DblListTest_int()
{
DblList＜int＞ a;
for (int i = 10; i ＞ 1; i--) a.Insert(i);
for (i = 10; i ＞ 1; i--) cout ＜＜ *a.Next() ＜＜ " ";
a.First();
cout ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
cout ＜＜ *a.Next() ＜＜ endl;
a.Remove();
cout ＜＜ *a.Get() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
cout ＜＜ *a.Prior() ＜＜ endl;
} 
 
参考链接： http://blog.csdn.net/fisher_jiang/archive/2006/03/19/629353.aspx
 

上一个：求教C++程序入门
下一个：C++是什么？