示例：数据结构实验——基本运算流程图

示例：数据结构实验——基本运算流程图

《数据结构》课程组

供“数据结构”实验及实验报告撰写参考

1、线性表基本运算流程图的一种参考设计

2、栈基本运算流程图的一种参考设计

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

数据结构习题(456章)

第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

计算机组成原理 实验一 运算器组成实验

实验一运算器组成实验 一、实验目的 1．熟悉双端口通用寄存器堆的读写操作。 2．熟悉简单运算器的数据传送通路。 3．验证运算器74LS181的算术逻辑功能。 4．按给定数据，完成指定的算术、逻辑运算。 二、实验电路 S3 S2 S1 S0 M 图3.1 运算器实验电路 图3.1示出了本实验所用的运算器数据通路图。参与运算的数据首先通过实验台操作板上的八个二进制数据开关SW7-SW0来设置，然后输入到双端口通用寄存器堆RF中。 RF(U54)由一个ispLSI1016实现，功能上相当于四个8位通用寄存器，用于保存参与运算的数据，运算后的结果也要送到RF中保存。双端口寄存器堆模块的控制信号中，RS1、RS0用于选择从B端口（右端口）读出的通用寄存器，RD1、RD0用于选择从A端口（左端口）读出的通用寄存器。而WR1、WR0用于选择写入的通用寄存器。LDRi是写入控制信号，当LDRi＝1时，数据总线DBUS上的数据在T3写入由WR1、WR0指定的通用寄存器。RF的A、

B端口分别与操作数暂存器DR1、DR2相连；另外，RF的B端口通过一个三态门连接到数据总线DBUS上，因而RF中的数据可以直接通过B端口送到DBUS上。 DR1(U47)和DR2(U48)各由1片74LS273构成，用于暂存参与运算的数据。DR1接ALU 的A输入端口，DR2接ALU的B输入端口。ALU(U31、U35)由两片74LS181构成，ALU的输出通过一个三态门（74LS244）发送到数据总线DBUS上。 实验台上的八个发光二极管DBUS7-DBUS0显示灯接在DBUS上，可以显示输入数据或运算结果。另有一个指示灯C显示运算器进位标志信号状态。 图中尾巴上带粗短线标记的信号都是控制信号，其中S3、S2、S1、S0、M、Cn#、LDDR1、LDDR2、ALU_BUS#、SW_BUS#、LDRi、RS1、RS0、RD1、RD0、WR1、WR0都是电位信号，在本次实验中用拨动开关K0—K15来模拟；T2、T3为时序脉冲信号，印制板上已连接到实验台的时序电路。实验中进行单拍操作，每次只产生一组T1、T2、T3、T4时序脉冲，需将实验台上的DP、DB开关进行正确设置。将DP开关置1，DB开关置0，每按一次QD按钮，则顺序产生T1、T2、T3、T4一组单脉冲。 三、实验设备 1.TEC-5计算机组成实验系统1台 2.逻辑测试笔一支（在TEC-5实验台上） 3.双踪示波器一台（公用） 4.万用表一只（公用） 四、实验任务 1.按图3.1所示，将运算器模块与实验台操作板上的线路进行连接。由于运算器模块 内部的连线已由印制板连好，故接线任务仅仅是完成数据开关、控制信号模拟开 关、与运算器模块的外部连线。注意：为了建立清楚的整机概念，培养严谨的科 研能力，手工连线是绝对必要的。 2.用开关SW7—SW0向通用寄存器堆RF内的R0—R3寄存器置数。然后读出R0—R3 的内容，在数据总线DBUS上显示出来。 3.验证ALU的正逻辑算术、逻辑运算功能。 令DR1=55H，DR2=0AAH，Cn#=1。在M=0和M=1两种情况下，令S3—S0的值从0000B变到1111B，列表表示出实验结果。实验结果包含进位C，进位C由指示灯显示。 注意：进位C是运算器ALU最高位进位Cn+4#的反，即有进位为1，无进位为0。 五、实验要求 1.做好实验预习，掌握运算器的数据传输通路及其功能特性，并熟悉本实验中所用 的模拟开关的作用和使用方法。 2.写出实验报告，内容是： (1)实验目的。 (2)按实验任务3的要求，列表表示出实验结果。 (3)按实验任务4的要求，在表中填写各控制信号模拟开关值，以及运算结果值。 六、实验步骤和实验结果 （1）实验任务2 的实验步骤和结果如下：（假定令R0=34H，R1=21H，R2=52H，R3=65H）1．置DP=1，DB=0，编程开关拨到正常位置。 接线表如下：

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验8实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序

