《排序问题求解》实验报告
一、算法的基本思想
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 while low A[low]←A[high] //将比枢轴记录小的记录移到低端 while low A[high]←A[low] //将比枢轴记录大的记录移到高端 A[low]←A[0] //枢轴记录到位 return low //返回枢轴位置 二、算法的理论分析 1. 直接插入排序算法理论分析 从空间来看，直接插入排序只需要一个数的辅助空间；从时间来看，直接插入排序的基 本操作为：比较两个关键字的大小和移动记录。先分析一趟直接插入排序的情况。伪代码InsertionSort 中while 循环的次数取决于待插入的数与前i-1 个数之间的关系。若 A[i] 若待排序数组是随机的，即待排序数组中的数可能出现的各种排序的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行数间的比较次数和数的移动次数，约为n^2/4。 因此直接插入排序算法，在最佳情况下的时间复杂度是O(n)，在最坏情况下的时间复杂度为O(n^2)。 2. 快速排序算法理论分析 下面我们来分析快速排序的平均时间性能。 假设T(n)为对n 个记录A[1..n]进行快速排序所需时间，则由算法QuickSort 可见：其中，Tpass(n)为对n 个记录进行一趟快速排序Partition（A,1,n）所需的时间，从一 趟快速排序算法可见，其和记录数n 成正比，可以用cn 表示（c 为某个常数）；T(k-1)和T （n-k）分别为对A[1..k-1]和A[k+1..n]中记录进行快速排序QuickSort（A,1,k-1）和QuickSort（A,k+1,n）所需时间。假设待排序列中记录是随机排列的，则在一趟排序之后， k 取1 至n 之间任何一值的概率相同，快速排序所需时间的平均值则为Tavg(n)=knInn，其中n 为待排序序列中记录的个数，k 为某个常数。 通常，快速排序被认为是，在所有同数量级（O(nlogn)）的排序方法中，其平均性能最 好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n^2)。 三、试验分析 1、试验环境 WIN 32系统，VC6.0 2、程序的执行 1)由函数datagenetare()生成20000 个在区间[1,100000]上的随机整数，并将随机整数保存到数组num[]，接着调用函数WriteFile()将这些数输出到外部文件data.txt 中。2)调用函数ReadFile()从data.txt 中读取数据，并将其保存到数组num1[]中。接着对数组num1 进行直接插入排序，并计算和记录其运行时间。最后，调用函数WriteFile()将直接插入排序的结果写入resultsIS.txt，并记录运行时间为TimeIS。 3)调用函数ReadFile()从data.txt 中读取数据，并将其保存到数组num2[]中。接着对数组num2 进行快速排序，并计算和记录其运行时间。最后，调用函数WriteFile()将快速排序的结果写入resultsQS.txt，并记录运行时间为TimeQS。 3、试验数据 当N=20000时： 当N=30000时：当N=40000时： 当N=50000时：当N=60000时： 当N=70000时：当N=80000时： 4、实验结果分析 做出折线统计图 四、试验心得 通过本次试验首先对在C++下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！ 五、实验代码 #include #include #include #include #include using namespace std; const int NumS = 80000; void datagenetare(int num[],int n); //产生随机数，保存到数组num void WriteFile(int num[],char name[],int n); //输出数组num到data.txt文件 void ReadFile(int num[],char name[]);//读取名为name文件中的数据，保存到数组num void QuickSort(int arr[], int n);//将数组arr[]中数据快速排序 void InsertionSort(int arr[],int n);//将数组arr[]中数据直接插入排序 int main() { int *num=(int *)malloc(sizeof(int)*NumS); int *num1=(int *)malloc(sizeof(int)*NumS); int *num2=(int *)malloc(sizeof(int)*NumS); clock_t start_time1,end_time1,start_time2,end_time2; double timeQS=0,timeIS=0; cout<<"Create "< datagenetare(num,NumS); //产生随机数，保存到数组num WriteFile(num,"data.txt",NumS); //输出数组到data.txt文件 cout.precision(6); //设置浮点数的显示精度 cout.setf(ios_base::showpoint); //输出末尾的 //直接插入排序的分析 ReadFile(num1,"data.txt");//读取data.txt中的数据，保存到数组num1 cout<<"\nInsertionSort Start ....\n"; start_time1=clock(); //开始计时 InsertionSort(num1,NumS); //直接插入排序数组num1中的数据 end_time1=clock(); //结束计时 timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC; cout<<"The Time-comsuption in InsertionSort is "< WriteFile(num1,"resultsIS.txt",NumS); //排序后的数据输出到resultQS.txt //输出运行时间timeIS到resultsIS.txt ofstream ocout; ocout.open("resultsIS.txt",ios::app); if(ocout.good()) //打开resultsIS.txt { ocout<<"\nThe Time-comsuption in InsertionSort is "< ocout.close(); } else { cout<<"\nCan not open resultsIS.txt!\n"; exit(1); //异常退出 } //快速排序的分析 ReadFile(num2,"data.txt"); //读取data.txt中的数据，保存到数组num2[] cout<<"QuickSort Start .....\n"; start_time2=clock(); //开始计时 QuickSort(num2,NumS); //快速排序数组num中的数据 end_time2=clock(); //结束计时 timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC; cout<<"The Time-comsuption in QuickSort is "< WriteFile(num2,"resultsQS.txt",NumS); //排序后的数据输出到resultQS.txt //输出运行时间timeQS到resultsQS.txt ocout.open("resultsQS.txt",ios::app); if(ocout.good()) //打开resultsIS.txt { ocout<<"\nThe Time-comsuption in QuickSort is "< ocout.close(); } else { cout<<"\nCan not open resultsQS.txt!\n"; exit(1); //异常退出 } return 0; } void datagenetare(int *num,int n) { int i; srand((unsigned)time(0)); //srand()种子发生器函数，还有rand()随机数生成器函数for(i=0;i num[i]=rand()%9999+1; printf("\n"); } //将数组中的数据输出到文件 void WriteFile(int *num,char name[],int n) { ofstream ocout; ocout.open(name,ios::trunc); int i=0; if(ocout.fail()) exit(1); //打开文件失败，退出 for(;i { ocout< if((i+1)%40==0||i==n-1) //每输出40个数，换一行 ocout<<"\n"; } ocout.close(); } //将文件中的数据输入到数组 void ReadFile(int *num,char name[]) { string strLine; int i=0; char achLine[300]; const char* pchTok; ifstream icin; icin.open(name,ios::in); //打开名为name的文件 while(icin.good()) { int i = 0; while(getline(icin,strLine)) { strLine.copy(achLine,strLine.size(),0); achLine[strLine.size()]='\0'; //每行中的元素以空格为标识断开转换为int类型后存入数组 pchT ok = strtok(achLine, " "); while((pchT ok != NULL)) { num[i] = atoi(pchT ok); i++; pchT ok = strtok(NULL, " "); } } } icin.close(); } //快速排序的实现，从左向右递增排序 void QuickSort(int *arr, int n) { int L = 0; int R = n-1; int t = arr[L]; //区间的第一个数作为基准 if(n<=1) //数组中存在个或个数据时，函数返回 return; //将数据分成两个区间 while(L while(L arr[L] = arr[R]; while(L arr[R] = arr[L]; } arr[L] = t; QuickSort(arr, L); //对左区间递归排序 QuickSort(arr+L+1,n-L-1);//对右区间递归排序 } //直接插入排序的实现，从左向右递增排序 void InsertionSort(int *arr,int n) { int i=0,temp=0,j=0; if(n<=1) return; for(i=1;i { temp=arr[i]; //temp记录要插入的数据arr[i] j=i; //要插入的数据的位置 for(;j>0&&arr[j-1]>temp;--j) //将a[i]插入到已排序的arr[0]~arr[i-1]中 { arr[j]=arr[j-1]; //比temp大的数据依次后移 } arr[j]=temp; //找到第一个不大于于temp的数据，在j处插入arr[i] } } 拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree 的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.vertices[j].indegree)++;）最后调用拓扑排序的算法，得出拓扑序列。 [程序代码] 头文件： #define MAX_VERTEX_NUM 30 #define STACKSIZE 30 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int InfoType; typedef int Status; typedef int SElemType; /* 定义弧的结构*/ typedef struct ArcNode{ int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/ 微机原理实验报告 班级：XXXXX 姓名：XXXX 学号：20XXXX XXXXX大学 信息科学与技术学院 信息工程系 实验一汇编语言程序设计-（具体题目） 一、实验目的（根据实际情况修改）： 1、熟悉MASM编译环境，了解程序的汇编方法； 2、熟悉常用汇编指令，学习汇编程序设计方法； 3、学习汇编语言的调试过程，通过调试过程认识CPU执行程序的方式； 4、了解冒泡法原理，学习多重循环的编程方法。 二、实验内容： 编写程序，用冒泡法实现将数据段内9,8,7,6，5,4,3,2,1按照由小到大的顺序重新排列。 三、程序流程图和程序代码 1、流程图 2、代码与注释（代码不能和指导书完全一样，写出注释，写出寄存器尤其是DS的值） data segment buf1 db 8,7,6,5,4,3,2,1 data ends code segment assume cs:code,ds:data start: mov ax,data //传送数据段data mov ds,ax mov dx,7 //dx放外循环7次 L3: mov cx,dx //cx放内循环7次 lea si,buf1 //将db里的数据传送到si L2: mov al,[si] cmp al,[si+1] //比较[si]与[si+1] jb L1 //[si]<[si+1],跳转到L1 xchg al,[si+1] //[si]>[si+1],两两交换 mov [si],al L1: inc si //si减1 loop L2 //循环L2 dec dx //外循环减1，没减到0则跳转到L3 jnz L3 //入内循环，计数初值 mov ah,4ch int 21h code ends end start 四、调试过程及遇到的问题 1、程序执行截图 算法设计与分析基础 实验报告 应用数学学院 二零一六年六月 实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort（A[0..n-1]） //用插入排序对给定数组A[0..n-1]排序 //输入：n个可排序元素构成的一个数组A[0..n-1] //输出：非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v Ⅲ、Java算法代码： import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字："); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i 算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房 目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示： 一、实验目的 （1）学习汇编语言循环结构语句的特点，重点掌握冒泡排序的方法。 （2）理解并掌握各种指令的功能，编写完整的汇编源程序。 （3）进一步熟悉DEBUG的调试命令，运用DEBUG进行调试汇编语言程序。 二、实验内容及要求 （1）实验内容：从键盘输入五个有符号数，用冒泡排序法将其按从小到大的顺序排序。（2）实验要求： ①编制程序，对这组数进行排序并输出原数据及排序后的数据； ②利用DEBUG调试工具，用D0命令，查看排序前后内存数据的变化； ③去掉最大值和最小值，求出其余值的平均值，输出最大值、最小值和平均值； ④用压栈PUSH和出栈POP指令，将平均值按位逐个输出； ⑤将平均值转化为二进制串，并将这组二进制串输出； ⑥所有数据输出前要用字符串的输出指令进行输出提示，所有数据结果能清晰显示。 三、程序流程图Array （1）主程序:MAIN （2）冒泡排序子程序: SORT 四、程序清单 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 ;出错则重新输入 LEA DX,STR2 MOV AH,09H ;9号DOS功能调用，提示输出原始数据 INT 21H CALL OUTPUT ;调用OUTPUT子程序，输出原始数据 CALL SORT ;调用SORT子程序，进行冒泡排序 LEA DX,STR3 MOV AH,09H ;9号DOS功能调用，提示输出排序后的数据 INT 21H CALL OUTPUT ;调用OUTPUT子程序，输出排序后的数据 《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 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 次记录移动(赋值)的操作。而实际上， 数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之 间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 《排序问题求解》实验报告 一、算法的基本思想 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 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："< 一、实验目的 (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 ;出错则重新输入 算法分析与设计实验报告 学院：信息科学与工程学院 专业班级： 指导老师： 学号： 姓名： 目录 实验一：递归与分治 (3) 1.实验目的 (3) 2.实验预习内容 (3) 3.实验内容和步骤 (3) 4.实验总结及思考 (5) 实验二：回溯算法 (6) 1.实验目的： (6) 2.实验预习内容： (6) 3. 实验内容和步骤 (6) 4. 实验总结及思考 (9) 实验三：贪心算法和随机算法 (10) 1. 实验目的 (10) 2.实验预习内容 (10) 3.实验内容和步骤 (10) 4. 实验总结及思考 (13) 实验一：递归与分治 1.实验目的 理解递归算法的思想和递归程序的执行过程，并能熟练编写快速排序算法程序。 掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。 2.实验预习内容 递归：递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 分治：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 3.实验内容和步骤 快速排序的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 源代码： #include 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 三、实验步骤 ㈠、数据结构与核心算法的设计描述 基本数据结构： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ #define INFINITY INT_MAX //定义无穷大∞ #define MAX_VERTEX_NUM 20 typedef int V ertexType; typedef int InfoType; typedef struct ArcNode // 表结点定义 { InfoType info; int adjvex; //邻接点域，存放与V i邻接的点在表头数组中的位置ArcNode *nextarc; //链域，指示依附于vi的下一条边或弧的结点， }ArcNode; typedef struct VNode //表头结点 { int data; //存放顶点信息 struct ArcNode *firstarc; //指示第一个邻接点 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { //图的结构定义 实验报告 实验名称冒泡排序和快速排序 班级 学号 姓名 成绩 #include 《排序问题求解》实验报告 一、算法得基本思想 1、直接插入排序算法思想 直接插入排序得基本思想就是将一个记录插入到已排好序得序列中,从而得到一个新得, 记录数增 1 得有序序列。 直接插入排序算法得伪代码称为InsertｉonＳorｔ，它得参数就是一个数组A[1、、n］,包含了n 个待排序得数。用伪代码表示直接插入排序算法如下: IｎsｅrtｉonＳｏｒt (Ａ) for i←2 tｏn ｄo ｋeｙ←Ａ[i］／/key 表示待插入数 //Ｉnsｅrt A［i] ｉnto ｔhｅsｏrteｄｓequence A［1、、i-１］ j←i-1 wｈｉｌe j＞0 ａnｄＡ[j]＞key do A[j＋１］←A［j］ j←j-1 Ａ[j+1］←keｙ 2、快速排序算法思想 快速排序算法得基本思想就是，通过一趟排序将待排序序列分割成独立得两部分，其中一 部分记录得关键字均比另一部分记录得关键字小,则可对这两部分记录继续进行排序,以达 到整个序列有序。 假设待排序序列为数组A[１、、n]，首先选取第一个数Ａ[0],作为枢轴(ｐｉvｏt)，然后按照下述原则重新排列其余数:将所有比Ａ[0]大得数都排在它得位置之前,将所有比 A[０]小得数都排在它得位置之后,由此以A[0]最后所在得位置i 作为分界线,将数组 A[1、、n]分成两个子数组Ａ［1、、i－1］与Ａ[ｉ+1、、n］。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1、、ｉ-1]与A[i＋1、、n]排序。 一趟快速排序算法得伪代码称为Paｒtｉtion，它得参数就是一个数组A[１、、n］与两个指针ｌoｗ、high,设枢轴为ｐｉvotｋeｙ，则首先从higｈ所指位置起向前搜索,找到第一个小于ｐivｏtｋey得数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 得数,并将其移到高端，重复这两步直至low=ｈigh。最后,将枢轴移到正确得位置上。用伪代码表示一趟快速排序算法如下: Partiｔｉｏn ( Ａ，low，higｈ) A[０］←A[low] ／／用数组得第一个记录做枢轴记录 priｖotkey←Ａ[low] //枢轴记录关键字 wｈile lｏw<ｈigh //从表得两端交替地向中间扫描 whｉle low WORD格式 一、实验目的 （1）学习汇编语言循环结构语句的特点，重点掌握冒泡排序的方法。 （2）理解并掌握各种指令的功能，编写完整的汇编源程序。 （3）进一步熟悉DEBUG的调试命令，运用DEBUG进行调试汇编语言程序。 二、实验内容及要求 （1）实验内容：从键盘输入五个有符号数，用冒泡排序法将其按从小到大的顺序排序。（2）实验要求： ①编制程序，对这组数进行排序并输出原数据及排序后的数据； ②利用DEBUG调试工具，用D0命令，查看排序前后内存数据的变化； ③去掉最大值和最小值，求出其余值的平均值，输出最大值、最小值和平均值； ④用压栈PUSH和出栈POP指令，将平均值按位逐个输出； ⑤将平均值转化为二进制串，并将这组二进制串输出； ⑥所有数据输出前要用字符串的输出指令进行输出提示，所有数据结果能清晰显示。 三、程序流程图 开 始（1）主程序:MAIN 初始化 键盘输入数据 调用INPUT子程序 显示输入错误 否 输入是否正确 是 显示原始数据 调用OUTPUT子程序 WORD格式 显示冒泡排序后的数据 调用SORT子程序 调用OUTPUT子程序 显示最小值Min 显示One子程序 显示最大值Max 调用One子程序 显示其余数平均值Average 调用One子程序 显示平均值二进制串Binary 调用One子程序 结束 （2）冒泡排序子程序:SORT COUNT1----外循环次数 进入COUNT2----内循环次数 i----数组下标 初始化 COUNT1=N-1 COUNT2=COUNT1 SI=0 否 Ai≥i A+1 是 Ai与A i+1两数交换 SI=SI+2 COUNT2=COUNT2-1 否 COUNT2=0？ 是 COUNT1=COUNT1-1 否 COUNT2=0？ 是 返回 实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。 实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 一:问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：1:随机生成n个0到100000的随机数用来排序的算法如下. for(int n=1000;n<20000;n+=1000) { int a[]=new int[n]; for(int i=0;i 数据结构实验报告 八种排序算法实验报告 一、实验内容 编写关于八种排序算法的C语言程序，要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。 二、实验步骤 各种内部排序算法的比较： 1.八种排序算法的复杂度分析（时间与空间）。 2.八种排序算法的C语言编程实现。 3.八种排序算法的比较，包括比较次数、移动次数。 三、稳定性，时间复杂度和空间复杂度分析 比较时间复杂度函数的情况： 时间复杂度函数O(n)的增长情况 所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。 时间复杂度来说： (1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于0和1之间的常数。 希尔排序 (4)线性阶(O(n))排序 基数排序，此外还有桶、箱排序。 说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）； 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性： 排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。 稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较； 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 数据结构实验报告 实验名称：实验四——排序 学生姓名：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、去掉已做过根节点的元素继续生成小顶堆大数据结构拓扑排序实验报告材料
微机原理-实验一-汇编语言-冒泡排序
插入排序算法实验报告
实验报告
微机原理实验报告-冒泡排序
《数据结构》实验报告——排序.docx
排序操作实验报告
离散数学实验报告四个实验
算法排序问题实验报告
各种排序实验报告
微机原理实验报告冒泡排序
算法实验报告
图的应用的实验报告
北航计算机软件技术基础实验报告计软实验报告3——冒泡排序和快速排序
算法排序问题实验报告
微机原理实验报告-冒泡排序
排序算法实验报告
排序算法实验报告
大数据结构实验四题目一排序实验报告材料
相关主题
文本预览