解决美猴王选择问题并构建二叉树——课程设计报告

2023-09-02 1643阅读

《数据结构》课程设计———————————————————————————————————————————————— ————————————————————。课程设计是学生在课程中所学知识的综合运用。《数据结构》是一门实践性课程，其中算法设计和编程的掌握尤为重要。新世纪需要培养具有丰富科学知识、独立解决实际问题、具有创造力的新型人才，这也是课程设计的最终目标。猴子即将离开圆圈，依次类推，直到圆圈中只剩下最后一只猴子，则猴子为王。设计一个基于菜单的界面，允许用户选择要解决的问题并同时退出程序。基于这个思想，递归调用函数构建二叉树。

《数据结构》课程设计———————————————————————————————————————————————— ————————————————————

计算机科学与技术专业

班级

导师

撰写日期：2012 年 6 月 24 日

一、课程设计目的（三）

2.课程设计要求（3）

3.相关知识（3）

四、问题分析（3）

5.数据结构说明（4）

6.算法设计（4）

七、代码实现（6）

8、程序运行成功演示（11）

九。经验 (14)

10. 参考文献 (14)

一、课程设计的目的

课程设计是学生在课程中所学知识的综合运用。与课堂讲授、计算机实验、课外练习、自学研究等相辅相成，形成完整的课程教学体系。《数据结构》是一门实践性课程，其中算法设计和编程的掌握尤为重要。学生虽然可以通过与课堂教学同步的计算机实验来完成相关内容的练习，但往往局限于一些功能简单、相互之间独立关系的算法和程序。课程设计是一种综合训练，致力于培养学生全面灵活的算法设计思想和较高的编程能力，为未来的计算机开发和应用奠定基础。新世纪需要培养具有丰富科学知识、独立解决实际问题、具有创造力的新型人才，这也是课程设计的最终目标。

2. 课程设计要求

1.孙悟空选择问题描述

一群猴子被编号，编号是1、2、3……米。这组猴子（m）按照1米的顺序围成一圈，从第1只开始数，一直数到第n只。猴子即将离开圆圈，依次类推，直到圆圈中只剩下最后一只猴子，则猴子为王。

2、二叉树的建立说明

给定二叉树T中节点的先序和中序遍历序列，编写算法构造满足上述条件的二叉树。

3、界面设计模块问题描述

设计一个基于菜单的界面，允许用户选择要解决的问题并同时退出程序。界面要求简洁、清晰、得体、易于用户使用。同时，可以有效处理用户的错误选择。

3.相关知识

1.解决孙悟空选择

约瑟夫斯戒指的问题是由古罗马历史学家约瑟夫斯提出的，他参与并记录了公元66-70年犹太人反抗罗马的起义。作为一名将军，约瑟夫成功地占领了犹大伯特城 47 天。城陷后，他和40名顽固士兵躲到附近的一个山洞里。在那里，叛军投票“投降或死亡”。于是约瑟夫建议大家轮流杀掉旁边的人，顺序是通过抽签决定的。约瑟夫有预谋地夺取了最后一批，并作为山洞中的两名幸存者之一，说服了他最初的受害者向罗马投降。

约瑟夫环问题的具体描述是：假设编号为1,2,...,n的n(n>0)个人围成一个圈，从第一个人开始计数，报m时停止计数，然后m个报告m的人走出圈子，然后从下一个人开始重新计数。当m被举报时停止计数，举报m的人离开圈子，……，以此类推，直到所有人都出圈。当n和m任意给定时，设计一个算法，求n的顺序人们离开圈子

2.二叉树的建立

二叉树的存储结构是二叉链表

C语言

二叉树遍历

四、问题分析

1.美猴王选择问题分析

通过问题的文字描述，首先可以将问题简化为一个简单的线性序列列表，然后通过顺序查找删除需要的元素。不过，由于该题需要循环计数，因此需要将这个线性序列表转化为循环链表。，通过指针连接表头和表尾，然后通过指针计数导出要删除的元素，最后通过重复操作将元素一个一个删除，得到最后一个想要的元素，这就是孙悟空。

2.二叉树的建立