6.37： #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar(); if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } typedef struct{ bitree *base; bitree *top; int stacksize; }sqstack; void initstack(sqstack &S){ S.base=(bitree*)malloc(STACK_INIT_SIZE *sizeof(bitree)); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,bitree e){ if(s.top - s.base >= s.stacksize){ s.base =

高考数学分项版解析专题11概率和统计、算法

专题11 概率和统计、算法 一．基础题组 1. 【2005江苏，理7】在一次歌手大奖赛上，七位评委为歌手打出的分数如下： 9.4 8.4 9.4 9.9 9.6 9.4 9.7 去掉一个最高分和一个最低分后，所剩数据的平均值和方差分别为 （A）9.4, 0.484 （B）9.4, 0.016 （C）9.5, 0.04 （D）9.5, 0.016 【答案】D 2. 【2006江苏，理3】某人5次上班途中所花的时间（单位：分钟）分别为x，y，10，11，9.已知这组数据的平均数为10，方差为2，则｜x－y｜的值为 （A）1 （B）2 （C）3 （D）4 【答案】D 【解析】由题意可得：x+y=20,(x-10)2+(y-10)2=8,解这个方程组需要用一些技巧，因为不 要直接求出x、y，只要求出 y x- ，设x=10+t, y=10-t, 24 x y t -== ，选D. 3. 【2008江苏，理2】若将一颗质地均匀的骰子（一种各面上分别标有1，2，3，4，5，6个点的正方体玩具），先后抛掷两次，则出现向上的点数之和为4的概率是▲． 【答案】 1 12 【解析】本小题考查古典概型．基本事件共6×6 个，点数和为4 的有(1,3)、(2,2)、(3,1) 共3 个，故 31 6612 P== ? . 4. 【2008江苏，理6】在平面直角坐标系xoy中，设D是横坐标与纵坐标的绝对值均不大于2的点构成的区域，E是到原点的距离不大于1的点构成的区域，向D中随机投一点，则所投点在E中的概率是▲

【答案】 16 π 【解析】本小题考查古典概型．如图：区域D 表示边长为4 的正方形的内部（含边界）， 区域E 表示单位圆及其内部，因此． 2 144 16P ππ ?= = ?. 5. 【2008江苏，理7】某地区为了解7080-岁的老人的日平均睡眠时间（单位：h ），随机选择了50位老人进行调查，下表是这50位老人睡眠时间的频率分布表： 在上述统计数据的分析中一部分计算见算法流程图，则输出的S 的值为 ▲ 序号i 分组 （睡眠时间） 组中值（i G ） 频数 （人数） 频率（i F ） 1 [4,5) 4.5 6 0.12 2 [5,6) 5.5 10 0.20 3 [6,7) 6.5 20 0.40 4 [7,8) 7.5 10 0.20 5 [8,9] 8.5 4 0.08

计算机组成原理实验-运算器组成实验报告

计算机组成原理课程实验报告 9.3 运算器组成实验 姓名：曾国江 学号： 系别：计算机工程学院 班级：网络工程1班 指导老师： 完成时间： 评语： 得分：

9.3运算器组成实验 一、实验目的 1．熟悉双端口通用寄存器堆的读写操作。 2．熟悉简单运算器的数据传送通路。 3．验证运算器74LS181的算术逻辑功能。 4．按给定数据，完成指定的算术、逻辑运算。 二、实验电路 ALU-BUS# DBUS7 DBUS0 Cn# C 三态门（244） 三态门（244）ALU（181） ALU（181） S3S2S1S0M A7A6A5A4F7F6F5F4 F3F2F1F0B3B2B1B0 Cn+4 Cn Cn Cn+4 LDDR2T2 T2 LDDR1LDRi T3 SW-BUS# DR1（273） DR2（273） 双端口通用寄存器堆RF （ispLSI1016） RD1RD0RS1RS0WR1WR0 数据开关(SW7-SW0)数据显示灯 A3A2A1A0B7B6B5B4 图3.1 运算器实验电路 LDRi T3A B 三态门 R S -B U S # 图3.1示出了本实验所用的运算器数据通路图。参与运算的数据首先通过实验台操作板上的八个二进制数据开关SW7-SW0来设置，然后输入到双端口通用寄存器堆RF 中。

