Question

数据结构C语言版问题

2-4针对带表头结点的单链表，试编写下列函数。

(1) 求最大值函数max：通过一趟遍历在单链表中

确定值最大的结点。

(2) 建立函数create：根据一维数组a[n]建立一个

单链表，使单链表中各元素的次序与a[n]中各元素

的次序相同，要求该程序的时间复杂性为O(n)。

(3) 整理函数tidyup：在非递减有序的单链表中删

除值相同的多余结点。

Answer 1

1.实现求最大值的函数如下：
template <class Type> ListNode <Type> * List <Type> :: Max ( ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针NULL
if ( first->link == NULL ) return NULL; //空表, 返回指针NULL
ListNode <Type> * pmax = first->link, p = first->link->link;
//假定第一个结点中数据具有最大值
while ( p != NULL ) { //循环, 下一个结点存在
if ( p->data > pmax->data ) pmax = p; //指针pmax记忆当前找到的具最大值结点
p = p->link; //检测下一个结点
}
return pmax;
}
2.实现从一维数组A[n]建立单链表的函数如下：
template <class Type> void List <Type> :: Create ( Type A[ ], int n ) {
//根据一维数组A[n]建立一个单链表，使单链表中各元素的次序与A[n]中各元素的次序相同
ListNode<Type> * p;
first = p = new ListNode<Type>; //创建表头结点
for ( int i = 0; i < n; i++ ) {
p->link = new ListNode<Type> ( A[i] ); //链入一个新结点, 值为A[i]
p = p->link; //指针p总指向链中最后一个结点
}
p->link = NULL;
}
或者采用递归方法实现
template<Type> void List<Type> :: create ( Type A[ ], int n, int i,
ListNode<Type> *& p ) {
//私有函数：递归调用建立单链表
if ( i == n ) p = NULL;
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 ); //递归建立单链表
}

3， 实现在非递减有序的单链表中删除值相同的多余结点的函数如下：
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进到链表下一个结点
}
参考别人的，这题目我才不会做。