由于需要根据二叉树中节点的中序和后序来遍历序列，因此建立的二叉树采用二叉链表的存储结构

存储并输出二叉树的前序遍历序列，所以我们首先以后序遍历序列的最后一个节点为根节点开始，然后找到中序遍历序列中的字符，然后左边和右边分别是左子数和右子数。字符序列。基于这个思想，递归调用函数构建二叉树。但前序遍历是先遍历根节点，再遍历左右词数。我们只需编写相关的函数调用即可。

5. 数据结构说明

typedef 结构 Lnode{

整数数据；

结构Lnode *下一个;

}linklist;//单链表解决了猴子选王时存储节点信息的问题

typedef 结构节点{

字符数据；

结构节点*lch,*rch;

}BTNode,*BTree;//二叉链表存储树的表示

6. 算法设计

1、程序功能模块图

程序功能模块图

2. 算法设计

(1)猴子选择问题

头 = (linklist*) malloc(sizeof(linklist)); /* 创建一个循环链表，头节点也存储信息*/

p = 头；

p->数据=1；

p->下一个 = p;

对于 (i = 2; i 数据 = i;

s->下一个 = p->下一个；

p->下一个=s；

p = p->下一个；

} /* 初始化循环链表 */

p = 头；

for (i = 1; i < k; i++){

p = p->下一个；

} /* 找到第k个节点 */

总计 = n； /* 保存节点总数 */

printf("\n输出序列是：");

q = 头；

while (total != 1) /* 当只剩下一个节点时停止循环*/

for (i = 1; i < m; i++){

p = p->下一个；

} /* 计数过程，p指向要删除的节点*/

printf("[%d] ", p->data);/*打印要删除的节点序号*/

while (q->下一个！= p){

q = q->下一个；

}/* q 指向 p 节点的前驱 */

q->下一个 = p->下一个； /* 删除p节点*/

s = p； /* 保存删除的节点指针 */

p = p->next;/* p指向被删除节点的后继*/

free(s);/* 释放已删除的节点*/

全部的 - ; /* 节点数减一*/

(2)二叉树的创建

