subject_45253.htm

一些关于vc的问答

<p>
序号：45253 发表者：蝎 发表日期：2003-06-28 09:31:21
<br>主题：紧急求救&nbsp;&nbsp;c++ 题目
<br>内容：小妹暑假实习，有三道题目实在是做不出来了，这次的老师好厉害，请哥哥姐姐们帮帮忙，先谢谢了：）<BR>要求用C++设计程序，并写出算法思路。请发到 [e-mail] 再次感谢<BR><BR><BR>一 用循环链表实现约瑟夫环。<BR>&nbsp;&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1。问题描述：编号为1，2，。。。，n 的 n 个人按顺时针方向围坐一圈，每人持<BR>有一个密码（正整数）开始任选一个正整数作为报数值 m ,自第一个人开始按顺时针方向自1<BR>开始顺序报数，报到 m 时停止报数，报 m 的人出列，将他持有的密码作为新的 m 值，从它<BR>的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人员不出列为止。编写<BR>完整的程序求出出列的顺序。<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2。具体要求：<BR>（1） 输入：从键盘输入人数 n , n 个人的密码，及初始 m 值。<BR>&nbsp;&nbsp;输入应有提示，输入数据错误应当有出错提示，然后退出。当输入 n 值过大，而<BR>输入的 n 个人整数不够适应有处理措施，将其补够 n 个整数。<BR>（2） 输出：输出最好是写到文件中，将原输入的值 n ，n 个整数，初始 m 值均<BR>写入到文件中，出列顺序也写入到文件中，这样文档编程人员将其插入即可。（调试阶段可以<BR>先输出到屏幕，以便及时看到结果）<BR><BR> 二&nbsp;&nbsp;实现中序后继线索二叉搜索树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1。问题描述：建立一棵有1000个整数结点的中序后继线索二叉搜索树，建立后，不<BR>用递归不用堆栈可以按中序输出（从小到大）结点数据，所有的输出均要求写入文件（包括产<BR>生的1000个原始树序列及编历结果）。<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2。具体要求：<BR>（1）输入数据不要从键盘输入而是由随机函数产生1000个整数（范围1?999），开<BR>始调试时可令少于100个，调好后再加大到1000个。<BR>（2）1000个整数中若有相同整数时（即在二叉搜索树中找到该整数结电），不应产<BR>生写结点而是增加该结点出现次数域,即结点结构如下：<BR>1child&nbsp;&nbsp; num&nbsp;&nbsp;&nbsp;&nbsp; data&nbsp;&nbsp;&nbsp;&nbsp;rtag&nbsp;&nbsp;&nbsp;&nbsp;rchild<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp; 1child&nbsp;&nbsp; num&nbsp;&nbsp; data&nbsp;&nbsp; rtag&nbsp;&nbsp; rchild <BR>&gt; _____________________________________<BR>&gt; |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |&nbsp;&nbsp;&nbsp;&nbsp; |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp; |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|<BR>&gt; |______ |_____|______|_____|________|<BR>&gt;&nbsp;&nbsp;<BR>&gt; (3) 提示：<BR> 1 必须编写一个找某结点后继的算法：nextNode().既访问到达某结点后，根据该结点右<BR>标记rtag的值确定rchild域是后继，还是右孩子？若是右孩子，则必须用选代方法找出该右子<BR>树中的最小结点，即为当前结点的后继。<BR> 2 编写一个插入算法（二叉搜索树的插入算法），但必须修改该算法使其能够维护中序<BR>后继线索。即从空树起每插入一个结点，既要根据其值大小插入到左/右子树/增加已有结点的<BR>出现次数，且若插入了新结点还必须维护线索。<BR> 3 要设一指针变量Thread(线头），保持存放该二叉搜索树中按中序访问到的第一个结点<BR>（data域最小的结点）的地址；这样，当所有输入数据完成后，中序遍历算法是从线头所指结<BR>点起（作为current结点），不断执行：输出当前（current）结点，找后继结点（nextNode)<BR>,成为新的后继结点，直到最后一个结点（rchild为NULL)。<BR> 4 要求用产生的随机数（先存入一个数组）即建立一个线索化的中序后继二叉搜索树，<BR>同时也建立一棵一般的二叉搜索树，然后将搜索树的不递归不设堆栈的中序遍历算法及一般二<BR>叉树搜索树的递归中序遍历(Inorder)算法调用前及调用后加上当前时间变量，得到该算法所<BR>用的具体时间值，对二者加以比较。<BR><BR>&nbsp;&nbsp;三 实现用Disksrta方法求最短路径的算法。<BR><BR>&nbsp;&nbsp; 1。问题描述：从用户指定的顶点为起点，输出该结点到其余各顶点的最短路径长度及其<BR>路径（path）。<BR>&nbsp;&nbsp; 2。具体要求：<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1) 结点数不应少于30。<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2) 可以从键盘或文件输入结点数据：顶点信息，边，权；建议从文件输入，这样可以预<BR>先建立输入文件，调试时不用每次都从键盘输入。<BR><BR>
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：wmf 回复日期：2003-06-28 10:28:12
<br>内容：这是数据结构的典型题目啊<BR>一般数据结构书上都有
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：罗兹维尔 回复日期：2003-06-28 11:26:17
<br>内容：第一题
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：蝎 回复日期：2003-06-28 15:48:35
<br>内容：谢谢了，我书上没找到才来求救的<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：唐炜 回复日期：2003-06-28 20:56:09
<br>内容：什么时候交 ！ ？<BR>可能的话 暑假结束 给你！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：欧阳煊 回复日期：2003-06-29 20:32:10
<br>内容：这几个题我曾经作课设的时候也做过。<BR>不会太难，你自己用心做一下，会有收获的！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>