信管软件11级数据结构课程设计(8)

37．设计程序完成如下功能：对给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树，并给出求解过程的动态演示。（难易度95） 说明：可以使用实验工具中的有关功能。

38.（马的遍历问题）：设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。（难易度95） 要求：

（1）依次输出所走过的各位置的坐标。

（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。 （3）程序能方便地地移植到其它规格的棋盘上。

39 长整数运算

[问题描述]

设计一个程序实现两个任意长的整数求和运算。

[基本要求]

利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是 -（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

[测试数据]

（1） 0；0；应输出“0”。

（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。

（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 （4） 1,0001,000；-1,0001,0001；应输出“0”。 （5） 1,0001,0001；-1,0001,0000；应输出“1”。

[实现提示]

（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。

（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。

[选作内容]