实验四 排序程序设计

实验三：排序程序设计

1、设计要求：设源程序代码段中有无序字符表，将其按代码值大小升序排序，显

示排序后字符表，显示完，提示OK字符。

2、程序算法：利用气泡排序法进行设计

3、程序如下

CODES SEGMENT

ORG 0100H

ASSUME CS:CODES

STAR: JMP SSTT

ASCII DB 'GAJXYDEBFIRKWR'

DB 'QOUZVCHMST4135'

COUNT =$-ASCII-1

OK DB 0DH,0AH,'OK!$'

SSTT: MOV AX,CS

MOV DS,AX

MOV DL,COUNT

MOV DH,1

XOR BX,BX

L0: OR DH,DH

JZ L3

MOV DH,0

MOV CX,COUNT

SUB CX,BX

MOV SI,OFFSET ASCII

L1: MOV AL,[SI]

INC SI

CMP AL,[SI]

JBE L2

XCHG AL,[SI]

MOV [SI-1],AL

MOV DH,1

L2: LOOP L1

INC BX

DEC DL

JNZ L0

L3: MOV DX,OFFSET ASCII

MOV AH,9

INT 21H

INT 20H

CODES ENDS

END STAR 4、运行结果

实验四-排序-实验报告

数据结构实验报告 实验名称：实验四排序 学生姓名： 班级： 班内序号： 学号： 日期：2012年12月21日 1、实验要求 题目2 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。 2、程序分析 存储结构 说明：本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 (1)单链表存储结构： （2）结点结构 struct Node { int data;

Node * next; }; 示意图： 关键算法分析 一：关键算法 (一)直接插入排序 void LinkSort::InsertSort() 直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。 （1）算法自然语言 1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录； 2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录； 3.重复执行2，直到无序区中没有记录为止。 （2）源代码 void 2. 3. 4.重复执行2和3 直接插入排序过程

《数据结构》实验报告——排序.docx

