广播电视大学试题开放本科2005年1月开放本科 5139数据结构B1643.doc

广播电视大学二○○四年下半年期末考试
“开放本科”计算机科学与技术专业
数据结构(上机)(B)试题
秦皇岛电大试题库(.cn/test)2005年1月
以下程序中定义了一个 List 链表类,成员函数Merge把两个按降序排列的整型链表合并成一个按降序排列的整型链表。
完成排序成员函数merge的编程及调试,使程序能正常实现功能。
#include<>
template <class T> class List;
template <class T> class ListNode
{
friend class List<T>;
public:
ListNode ( );
ListNode ( const T& item );
private:
T data;
ListNode<T> *link;
};
template <class T> class List
{
public:
List ( const T finishied );
void Browse ( );
void Merge ( List<T> &hb );
private:
ListNode<T> *first, *last;
};
template <class T>
ListNode<T> :: ListNode ( ) : link ( NULL ) { }
template <class T> ListNode<T> :: ListNode ( const T & item ) : data ( item ), link ( NULL ) { }
template <class T> List<T> :: List ( const T finished )
{
first = last = new ListNode<T>( );
T value;
ListNode<T> *p, *q, *s;
cin >> value;
while ( value != finished )
{
s = new ListNode<T>( value );
q = first;
p = first->link;
while ( p != NULL && p->data >= value )
{
q = p;
p = p->link;
}
q->link = s;
s->link = p;
if ( p