余姚崇文书院官网:做一个双向连接表

给你提供两个版本的实现，是我过去写的，前一个是结构化的链表，后一个是C++的List模板实现的，用了容器Iterator访问元素，实现了STL里的list的部分功能，界面也尽量和STL里的那个保持一致。希望对你有帮助。^_^
注意我写了我的平台信息，你的平台有不同的话可能要稍微做点小更改~
还有在第一个程序里的节点名字用错了，应该是prev和next的，我写成了了left和right了，不过你清楚就行，不影响运行的。

示例1：
//*************************************************************************************************

// 问题描述：本程序还提供暸别的一般链表的功能；

//备注： 没有加入Delete！
//作者： KimiaZhu

//*************************************************************************************************

#include <iostream>
#include <string>

using namespace std;

struct Tnode
{
string word;
int count;
Tnode *left;
Tnode *right;
};

struct Tnode * HeadNode; //头节点
struct Tnode * TailNode; //尾节点
struct Tnode * InternalNode; //当前节点

void Clear(); //清屏
bool CreatList(); //生成链表
bool DeleteAll(); //删除所有节点
bool DeleteOne(); //删除当前节点
void Error(int); //错误类型捕捉
void InsertNode(string); //插入新节点
void PrintAll(); //显示所有内容
int ShowMenu(); //显示选项菜单
void Sort(); //排序
void Swamp(struct Tnode *,struct Tnode *); //交换两节点

enum ERROR_TYPE{EMPTY = 1, NO_SOURCE, UNKNOW};

//*************************************************************************************************

int main()
{
try{
bool quit = false;
if(CreatList() == true)
{
while(quit == false)
{
int command = 0;
command = ShowMenu();
switch(command)
{
case 1:
cout << "请输入单词，输入"<<"quit"<<"结束输入，返囬上一层菜单:" << endl;
while(1)
{
string str;
string quit = "quit";
cin >> str;
if(str != quit)
InsertNode(str);
else
break;
}
break;
case 2:
Sort();
break;
case 3:
PrintAll();
break;
case 4:
DeleteOne();
break;
case 5:
DeleteAll();
break;
case 6:
Clear();
break;
default:
quit = true;
break;
}
}
}
else
Error(NO_SOURCE);
return 0;
}
catch(...)
{
Error(UNKNOW);
}
}

//*************************************************************************************************

