else { p = new ListNode<Type>( A[i] ); //建立链表的新结点
create ( A, n, i+1, p->link ); //递归返回时 p->link 中放入下层 p 的内容
}
}
template<Type> void List<Type> :: create ( Type A[ ], int n ) {
//外部调用递归过程的共用函数
first = current = new ListNode<Type>; //建立表头结点
create ( A, n, 0, first->link ); //递归建立单链表
}
(5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下:
template <class Type> void List <Type> :: tidyup ( ) {
ListNode<Type> * p = first->link, temp; //检测指针, 初始时指向链表第一个结点
while ( p != NULL && p->link != NULL ) //循环检测链表
if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等
temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链
delete temp; //删除后一个值相同的结点
}
else p = p->link; //指针 p 进到链表下一个结点
}
3-3 设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将
这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存
储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
【解答】
#include <iostream.h>
template <class Type> class List;
template <class Type> class ListNode {
friend class List<Type>;
public:
ListNode ( ) : link ( NULL ) { } //构造函数, 仅初始化指针成员
ListNode ( Type item, ListNde<Type> * next = NULL ) : data ( item ), link ( next ) { }
private: //构造函数, 初始化数据与指针成员
Type data;
ListNode<Type> *link;
};
template <class Type> class List {
private:
ListNode<Type> *first, *last;
public:
List ( Type finishied ) { first = last = new ListNode<Type>( finished ); }
//建立链表, 在表头结点的 data 域中存放数据输入结束标志, 它是表中不可能出现的数据
void Merge ( List<Type> &hb ); //连接链表
friend istream& operator >> ( istream& in, List<Type> inList ); //输入链表
friend ostream& operator << ( ostream& out, List<Type> outList ); //输出链表