《数据结构习题解答》习题2解答.doc_大学文库

6 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第 5 人出局, i = 4 k = 8 1 2 3 4 6 7 8 9 5 第 1 人出局, i = 0 k = 7 2 3 4 6 7 8 9 1 5 第 7 人出局, i = 4 k = 6 2 3 4 6 8 9 7 1 5 第 4 人出局, i = 2 k = 5 2 3 6 8 9 4 7 1 5 第 3 人出局, i = 1 k = 4 2 6 8 9 3 4 7 1 5 第 6 人出局, i = 1 k = 3 2 8 9 6 3 4 7 1 5 第 9 人出局, i = 2 k = 2 2 8 9 6 3 4 7 1 5 第 2 人出局, i = 0 8 2 9 6 3 4 7 1 5 第 8 人出局, i = 0 逆置 5 1 7 4 3 6 9 2 8 最终出局顺序例：n = 9, s = 1, m = 0 报错信息 m = 0 是无效的参数！例：n = 9, s = 1, m = 10 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第 1 人出局, i = 0 k = 8 2 3 4 5 6 7 8 9 1 第 3 人出局, i = 1 k = 7 2 4 5 6 7 8 9 3 1 第 6 人出局, i = 3 k = 6 2 4 5 7 8 9 6 3 1 第 2 人出局, i = 0 k = 5 4 5 7 8 9 2 6 3 1 第 9 人出局, i = 4 k = 4 4 5 7 8 9 2 6 3 1 第 5 人出局, i = 1 k = 3 4 7 8 5 9 2 6 3 1 第 7 人出局, i = 1 k = 2 4 8 7 5 9 2 6 3 1 第 4 人出局, i = 0 8 4 7 5 9 2 6 3 1 第 8 人出局, i = 0 逆置 1 3 6 2 9 5 7 4 8 最终出局顺序当 m = 1 时，时间代价最大。达到( n-1 ) + ( n-2 ) + ∙∙∙∙∙∙ + 1 = n(n-1)/2  O(n2 )。 2-3 设有一个线性表 (e0, e1 , …, en-2, en-1) 存放在一个一维数组 A[arraySize]中的前 n 个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置换为 (en-1, en-2, …, e1, e0)。【解答】 template void inverse ( Type A[ ], int n ) { Type tmp; for ( int i = 0; i <= ( n-1 ) / 2; i++ ) { tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp; } } 2-4 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素? 【解答】若设顺序表中已有 n = last+1 个元素，last 是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有 n+1 个插入位置(可以  − = − = − = − − = − + − + + + = n 1 i 0 2 n 1 2 (n 1)n n 1 ((n 1) (n 2) 1 0) n 1 (n i 1) n 1 AMN 

7 在表中最后一个表项后面追加)，每个元素位置插入的概率为 1/(n+1)，但在删除时只能在已有 n 个表项范围内删除，所以每个元素位置删除的概率为 1/n。插入时平均移动元素个数 AMN(Averagy Moving Number )为删除时平均移动元素个数 AMN 为 2-5 利用顺序表的操作，实现以下的函数。 (1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。 (2) 从顺序表中删除第 i 个元素并由函数返回被删元素的值。如果 i 不合理或顺序表为空则显示出错信息并退出运行。 (3) 向顺序表中第 i 个位置插入一个新的元素 x。如果 i 不合理则显示出错信息并退出运行。 (4) 从顺序表中删除具有给定值 x 的所有元素。 (5) 从顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素，如果 s 或 t 不合理或顺序表为空则显示出错信息并退出运行。 (6) 从有序顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素，如果 s 或 t 不合理或顺序表为空则显示出错信息并退出运行。 (7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。 (8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】 (1) 实现删除具有最小值元素的函数如下： template Type SeqList :: DelMin ( ) { if ( last == -1 ) //表空, 中止操作返回 { cerr Type SeqList :: DelNo#i ( int i ) { if ( last == -1 || i last ) //表空, 或 i 不合理, 中止操作返回 { cerr << “ List is Empty or Parameter is out range! ” << endl; exit(1); } Type temp = data[i]; //暂存第 i 个元素的值 for ( int j = i; j < last; j++ ) //空出位置由后续元素顺次填补 data[j] = data[j+1]; last--; //表最后元素位置减 1 return temp; } (3) 实现向第 i 个位置插入一个新的元素 x 的函数如下(设第 i 个元素在 data[i]

ListNode* Find( Type value ) //搜索含数据 value的元素并成为当前元素 ListNode* Locate( int i //搜索第i个元素的地址并置为当前元素 Type GetData () //取出表中当前元素的值 int Insert( Type value //将 value插在表当前位置之后并成为当前元素 //将链表中的当前元素删去,填补者为当前元素 Listnodelink ! NULL: 1 //当前元素下一元素空否?空返回1,不空返回0 2-6线性表可用顺序表或链表存储。试问: (1)两种存储表示各有哪些主要优缺点? (2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用哪种存储表示?为什么? (3)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时应采用哪种存储表示?为什么? 【解答】 (1)顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变, 因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要移动一半(或近一半)元素, 修改效率不高链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间, 就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高 (2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用链接存储表示如果采用顺序存储表示,必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用的空间增长得慢;有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入时就必须成片地移动其他的表的空间,以空出位置进行插入;在元素删除时,为填补空白,也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储分配解决,只要存储器未满,就不会有表溢出的问题;表的收缩可以通过动态存储释放实现,释放的空间还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于n个表(包括表的总数可能变化共存的情形,处理十分简便和快捷。所以选用链接存储表示较好 (3)应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好。 2-7针对带表头结点的单链表,试编写下列函数。 (1)定位函数 Locate:在单链表中寻找第i个结点。若找到,则函数返回第i个结点的地址:若

11 ListNode * Find ( Type value ); //搜索含数据 value 的元素并成为当前元素 ListNode * Locate( int i ); //搜索第 i 个元素的地址并置为当前元素 Type * GetData ( ); //取出表中当前元素的值 int Insert ( Type value ); //将 value 插在表当前位置之后并成为当前元素 Type *Remove ( ); //将链表中的当前元素删去, 填补者为当前元素 ListNode * Firster ( ) { current = first; return first; } //当前指针定位于表头结点 Type *First ( ); //当前指针定位于表中第一个元素并返回其值 Type *Next ( ); //将当前指针进到表中下一个元素并返回其值 int NotNull ( ) { return current != NULL; } //表中当前元素空否？空返回 1, 不空返回 0 int NextNotNull ( ) { return current != NULL && current->link != NULL; } //当前元素下一元素空否？空返回 1, 不空返回 0 }; 2-6 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】 (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。 (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n 个表(包括表的总数可能变化) 共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。 2-7 针对带表头结点的单链表，试编写下列函数。 (1) 定位函数 Locate：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若

12 找不到，则函数返回 NULL。 (2) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。 (3) 统计函数 number：统计单链表中具有给定值 x 的所有元素。 (4) 建立函数 create：根据一维数组 a[n]建立一个单链表，使单链表中各元素的次序与 a[n]中各元素的次序相同，要求该程序的时间复杂性为 O(n)。 (5) 整理函数 tidyup：在非递减有序的单链表中删除值相同的多余结点。【解答】 (1) 实现定位函数的算法如下： template ListNode * List :: Locate ( int i ) { //取得单链表中第 i 个结点地址, i 从 1 开始计数, i * p = first; int k = 0; //从表头结点开始检测 while ( p != NULL && k link; k++; } //循环, p == NULL 表示链短, 无第 i 个结点 return p; //若 p != NULL, 则 k == i, 返回第 i 个结点地址 } (2) 实现求最大值的函数如下： template ListNode * List :: Max ( ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL if ( first->link == NULL ) return NULL; //空表, 返回指针 NULL ListNode * pmax = first->link, p = first->link->link; //假定第一个结点中数据具有最大值 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data > pmax->data ) pmax = p; //指针 pmax 记忆当前找到的具最大值结点 p = p->link; //检测下一个结点 } return pmax; } (3) 实现统计单链表中具有给定值 x 的所有元素的函数如下： template int List :: Count ( Type& x ) { //在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULL int n = 0; ListNode * p = first->link; //从第一个结点开始检测 while ( p != NULL ) { //循环, 下一个结点存在 if ( p->data == x ) n++; //找到一个, 计数器加 1 p = p->link; //检测下一个结点 } return n; } (4) 实现从一维数组 A[n]建立单链表的函数如下： template void List :: Create ( Type A[ ], int n ) { //根据一维数组 A[n]建立一个单链表，使单链表中各元素的次序与 A[n]中各元素的次序相同 ListNode * p; first = p = new ListNode; //创建表头结点 for ( int i = 0; i link = new ListNode ( A[i] ); //链入一个新结点, 值为 A[i]