void Clear()
{
for(int line = 0; line < 50; line++)
cout << endl;
}
//*************************************************************************************************
bool DeleteAll()
{
string yesOrNo;
string no1 = "N";
string no2 = "n";
struct Tnode * DeleteNode;
DeleteNode = HeadNode -> right -> right;
if(HeadNode -> right == TailNode)
{
Error(EMPTY);
return false;
}
cout << "确认要删除整个链表？（Y/N）:";
cin >> yesOrNo;
if(yesOrNo == no1 || yesOrNo ==no2)
return false;
for(; DeleteNode -> right != NULL; DeleteNode = DeleteNode -> right)
{
delete DeleteNode -> left;
}
cout << "已经删除所有节点！" << endl;
return true;
}
//*************************************************************************************************
bool DeleteOne()
{
string yesOrNo;
string no1 = "N";
string no2 = "n";
struct Tnode * DeleteNode;
if(HeadNode -> right == TailNode)
{
Error(EMPTY);
return false;
}
cout << "确认要删除这个节点？（Y/N）:";
cin >> yesOrNo;
if(yesOrNo == no1 || yesOrNo ==no2)
return false;
DeleteNode = InternalNode;
InternalNode -> left -> right = InternalNode -> right;
InternalNode -> right -> left = InternalNode -> left;
delete InternalNode;
InternalNode = DeleteNode;
cout << "已经这个删除节点！";
return true;
}
//*************************************************************************************************
bool CreatList()
{
HeadNode = new Tnode[sizeof(struct Tnode)];
TailNode = new Tnode[sizeof(struct Tnode)];
HeadNode -> left = NULL;
HeadNode -> right = TailNode;
TailNode -> left = HeadNode;
TailNode -> right = NULL;

HeadNode -> count = 0;
HeadNode -> word = "HEAD";
TailNode -> count = 1;
TailNode -> word = "TAIL";

if(HeadNode != TailNode)
{
InternalNode = HeadNode;
return true;
}
else
return false;
}
//*************************************************************************************************
void Error(int error)
{
switch(error)
{
case EMPTY:
cout << "链表为空！" << endl;
break;
case NO_SOURCE:
cout << "没有足够系统资源创建链表！" << endl;
break;
case UNKNOW:
cout << "未知异常！将推出程序！" << endl;
break;
default:
cout << "未知异常！将推出程序！" << endl;
break;
}
}
//*************************************************************************************************
void InsertNode(string str)
{
struct Tnode * NewNode;
NewNode = new Tnode[sizeof(struct Tnode)];

NewNode -> right = TailNode;
NewNode -> left = InternalNode;
InternalNode -> right = NewNode;

NewNode -> count = (InternalNode -> count) + 1;
NewNode -> word = str;

InternalNode = NewNode;
}
//*************************************************************************************************
void PrintAll()
{
int counter = 0;
struct Tnode * PrintAllNode;

if(HeadNode -> right == TailNode)
{
Error(EMPTY);
return;
}

//cout << "********************************" << endl;
PrintAllNode = HeadNode -> right;
cout << "正在输出......";
for(; PrintAllNode -> right != NULL; PrintAllNode = PrintAllNode -> right)
{
cout << PrintAllNode -> word << " ";
}
cout << "输出完毕！";
cout << endl << "********************************" << endl;
}
//*************************************************************************************************
int ShowMenu()
{
int command = 0;
cout << "********************************" << endl;
//cout << "请选择一项序号：" << endl;
cout << "1.插入单词。" << endl;
cout << "2.排序。" << endl;
cout << "3.打印所有单词。" << endl;
cout << "4.删除上一个输入的单词。" << endl;
cout << "5.删除所有单词。" << endl;
cout << "6.清屏。" << endl;
cout << "0.退出程序。" << endl;
cout << "********************************" << endl;
cout << "请选择一项序号：";
cin >> command;
return command;
}
//*************************************************************************************************
/*bool DoCommand(int command)
{
switch(command)
{
case 1:
{
cout << "请输入单词并按囬车，当输入/"quit/"时结束输入:" << endl;
//string str;
//cin >> str;
}
case 2:
Sort();
default:
return true;
}
}*/
//*************************************************************************************************
void Sort()
{
if(HeadNode -> right == TailNode)
{
Error(EMPTY);
return;
}

struct Tnode * SortNodeDone;
struct Tnode * SortNodeOn;
SortNodeDone = HeadNode -> right;
SortNodeOn = SortNodeDone -> right;
cout << "正在排序......" << endl;
for(; SortNodeDone -> right != NULL; SortNodeDone = SortNodeDone -> right)
{
for(; SortNodeOn -> right != NULL; SortNodeOn = SortNodeOn -> right)
{
if((SortNodeDone -> word) > (SortNodeOn -> word))
Swamp(SortNodeDone, SortNodeOn);
}
}
}
//*************************************************************************************************
void Swamp(struct Tnode * ANode, struct Tnode * BNode)
{
ANode -> left -> right = BNode;
BNode -> right -> left = ANode;

BNode -> left = ANode -> left;
ANode -> right = BNode -> right;

ANode -> left = BNode;
BNode -> right = ANode;
//cout << "Swamp!" << endl;
}

示例2：
/**************************************************************************************************

问题描述： 写一个双链表与它的容器，用容器访问元素
调试平台： Windows Sever 2003 Enterprise Edition sp1 with .Net 2.0
编写环境： Visual Studio 2005 Team Edition
解决方案：
作者： KimiaZhu
完成日期： 2006-5-29
错误报告： KimiaZhu@sina.com

**************************************************************************************************/
#include <string>
#include <iostream>
#include <stdlib.h>
//**************** Incomplete declaration ****************

template <typename T> class List;
template <typename T> class ListNode;
template <typename T> class ListIterator;

//******************* Declare ListNode *******************