RF(U30)由一个ispLSI1016实现，功能上相当于四个8位通用寄存器，用于保存参与运算的数据，运算后的结果也要送到RF中保存。双端口寄存器堆模块的控制信号中，RS1、RS0用于选择从B端口（右端口）读出的通用寄存器，RD1、RD0用于选择从A端口（左端口）读出的通用寄存器。而WR1、WR0用于选择写入的通用寄存器。LDRi是写入控制信号，当LDRi＝1时，数据总线DBUS上的数据在T3写入由WR1、WR0指定的通用寄存器。RF的A、B端口分别与操作数暂存器DR1、DR2相连；另外，RF的B端口通过一个三态门连接到数据总线DBUS上，因而RF中的数据可以直接通过B端口送到DBUS 上。 DR1和DR2各由1片74LS273构成，用于暂存参与运算的数据。DR1接ALU的A输入端口，DR2接ALU的B输入端口。ALU由两片74LS181构成，ALU的输出通过一个三态门（74LS244）发送到数据总线DBUS上。 实验台上的八个发光二极管DBUS7-DBUS0显示灯接在DBUS上，可以显示输入数据或运算结果。另有一个指示灯C显示运算器进位标志信号状态。 图中尾巴上带粗短线标记的信号都是控制信号，其中S3、S2、S1、S0、M、Cn#、LDDR1、LDDR2、ALU_BUS#、SW_BUS#、LDRi、RS1、RS0、RD1、RD0、WR1、WR0都是电位信号，在本次实验中用拨动开关K0—K15来模拟；T2、T3为时序脉冲信号，印制板上已连接到实验台的时序电路。实验中进行单拍操作，每次只产生一组T1、T2、T3、T4时序脉冲，需将实验台上的DP、DB开关进行正确设置。将DP开关置1，DB开关置0，每按一次QD 按钮，则顺序产生T1、T2、T3、T4一组单脉冲。 三、实验设备 1.TEC-5计算机组成实验系统1台 2.逻辑测试笔一支（在TEC-5实验台上） 3.双踪示波器一台（公用） 4.万用表一只（公用） 四、实验任务 1、按图3.1所示，将运算器模块与实验台操作板上的线路进行连接。由于运 算器模块内部的连线已由印制板连好，故接线任务仅仅是完成数据开关、控制信号

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

数据结构实验报告(四)

《数据结构》实验报告 班级： 学号： 姓名：

实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

一、程序源代码 #include #include #define MAXSIZE 30 typedef char ElemType; typedef struct TNode *BiTree; struct TNode { char data; BiTree lchild; BiTree rchild; }; int IsEmpty_BiTree(BiTree *T) { if(*T == NULL) return 1; else return 0;

} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;

概率论与数理统计逻辑框图(免费)

