头文件--定义基类、双向链表类、结点类
#include "iostream.h"
#include "string.h"
class Object //定义抽象类
{
public:
Object(){}
virtual int IsEqual(Object&)=0;//实现2个结点数据的比较
virtual void Show()=0;//输出一个结点的数据
virtual ~Object(){}
};
class Node //结点类
{
public:
Node(){
Info=0;Prev=0;Next=0;
}
Node(Node &node) //拷贝构造函数
{
Info=node.Info;
Prev=node.Prev;
Next=node.Next;
}
void FillInfo(Object *obj){//使Info指向数据域
Info=obj;
}
friend class List; //友元类list
private:
Object *Info;//指向描述结点的数据域
Node *Prev,*Next;//构成链表的前后指针
};
class List //实现双向链表操作
{
public:
List(){Head=Tail=0;
}
~List(){DeleteList();
}
void AddNode(Node*); //链表尾加一结点
Node *DeleteNode(Node*);//删除指定结点
Node *LookUp(Object&);//查找一指定结点
void ShowList();//输出链表
void DeleteList();//删除链表
private:
Node *Head,*Tail;
};
void List::AddNode(Node *node)
{
if (Head==0) {
Head=Tail=node;
node->Next=node->Prev=0;
}
else{//加入链表尾
Tail->Next=node;//使链表尾结点的后指针指向插入的结点
node->Prev=Tail;//使插入结点的前指针指向原链表尾结点
Tail=node;//使Tail指向新的链表尾结点
node->Next=0;
}
}
Node *List::DeleteNode(Node *node)
{
if (node==Head)//要删除的结点为首结点
if(node==Tail)//表示链表上只有一个结点的情况
Head=Tail=0;
else{
Head=node->Next;
Head->Prev=0;
}
else{
node->Prev->Next=node->Next;//从后向链指针上取下该结点
if (node!=Tail) node->Next->Prev=node->Prev;
else{
Tail=node->Prev;Tail->Next=0;//要删除的结点为尾结点
}
}
node->Prev=node->Next=0;//将已删除结点的前后指针置空
return (node);
}
Node *List::LookUp(Object &obj)
{
Node *pn=Head;
while (pn) {
if (pn->Info->IsEqual(obj))return pn;//找到结点
pn=pn->Next;
}
return 0;//没有找到结点
}
void List::ShowList()
{
Node *p=Head;
while (p) {
p->Info->Show();
p=p->Next;
}
}
void List::DeleteList()
{
Node *p,*q;
p=Head;
while (p) {
delete p->Info;//释放结点数据
q=p;
p=p->Next;
delete q;//释放Node占的空间
}
}
类实现及主函数
class IntObj:public Object //派生描述结点数据的类
{
public:
IntObj(int x=0){data=x;}
void SetData(int x){
data=x;
}
int IsEqual(Object&);
void Show(){
cout<<"Data="<<data<<'\t';
}
private:
int data;
};
int IntObj::IsEqual(Object &obj)//重新定义比较2个结点是否相等的虚函数
{
IntObj &temp=(IntObj &)obj;
return (data==temp.data);
}
int main(void)
{
IntObj *p;
Node *pn,*pt,node;
List list;
for(int i=1;i<10;i++){//建立双向链表
p=new IntObj(i+50);//建立IntObj对象
pn=new Node;
pn->FillInfo(p);
list.AddNode(pn);
}
list.ShowList();
cout<<"\n";
IntObj da;
da.SetData(52);
pn=list.LookUp(da);
if (pn) {
pt=list.DeleteNode(pn);
}
list.ShowList();
cout<<"\n";
if (pn) {
list.AddNode(pt);
}
list.ShowList();
cout<<"\n";
return 0;
}
分享到:
相关推荐
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
自己写的实现c++双向链表的功能,包括InsertAtHead,Append,RemoveHead,RemoveTail,InsertAfter, DeleteAt,Reset,GetPre,GetNext等函数 压缩包里包含CMyList.h和CMyList.cpp两个文件
使用C++双向列表统计文章单词出现频率,其中双向列表模仿STL中的List.
c++模板实现双向链表操作如逆序建立双向链表,插入结点等。
c++的双向链表 next pre 。的建立和插入一个介于ab之间的值x的方法
主要介绍了c++双向链表操作示例,包括创建双向链、删除双向链表、双向链表中查找数据、插入数据等,需要的朋友可以参考下
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
基础数据结构双向链表的C++描述版。实现了双向链表的基本功能。包括拷贝构造函数和IO操作符重载、赋值操作符重载
用C++实现双向链表的插入,删除,更新等操作。
C++ 双向链表实现学生管理系统
C++经典算法 双向链表 采用了结构体,链表的知识。
C++双向链表删除,修改,插入,排序,全面,界面人性化
这是数据结构的约瑟夫双向链表算法,用c++做的,使我们学习数据结构的时候老师让我们做的实验,很经典,提供给大家参考一下!
详细的介绍了Linux内核中使用的最频繁的双向链表
C语言链表程序,内含链表的创建、插入、查找、遍历、删除和释放。 C语言链表程序,内含链表的创建、插入、查找、遍历、删除和释放。
这是使用VC6.0实现的双向循环链表操作的程序,实现了查找元素,查找前驱后继等功能,并在MFC界面下实现了链表操作的具体过程。
C++实现的双向链表类,很好的资源。。希望大家支持啊。。。
C++ 实现的约瑟夫环的操作,双向链表实现,适合初学者的了解双向链表
mfc双向链表 注释详细 对于数据结构的理解有一定帮助