基于模板技术的多层次可视化数据结构实验环境研究.docx

基于模板技术的多层次可视化数据结构实验环境研究
可视化数据结构实验环境VCDS v1.0
编程实验（C++版）
（编号：20050202A）

参
考
手
册

合肥工业大学
《数据结构》课程组
2005年7月15日
第1章 DSSTL类库
1.1 DSSTL类库概述
数据结构基础类模板库。这是实验环境所用到的最重要也是最基础的类库，其中类名全部以大写字母D开始，在本文中将此类库简称为D类库。D类库全部以标准C++语言编写，适合于所有标准C++编译器且不依赖第三方类库。它定义了每种数据结构的最基本的物理实现部分，提供了数据结构最基本的逻辑操作，如堆栈的入栈和出栈，并采用了C++输入输出流机制对数据结构进行存储。
在数据层的设计中体现了C++的虚继承与继承的特点，采用模板技术实现多种数据类型的代码封装，大大减少了代码的冗余，整个数据层的设计学习VC中的MFC类库的特点达到了结构明确，层次清晰，类与类之间的关系紧密。由于整个软件中的数据结构较多有八大模块，为了很好的实现类的层次架构，设计过程中设置了数据层基类DObject,然后依据具体模块设置相应的类层次，其结构框架见附录一。
1.2 DObject
DOject是数据结构标准摸班类库DSSTL中所有类的基类，定义了许多公用的虚函数。这些虚函数有相当一部分是纯虚函数，因此无法直接使用DOject来声明对象。常用的方法是使用DOject指针。
1.2.1 类层次关系
正像前面介绍的那样，DObject是整个数据层的基类，包含着各个模块的公共操作接口，是一个虚类。
1.2.2 类成员
virtual void Output(ostream& out) const;
——流输出函数，保存类中数据
virtual void Input(istream& in);
——流输入函数，读取数据
virtual void Save(char* fname) const;
——将数据保存到文件中
virtual void Load(char* fname);
——从文件中取出数据
1.3线性表
1.3.1 DList
DList是线性表逻辑类。它是具体存储类型线性表的基类，同样它内部封装着底层具体的线性表的公共操作接口。
1.3.1.1类层次关系
DObject
∟DList
相关类：DObject
头文件：DList.h
1.1.1.1 成员说明
SetNull
原型：void SetNull()
用法：清除线性表内容，无返回值。
参数：无
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list.SetNull();
}
输出：无
RemoveAll
原型：virtual void RemoveAll ()
用法：将线性表中的数据全部移除，无返回值
参数：无
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list.RemoveAll();
}
输出：无
IsEmpty
原型：virtual bool IsEmpty ()const
用法：判断线性表是否为空，返回类型为布尔型
参数：无
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list. IsEmpty ();
}
输出：ture或着false
Length
原型：virtual int Length ()const
用法：判断线性表的长度，返回值为整型
参数：无
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list. Length ();
}
输出：整型数值
Search
原型：virtual int Search (const T&x)const
用法：在线性表中查找元素x，返回值为整型
参数：模板类型参数
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list. Search (23);
}
输出：在线性表中查到数据23所在的位置，查不到时返回-1。
Insert
原型：virtual void Insert( int k, const T&x)
用法：在线性表中第k个位置插入元素x，无返回值
参数：模板类型参数
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list. Insert(2,56);
}
输出：无
Delete
原型：virtual void Delete (int k, T&x)
用法：删除线性表中的第k个元素，将删除的元素放到变量x中，返回值无
参数：模板类型参数可以是整型，字符型，双精度类型，字符串类型等。
示例：
#include “DList.h”
void main()
{ Dlist<int> list ;
list. Delete(2,35);
}
输出：无

