算法题目和答案.docx

1． 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素。 算法如下 ListNode * Merge ( ListNode * L1, ListNode * L2 ) {//根据两个带表头结点的有序单链表L1和L2, 生成一个新的有序单链表 ListNode *first = new ListNode; ListNode *p1 = L1-link, *p2 = L2-link, *p = first, *q; while ( p1 != NULL p2 != NULL ) { q = new ListNode; if ( p1-data == p2-data ) { q-data = p1-data; p2 = p2-link; p1 = p1-link; } else if ( p1-data p2-data ) { q-data = p1-data; p1 = p1-link; } else { q-data = p2-data; p2 = p2-link; } p-link = q; p = q; } while ( p1 != NULL ) { q = new ListNode; q-data = p1-data; p1 = p1-link; p-link = q; p = q; } while ( p2 != NULL ) { q = new ListNode; q-data = p2-data; p2 = p2-link; p-link = q; p = q; } p-link = NULL; return first; } 2． 设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraysize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, …, e1, e0)。 数组原地逆置算法 参数表中给出数组A[ ] 及指定的数组中前n个元素，函数执行后从A[ ] 中得到数组原地逆置后的结果。 Templateclass T void inverse ( T A[ ], int n ) { T tmp; for ( int I = 0; I = ( n-1 ) / 2; I++ ) { tmp = A[I]; A[I] = A[n-I-1]; A[n-I-1] = tmp;} } 3． 设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以从小到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以从小到大的升序排列。 合并两个升序排列的顺序表的算法 参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。 算法中用到顺序表的4个共有函数：Length( ) 求表的当前长度；maxLength( ) 求表的最大允许长度；getData(k) 提取第k个元素的值；setData(k) 修改第k个元素的值。 Template class T void merge ( SeqListint A, SeqListint B, SeqListint C ) { int m = A.Length( ), n = B.Length( ), mpn = m + n; if ( mpn C.maxLength( ) ) { cerr “合并后表的长度超出表的最大允许长度” endl; exit (1); } int I = 0, j = 0, k = 0, av = A.getData(I), bv = B.getData(j); while ( I m j n ) if ( av = bv ) { C.setData(k++, av); av = A.getData(++I); } else { C.setData(k++, bv); B.getData(++j); } if ( I m ) while ( k mpn ) { C.setData(k++, av); av = A.getData(++I); } else while ( k mpn ) { C.setData(k++, bv); B.getData(++j); } } 4． 已知一个带表头结点的单链表中包含有三类字符（数字字符、字母字符和其他字符），试编写一个函数，构造三个新的单链表，使每个单链表中只包含同一类字符。要求使用原表的空间，表头结点可以另辟空间。 算法如下