《设n个人围坐在一个圆桌周围》由会员分享，可在线阅读，更多相关《设n个人围坐在一个圆桌周围（19页珍藏版）》请在金锄头文库上搜索。
1、5顺序表2-1 设 n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一个人重新开始报数，数到第 m 个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n, s 和 m，求出这n 个人的出局序列。请以 n = 9, s = 1, m = 5 为例，人工模拟 Josephus 的求解过程以求得问题的解。【解答】出局人的顺序为 5, 1, 7, 4, 3, 6, 9, 2, 8。2-2 试编写一个求解 Josephus 问题的函数。用整数序列 1, 2, 3, , n 表示顺序围坐在圆桌周围的
2、人，并采用数组表示作为求解过程中使用的数据结构。然后使用 n = 9, s = 1, m = 5，以及 n = 9, s = 1, m = 0，或者 n = 9, s = 1, m = 10 作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下：void Josephus( int A , int n, s, m ) int i, j, k, tmp;if ( m = 0 ) cout 1; i- ) /*逐个出局，执行 n-1 次*/if ( i = k ) i = 0;i = ( i + m - 1 ) % k; /*寻找出局位置*/if
3、( i != k-1 ) tmp = Ai; /*出局者交换到第 k-1 位置*/for ( j = i; j void inverse ( Type A , int n ) Type tmp;for ( int i = 0; i Type SeqList : DelMin ( ) if ( last = -1 ) /表空, 中止操作返回 cerr Type SeqList : DelNo#i ( int i ) if ( last = -1 | i last ) /表空, 或 i 不合理, 中止操作返回 cerr void SeqList : InsNo#i ( int i, Type& x
4、 ) /表满或参数 i 不合理, 中止操作返回if ( last = MaxSize-1| i last+1 ) cerr = i; j- ) dataj+1 = dataj;datai = x; /插入last+; /表最后元素位置加 1(4) 从顺序表中删除具有给定值 x 的所有元素。template void SeqList : DelValue ( Type& x ) int i = 0, j;while ( i void SeqList : DelNo#sto#t ( Type& s, Type& t ) if ( last = -1 | s = t ) cerr = s & dat
5、ai void SeqList : DelNo#sto#t1 ( Type& s, Type& t ) if ( last = -1 | s = t ) cerr = s ) break; /退出循环时, i 指向该元素if ( i t 的第一个元素if ( datai+j t ) break; /退出循环时, i+j 指向该元素/删除满足条件的元素, 后续元素前移for ( int k = i+j; k SeqList& SeqList : Merge ( SeqList& A, SeqList& B ) /合并有序顺序表 A 与 B 成为一个新的有序顺序表并由函数返回if ( A.Leng
6、th() + B.Length() MaxSize ) cerr void SeqList : DelDouble ( ) if ( last = -1 ) cerr class List; /前视的类定义template class ListNode /链表结点类的定义friend class List; /List 类作为友元类定义private:Type data; /数据域ListNode *link; /链指针域public:ListNode ( ) : link (NULL) /仅初始化指针成员的构造函数ListNode ( const Type& item ) : data (i
7、tem), link (NULL) /初始化数据与指针成员的构造函数ListNode * getNode ( const Type& item, ListNode *next = NULL )/以 item 和 next 建立一个新结点ListNode * getLink ( ) return link; /取得结点的下一结点地址Type getData ( ) return data; /取得结点中的数据void setLink ( ListNode * next ) link = next; /修改结点的 link 指针void setData ( Type value ) data =
8、value; /修改结点的 data 值;template class List /单链表类定义private:ListNode *first, *current; /链表的表头指针和当前元素指针public:List ( const Type /构造函数List ( ) MakeEmpty ( ); delete first; /析构函数void MakeEmpty ( ); /将链表置为空表int Length ( ) const; /计算链表的长度ListNode * Find ( Type value ); /搜索含数据 value 的元素并成为当前元素ListNode * Locat
9、e( int i ); /搜索第 i 个元素的地址并置为当前元素Type * GetData ( ); /取出表中当前元素的值int Insert ( Type value ); /将 value 插在表当前位置之后并成为当前元素Type *Remove ( ); /将链表中的当前元素删去, 填补者为当前元素ListNode * Firster ( ) current = first; return first; /当前指针定位于表头结点Type *First ( ); /当前指针定位于表中第一个元素并返回其值Type *Next ( ); /将当前指针进到表中下一个元素并返回其值int No
10、tNull ( ) return current != NULL; /表中当前元素空否？空返回 1, 不空返回 0int NextNotNull ( ) return current != NULL /当前元素下一元素空否？空返回 1, 不空返回 0;2-6 线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动12改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解
11、答】(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2)
12、如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配
13、解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n 个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。2-7 针对带表头结点的单链表，试编写下列函数。(1) 定位函数 Locate：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若找不到，则函数返回 NULL。(2
14、) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。(3) 统计函数 number：统计单链表中具有给定值 x 的所有元素。(4) 建立函数 create：根据一维数组 an建立一个单链表，使单链表中各元素的次序与 an中各元素的次序相同，要求该程序的时间复杂性为 O(n)。(5) 整理函数 tidyup：在非递减有序的单链表中删除值相同的多余结点。【解答】(1) 实现定位函数的算法如下：template ListNode * List : Locate ( int i ) /取得单链表中第 i 个结点地址, i 从 1 开始计数, i * p = first; int k =
15、0; /从表头结点开始检测while ( p != NULL /循环, p = NULL 表示链短, 无第 i 个结点return p; /若 p != NULL, 则 k = i, 返回第 i 个结点地址(2) 实现求最大值的函数如下：13template ListNode * List : Max ( ) /在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULLif ( first-link = NULL ) return NULL; /空表, 返回指针 NULLListNode * 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 ) /在单链表中进行一趟检测，找出具有最大值的结点地址, 如果表空, 返回指针 NULLi