1.3.2 DListSeq
DListSeq是线性表模板类，此类命名规则是因为存储结构是顺序表结构。它是线性表的具体实现的类。
1.3.2.1类层次关系
DOject
∟DList
∟DListSeq
相关类：Doject,DList
头文件：DListSeq.h
1.3.2.2成员说明
SetNull
原型：void SetNull()
用法：清除线性表内容，无返回值。
参数：无
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listseq ;
listseq.SetNull();
}
输出：无
参阅：DList::SetNull
RemoveAll
原型：void RemoveAll ()
用法：删除顺序表存储的线性表中的所有数据，返回值无
参数：无
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listseq ;
listseq.RemoveAll();
}
输出：无
参阅：DList::RemoveAll
Set
原型：void Set( int MaxListSeqSize, bool copy = true )
用法：重新设置顺序表线性表的最大长度，返回值无
参数：MaxListSeqSize:设置顺序表存储的线性表的最大长度，布尔变量：copy为true时，将原线性表中的数据拷贝到设置为新长度的线性表中，否则该线性表清空，最大长度设置为MaxListSeqList
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listseq ;
listseq.Set(10,true);
}
输出：无
IsEmpty
原型：virtual bool IsEmpty ()const
用法：判断线性表是否为空，返回类型为布尔型
参数：无
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
listSeq. IsEmpty ();
}
输出：ture：线性表空或着false：线性表不为空
参阅：DList::IsEmpty
Length
原型：virtual int Length ()const
用法：判断线性表的长度，返回值为整型
参数：无
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
listSeq. Length ();
}
输出：整型数值
参阅：DList::Length
Search
原型：virtual int Search (const T&x)const
用法：在线性表中查找元素x，返回值为整型
参数：模板类型参数针对对象建立的类型而确定
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
listSeq. Search (a);
}
输出：在线性表中查到字符型数据a的位置，查找失败时返回-1。
Insert
原型：virtual void Insert( int k, const T&x)
用法：在线性表中第k个位置插入元素x，无返回值
参数：模板类型参数：依据建立的对象类型而定
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
listSeq. Insert(6,y);
}
输出：无
Delete
原型：virtual void Delete (int k, T&x)
用法：删除线性表中的第k个元素，将删除的元素放到变量x中，返回值无
参数：模板类型参数可以是整型，字符型，双精度类型，字符串类型等。
示例：
#include “DList.h”
void main()
{ Dlist<char> list ;
char x;
list. Delete(2,x);
}
输出：无
参阅：DList::Delete
Get
原型：virtual bool Get( int k, T &x ) const
用法：取顺序表存储的线性表中的第k个元素，将该元素放到变量x中，返回值为布尔值
参数：第一个参数：表示线性表中的第k个位置,第二个参数模板类型参数可以是整型，字符型，双精度类型，字符串类型等。
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> lisSeq ;
char x;
list. Get(2,x);
}
输出：true或着false
operator[]
原型：T &operator[]( int i )
用法：重载运算符[],取顺序表存储的线性表中下标是i的元素,返回值为建立对象的数据类型
参数：表示线性表中的第i个位置的数据
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> lisSeq ;
char x;
x = listSeq[i];
}
输出：返回第i个数据
Output
原型：void Output( ostream &out)const
用法：将数据以流的形式输出，无返回值
参数：out输出流变量。
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
ofstream outFile ( “d:\\li1.txt”) ;
listSeq.Output( outFile ) ;
}
输出：无
Input
原型：void Input( istream &in)
用法：将数据以流的形式输入，无返回值
参数：in输入流变量。
示例：
#include “DListSeq.h”
void main()
{ DlistSeq<char> listSeq ;
ifstream inFile ( “d:\\li1.txt”) ;
listSeq.Input( inFile ) ;
}
输出：无
说明：Input和OutPut两个函数接口一般不在数据层使用，而应用在视化框架中的导入导出操作中。
1.4栈
1.4.1 DStack
1.4.1.1类层次关系
DOject
∟DStack
相关类：DOject
头文件：DStack.h
1.4.1.2成员说明
Push
原型：bool Push(T item)=0
用法：将数据item 入栈，纯虚函数在子类中实现。返回值为布尔值。
参数：入栈数据，类型与建立的对象数据类型一致
Pop
原型：bool Pop(T &value)=0
用法：将栈顶数据出栈放到变量value中，返回值为布尔值。
参数：出栈数据所放位置的变量，类型与建立的对象数据类型一致
Length
原型：int Length() const=0
用法：返回栈中数据长度，纯虚函数在子类中实现。返回值：整型。
参数：无
GetTop
原型： T GetTop()=0
用法：取栈顶数据，纯虚函数在子类中实现。返回值：返回栈顶数据，数据类型为建立的对象的数据类型。
参数：无
IsEmpty
原型：bool IsEmpty() const
用法：判断栈是否为空，纯虚函数在子类中实现。返回值为布尔值。
参数：无
Clear
原型：bool Clear()
用法：清空栈，纯虚函数在子类中实现。返回值为布尔值。
参数：无
GetNodeNum
原型：virtual int GetNodeNum() const=0
用法：纯虚函数，供在子类中被重载，返回值为整型。
参数：无
Input
原型：virtual void Input( istream &in)=0
用法：纯虚函数，供在子类中被重载，返回值无。
参数：流输入参数
Output
原型：virtual void Output( ostream &out)const
用法：虚函数，供在子类中被重载，返回值无。
参数：流输出参数
1.4.2 DstackSeq
1.4.2.1类层次关系
DOject
∟DStack
∟DStackSeq
相关类：Doject,DStack
头文件：DStack.h
1.4.1.2成员说明
Push
原型：bool Push(T item)
用法：将数据item 入栈，返回值为布尔值。
参数：入栈数据，类型与建立的对象数据类型一致
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
Dstring x;
Cin>> x;
stackSeq..Push(x);
}
输出：入栈操作成功返回true,否则为false
参阅：Dstack::Push
Pop
原型：bool Pop(T &value)
用法：将栈顶数据出栈放到变量value中，返回值为布尔值。
参数：出栈数据所放位置的变量，类型与建立的对象数据类型一致
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
Dstring x;
stack.Seq.Pop(x);
}
输出：出栈操作成功返回true,否则为false
参阅：Dstack::Pop
Length
原型：int Length() const
用法：返回栈中数据长度，返回值：整型。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
stack.Seq.Length();
}
输出：栈长度：整型值
参阅：DList::Length，DlistSeq::Length,Dstack::Length
GetTop
原型： T GetTop()
用法：取栈顶数据，返回值：返回栈顶数据，数据类型为建立的对象的数据类型。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
Dstring strData;
StrData = stackSeq..GetTop();
}
输出：栈顶数据
IsEmpty
原型：bool IsEmpty() const
用法：判断栈是否为空，返回值为布尔值。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
stack.Seq.IsEmpty();
}
输出：false 表示栈不空，否则为空
参阅：DList::IsEmpty, DlistSeq::IsEmpty,Dstack::IsEmpty
Clear
原型：bool Clear()
用法：清空栈，返回值为布尔值。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
stackSeq..Clear();
}
输出：返回值为true 表示栈被清空
GetNodeNum
原型：virtual int GetNodeNum() const
用法：获得栈中数据个数，返回值为整型。
参数：无
示例：#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
int x;
x = stackSeq..GetNodeNum();
}
输出：返回值为true 表示栈被清空
参阅：Dstack::GetNodeNum
Input
原型：virtual void Input( istream &in)
用法：以流的方式读入数据，返回值无。
参数：流输入参数
参阅：DList::Input，DlistSeq::Input,Dstack::Input
Output
原型：virtual void Output( ostream &out)const
用法：以流的方式保存数据，返回值无。
参数：流输出参数
参阅：DList::Output，DlistSeq::Output,Dstack::Output
SetData
原型：void SetData(T data,int NodeNum)
用法：将栈中第NodeNum个数据设置为data值，返回值无。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackSeq<Dstring> stackSeq;
stackSeq..SetData(x,stack.Length()-1);
}
输出：无
参阅：DList::Inseart, DlistSeq::Inseart
Input_i
原型：void Input_i( int NodeNum,istream &in)
用法：以流的方式读入第NodeNum个数据，返回值无。
参数：流输入参数
Output_i
原型：void Output_i( int NodeNum,ostream &out)
用法：以流的方式取出第NodeNum个数据，返回值无。
参数：流输出参数
1.4.3DstackLink
1.4.3.1类层次关系
DOject
∟DStack
∟DStackLink
相关类：Doject,DStack
头文件：DStack.h
1.4.3.2成员说明
Push
原型：bool Push(T item)
用法：将数据item 入栈，返回值为布尔值。
参数：入栈数据，类型与建立的对象数据类型一致
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring> *stackLink;
Dstring x;
Cin>> x;
StackLink->Push(x);
}
输出：入栈操作成功返回true,否则为false
参阅：Dstack::Push, DstackSeq::Push
Pop
原型：bool Pop(T &value)
用法：将栈顶数据出栈放到变量value中，返回值为布尔值。
参数：出栈数据所放位置的变量，类型与建立的对象数据类型一致
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
Dstring x;
stack.Link->Pop(x);
}
输出：出栈操作成功返回true,否则为false
参阅：Dstack::Pop, DstackSeq::Pop
Length
原型：int Length() const
用法：返回栈中数据长度，返回值：整型。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring> * stackLink;
stack.Link->Length();
}
输出：栈长度：整型值
参阅：DList::Length，DlistLink::Length,Dstack::Length, DstackSeq::Length
GetTop
原型： T GetTop()
用法：取栈顶数据，返回值：返回栈顶数据，数据类型为建立的对象的数据类型。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
Dstring strData;
StrData = stackLink->GetTop();
}
输出：栈顶数据
参阅：DstackSeq::GetTop
IsEmpty
原型：bool IsEmpty() const
用法：判断栈是否为空，返回值为布尔值。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
stack.Link->IsEmpty();
}
输出：false 表示栈不空，否则为空
参阅：DList::IsEmpty, DlistLink::IsEmpty,Dstack::IsEmpty, DstackSeq::IsEmpty
Clear
原型：bool Clear()
用法：清空栈，返回值为布尔值。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
stackLink->Clear();
}
输出：返回值为true 表示栈被清空
参阅：DstackSeq::Clear
GetNodeNum
原型：virtual int GetNodeNum() const
用法：获得栈中数据个数，返回值为整型。
参数：无
示例：#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
int x;
x = stackLink->GetNodeNum();
}
输出：返回值为true 表示栈被清空
参阅：Dstack::GetNodeNum, DstackSeq::GetNodeNum
Input
原型：virtual void Input( istream &in)
用法：以流的方式读入数据，返回值无。
参数：流输入参数
参阅：DList::Input，DlistLink::Input,Dstack::Input, DstackSeq::Input
Output
原型：virtual void Output( ostream &out)const
用法：以流的方式保存数据，返回值无。
参数：流输出参数
参阅：DList::Output，DlistLink::Output,Dstack::Output, DstackSeq::Output
SetData
原型：void SetData(T data,int NodeNum)
用法：将栈中第NodeNum个数据设置为data值，返回值无。
参数：无
示例：
#include “DStack.h”
void main()
{ DstackLink<Dstring>* stackLink;
stackLink->SetData(x,stack.Length()-1);
}
输出：无
参阅：DList::Inseart, DlistLink::Inseart,DstackSeq::SetData
Input_i
原型：void Input_i( int NodeNum,istream &in)
用法：以流的方式读入第NodeNum个数据，返回值无。
参数：流输入参数
参阅：DstackSeq::Input_i
Output_i
原型：void Output_i( int NodeNum,ostream &out)
用法：以流的方式取出第NodeNum个数据，返回值无。
参数：流输出参数
参阅：DstackSeq:: Output_i
说明：DstackSeq与DstackLink 所具有的函数接口实现效果一致，因为存储结构不同，因而实现具体内容不同。
1.5队列
1.5.1 DQueue
1.5.1.1类层次关系
DOject
∟DQueue
相关类：DOject
头文件：DQueue.h
1.5.1.2 成员说明
EnQueue
原型：virtual bool EnQueue(T item)=0
用法：将数据item 入队，纯虚函数在子类中实现。返回值为布尔值。
参数：入栈数据，类型与建立的对象数据类型一致
DeQueue
原型：virtual bool DeQueue(T &value)=0
用法：取出队首数据放到变量value中，返回值为布尔值。
参数：出队列数据所放位置的变量，类型与建立的对象数据类型一致
GetHead
原型：virtual T GetHead()=0
用法：取队首数据，纯虚函数在子类中实现。返回值为建立对象的类型。
参数：无
GetRear
原型：virtual T GetRear()=0
用法：取队尾数据，返回值为取到的队尾数据，类型为建立对象的类型。
参数：无
Length
原型：int Length() const=0
用法：返回栈中数据长度，纯虚函数在子类中实现。返回值：整型。
参数：无
IsEmpty
原型：bool IsEmpty() const
用法：判断栈是否为空，纯虚函数在子类中实现。返回值为布尔值。
参数：无
Clear
原型：bool Clear()
用法：清空栈，纯虚函数在子类中实现。返回值为布尔值。
参数：无
GetNodeNum
原型：virtual int GetNodeNum() const=0
用法：纯虚函数，供在子类中被重载，返回值为整型。
参数：无
Input
原型：virtual void Input( istream &in)=0
用法：纯虚函数，供在子类中被重载，返回值无。
参数：流输入参数
Output
原型：virtual void Output( ostream &out)const
用法：虚函数，供在子类中被重载，返回值无。
参数：流输出参数
1.5.2 DQueueSeq
1.5.2.1类层次关系
DOject
∟DQueue
∟DQueueSeq
相关类：Doject,DQueue
头文件：DQueue.h
1.5.2.2成员说明
GetHead
原型：T GetHead()
用法：取队首元素，返回值：返回所取队首数据，类型为建立对象所对应的类型。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
Dstring x;
x = QueueSeq. GetHead ();
}
输出：返回所取队首数据
参阅：DQueue:: GetHead
GetRear
原型：T GetRear()
用法：取队尾数据，返回值：返回所取队尾数据，数据类型与所见对象类型一致。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
Dstring x;
x = QueueSeq.GetRear();
}
输出：返回所取队尾数据
参阅：DQueue::GetRear
EnQueue
原型：bool EnQueue (T item)
用法：将数据item 入队列，返回值为布尔值。
参数：入队列数据，类型与建立的对象数据类型一致
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
Dstring x;
Cin>> x;
QueueSeq. EnQueue (x);
}
输出：入队操作成功返回true,否则为false
参阅：DQueue:: EnQueue
DeQueue
原型：bool DeQueue(T &value)
用法：将队首数据出队列放到变量value中，返回值为布尔值。
参数：出队列数据所放位置的变量，类型与建立的对象数据类型一致
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
Dstring x;
QueueSeq.DeQueue(x);
}
输出：出队操作成功返回true,否则为false
参阅：DQueue::DeQueue
Length
原型：int Length() const
用法：返回队列中数据长度，返回值：整型。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
QueueSeq. Length();
}
输出：队列长度：整型值
参阅：DList::Length，DlistSeq::Length,DQueue::Length
IsEmpty
原型：bool IsEmpty() const
用法：判断队列是否为空，返回值为布尔值。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
QueueSeq.IsEmpty();
}
输出：false 表示栈不空，否则为空
参阅：DList::IsEmpty, DlistSeq::IsEmpty,Dstack::IsEmpty,DQueue::IsEmpty
Clear
原型：bool Clear()
用法：清空队列，返回值为布尔值。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
QueueSeq.Clear();
}
输出：返回值为true 表示队列被清空
GetNodeNum
原型：virtual int GetNodeNum() const
用法：获得队列中数据个数，返回值为整型。
参数：无
示例：#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
int x;
x = QueueSeq..GetNodeNum();
}
输出：返回值为true 表示队列被清空
参阅：DQueue::GetNodeNum, Dstack::GetNodeNum
Input
原型：virtual void Input( istream &in)
用法：以流的方式读入数据，返回值无。
参数：流输入参数
参阅：DList::Input，DlistSeq::Input,DQueue::Input, Dstack::Input
Output
原型：virtual void Output( ostream &out)const
用法：以流的方式保存数据，返回值无。
参数：流输出参数
参阅：DList::Output，DlistSeq::Output,DQueue::Output, Dstack::Output
SetData
原型：void SetData(T data,int NodeNum)
用法：将队列中第NodeNum个数据设置为data值，返回值无。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQueueSeq<Dstring> QueueSeq;
QueueSeq.SetData(x,QueueSeq.Length()-1);
}
输出：无
参阅：DList::Inseart, DlistSeq::Inseart, Dstack::SetData
Input_i
原型：void Input_i( int NodeNum,istream &in)
用法：以流的方式读入第NodeNum个数据，返回值无。
参数：流输入参数
参阅：Dstack::Input_i
Output_i
原型：void Output_i( int NodeNum,ostream &out)
用法：以流的方式取出第NodeNum个数据，返回值无。
参数：流输出参数
参阅：Dstack::Output_i
1.5.3 DQueueLink
1.5.3.1类层次关系
DOject
∟DQueue
∟DQueueLink
相关类：Doject,DQueue
头文件：DQueue.h
1.5.3.2成员说明
GetHead
原型：T GetHead()
用法：取队首元素，返回值：返回所取队首数据，类型为建立对象所对应的类型。
参数：无
示例：
#include “DQueue.h”
void main()
{ DQu