实验14 基数排序

实验14 基数排序实验14 基数排序姓名:江婷学号:20090810309 班级:计科三班一、需求分析 1( 本程序要求对用户输入一个非负的十进制整数，打印输出与其等值的八进制数。 82( 十进制整数由用户通过键盘输入，其取值范围为(0， 2)。不对非法输入做处理，即假设输入都是合法的。 3( 在Dos界面输出其等值的八进制数。 4( 测试数据输入 1348 输出 2504 二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入。为了实现求模取余法，利用堆栈保存计算的结果。堆...

实验14 基数排序姓名:江婷学号:20090810309 班级:计科三班一、需求分析 1( 本程序要求对用户输入一个非负的十进制整数，打印输出与其等值的八进制数。 82( 十进制整数由用户通过键盘输入，其取值范围为(0， 2)。不对非法输入做处理，即假设输入都是合法的。 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) 输出模块:从堆栈中取数，并显示在屏幕上。三、详细设计物理数据类型 8题目要求输入的正整数的取值范围在(0， 2)之间，为了能够存储，变量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的大小决定，具体来说 k 是要除8几次，即8 >= N。由此可知上述设计的时间复杂度是O(logN)。 8 函数的调用关系图输入十进制数N InitStack //堆栈初始化 Conversion () //进制转换 Push //入堆栈主程序 StackEmpty // 判定栈空 Display () //显示结果 Pop //出堆栈输入和输出的格式输入本程序可以把输入的十进制数转换为八进制的数 //提示请输入十进制的正整数(注意输入的数要小于2100000000)://提示等待输入输出 //提示八进制数数是://输出结果的位置四、调试分析略。五、测试结果略。六、用户使用说明(可选) 1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe 2、运行程序时提示输入本程序可以把输入的十进制数转换为八进制的数请输入十进制的正整数(注意输入的数要小于2100000000): 输出八进制数数是: 七、实验心得(可选) 略。七、附录(可选) conversion.c 主程序 stack.h 堆栈实现(数据结构)

                    本文档为【实验14 基数排序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

实验14 基数排序

你可能还喜欢