数据结构实验指导书(给学生正式1)

目 录 实习步骤    2 实习报告规范    4 实习报告样例1最大公因数    5 实习报告样例2 进制转换    11 DEV C++ 调试方法简介    18 Visual C++6.0调试方法简介    24 预备实验1 字符串处理    28 预备实验2 文件读取    29 预备实验3 随机数生成    30 预备实验4 递归函数    31 预备实验5 字符串数组的查找    32 实验1约瑟夫环问题    33 实验2 逆波兰表达式求值    34 实验3四则运算表达式求值    36 实验4 优先队列与堆    37 实验5 图的遍历问题    39 实验6 最短路径问题    41 实验7 排序    43 实验8 散列表    45 实习步骤 （一）问题和任务定义 在进行之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么。注意：本步骤强调的是做什么？而不是怎么做。 主要完成三个方面的工作： （1） 分析并确定问题要处理的对象（数据）是什么。例如：输入数据的类型、值的范围以及输入的形式。 （2） 分析并确定要实现的功能是什么。也就是说要对输入的数据进行什么样的处理。注意：对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所涉及的数据类型，仅需对所需完成的任务做出明确的定义。 （3） 分析并确定处理后的结果如何显示。 这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；以及相应的输出结果。 （二）数据类型和系统设计 当需求分析结束，明确问题要求后，开始为编写程序设计合适的数据结构和算法。本步骤分概要设计和详细设计两步实现。 概要设计指的是，对问题描述中涉及的操作对象定义相应的抽象数据类型，并设计合适的算法；以及定义程序各个功能模块和模块之间的关系。在这个过程中，要根据问题的功能需求综合考虑，设计时空复杂度最优的抽象数据结构和算法（注意：实现提示和给出的部分代码中以及给出了建议）。抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体，算法思想和过程明确有效，程序结构清晰、合理、简单和易于调试。作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），主要模块的算法思想，并画出模块之间的调用关系图。 详细设计则定义相应的物理存储结构（抽象数据类型的物理实现）并写出各基本操作的伪码算法，以及主要模块算法的具体步骤。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，算法书写规范（采用文字性的步骤描述或者算法流程图的形式都行）。在求精的过程中，应尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。 （三）编码实现和静态检查 在实验过程中，题目中会给出程序的部分源代码，根据实习第二步的设计结果以及源代码的提示，编码实现程序的其余部分。 编码是把详细设计的结果进一步求精为程序设计语言程序。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。 写出编码的程序后，在上机（编译和调试）之前，认真的静态检查是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为纠查错误是编译器的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率是极低的。 静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。 （四）上机准备和上机调试 上机准备包括一下几个方面： （1） 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 （2） 上机调试程序时要带一本高级语言教材或手册。 （3） 掌握调试工具，考虑调试，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。 上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试底层函数。必要时可以另写一个调用驱动程序。这种表面上的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。 在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。 （五）总结和整理实习报告 按照实习报告的格式完成整个实习报告。同时总结和思考，回味设计的过程，体会调试的过程，总结编程中的收获，记录实习过程的体会，交流程序设计各个步骤的心得。“学而不思则罔，思而不学则殆。”在程序设计中，只有做到勤思考、善总结，才能不断进步。 实习报告规范 实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容： 1． 需求分析 以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定： （1） 输入的形式和输入值的范围； （2） 输出的形式； （3） 程序所能达到的功能； （4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2． 概要设计 说明本程序中用到的所有抽象数据类型的定义、算法的基本思想、主程序的流程以及各程序模块之间的层次（调用）关系。 3． 详细设计 （1） 实现概要设计中定义的所有数据类型（物理数据结构），对每个操作只需要写出伪码算法； （2） 算法的具体步骤； （3） 算法的时空分析和改进设想； （4） 画出函数的调用关系图。 （5） 输入和输出的格式。 4． 调试分析 调试过程中遇到的问题，以及如何解决的； 5． 测试结果 根据实验提供的测试数据，列出你所编写的程序的测试结果。 6． 用户使用说明（可选） 说明如何使用编写的程序，详细列出每一步的操作步骤。 7． 实验心得（可选） 对实验设计与实现过程的回顾和分析，以及经验和体会。 8． 附录（可选） 带注释的源程序。如果是提交源程序电子版，只需列出程序文件名的清单。 实习报告样例1最大公因数 背景 因数分解，求最大公因数和公倍数等问题都是数学中古老而又重要德问题，这些问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。 问题描述 两个整数的最大公因数是同时整除二者的最大整数。试设计一个计算两个整数的最大公因数的程序。 基本要求 （1） 用户输入两个正整数，其取值范围为（0， 216）， （2） 要求采用欧几里德算法，计算最大公因数。 测试数据 输入 759        1035 输出 69 实现提示 （1） 注意题目给出的正整数的取值范围，定义变量时，选择合适的数据类型。 （2） 欧几里德算法计算最大公因数，编写成一个独立的函数，并注意该算法对两个数据的大小关系有要求，在设计函数的输入参数以及函数处理代码时要注意处理。 选作内容 （1） 设计一个求取n个正整数的最大公因数的函数。 （2） 如果用户输入的正整数的取值范围为（0, 232）、（0, 264），请设计求取两个大的正整数的最大公因数的函数。 源程序及填空部分 #include “stdio.h” typedef long elemtype; //欧几里德算法计算最大公因数函数 elemtype gcd (elemtype M, elemtype N) { //填空 } main () { elemtype a, b, g; //输入 printf(“\n本程序可以求取两个正整数的最大公因数\n”); printf(“\n请输入第一个正整数（注意输入的数要小于2100000000）：”); scanf(“%ld”, &a); printf(“\n请输入第二个正整数（注意输入的数要小于2100000000）：”); scanf(“%ld”, &b); g=gcd(a, b); //输出 printf(“\n两者的最大公因数是：%ld”, g); } HUNAN  UNIVERSITY 课程实习报告 题    目：   最大公因数                        学生姓名                           学生学号                           专业班级                                  指导老师                                    完 成 日  期                                                              一、需求分析 1． 本程序要求采用欧几里德算法，计算并输出用户输入的两个正整数的最大公因数。 2． 两个正整数由用户通过键盘输入，其取值范围为（0， 216）。不对非法输入做处理，即假设输入都是合法的。 3． 在Dos界面输出最大公因数。 4． 测试数据 输入 759        1035 输出 69 二、概要设计 抽象数据类型 为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，采用欧几里德算法计算两个正整数的最大公因数。该算法的基本思想是辗转相除法。 设两数为a、b（b＜a），求它们最大公约数(a、b)的步骤如下： 1. a ÷ b，令r为所得余数（0≤r＜b） 若 r = 0，算法结束；b 即为答案。 2. 互换：置 a←b，b←r，并返回第一步。 程序的流程 程序由三个模块组成： （1） 输入模块：完成两个正整数的输入，存入变量a和b中。 （2） 计算模块：设计一个最大公因数函数，elemtype gcd (elemtype M, elemtype N)，两个整数作为函数参数，计算结果通过函数名返回。 （3） 输出模块：屏幕上显示计算的最大公因数。 三、详细设计 物理数据类型 题目要求输入的正整数的取值范围在（0， 216）之间，为了能够存储，采用C语言中的长整型定义变量。 typedef long elemtype 算法的具体步骤 欧几里德算法计算两个正整数的最大公因数的算法流程图如下 算法的时空分析 算法的运行时间依赖与确定余数序列有多长。可以证明，在两次迭代后，余数最多是原始值的一半。则迭代次数是2log N＝O(log N)。 输入和输出的格式 输入 本程序可以求取两个正整数的最大公因数    //提示 请输入第一个正整数（注意输入的数要小于2100000000）：//提示 等待输入 请输入第二个正整数（注意输入的数要小于2100000000）：//提示 等待输入 输出 //提示 两者的最大公因数是：//输出结果的位置 四、调试分析 略。 五、测试结果 输入    50    15        输出    5 输入    1989 1590  输出        3 六、用户使用说明（可选） 1、本程序的运行环境为DOS操作系统，执行文件为gcd.exe 2、运行程序时 提示输入两个整数 本程序可以求取两个正整数的最大公因数 请输入第一个正整数（注意输入的数要小于2100000000）： 请输入第二个正整数（注意输入的数要小于2100000000）： 输出 两者的最大公因数是： 七、实验心得（可选） 略。 七、附录（可选） Gcd.c 主程序 实习报告样例2 进制转换 背景 机制转换是计算机实现计算的基本问题。 问题描述 十进制数N和其他d进制数的转换是计算机实现计算的基本问题。请编制一个满足下列要求的进制转换程序。 基本要求 （1） 用户输入一个非负的十进制整数，其取值范围为（0， 216）， （2） 打印输出与其等值的八进制数。 测试数据 输入 1000        输出 1750 实现提示 （1） 利用求模取余法，N＝（N div d）× d ＋ N mod d公式实现。 （2） 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。 选作内容 （1） 设计一个能处理小数的进制转换程序。 （2） 设计一个能处理负数的进制转换程序。 源程序及填空部分 #include #include /*包含动态内存分配函数的头文件*/ typedef int ElemType; typedef struct NodeType { ElemType    data; struct NodeType    *next; }Node; typedef struct { Node * top; int len; }LinkStack; void InitStack(LinkStack *S)//构造一个空栈S。 { S->top=NULL; S->len=0; } int StackEmpty(LinkStack *S)//若栈S为空栈，则返回TRUE，否则返回FALSE { if (S->len == 0) return 1; else return 0;//返回1 表示TRUE    ，否则返回0表示FALSE } int Push(LinkStack *S, ElemType e) //新元素e入栈 { //填空 } int Pop(LinkStack *S, ElemType *e) //栈顶元素出栈，并以e返回其值 { //填空 } void conversion(LinkStack *S, int N) //进制转换，保存（入栈）在S中 { //填空 } void display(LinkStack *S) //输出，把S中元素出栈，并显示 { //填空 } main() { struct LinkStack * LS; int N; int d; LS=(LinkStack *)malloc(sizeof(LinkStack)); //关键的初始化 scanf("%d", &N); InitStack(LS); conversion(LS, N); display(LS); } HUNAN  UNIVERSITY 课程实习报告 题    目：   进制转换                      学生姓名                           学生学号                           专业班级                                  指导老师                                    完 成 日  期                                                              一、需求分析 1． 本程序要求对用户输入一个非负的十进制整数，打印输出与其等值的八进制数。 2． 十进制整数由用户通过键盘输入，其取值范围为（0， 28）。不对非法输入做处理，即假设输入都是合法的。 3． 在Dos界面输出其等值的八进制数。 4． 测试数据 输入 1348 输出 2504 二、概要设计 抽象数据类型 为实现上述程序的功能，应以整数存储用户的输入。 为了实现求模取余法，利用堆栈保存计算的结果。堆栈定义如下： ADT stack 数据对象：整数 基本操作： InitStack（&S）//构造一个空栈S。 StackEmpty（S）//若栈S为空栈，则返回TRUE，否则返回FALSE Push（S，&e）//新元素e入栈 Pop（&S，&e）//栈顶元素出栈，并以e返回其值 算法的基本思想 根据题目要求，用求模取余法，N＝（N div d）× d ＋ N mod d公式实现。 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。 程序的流程 程序由三个模块组成： （1） 输入模块：完成正整数的输入，存入变量N中。 （2） 转换模块：实现求模取余法，余数依次入堆栈中。 （3） 输出模块：从堆栈中取数，并显示在屏幕上。 三、详细设计 物理数据类型 题目要求输入的正整数的取值范围在（0， 28）之间，为了能够存储，变量N采用C语言中的int定义变量。 因为堆栈需存储的元素个数和十进制数N的大小直接相关，其长度变化很大，所以堆栈采用单链表来实现其物理数据结构。堆栈的每个元素只需存储0－8的字符，所以栈中元素类型定义为字符型。 typedef int ElemType typedef struct NodeType { ElemType    data; struct NodeType    *next; }Node; typedef struct { Node * top; int len; }LinkStack; Void InitStack（LinkStack *S）//构造一个空栈S。 { S->top = NULL; S->len=0; } int StackEmpty（LinkStack *S）//若栈S为空栈，则返回TRUE，否则返回FALSE { 若S->len= = 0 //返回1 表示TRUE    ，否则返回0表示FALSE } int Push（LinkStack *S，ElemType e）//新元素e入栈 { //分配新空间，建立一个新结点 L ＝ (Node *) malloc (sizeof(Node)); 若L ＝＝ NULL 返回0表示FALSE；入栈失败 L->data = e; L->next = S->top; //插入 S->top = L; S->len++; 返回1 表示TRUE，入栈成功 } int Pop（LinkStack &S，ElemType *e）//栈顶元素出栈，并以e返回其值 { 若栈空，返回0表示FALSE；出栈失败 *e = S->top->data; L = S->top; S->top = S->top->next；free（L）； S->len--; 返回1 表示TRUE，出栈成功 } 算法的具体步骤 求模取余法流程图如下：函数名conversion(*S, N) 输出的算法（函数Display (*S)）：栈顶元素出栈，转换为字符的Ascii码，然后用字符格式输出。 算法的时空分析 算法的执行，主要是每次N除8，以及入栈，出栈显示，由于采用链表实现，入栈和出栈的时间复杂度都是O(1)，那么进制转换的时间复杂度，主要由N的大小决定，具体来说是要除8几次，即8 k >= N。由此可知上述设计的时间复杂度是O(log8N)。 函数的调用关系图 InitStack //堆栈初始化 输入十进制数N Conversion () //进制转换 Push //入堆栈 主程序 StackEmpty // 判定栈空 Display () //显示结果 Pop //出堆栈 输入和输出的格式 输入 本程序可以把输入的十进制数转换为八进制的数    //提示 请输入十进制的正整数（注意输入的数要小于2100000000）：//提示 等待输入 输出 //提示 八进制数数是：//输出结果的位置 四、调试分析 略。 五、测试结果 略。 六、用户使用说明（可选） 1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe 2、运行程序时 提示输入 本程序可以把输入的十进制数转换为八进制的数 请输入十进制的正整数（注意输入的数要小于2100000000）： 输出 八进制数数是： 七、实验心得（可选） 略。 七、附录（可选） conversion.c 主程序 stack.h      堆栈实现（数据结构） DEV C++ 调试方法简介 一、DEV C++下的调试的几个基本步骤。 1. 把“生成调试信息”设置为 Yes。方法如下： Tools（工具） --> Compiler Options（编译器选项） --> Settings（设置） 2. 编译程序。 程序“编译”编译后会出来这个对话框。 点击“关闭”，关闭该按钮。 3. 设置断点（Break point） 把光标移动到您想暂停执行的那一行，按 ctrl + F5，或者直接用鼠标点击下图红线标明的区域。（如下图） 4. 开始调试（Debug） 按 F8 开始调试，或者点击“调试”选项（ Debug ）后就弹出下拉菜单（如下图）。如果您没有把“生成调试信息”设置为 Yes，Dev-C++ 会提示说您的