《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1. 插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i 趟直接插入排序的操作为：在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后，变成含有i 个记录的有序子序列r[1..i ]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r [0]处设置哨兵。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 （通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线，将序列{L.r[s] ，… ，L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针lOw 和high ，他们的初值分别为lOw 和high ，设枢轴记录的关键字为PiVOtkey ，则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换，然后从lOw 所指位置起向后搜索，找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至low=high 为止。 具体实现上述算法是，每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上，

实验二选择结构程序设计实验报告

实验三：C程序的选择结构 一、实验目的和要求 （1）了解 C 语言表示逻辑量的方法（以0 代表“假”，以非0 代表“真”）。 （2）学会正确使用逻辑运算符和逻辑表达式。 （3）熟练掌握if 语句的使用（包括if 语句的嵌套）。 （4）熟练掌握多分支选择语句—switch 语句。 （5）结合程序掌握一些简单的算法。 （6）进一步学习调试程序的方法。 二、、实验软硬件配置 1.硬件配置 电脑 2.软件配置 Windows xp Visual C++6.0 三、实验内容及过程描述 实验步骤： ①进入Visual C++ 6.0 集成环境。 ②输入自己编好的程序。 ③检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有错，及时 改正。 ④进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，根据提 示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 ⑤运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正 确，应运行多次，分别检查在不同情况下结果是否正确。 实验内容： 本实验要求事先编好解决下面问题的程序，然后上机输入程序并调试运行程序。 x x 1 （1）有一函数：y 2x 1 1 x 10 3x 11 x 10 写程序，输入x 的值，输出y 相应的值。用scanf 函数输入x 的值，求y 的值。程序如下：#include int main() {float x,y; int i; while(i<1000) { printf(" 请输入x 的值："); scanf("%f",&x); if(x<1) y=x; else if(1<=x&&x<10)

排序操作实验报告

数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院

一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序

图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡

排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include #define MAXSIZE 100 typedef int KeyType; typedef int DataType; typedef struct{ KeyType key; DataType data; }SortItem,SqList[MAXSIZE]; /*******直接插入顺序表*******/ void InsertSort(SqList L,int n) { int i,j,x; SortItem p; for(i=1;i

实验报告-排序与查找

电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 5月20日 2014-2015-2学期 信息与软件工程学院

实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key

实验4选择结构程序设计

实验4 选择结构程序设计 一、实验目的 1．掌握C语言中逻辑量的表示和使用方法。 2．掌握if语句及switch语句的使用。 3．熟悉各种表达式作为if语句及switch语句的条件。 4．了解Turbo C程序的基本调试方法。 二、实验内容 1．验证性实验 (1)分析程序的运行结果。 ①运行下列程序，输入1-7之间的任意数字，观察程序的运行结果。 #include void main() { int week; printf("Input(1-7):"); scanf("%d",&week); switch(week) { case 1:printf("Mon.\n"); break; case 2:printf("Tue.\n"); break; case 3:printf("Wed.\n"); break; case 4:printf("Tur.\n"); break; case 5:printf("Fri.\n"); break; case 6:printf("Sat.\n"); break; case 7:printf("Sun.\n"); break; default:printf("The input is wrong!\n"); } } ②运行5次下列程序,输入的数据分别是1,2,3,4,5，请观察每次的运行结果,并根据结果分析原因。 #include void main() { int n,a=0,b=0,c=0,d=0,k=0; scanf("%d",&n); switch(n) { case 1:b++;break; case 2:c++; case 3:d++;break; case 4:k++; default:a++; } printf("%d,%d,%d,%d",a,b,c,d,n); } (2)输入x的不同值，以下程序将求一给定“y=f(x)”函数的值。

北京理工大学数据结构实验报告4

《数据结构与算法统计》 实验报告 ——实验四 学院： 班级： 学号： 姓名：

一、实验目的 1、熟悉VC 环境，学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 ⑶模块调用关系

(完整word版)查找、排序的应用 实验报告

实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。

四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若keyr[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败 b、顺序查找 从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。 void chaxun(SqList &ST) //查询信息 { cout<<"\n************************"<=1;j--) if(ST.r[j].xuehao

实验4 Matlab程序设计1

实验4 Matlab 程序设计1 实验目的： 1、 掌握建立和执行M 文件的方法； 2、 掌握实现选择结构的方法； 3、 掌握实现循环结构的方法。 实验内容： 1. 从键盘输入一个4位整数，按如下规则加密后输出。加密规则：每位数字都加上7，然 后用和除以10的余数取代该数字；再把第一位与第三位交换，第二位与第四位交换。 2. 求分段函数的值。 ,x x x x y x x x x x x x ?+- <≠-?=-+ ≤<≠≠??-- ?2226035605231且且及其他 用if 语句实现，分别输出x=-5,-3,0,1,2,2.5,3,5时的y 值。 3. 输入一个百分制成绩，要求输出成绩等级A 、B 、C 、D 、E ，其中90~100分为A ，80~89 分为B ，70~79分为C ，60~69分为D ，60分以下为E 。 要求： （1） 分别用if 语句和swich 语句实现。 （2） 输入百分制成绩后要判断该成绩的合理性，对不合理的成绩应输出出错信息。 4. 硅谷公司员工的工资计算方法如下： （1） 工作时数超过120小时者，超过部分加发15%； （2） 工作时数低于60小时者，扣发700元； （3） 其余按每小时84元计发。

试编程按输入的工号和该号员工的工时数，计算应发工资。 5.设计程序，完成两位数的加、减、乘、除四则运算。即：输入两个两位随机整数，再输 入一个运算符号，做相应的运算，并显示相应的结果。 6.建立5×6矩阵，要求输出矩阵的第n行元素。当n值超过矩阵的行数时，自动转为输 出矩阵的最后一行元素，并给出出错信息。 7.产生20个两位随机整数，输出其中小于平均数的偶数。 实验代码及实验结果 1. >> a=input('请输入一个四位整数：'); 请输入一个四位整数：9988 >> a1=fix(a/1000); >> a2=rem(fix(a/100),10); >> a3=rem(fix(a/10),10); >> a4=rem(a,10); >> a1=rem(a1+7,10); >> a2=rem(a2+7,10); >> a3=rem(a3+7,10); >> a4=rem(a4+7,10); >> b=a1;a1=a3;a3=b; >> b=a2;a2=a4;a4=b; >> c=a1*1000+a2*100+a3*10+a4; >> disp(c)

顺序表的查找、插入与删除实验报告

《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);

实验四 答案 选择结构程序设计

实验四选择结构程序设计答案 实验时间：年月日 【实验步骤】 一、程序调试练习 1、写出下列程序的运行结果： （1）ex4_1.c #include void main() { char ch; printf("input a character:"); ch=getchar(); if(ch>='A' && ch<='Z') ch=ch+32; printf("%c\n",ch); } 具体要求： ①从键盘上输入a，分析程序运行的结果。 ②从键盘上输入A，分析程序运行的结果。 ③从键盘上输入5，分析程序运行的结果。 程序运行结果： ①a ②a ③5 （2）ex4_2.c #include void main() { int x,y,z; printf("input x,y,z"); scanf("%d,%d,%d",&x,&y,&z); if(x

②从键盘上给x、y、z分别输入3，5，2，分析程序运行的结果。 ③从键盘上给x、y、z分别输入-5，-3，2，分析程序运行的结果。 程序运行结果： ①z=2 ②z=3 ③z=0 （3）ex4_3.c #include main() { int x=1,a=0,b=0; switch(x) { case 0:b++; case 1:a++; case 2:a++;b++; } printf("a=%d,b=%d\n",a,b); } 程序运行结果： a=2,b=1 （4）ex4_4.c #include void main() { int x=1,y=0,a=0,b=0; switch(x) { case 1: switch(y) { case 0: a++; break; case 1: b++; break; } case 2: a++; b++; break; case 3: a++; b++; } printf("a=%d,b=%d\n",a,b); } 具体要求：

查找与排序实验报告

实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct {

Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length;

算法排序问题实验报告

《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小的记录移到低端 while low

《数据结构》实验报告查找

实验四——查找 一、实验目的 1.掌握顺序表的查找方法，尤其是折半查找方法； 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表，用顺序查找的方法对其实施查找； 2.建立一个有序表，用折半查找的方法对其实施查找； 3.建立一个二叉排序树，根据给定值对其实施查找； 4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有：结构体typedef struct，插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main(). 四、上机实验 实验一： 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<

第四版C语言实验报告实验4选择程序设计

仲恺农业工程学院实验报告纸 计算机科学与工程（院）计算机科学与技术专业计111班1 组C语言程序设计课 实验4 选择结构程序设计 一、实验目的 一．实验目的 （1）了解C语言表示逻辑量的方法（以0代表“假”，以非0代表“真”）。 （2）学会正确使用逻辑运算符和逻辑表达式。 （3）熟练掌握if语句的使用（包括if语句的嵌套）。 （4）熟练掌握多分支选择语句——switch语句。 （5）结合程序掌握一些简单的算法。 （6）进一步学习调试程序的方法。 二、实验内容和步骤 程序1 写程序，输入x值，输出相应y值 程序：#include int main() { int x,y; scanf("%d",&x); if (x<1) { y=x; } else if (x<10) { y=2*x-1; } else

{ y=3*x-11; } printf ("x=%d,y=%d\n",x,y); return 0; 结果： } 程序2 程序： #include #include #define M 1000 int main() {

int i,k; printf("please input:",M); scanf("%d",&i); while (i>M) { printf("warning!\n",M); scanf("%d",&i); } k=sqrt(i); printf("the answer is%d\n",k); return 0; } 结果： 程序3 #include int main() { float score; char grade; printf("please input student's score:"); scanf("%f",&score); while(score>100||score<0) { printf("\n is wrong,please input again\n"); scanf("%f",&score); } switch((int)(score/10)) {