template <typename T>
class ListNode
{
private:
ListNode( const T& theElement = T(), ListNode* next = NULL, ListNode* prev = NULL)
: itsElement( theElement), itsNext ( next), itsPrevenient( prev)
{
}

T itsElement;
ListNode* itsPrevenient;
ListNode* itsNext;

friend class List<T>;
friend class ListIterator<T>;
};
//*************************************************************************************************
template <typename T>
class ListIterator
{
public:
ListIterator(void);
~ListIterator(void);
bool IsValid() const;
void Advance();
void Back();
T& Retrieve() const;

ListIterator<T> operator++();
ListIterator<T> operator++(int);
ListIterator<T> operator--();
ListIterator<T> operator--(int);
virtual T& operator*();
virtual bool operator==( const ListIterator<T>& rhs) const;
virtual bool operator!=( const ListIterator<T>& rhs) const;

class BadIterator{};
private:
ListNode<T>* itsCurrent;//返回所装的节点

ListIterator( ListNode<T>* theNode);//私有的构造函数
friend class List<T>;
};

template <typename T>
ListIterator<T>::ListIterator(void) : itsCurrent ( NULL)
{
}

template <typename T>
ListIterator<T>::~ListIterator(void)
{
}

template <typename T>
bool ListIterator<T>::IsValid() const //若当前节点在链表内则返回真，否则为假
{
if( itsCurrent -> itsNext != NULL || itsCurrent ->itsPrevenient != NULL)
return true;
else
return false;
//return itsCurrent -> itsNext != NULL;
}

template <typename T>
void ListIterator<T>::Advance()
{
if( IsValid())
itsCurrent = itsCurrent -> itsNext;
}

template <typename T>
void ListIterator<T>::Back()
{
if( IsValid())
itsCurrent = itsCurrent -> itsPrevenient;
}

template <typename T>
T& ListIterator<T>::Retrieve() const
{
if( !IsValid( )) throw BadIterator();
return itsCurrent -> itsElement;
}

template <typename T>
ListIterator<T>::ListIterator( ListNode<T>* theNode)
: itsCurrent ( theNode)
{
}

template <typename T>
ListIterator<T> ListIterator<T>::operator++()
{
if( !IsValid( )) throw BadIterator();
itsCurrent = itsCurrent -> itsNext;
return *this;
}

template <typename T>
ListIterator<T> ListIterator<T>::operator++( int)
{
ListIterator<T> tempIter = *this;
++( *this);
return tempIter;
}

template <typename T>
ListIterator<T> ListIterator<T>::operator--()
{
if( !IsValid( )) throw BadIterator();
itsCurrent = itsCurrent -> itsPrevenient;
return *this;
}

template <typename T>
ListIterator<T> ListIterator<T>::operator--( int)
{
ListIterator<T> tempIter = *this;
--( *this);
return tempIter;
}

template <typename T>
T& ListIterator<T>::operator*()
{
return Retrieve();
}

template <typename T>
bool ListIterator<T>::operator !=(const ListIterator<T>& rhs) const
{
return !( *this == rhs);
}

template <typename T>
bool ListIterator<T>::operator ==(const ListIterator<T>& rhs) const
{
return ( itsCurrent == rhs.itsCurrent);//***********
//return *this == rhs;
}
//*************************************************************************************************
template <typename T>
class List
{
public:
List();
List( const List& rhs);
virtual ~List();

virtual bool IsEmpty() const;
virtual void MakeEmpty();
//ListIterator<T> GetHeader() const;
virtual ListIterator<T> Begin() const;
virtual ListIterator<T> End() const;
virtual void Insert( const T& element, const ListIterator<T>& iter);//前端插入元素
//以下一句将element插入listElement前，若listElement在链表内返回插入成功则返回真，否则返回假
virtual bool Insert( const T& element, const T& listElement);
virtual ListIterator<T> Find( const T& element);
virtual void Remove( const T& element);
virtual void PushFront( const T& element);
virtual void PushBack( const T& element);

class ErrorMessage
{
public:
ErrorMessage(){};
ErrorMessage(string message){ itsMessage = message;}
string& GetErrorMessage() const{ return itsMessage;}
private:
string itsMessage;
};
private:
ListNode<T>* itsHead;
ListNode<T>* itsTail;
};