工程

路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理

中没有调试信息。点击 Yes，Dev-C++ 会自动把“生成调试信息”设置为 Yes，并且重新编译您的工程。程序运行到断点处会暂停； 按 F7 执行当前行，并跳到下一行； ctrl + F7 跳到下一断点，shift + F4 跳到光标所在行，并在该行设置断点。 注意一点。比如。设置的“断点”是printf语句处。那执行只执行到scanf语句后就不会显示答案了。如下图。 大家看到那蓝条，这是做什么的呢，这是因为设置的“断点”是printf语句后，但又显示不出答案。如果想得到答案。可以按左下角的。“下一步”如下图。 5. 查看变量的值 开始调试后，在图示区域按右键（如果您使用的是左手习惯，则是左键），选择“添加监测（Add Watch）”；或者直接按 F4。在弹出窗口中输入您想查看的变量名，然后按确定（OK），就可以看到该变量的值： 用鼠标选择源文件中的变量名，然后按 F4 也可以查看变量的值，该变量会出现在左边的监测列表中： 如果在环境选项（Environment Options）中选择了“通过鼠标监测变量（Watch variable under mouse）”，用鼠标指向您想要查看的变量一段时间，该变量也会被添加到监测列表中。 重要提示： 1)  当您想查看指针指向的变量的值的时候，按 F4，然后输入星号及指针的名字（如 *pointer）。 如果没加 *，看到的将会是一个地址，也就是指针的值。 2)  有时，调试器（Debugger）可能不知道某个指针的类型，从而不能显示该指针指向的变量的值。此时，我们需要手动输入该指针的类型。按 F4 后，以 *(type *)pointer 形式输入。例如，*(int *)pointer。 6. 最后点击“停止执行”就退出调试了。如下图。 二、调式例子 下面这个程序，编译能正常通过，但是运行时计算结果无法显示，通过调式可以找出存在死循环。 #include #include int main(int argc, char *argv[]) { int i=1, sum=0; while(i<=100) sum+=i; i++; printf("1到100的和是%d\n",sum); system("PAUSE");    return 0; } 上面这个程序是用来计算从1到100之间所有整数之和。该程序在Dev C++可以正常编译通过，如下图。 但是执行时，程序不显示结果。因此，通过调式来找出程序中存在的逻辑问题。 第一步：设置断点。 第二步：设置查看，在调式过程中通过查看变量的值来判断程序中存在的问题。 第三步：按F8调式，程序运行之断点处停止，在断点处开始是红色的，当运行至断点处时变成蓝色。同时可以看到变量的值sum=0和i=1，这是它们的初始值。 第四步：按F7，单步调式，按逻辑，i应等于2，sum应等于1。但我们发现结果是sum=1，而i=1； 第五步：经过多次单步调式，发现i的值不变，sum的值每次多1，同时发现，i++这一行在循环的过程中没有被执行到。因此，可以分析出本程序是一个死循环，故不会输出结果。 第六步：改进程序，得到正确答案。 Visual C++6.0调试方法简介 Visual C++6.0下的调试的几个基本步骤。 1. 首先新建一个C++文件 2. 输入程序： 3. 编译程序。 注意窗口中间上方的编译微型条。将鼠标放在相应位置会显示快捷键。 从左到右依次是编译、组建、中断、组建并执行、调试、设置断点。 编译成功时窗口下方的状态框显示没有错误和警告。 4. 设置断点（Break point） 把光标移动到您想暂停执行的那一行，按 F9，或者直接用鼠标点击右键设置断点。（如下图） 5. 开始调试（Debug） 按 F5 开始调试，或者点击“组建”选项（B）后就弹出下拉菜单（如下图）。程序运行到断点处会暂停；按F11 执行步进调试；ctrl + F10跳到光标所在行，并在该行设置断点。 注意一点。比如，我设置的”断点”是for语句处。那执行只执行到cin语句后就不会显示答案了。如下图。 6. 查看变量的值 在调试窗口的下方我们可以看到各变量的值。 注意: 数组本身是一个指针，所以数组显示的是地址的值、  6．最后点击“停止执行”就退出调试了。如下图。 预备实验1 字符串处理 问题描述 从字符界面输入一串字符串，将其倒置后打印在屏幕上。 基本要求 需要至少两种算法实现之。 测试数据 输入 abcdefg 输出 gfedcba 预备实验2 文件读取 问题描述 从文件中读取数据存储在二维数组中。 基本要求 文件的格式如测试数据所示，第一行的数值表示二维数组的实际行列数（最大不超过500）。 文件中数值都是整数。 从文件中读入后，把二维数组中的内容输出到屏幕上，格式见测试数据。 测试数据 输入（文件） 5 －1  10    3  20  －1 －1  －1  －1  5  －1 －1  2  －1  －1  15 －1  －1  －1  －1  11 －1  －1  －1  －1  －1 输出（屏幕） －1  10    3  20  －1 －1  －1  －1  5  －1 －1  2  －1  －1  15 －1  －1  －1  －1  11 －1  －1  －1  －1  －1 预备实验3 随机数生成 问题描述 生成n个随机数输出在屏幕上，求出这n个数的平均数输出在屏幕上。 基本要求 （1） 输入有一行，只有一个正整数n，表示要生成的随机数个数。 （2） 输出n行，每行一个正整数，是你生成的随机数（1到1000以内）。 （3） 输出1行，一个6位浮点数表示n个随机数的平均数。 （4） 要求有初始化随机数种子，使得程序每次生成的随机数序列不相同。 测试数据 输入（随机数个数n） 10 输出（n个随机数以及它们的平均数） 892 269 382 544 345 227 804 662 38 404 456.700000 预备实验4 递归函数 问题描述 斐波那契数列（Fibonacci Sequence）, 又称为黄金分割数列。 在数学上，斐波那契数列是以递归的方法来定义： F0 = 0 F1 = 1 Fn = Fn - 1 + Fn - 2 基本要求 （1） 要求用递归函数实现斐波那契数列的求解。 （2） 用户键盘输入n，输出斐波那契数列第n个数值（0≤n≤100）。 （3） 用户键盘输入－1，程序结束。 测试数据 请输入n（0≤n≤100）：10 斐波那契数列第10个数值是：55 请输入n（0≤n≤100）：20 斐波那契数列第10个数值是： 6765 请输入n（0≤n≤100）：－1 预备实验5 字符串数组的查找 问题描述 通过键盘输入多个字符串，存储在字符串数组中。然后根据用户输入的字符串，判断是否保存在数组中，如果保存了，输出在数组中的位置，如果未保存，将其加入数组中。 基本要求 （1） 录入格式如测试数据所示，第一行的数值表示字符串的个数（最大不超过100）。 （2） 输入quit字符串，表示查询结束。 测试数据 //字符串录入 4 a ans and hellocpp 请输入查找字符串：and 找到。在数组中第二个位置。 请输入查找字符串：kkk 未找到。已经添加到数组的第五个位置。 请输入查找字符串：quit 实验1约瑟夫环问题 背景 约瑟夫问题（Josephus Problem）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。   原题：  用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人 求最后一个剩下的人是几号？ 问题描述 设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列口。 基本要求 需要用线性表的基本操作来实现约瑟夫问题 需要利用数组来实现线性表 输入输出格式 输入格式：n，m 输出格式1：在字符界面上输出这n个数的输出序列 输出格式2：将这n个数的输出序列写入到文件中 选做内容 （1） 使用单链表来实现之 （2） 使用循环链表来实现之 测试用例 输入：10，3 输出：3  6  9  2  7  1  8  5  10  4 课后习题 请以O（n）的时间复杂度来实现约瑟夫问题。 实验2 逆波兰表达式求值 背景 表达式求值是程序设计语言编译中的一个最基本的问题．因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。 通常，我们所说的表达式是由运算符、操作数、界限符所组成。而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。 1、中缀表达式———将运算符放在两操作数的中间。在运算中存在运算符的优先权与结合性的问题。例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符“*”时还无法知道是否执行；待检查到第二个运算符“ + ”时，因为知道“*”的优先级别高于“ + ”时，才知道执行“a*b”；当继续检查到“ ( ”时，可知道先执行括号以内部分等。 2、前缀表达式———将运算符放在两操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家—Jan Lukasiewicz，这种表示法也称波兰表示法。 3、后缀表达式———将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。 前缀和后缀表示法有三项公共特征： （1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致 （2） 不需要括号 （3） 操作符的优先级不相关 问题描述 读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。 基本要求 （1）从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。 （2）用堆栈来实现 输入输出格式 输入： 在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。以“#”表示结束。 输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。 选作内容 （1） 在输入和输出方式上发生改变： 输入：将后缀表达式存于文本文件中，其中后缀表达式中两相邻操作数之间利用空格隔开，程序从该文本文件中读出表达式。 输出：如果该后缀表达式正确，则计算结果，计算结果保留小数点后面两位有效数字，同时将结果输出到该文件中原表达式的后面，结果与表达式之间用“=”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。 （2） 表达式中操作数为一实数，该实数精确到小数点后面两位有效数字。 测试用例 输入：2 3 * 1 –# 输出：5 课后习题 n个元素｛1,2…,n｝有n!个不同的排列。将这n！个排列按字典序列排列，并编号为0，1,…,n!-1.每个排列的编号为其字典序值。例如，当n=3时，6个不同排列的字典序值如下： 字典序值 0 1 2 3 4 5 排列 123 132 213 231 312 321               请编程实现之。 实验3四则运算表达式求值 背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。 问题描述 四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。 基本要求 (1) 使用二叉树来实现。 实现提示 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 输入输出格式： 输入：在字符界面上输入一个中缀表达式，回车表示结束。 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 选作内容 （1）在输入输出方式上要求使用： 输入：将中缀表达式存于文本文件中，程序从该文本文件中读出表达式。 输出：如果该中缀表达式正确，则将后缀表达式输出到该文件中原表达式的后面，它们之间用“---”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。 (2) 利用堆栈来实现中缀表达式转换为后缀表达式。 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 课后习题 采用非递归的编程方法分别统计二叉树的节点个数度为1和叶子节点的个数以及数据值的最大值和最小值。 实验4 优先队列与堆 背景 优先级队列（priority queue）就是遵循两个排序规则的集合。首先，具有高优先级的项目在先。第二，具有相同优先级的项目使用先进先出方法来确定其排序。 用到优先队列的地方：凡是需要取出集合中最值元素的地方。 ● 构建霍夫曼编码 构建霍夫曼编码需要找到结点集合中频率最小的两个结点。然后合并结点插入到集合。依次循环。 ● 一些任务调度算法 比如操作系统中线程调度算法，有的是按照优先级来调度的，每次都执行优先级最高的线程。 ● 合并n个有序文件为一个有序文件。 首先把n个有序文件的第一个元素都提取出来，放入优先队列中，然后取出最小的元素。然后再插入元素到优先队列，在取出最小元素。 ● 由于优先队列内部一般是采用堆实现的，所以，所有适用于堆得算法，都适用于优先队列。比如，排序，找中位数，找最大的K个数等。 可以以很多方式实现优先队列，比如链表、二叉查找树。但从时空复杂度优化的角度来看，对于优先队列最普遍的实现是堆。堆的意义就在于：最快的找到最大/最小值，在堆结构中插入一个值重新构造堆结构，取走最大/最下值后重新构造堆结构，其时间复杂度为O(logN)，而其他方法最少为O(N)。 问题描述 假设某医生看病人的顺序是由病人的病情严重程度来决定。护士按照所有病人来医院的时间顺序给病人编号ID，依次为1，2，3，…，n；并且根据病人的病情严重程度设置Priority值，病越重，Priority的值越小。当医生开始工作时，护士根据病人的Priority值，由小到大依次安排病人看病。试为护士编写程序安排病人看病的先后次序。 基本要求 （1） 利用最小值堆实现一个优先队列。 （2） 对于优先队列应该支持如下操作：初始化队列的init操作；获得队列中元素个数的size操作；判定队列是否为空的empty操作；获得队列中最优先的元素的值的top操作；向队列中插入一个元素的push操作；删除队列中最优先的元素的pop操作。 （3） 利用优先队列存入所有病人的信息（编号和病情严重程度）。最后利用优先队列获得病人看病的次序。 测试数据 输入 1 15 2 3 3 5 4 20 5 10 －1  －1 输出 2 3 5 1 4 实现提示 （1） 最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，包含编号ID和病情严重程度Priority值。 （2） 用户录入－1  －1表示输入结束。 选做内容 （1） 为优先队列添加一个改变某个元素优先级的操作。 （2） 设计一个最大值堆的优先队列。 （3） 如果允许不同病人设置相同的Priority值，那么当出现优先队列中有多个病人具有最优先的Priority值时，先到医院的病人先出队列看病，请思考如何修改程序以满足这种要求。 课后题目 （1） 写一个在一百万个数字中求最大的10个数字的算法。（提示：基于堆的算法是一个较好的解决方案，构建最大值堆，取得第一个元素，然后循环10次即可达到题目要求。） 实验5 图的遍历问题 背景 网络蜘蛛即Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网 站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。这样看来，网络蜘蛛就是一个爬行程序，一个抓取网页的程序。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下面这张简单化的网页连接模型图所示，其中A为起点 也就是蜘蛛索引的起点）。 深度优先顾名思义就是让网络蜘蛛尽量的在抓取网页时往网页更深层次的挖掘进去 讲究的是深度!也泛指: 网络蜘蛛将会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接! 则访问的节点顺序为==> A --> B --> E --> H --> I --> C  --> D --> F --> K --> L --> G。深度爬行的优点是:网络蜘蛛程序在设计的时候相对比较容易些；缺点是每次爬行一层总要向"蜘蛛老家" 数据库访问一下。问问老总有必要还要爬下一层吗! 爬一层 问一次.... 如果一个蜘蛛不管3721不断往下爬 很可能迷路更有可能爬到国外的网站去，不仅增加了系统数据的复杂度更是增加的服务器的负担。 广度优先在这里的定义就是层爬行，即一层一层的爬行， 按照层的分布与布局去索引处理与抓取网页。则访问的节点顺序为==> A --> B --> C --> D --> E --> F --> G --> H --> I--> K --> L。广度爬行的优点是对数据抓取更容易控制些，对服务器的负栽相应也明显减轻了许多。 问题描述 若用有向网表示网页的链接网络，其中顶点表示某个网页，有向弧表示网页之间的链接关系。试设计一个网络蜘蛛系统，分别以广度优先和深度优先的策略抓取网页。 基本要求 （1） 首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。 （2） 输出从首个顶点开始的广度优先遍历序列和深度先遍历序列。 测试数据（以背景描述的图为例） 输入 输入顶点数和弧数:8 9 输入8个顶点. 输入顶点0:a 输入顶点1:b 输入顶点2:c 输入顶点3:d 输入顶点4:e 输入顶点5:f 输入顶点6:g 输入顶点7:h 输入9条弧. 输入弧0:a b 1 输入弧1:b d 1 输入弧2:b e 1 输入弧3:d h 1 输入弧4:e h 1 输入弧5:a c 1 输入弧6:c f 1 输入弧7:c g 1 输入弧8:f g 1 输出 广度优先遍历: a b d h e c f g 深度优先遍历: a b c d e f g h 实现提示 （1） 设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。 （2） 此题为求有向图的遍历问题，采用邻接表存储图，实现图的基本操作，并编写DFS和BFS程序。 选做内容 使用邻接矩阵存储图，编写DFS和BFS程序。 课后题目 求图的最大连通子图。 实验6 最短路径问题 背景 乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？ 这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。 问题具体的形式包括： ● 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。 ● 确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 ● 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。 ● 全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。 问题描述 若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。 基本要求 （1） 从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。 （2） 以用户指定的起点和终点，输出从起点到终点的花费。 测试数据 输入 （文件） 5 －1  10    3  20  －1 －1  －1  －1  5  －1 －1  2  －1  －1  15 －1  －1  －1  －1  11 －1  －1  －1  －1  －1 （用户） 起点 0 终点 4 输出 18 实现提示 （1） 设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。 （2） 此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。 （3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。 （4） 考虑没有路径时的输出。 选作内容 （1） 以用户指定的起点，输出到其它各点的花费。 （2） 以用户指定的起点和终点，输出从起点到终点的花费以及路径（经过的中间顶点）。 课后题目 全局最短路径问题，求图中所有点对的最短路径。（提示：使用Floyd-Warshall算法） 实验7 排序 背景 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为  { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn }的操作称作排序。 排序算法是计算机科学中最重要的研究问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。 例1：有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支票的号码对支票排序； 例2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。 例3：在一个由n个数构成的集合上，求集合中第i小/大的数。 例4：对一个含有n个元数的集合，求解中位数、k分位数。 问题描述 在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。 只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。 基本要求 （1）数据的输入输出格式： 输入： 第一行是一个整数n，代表任务的件数。 接下来一行，有n个正整数，代表每件任务所用的时间。 输出： 输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。 （2）使用快速排序，轴值采用随机数确定。 测试数据 输入 9 5 3 4 2 6 1 5 7 3 输出 1 2 3 3 4 5 5 6 7 实现提示 （1）将n个正整数排序后依次输出即可。 （2）需调用srand()，才能让每次的随机数不一样。 选做内容 若采用并行操作系统，一次可同时处理两件任务，求让所有任务等待的时间和最小的任务处理顺序。 课后题目 给出一个能列出某一集合的k分位数的O(nlogk)的算法。 实验8 散列表 背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。 例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。 问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。 为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。 基本要求 （1） 根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 测试数据 输入： 4 a ans and hellocpp 9 a b an as ans and ande hellocbb hellocpp 输出： YES NO NO NO YES YES NO NO YES 实现提示 （1）冲突处理方法为：顺次循环后移到下一个位置，寻找空位插入。 （2）BKDE 字符串哈希 unsigned int hash_BKDE(char *str) { /* 初始种子 seed 可取31 131 1313 13131 131313 etc.. */ unsigned int seed = 131; unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } 将字符串哈希到小于2^31的整数 t，再将t用随机数哈希法映射到 2^15以内的数。 选做内容 每一种西文图书都有一个国际

标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载

图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，采用折叠法构造一个四位数的哈希函数。 课后题目 实现文本LZW压缩和解压缩。