河南工业大学实验报告——查找和排序(排序)——张伟龙

河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容：1．实现希尔排序。 2．实现快速排序。 3. 实现堆排序。 （三选一） 实验要求：1. 根据所选题目，用C语言编写程序源代码。 2. 源程序必须编译调试成功，独立完成。 三实验过程及运行结果 选择第三题： Source Code： #include #include using namespace std; void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号

int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } }

微机原理实验报告冒泡排序

一、实验目的 (1)学习汇编语言循环结构语句的特点,重点掌握冒泡排序的方法。 (2)理解并掌握各种指令的功能,编写完整的汇编源程序。 (3)进一步熟悉DEBUG的调试命令,运用DEBUG进行调试汇编语言程序。 二、实验内容及要求 (1)实验内容:从键盘输入五个有符号数,用冒泡排序法将其按从小到大的顺序排序。 (2)实验要求: ①编制程序,对这组数进行排序并输出原数据及排序后的数据; ②利用DEBUG调试工具,用D0命令,查瞧排序前后内存数据的变化; ③去掉最大值与最小值,求出其余值的平均值,输出最大值、最小值与平均值; ④用压栈PUSH与出栈POP指令,将平均值按位逐个输出; ⑤将平均值转化为二进制串,并将这组二进制串输出; ⑥所有数据输出前要用字符串的输出指令进行输出提示,所有数据结果能清晰显示。 三、程序流程图Array (1)主程序:MAIN

(2)

就是 NAME BUBBLE_SORT DATA SEGMENT ARRAY DW 5 DUP(?) ;输入数据的存储单元 COUNT DW 5 TWO DW 2 FLAG1 DW 0 ;判断符号标志 FLAG2 DB 0 ;判断首位就是否为零的标志FAULT DW -1 ;判断出错标志 CR DB 0DH,0AH,'$' STR1 DB 'Please input five numbers seperated with space and finished with Enter:','$' STR2 DB 'The original numbers:','$' STR3 DB 'The sorted numbers:','$' STR4 DB 'The Min:','$' STR5 DB 'The Max:','$' STR6 DB 'The Average:','$' STR7 DB 'The binary system of the average :','$' STR8 DB 'Input error!Please input again!''$' DATA ENDS CODE SEGMENT MAIN PROC FAR ASSUME CS:CODE,DS:DATA,ES:DATA START: PUSH DS AND AX,0 PUSH AX MOV AX,DATA MOV DS,AX LEA DX,STR1 MOV AH,09H ;9号DOS功能调用,提示输入数据 INT 21H CALL CRLF ;回车换行 REIN: CALL INPUT ;调用INPUT子程序,输入原始数据CMP AX,FAULT ;判断就是否出错, JE REIN ;出错则重新输入