template <typename T>
List<T>::List()
{
itsHead = new ListNode<T>;
itsTail = new ListNode<T>;
itsHead -> itsNext = itsTail;
itsTail -> itsPrevenient = itsHead;
}

template <typename T>
List<T>::List(const List<T> &rhs)
{
itsHead = new ListNode<T>;
itsTail = new ListNode<T>;
itsHead -> itsNext = itsTail;
itsTail -> itsPrevenient = itsHead;
*this = rhs;
}

template <typename T>
List<T>::~List()
{
MakeEmpty();
delete itsHead;
delete itsTail;
}

template <typename T>
ListIterator<T> List<T>::Find(const T &element)
{
ListNode<T> * currentNode = itsHead -> itsNext;
while( /*currentNode != NULL && */currentNode -> itsElement != element)
{
if( currentNode == itsTail)
break;
currentNode = currentNode -> itsNext;
}
return ListIterator<T>( currentNode);
}

template <typename T>
ListIterator<T> List<T>::Begin() const
{
return ListIterator<T>( itsHead -> itsNext);
}

template <typename T>
ListIterator<T> List<T>::End() const
{
return ListIterator<T>( itsTail);
}

template <typename T>
void List<T>::Insert(const T &element, const ListIterator<T>& iter)
{
if( !iter.IsValid() || iter.itsCurrent == itsHead)//后半句条件相当于iter.itsCurrent-> itsPrevenient == NULL)
ErrorMessage("错误：意外的插入位置！");
ListNode<T>* tempNode = new ListNode<T>(element);
tempNode ->itsNext = iter.itsCurrent;
tempNode ->itsPrevenient = iter.itsCurrent -> itsPrevenient;
tempNode ->itsPrevenient ->itsNext = tempNode;
tempNode ->itsNext ->itsPrevenient = tempNode;
}

template <typename T>
bool List<T>::Insert(const T &element, const T& listElement)//************
{
ListNode<T>* currentNode = Find( listElement).itsCurrent;
ListIterator<T> tempIterator = ListIterator<T>( currentNode);
Insert( element, tempIterator);
return true;
}

template <typename T>
bool List<T>::IsEmpty() const
{
return itsHead -> itsNext == itsTail;
}

template <typename T>
void List<T>::MakeEmpty()
{
ListNode<T>* currentNode = itsHead;// -> itsNext;
while( currentNode->itsNext != itsTail)
{
Remove( currentNode -> itsNext -> itsElement);
}
}

template <typename T>
void List<T>::PushFront( const T& element)
{
//ListNode<T>* currentNode = itsHead;
ListIterator<T> iter = ListIterator<T>( itsHead -> itsNext);
Insert( element, iter);
}

template <typename T>
void List<T>::PushBack( const T& element)
{
//ListNode<T>* currentNode = itsTail -> itsPrevenient;
ListIterator<T> iter = ListIterator<T>( itsTail);
Insert( element, iter);
}

template <typename T>
void List<T>::Remove(const T &element)
{
ListNode<T>* currentNode = Find( element).itsCurrent;
if( currentNode -> itsNext != NULL)//判断当前节点是否尾节点
{
currentNode ->itsPrevenient ->itsNext = currentNode ->itsNext;
currentNode ->itsNext ->itsPrevenient = currentNode ->itsPrevenient;
delete currentNode;
currentNode = itsHead;
}
}

//提供一个测试函数的范本
int main()
{
List<string> myList;
ListIterator<string> lIter, lIter2;
myList.PushFront("Kimi");
myList.PushFront("Kimia");
myList.PushFront("Hello");
myList.PushBack("HaHa");
lIter = myList.End();
lIter.Back();
lIter.Advance();
cout << "after --: " <<*(--lIter) << endl;
myList.Insert("Hai", --lIter);
myList.Insert("Hi!","qq");
for( lIter = myList.Begin(); lIter != myList.End(); lIter++)
{
cout << (*lIter) << endl;
}
lIter2 = myList.Find("Kimi");
cout << "Find: " << *lIter2 << endl;
return 0;
}