第一，我要说的是同学们在学习概率论与数理统计的时候不要一头扎入古典概型的概率计算中不可自拔。概率论的第一部分就是关于古典概型与几何概型的计算问题，有很多问题是很复杂的，一旦陷入这一类问题的题海中，要么你的脑瓜会越来越聪明，要么打击你的信心，对概率论失去兴趣。一般同学都会处于后一种状态。那么怎么办呢？请转阅第二条。 第二，对概率论与数理统计的考点要整体把握。考研中，概率论的重点考查对象在于随机变量及其分布和随机变量的数字特征。所以对于第一条中所讲的古典概型与几何概型这部分，只要掌握一些简单的概率计算就可，把大量精力放在随机变量的分布上。数理统计的考查重点在于与抽样分布相关的统计量的分布及其数字特征。曹显兵教授编写的《概率论与数理统计过关与提高》就是能够帮助同学们正确把握考研重点、具体解析考研难点的佳品。2009年考研数学考试大纲数学三删除了对概率论与数理统计中的假设检验的要求，这算是较上一年大纲的一个大的变化，但如果同学们在复习的时候就是整体把握的，就会明白大纲的这点变化对自己的复习是没有影响的。这就是对一门课程整体把握的优势。 第三，在心理上重视。考研数学试题中有关概率论与数理统计的题目对大多数考生来说有一定难度，这就使得很多考完试的同学感慨万千，概率题太难了！同时也为学弟学妹们传达了概率题目难的信息。所以同学们在复习之前就已经有了先入为主的看法：概率比较难！但同学们没有注意到，在自己复习之初做得准备都是关于高等数学（微积分）的，在概率上的时间本身就不足。而且如果你的潜意识中觉得一件事情难的话，那么那件事情对你来说就真的很难。我一直认为，人的潜力是非常巨大的。这也与"有多少想法，就有多大成就"的说法相合。如果你相信自己，那么概率复习起来是简单的，考试中有关概率的题目也是容易的，数学满分不是没有可能的。那么，从现在开始，在心理上告诉自己：概率并不难！

计算机组成原理实验三运算器

实验三：八位运算器组成实验 一：实验目的： 1：掌握运算器的组成原理、工作原理； 2：了解总线数据传输结构； 3：熟悉简单的运算器的数据通路与控制信号的关系； 4：完成给定数据的算术操作、逻辑操作； 二：实验条件： 1：PC机一台； 2：MAX+PLUSⅡ软件； 三：实验内容（一） 1：所用到的芯片 74181：四位算术逻辑运算单元； 74244：收发器（双向的三态缓冲器） 74273：八位D触发器； 74374：八位D锁存器； 74163：八进制计数器； 7449：七段译码器 2:实验电路图 （1）运算器电路图 （A）数据输入电路由两个十六进制计数器连接成16*16=256进制的计数器，可以实现八位的输入。 （B）运算功能选择电路由一个十六进制计数器组成，可以实现16种不同运算的选择。再加上逻辑运算器上的M位和Cn位的选择，一共可以实现16*3=48种运算功能。内部由一个74163构成。

内部结构： （C）数码管扫描显示电路由一个扫描电路scan和一个七段译码器7449组成，scan 内部是一个二选一的多路复用器。 scan内部结构： （D）运算器电路图

（2）波形仿真图 （A）输入两个数A=05H,B=0AH,O5H DR1,0AH DR2,并通过经由74181在总线上显示。

（B）对两个数进行各种数学运算和逻辑运算。加法运算：输出控制：s4s3s2s1=0001,M=0,CN=0 输出使能：ALU_BUS=0 计算结果：05H+0AH=10H

四：实验内容（二） 给定A,B两个数，设A=05H,B=0AH,完成几种常见的算术运算和逻辑运算画出运算的波形和仿真图 （1）逻辑运算：A and B,A or B,取反/A,A⊙B,A⊕B; /A A⊕B A⊙B A and B A or B 输入控制s3s2s1s0 0000 0110 1001 1011 1110 计算结果FAH 0FH F0H 00H 0FH

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);

正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

高一数学必修三,算法与程序框图知识点及题型

第二节算法与程序框图 一、基础知识 1．算法 (1)算法通常是指按照一定规则解决某一类问题的明确和有限的步骤． (2)应用：算法通常可以编成计算机程序，让计算机执行并解决问题． 2．程序框图 程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形．3．三种基本逻辑结构 (1)顺序结构 (2)条件结构

(3)循环结构 三种基本逻辑结构的适用情境 (1)顺序结构：要解决的问题不需要分类讨论． (2)条件结构：要解决的问题需要分类讨论． (3)循环结构：要解决的问题要进行许多重复的步骤，且这些步骤之间有相同的规律．考点一顺序结构和条件结构

[例1] (2019·沈阳质检)已知一个算法的程序框图如图所示，当输出的结果为0时，输入的实数x 的值为( ) A ．－3 B ．－3或9 C ．3或－9 D ．－3或－9 [解析] 当x ≤0时，y ＝????12x －8＝0，x ＝－3；当x >0时，y ＝2－log 3x ＝0，x ＝9.故x ＝－3或x ＝9，选B. [答案] B [例2] 某程序框图如图所示，现输入如下四个函数，则可以输出的函数为( ) A ．f (x )＝cos x x ????－π 2