void create(BTree *t,int instart,int inend,int poststart,int postend) {int i;

if(inend>=instart&&postend>=poststart)

*t=(BTree)malloc(LEN);

(*t)->data=post[postend];

我=开始；

while(pin[i]!=post[postend])i++;

if(i==开始)

(*t)->lch=NULL;

别的{

创建(&(*t)->lch,instart,i-1,poststart,poststart+i-1-instart);

/*左子树中序的起点就是整棵树的起点*/

/* 终点为根节点的前i-1 */

/* 后序起点是整棵树的后序起点poststart*/

/* 后序列终点为后序列起点加上左子树节点数减一： */

/* 启动后+(i-1-启动+1)-1*/

if(i==inend)

(*t)->rch=NULL; /*如果根位于中序序列的最后一个右空*/

别的

创建(&(*t)->rch,i+1,inend,poststart+i-instart,postend-1);

/*右子树的中序起点是根的下一个i+1*/

/* 终点为整个树序inend的终点inend*/

/* 后序的起点是左子树后序结束点的下一个 poststart+i-1-instart+1*/ /* 结束点是除根之外的最后一个节点，即倒数第二个节点*/

别的

*t=NULL;

7. 代码实现

#include“stdafx.h”

＃包括

#定义 EL 10

#定义电话2*EL+1

#define LEN sizeof(结构节点)

无效欢迎（）{

printf(" ******** 欢迎来到我们的系统 ********\n"); printf("********\n");

printf(" **** ****\n");

printf(" ** **\n");

printf(" ** ∩∩ **\n");

printf(" ** **\n");

printf(" ** O **\n");

printf(" ** **\n");

printf(" ** _______ **\n");

printf(" **** ****\n");

printf(“**************************************************** * ***\n"); printf(" * * *\n");

printf(" * * *\n");

printf(" * ************************** *\n");

printf(" * **1.美猴王精选** *\n");

printf(" * ************************** *\n");

printf("* *\n");

printf("**************** ************\n");

printf(" **2.二叉树** **3.退出**\n");

printf("**************** ************\n");

/* 下面是二叉树的程序*/

char post[TEL]="CEDBHGJIFA";

char pin[TEL]="CBEDAGHFJI";

typedef 结构节点

{ 字符数据；

结构节点*lch,*rch;

}BTNode,*BTree;

BT节点根；

BTree rt=&root;

void create(BTree *t,int instart,int inend,int poststart,int postend)

{int 我;

if(inend>=instart&&postend>=poststart)

*t=(BTree)malloc(LEN);

(*t)->data=post[postend];

我=开始；

while(pin[i]!=post[postend])i++;

if(i==开始)

(*t)->lch=NULL;

别的{

创建(&(*t)->lch,instart,i-1,poststart,poststart+i-1-instart);

/*左子树的中序起点就是整棵树instart的中序起点*/

/* 终点为根节点的前i-1 */

/* 后序起点是整棵树poststart的后序起点*/

/* 后序的终点是后序的起点加上左子树节点数减一： */

/* 启动后+(i-1-启动+1)-1*/

if(i==inend)

(*t)->rch=NULL; /*如果根是中序序列最后一个右边的空值*/

别的

创建(&(*t)->rch,i+1,inend,poststart+i-instart,postend-1);

/*右子树的中序起点是根的下一个i+1*/

/* 终点是整棵树的终点inend */

/* 后序的起点是下一个poststart+i-1-instart+1*/

/* 终点是除根之外的最后一个节点，即倒数第二个节点 */

别的

*t=NULL;

无效旅行（BTree t）

{如果（t）

putchar(t->数据);

旅行（t->lch）；

旅行（t->rch）；

无效二进制 (){

printf("********************************欢迎二叉树**************** **** **********************\n"); printf("小组成员：PPT发言：张琪\n");

printf("\n");

printf("数据采集：石方\n");

printf("\n");

printf("程序编译器：陈小健\n");

printf("\n");

printf("后缀为：CBEDAGHFJI\n");

printf("中间序列是：CEDBHGJIFA\n");

printf("输入任意字符查看预购顺序：");

getch();

创建(&rt,0,9,0,9);

如果（rt）旅行（rt）；

/* 下面是猴子选择国王的过程*/

typedef 结构 Lnode{

整数数据；

结构Lnode *下一个;

}linklist;/* 定义链表节点类型*/

int mokeyking(){

int i、n、k、m、总计；

链接列表*head、*p、*s、*q；

printf("\n");

printf("************************欢迎美猴王

SLECT****************************\n");

printf("小组成员：PPT演讲：卢光跃\n");

printf("\n");

printf("数据采集：楼兵\n");

printf("\n");

printf("程序编译：龙其昌\n");

printf("\n");

printf("请输入猴子的数量n:");

scanf("%d", &n);

printf("请输入开始数k的猴子数量：");

scanf("%d", &k);

printf("请输入呼出号码m:");

scanf("%d", &m); /* 读入问题条件 */

头 = (linklist*) malloc(sizeof(linklist)); /* 创建一个循环链表，头节点也存储信息*/ p = head;

p->数据=1；

p->下一个 = p;

对于 (i = 2; i 数据 = i;

s->下一个 = p->下一个；

p->下一个=s；

p = p->下一个；

} /* 初始化循环链表 */

p = 头；

for (i = 1; i < k; i++){

p = p->下一个；

} /* 找到第k个节点 */

总计 = n； /* 保存节点总数 */

printf("\n输出序列是：");

q = 头；

while (total != 1) /* 当只剩下一个节点时停止循环*/

for (i = 1; i < m; i++){

p = p->下一个；

} /* 计数过程，p指向要删除的节点*/

printf("[%d] ", p->data);/*打印要删除的节点序号*/

while (q->下一个！= p){

q = q->下一个；

}/* q 指向 p 节点的前驱 */

q->下一个 = p->下一个； /* 删除p节点*/

s = p； /* 保存删除的节点指针 */

p = p->next;/* p指向被删除节点的后继*/

free(s);/* 释放已删除的节点*/

全部的 - ; /* 节点数减一*/

printf("\n\n孙悟空是数字[%d]\n\n", p->data); /* 打印最后剩余的节点号*/ free(p);

//系统(“暂停”);

返回0；

int _tmain(int argc, _TCHAR* argv[])

整数a;

欢迎（）;

printf("请选择函数：");

scanf("%d",&a);

而（a！= 3）{

开关（一）{

情况1：系统（“cls”）；莫基金（）； getch();中断;

案例2：系统（“cls”）；二进制 (); getch();中断;

默认值： printf("请选择正确的选项！");break;

系统（“cls”）；

欢迎（）;

printf("请选择函数：\n");

scanf("%d",&a);

返回0；

8. 程序运行成功演示

1、主键面

2. 输入1

3、输入23只猴子，从第一只开始数，每次数到5就出局

4. 按任意键返回主键面输入2

5. 按任意键

6. 按任意键返回主键面输入3

7.退出程序

9. 经验

1、孙悟空选择问题

设计是培养和提高我们对所学知识的中和运用能力，锻炼我们解决实际问题的能力，检验和提高学生的实际工作能力。

从拿到题目到完成整个编程，从理论到实践，在一个多星期的时间里，我学到了很多课堂上听不懂的东西，巩固了之前学过的知识，能够结合起来理论与实践。通过与实践的结合，我提高了自己的动手能力和独立思考能力。我在设计过程中发现了自己的不足并做了一些改进。总的来说，通过这次课程设计，我不断完善了方案。同时，这也是自我不断完善的过程。非常感谢学校给我这次课程设计的机会。

2.二叉树的创建

从本次课程设计中，我们了解了二叉树遍历的重要性，以及前序遍历、中序遍历、后序遍历的相关算法。我们理解二叉树是一种重要的数据结构，也是一种很好的编程思想。它有很多功能。通过本课程设计，可以将理论知识与实践相结合，实现方案。通过查阅资料，丰富了以前遗漏的知识。同时丰富了之前遗漏的知识，了解了算法在编程中的作用。重要的是，好的算法可以极大地优化程序

通过本次课程设计，我们学会了如何从一个实际问题出发，建立模型，找到相应的存储结构和实现方法，实际运行，反复调试修改，最终实现功能。接受编程方法、计算机操作等基本技能和科学作风的较为系统、严格的训练。学习如何组织数据、在计算机内部表达现实世界中的实际问题以及使用软件解决问题，培养良好的技能。编程技能。

10. 参考文献：

[1]朱蓉. 数据结构实验指导

[2]蔡子敬，石伯乐。数据结构教程。上海：复旦大学出版社。 1994年

[3] 严伟民，吴伟民。数据结构（C语言版）。北京：清华大学出版社。 1997；

[4] 严伟民，吴伟民。数据结构习题集（C语言版）。北京：清华大学出版社。 1997；

[5]孟嘉娜，胡晓坤。算法和数据结构实验和练习。北京：机械工业出版社。 2004年。

会计期间期初余额试算不平衡怎么办？

有贷必有贷，贷必对等。这就是会计规则。如果出现不平衡，就会出现100%凭证不齐或会计错误。

查找账户方法：

1、检查前期科目汇总表是否平衡；

2.看区别。如果能被9整除，记账时数字就倒过来。例如，79记录为97，相差18。

3.查找上一期，直到发现错误，改正，就完成了。

会计试算表不平衡的原因是什么？

答案：过账错误总账过账错误是试算表不平衡的主要原因。一般情况下，总账核算基础上的错误可以通过其自身的余额验证方法或其他手段来发现，而总账过账的错误，则只能通过试算表的方式来检查。

编制错误编制试算表时，需要从总账中获取各科目的借方总额和贷方总额。如果在编制表格时使用了错误的数字或写错了，试算表就会不平衡。

计算误差主要来自两个方面：一是总账本期借方总额或贷方总额计算时的汇总误差；二是试算表各科目借方总额和贷方总额的计算在汇总时出现了汇总误差。

一般情况下，总账登记依据的错误能够被会计人员及时发现。例如，会计凭证汇总和汇总会计凭证中的错误可以通过计算表格上借方和贷方的总会计数来验证。。

此外：

1.如果仔细查找，就会发现不平衡的地方。

1.找出数据错误的受试者。如果试算不平衡，则无法激活账户集。

2、可以用期末余额减去期初余额，根据期初数据检查是否存在录入错误。

3、检查损益科目期初数据和期间数据输入是否正确。

4、可以检查利润分配科目是否有错误。

2、期初试算表不平衡，因期初余额不平衡而无法入账，会计处理后的报表仍不平衡。

首次使用会计处理子系统时，应将已分类的手工账户的期初余额输入计算机。企业于年初建账的，录入的期初余额为期初余额。企业若在年中建账，应输入建账当月的期初余额以及年初至今借款人和债权人的累计金额，系统自动计算余额今年年初。

例如，某企业于2000年4月开始使用总账系统，则应计算2000年3月末各科目期末余额以及1月至3月累计发生额，准备录入总账系统。账户作为系统的开通数据。在业务处理子系统中，系统会自动计算年初余额；如果该科目有辅助核算，还应将各辅助项目的期初余额进行整理，以便计入期初余额。

期初余额不平衡怎么办

期初余额不平衡主要涉及财务软件期初数据不平衡如何处理，如下：

1、首先要看录入期初余额的相关数据能否保证贷款余额。

2、检查录入数据的借方余额与科目余额表数据是否一致。

3. 检查系统中输入的数据有多少差异。财务软件初始数据不相等怎么办，是否有相关数据可查。

4、设定账户的借方和贷方是否正确。

5、明细账财务软件的期初数据不一致怎么办，如应收账款、存货等，检查二级科目是否录入正确。

期初余额分录中总账和辅助账不一致怎么办？

建议检查一下财务软件的开户数据参差不齐怎么办，并仔细审核凭证，看是否有缺失的凭证，盈亏结转是否已转，是否有新的账户明细项目结转损益时不进行检查。 1、首先检查总账和辅助科目中的期初数据试算在期初余额数据中是否平衡； 2、然后检查涉及的财务软件的凭证是否有错误。如有不符，解决方法：取消全年结账的结账标记，将所有凭证恢复为未记账凭证，从年初开始，每月记录一个月，对账，再记录一个月如果是正确的，最后你会发现问题出在哪里？ 3、还有本月某个会计科目的【辅助会计】是否有修改。如果科目已经有数据，而科目的辅助核算被修改，那么很可能会导致总账和辅助账之间出现问题。和解

一般是上年不平衡造成的，中途将补充会计添加到科目中。方法一：（1）取消账户辅助核算，将预付款项期初余额改为明细总额。（2）重新链接辅助核算，然后将对应的明细期初添加到预付款科目的供应商交易期初，该科目的总账期初将自动汇总。方法二：（1）删除供应商预付账款的期初明细，然后取消会计科目中预付账款的辅助核算。（2）回到期初余额界面，将预付账户的期初记录为0。然后重新将账户链接至该交易的辅助会计，并输入辅助会计的期初余额

输入总账辅助期初余额时，系统会自动为设置为辅助核算的科目打开辅助科目页面。相应地，在录入期初余额时，该类科目的总账期初余额是从辅助科目的期初明细中汇总而来的，即不能直接录入总账期初余额；对于没有辅助会计的科目，可以直接录入期初余额。

一般使用“用友财务软件”录入，录入流程如下： 1、首先点击“总账”-“设置”，选择“期初余额”； 2、之后弹出“期初余额录入”对话框； 3、直接点击空白根据企业实际情况，输入企业会计科目期初余额即可； 4、输入后点击上方“试算”即可查看试算余额； 5. 如果出现“试算结果不平衡”，则需要检查原因，录入是否有错误，否则会影响以后的操作。 6. 如果出现“试算结果平衡”，则说明输入的数据有误。表示期初余额录入已平衡，操作完成。

以上就是关于如何处理财务软件初始数据不均匀以及财务软件初始数据录入后不均匀的全部内容。作为一名会计师，你学会了吗？如果还有疑问，可以在下方评论，小编会不定期回复。

VPS购买请点击我

解决美猴王选择问题并构建二叉树——课程设计报告

相关阅读

纹身为什么不能纹眼睛？

张伟为什么叫张益达？

纹身为什么会上瘾？

黑人为什么不吃巧克力？

目录[+]