实验四-答案--选择结构程序设计讲课讲稿

实验四-答案--选择结构程序设计

实验四选择结构程序设计答案 实验时间：年月日【实验步骤】 一、程序调试练习 1、写出下列程序的运行结果： （1）ex4_1.c #include void main() { char ch; printf("input a character:"); ch=getchar(); if(ch>='A' && ch<='Z') ch=ch+32; printf("%c\n",ch); } 具体要求： ①从键盘上输入a，分析程序运行的结果。 ②从键盘上输入A，分析程序运行的结果。 ③从键盘上输入5，分析程序运行的结果。 程序运行结果： ①a ②a ③5 （2）ex4_2.c #include void main() { int x,y,z; printf("input x,y,z"); scanf("%d,%d,%d",&x,&y,&z); if(x

①从键盘上给x、y、z分别输入2，-1，2，分析程序运行的结果。 ②从键盘上给x、y、z分别输入3，5，2，分析程序运行的结果。 ③从键盘上给x、y、z分别输入-5，-3，2，分析程序运行的结果。 程序运行结果： ①z=2 ②z=3 ③z=0 （3）ex4_3.c #include main() { int x=1,a=0,b=0; switch(x) { case 0:b++; case 1:a++; case 2:a++;b++; } printf("a=%d,b=%d\n",a,b); } 程序运行结果： a=2,b=1 （4）ex4_4.c #include void main() { int x=1,y=0,a=0,b=0; switch(x) { case 1: switch(y) { case 0: a++; break; case 1: b++; break; } case 2: a++; b++; break; case 3: a++; b++;

大数据结构实验四题目一排序实验报告材料

数据结构实验报告 实验名称：实验四——排序 学生姓名：XX 班级： 班内序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构

存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆

实验四 选择结构程序设计

实验四选择结构程序设计 【实验目的】 1、了解选择结构的结构特点 2、掌握选择结构程序设计方法 3、掌握选择结构中各种条件语句的结构特点及使用 【实验内容】 例1、税务部门征收所得税，规定如下（用IF语句实现）： ①收人在 200 元以内，免征； ②收人为 200 ～ 400 元，超过 200 元的部分纳税 3% ； ③收入超过 400 元的部分，纳税 4% ； ④当收人达 5 000 元或超过时，将 4% 税金改为 5% 。 程序运行后，单击窗体，在输人对话框中输入收入数，程序将输出纳税金额，运行情况如图 4.1 所示。 图4.1 提示： 因为该程序的条件分支较多，故可采用多分支的条件语句进行编写。 多分支条件语句格式如下： If 条件1 Then 语句块1 【ElseIf 条件2 Then 语句块2 】 【ElseIf 条件3 Then 语句块3】 …… 【Else 语句块 n+1】 End If 例 2 将上题用SELECT CASE 多分支结构设计。 提示：Case语句的一般格式为 Select Case 测试表达式 Case 表达式列表1 【语句块1】 【Case 表达式列表1 【语句块1】】 …… 【Case Else 【语句块1】】 End Select

【上机参考练习题】 要求：利用空余时间设计调试出来，并将设计方法及代码写入试验报告。 1.（基本设计题）在购买某物品时，若所花的的钱 x 在下述范围内，所付钱 Y 按对应折扣支付： 提示：此例可以多分支结构或者选择结构实现，注意计算公式和条件表达式的正确书写。 图4.2 2.（基本设计题）编一程序根据上网时间计算上网费用，同时为了鼓励多上网，每月收费最多不超过 150 元。计算的方法如下： 图 4.3 提示：此题用可以用多分支结构或者选择结构实现，但请特别注意有个条件“每月收费最多不超过 150 元” 3.（基本设计题）输入一个数字 (1－7) ，用英文显示对应的星期一到星期日。 提示：用 Select Case语句来实现。 4.（提高设计题）编一模拟袖珍计算器的完整程序，界面如图4.4 所示。要求：输入两个操作数和一个操作符，根据操作符决定所做的运算。 提示： (1) 为了程序运行正确，对存放操作符的文本框 Text3 ，应使用 trim(Text3) 函数，去除运算符两边的空格。 (2) 根据存放操作符的文本框利用 Select Case 语句实现。 图4.4 5.（提高设计题）某市公用电话收费标准如下：通话时间在 3 分钟以下，收费 0.50 元； 3 分钟以上，则每超过 1分钟加收 0.152元。 提示：此例用分支结构实现，注意判断时间范围。