第二章 线性表(13)

17．裴波那契(Fibonacci)数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib(n)表示，则计算公式为： ? 1 (n=1或2) Fib(n)=?

? Fib(n-1)+Fib(n-2) (n>=2)

试编写出计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。

递归算法：

long Fib( int n ) {

if ( n==1 || n=2 ) // 终止递归条件 return 1; else

return Fib(n-1)+Fib(n-2); }

非递归算法：

long Fib( int n ) {

int a , b , c; // c代表当前项，a和b分别代表当前项前面的第2项和第1项

a = b = 1;

if ( n == 1 || n == 2 ) return 1; else

for ( int i = 3 ; i<=n ; i++ ) { c = a+b; // 求当前项 a = b; // 产生第2项 b = c; // 产生第1项 }

return c; // 返回所求的第n项 }

递归算法的时间复杂度为 O(2n)，空间复杂度为 O(n)；非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

18．编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，??an-1，an，则逆序链接后变为, an，an-1，??a1。

Void contrary (Lnode * & HL)

根据编程情况，酌情给分。 {

Lnode *P=HL; HL=NULL;

While (p!=null) {

Lnode*q=p; P=p→next; q→next=HL; HL=q;

41

}

}

19．一个一维整数数组A[m]中有n (n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。

（1）在数组A[ ]中插入一个新的整数x ，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。（5分）

void InsertSort (int A[ ], int m , int & n , int x)

{

}

插入函数如下：

void InsertSort (int A[ ], int m , int & n , int x) { if (n

for (i=0 ; i

for (j=n-1 ; j>=I ; j-- )A[j+1] = A[ j ] ; A[ I ]=x ; n++; }

else{cerr<<”数组已满，不能插入！”<

}

（2）将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。（5分）

void reverse (int A [ ], int n )

{

}

逆置函数如下：

void reverse (int A [ ], int n ) { int mid=n/2 , I, temp ; for ( i=0 ; i

{temp=A[i] ; A[i]=A[n-i-1] ;A[n-i-1]=temp ; }

}

（3）删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。（5分）

Void delDuplicate (int A [ ] , int & n) {

}

删除函数如下：

Void delDuplicate (int A [ ] , int & n) { Int i=0 , j , k ;

42

While (i

If (A[i]= =A[j]) {

For ( k=j+1 ; k

}

20．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三.1(5分)】【厦门大学2006 1(3)(20/3分)】

[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList la,lb)

∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列

∥本算法将两链表合并成一个按元素值递减次序排列的单链表

{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针 la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空

while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data)

{ r=pa->next; ∥将pa 的后继结点暂存于r

pa->next=la->next; ∥将pa结点链于结果表中，同时逆置 la->next=pa;

pa=r; ∥恢复pa为当前待比较结点 } …… 此处隐藏：4字，全部文档内容请下载后查看。喜欢就下载吧 ……