首页 理论教育实例:C++程序设计基础教程中的类模板设计及线性表运算测试

实例:C++程序设计基础教程中的类模板设计及线性表运算测试

【摘要】:本节采用类模板设计几个通用的数据结构,这种类属程序设计方法不仅提高了程序的可靠性,而且大大提高了程序设计效率。抽象数据类型线性表的定义如下:设计满足上述定义的List类模板,并用相关数据对程序进行测试。另设计一个线性表类模板List,用于实现线性表的各种运算。

本节采用类模板设计几个通用的数据结构,这种类属程序设计方法不仅提高了程序的可靠性,而且大大提高了程序设计效率

【例5.9】抽象数据类型线性表的定义如下:

设计满足上述定义的List<T>类模板,并用相关数据对程序进行测试。

解:对于线性表采用带头节点的单链表的存储结构,其中每个元素用一个节点进行存储,并通过next将所有节点串起来表示元素之间的线性关系。

设计一个节点类模板Node<T>,包含有节点的data值和下一个节点的指针next等私有数据成员和相关成员函数。

另设计一个线性表类模板List<T>,用于实现线性表的各种运算。

为了方便在List<T>中对Node<T>中的私有数据成员操作,将List<T>声明为Node<T>的友元类模板,因此需要对List<T>类模板进行前向引用声明。完整的程序如下:

程序执行结果如下:

初始化表L

表空

插入元素a,b,c,d

表不空

表L:a b c d

c的序号:3

在序号3处插入e,f

表L:a b f e c d

c的序号:5

序号3的元素:f

删除两个元素

表L:a b e d

销毁表

【例5.10】抽象数据类型栈的定义如下:

设计满足上述定义的Stack<T>类模板,并用相关数据对程序进行测试。(www.chuimin.cn)

解:对于栈采用不带头节点的单链表的链栈存储结构,其中每个元素用一个节点进行存储,并通过next将所有节点串起来表示元素之间的线性关系。

设计一个节点类模板Node<T>,包含有节点的data值和下一个节点的指针next等私有数据成员和相关成员函数。

另设计一个栈类模板Stack<T>,用于实现栈的各种运算。

为了方便在Stack<T>中对Node<T>中的私有数据成员操作,将Stack<T>声明为Node<T>的友元类模板,因此需要对Stack<T>类模板进行前向引用声明。完整的程序如下:

程序执行结果如下:

初始化栈s

栈空

进栈元素a,b,c,d

栈不空

栈顶元素:d

出栈次序:d c b a

销毁栈

【例5.11】抽象数据类型队列的定义如下:

设计Queue<T>类模板,并用相关数据对程序进行测试。

解:采用顺序队的存储结构,在初始化时创建一个大小为MaxSize的连续内存空间,用qu指向其起始位置,用front和rear分别指向队头和队尾位置。完整的程序如下:

程序执行结果如下:

初始化队列q

队空

进队a,b,c,d

队不空

所有元素出队:a b c d

销毁队列