C ．f (x )＝|x | x D ．f (x )＝x 2ln(x 2＋1) [解析] 由程序框图知该程序输出的是存在零点的奇函数，选项A 、C 中的函数虽然是奇函数，但在给定区间上不存在零点，故排除A 、C.选项D 中的函数是偶函数，故排除D.选B. [答案] B [解题技法] 顺序结构和条件结构的运算方法 (1)顺序结构是最简单的算法结构，语句与语句之间、框与框之间是按从上到下的顺序进行的．解决此类问题，只需分清运算步骤，赋值量及其范围进行逐步运算即可． (2)条件结构中条件的判断关键是明确条件结构的功能，然后根据“是”的分支成立的条件进行判断． (3)对于条件结构，无论判断框中的条件是否成立，都只能执行两个分支中的一个，不能同时执行两个分支． [题组训练] 1．半径为r 的圆的面积公式为S ＝πr 2，当r ＝5时，计算面积的流程图为( ) 解析：选D 因为输入和输出框是平行四边形，故计算面积的流程图为D. 2．运行如图所示的程序框图，可输出B ＝______，C ＝______.

遗传算法的流程图

一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual

{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色

运算器部件实验报告

实验一运算器部件实验报告 班级____________ 姓名_______________ 学号 _______________ 日期_____________ 一、实验目的 熟悉与深入理解4位运算器芯片Am2901的功能和内部组成，运行中要求使用的控制信号及其各自的控制作用。 熟悉与深入理解用4片4位的运算器芯片构成16位的运算器部件的具体方案，各数据位信号、各控制位信号的连接关系。 熟悉与深入理解用2片GAL20V8芯片解决ALU最低位的进位输入信号和最高、最低位的移位输入信号、实现4位的标志位寄存器的方案，理解为什么这些功能不能在运算器芯片之内实现而要到芯片之外另外处理。 明确教学计算机的运算器部件，使用总计24位的控制信号就完全确定了它的全部运算与处理功能，脱机运算器实验中可以通过24位的微型开关提供这些控制信号。 二、实验说明 脱机运算器实验，是指让运算器从教学计算机整机中脱离出来，此时，它的全部控制与操作均需通过24位的微型开关来完成，通过开关、按键控制教学机的运算器完成指定的运算功能，并通过指示灯观察运算结果。 三、实验要求 1、实验之前认真预习，写出预习报告，包括操作步骤，实验过程所用数据和运行结果等 2、实验过程当中，要仔细进行，防止损坏设备，分析可能遇到的各种现象，判断结果是否正确，记录运行结果 3、实验之后，认真写出实验报告，包括对遇到的各种现象的分析，实验步骤和实验结果，自己在这次实验的心得体会与收获。 四、实验所使用到的控制信号 AM2901所用的控制信号 运算器用到的GAL20V8的控制信号

五、实验步骤 1、将教学机设置为单步、16位、脱机状态下，即把教学机左下方的5个控制开关置为1XX00。 2、按一下RESET按键，进行初始化。 3、按照指定功能给出控制信号和数据信息，观察各信号指示灯状态。 4、按压START键，给出脉冲信号，观察各信号灯状态。 六、实验内容 1、下表中所列操作在教学机上进行运算器脱机实验。并将结果填入表中 2、下表中所列操作在教学机上进行运算器脱机实验。并将结果填入表中 运算器功能所用到的控制信号

数据结构实验三实验报告

三题目：哈夫曼编/译码器 班级：姓名：学号：完成日期：15.11.14 一、题目要求 描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 输入：输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。 输出：经过编码后的二进制码，占一行； 以及对应解码后的报文，占一行； 最后输出一个回车符。 输入样例： 5 a b c d e 12 40 15 8 25 bbbaddeccbbb 输出样例： 00011111110111010110110000 bbbaddeccbbb 提示：利用编码前缀性质。 二、概要设计 1.设计需要的数据结构：树型结构 2.需要的抽象数据类型： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi?Di有?H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi}) 是一棵符合本定义的树，称为根root的子树。 基本操作： InitTree(&T); 操作结果：构造空树T。