https://www.doczj.com/doc/a116291770.html,/archives/490
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
1.1 字符串A/B，找出共同包含的最长子串
#include
#include
void max_same_substr( char a[], char b[], char substr[], int *max )
{
int i;
char *ptr;
char tmp[ 20 ] = { 0 };
for ( i = 0; *a != '\0'; ++i ) {
strncat( tmp, a++, 1 ); // add each char to the end of the tmp
ptr = strstr( b, tmp );
if ( ptr != NULL ) {
if ( strlen(tmp) > *max ) {
strcpy( substr, tmp );
*max = strlen( tmp );
}
}
else {
break;
}
}
if ( *a != '\0' )
max_same_substr( a, b, substr, max );
}
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
1）希尔排序
希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 Shell排序的算法实现: 1．不设监视哨的算法描述 void ShellPass(SeqList R，int d) {//希尔排序中的一趟排序，d为当前增量 for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区 if(R[ i ].key R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵 do {//查找R的插入位置 R[j+d]=R[j]； //后移记录 j=j-d； //查找前一记录} while(j>0&&R[0].key R[j+d]=R[0]； //插入R到正确的位置上 } //endif } //ShellPass 2）选择排序 对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了 void SelectSort(RecordType r[], int length) /*对记录数组r做简单选择排序，length为数组的长度*/ { n=length; for ( i=1 ; i<= n－１; ++i) { k=i； for ( j=i+1 ; j<= n ; ++j) if (r[j].key < r[k].key ) k=j； if ( k!=i) { x= r[i]； r[i]= r[k]； r[k]=x; } } } /* SelectSort */ 3）快速排序 #include using namespace std; void QuickSort(int *pData,int left,int right) { int i(left),j(right),middle(0),iTemp(0); middle=pData[(left+right)/2];//求中间值 middle=pData[(rand()%(right-left+1))+left]; //生成大于等于left小于等于right的随机数 do{ while((pData[i] i++; while((pData[j]>middle) && (j>left))//从右扫描小于中值的数 j--; //找到了一对值,交换 if(i<=j) { iTemp=pData[j]; pData[j]=pData[i]; pData[i]=iTemp; i++; j--; } } while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）//当左边部分有值(left if(left { QuickSort(pData,left,j); } //当右边部分有值(right>i)，递归右半边 if(right>i){ QuickSort(pData,i,right); } } 3.递归/非递归实现Fibonacci //递归计算Fibonacci typedef unsigned long ulong; ulong Fiblnacci(int n) if (n <= 2) { return 1; } return Fiblnacci(n - 1) + Fiblnacci(n-2); } //非递归 ulong Fibonacci(int n) { ulong result; ulong prev_result; ulong next_result; result = prev_result = 1; while (n > 2) { n--; next_result = prev_result; prev_result = result; result = prev_result + next_result; } return result; } 本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/a116291770.html,/winglet/archive/2008/05/27/2485140.aspx 3.1 输入一个单链表，输出该单链表中倒数第k个节点 倒数第k个（对应节点数为n的链表）节点的编号为n+1-k，所以从第一个节点移动n-k次即可。 struct node * fun(struct node *head,int k) { int len=0,i=0; struct node * p=head; while(p ) { len++; p=p->next ; } p=head; for (i=1;i p=p->next ; return p; } 4.在链表里如何发现循环链接？ 步长法。 1）初始化两个指针，p=head，q=head 2）循环遍历链表 p=p->next; q=q->next->next 如果有 p=q 的时刻，则说明为循环链表 否则为非循环链表 这个算法的思想是：可以看做两个在那里跑步，一个速度快，一个速度慢，当链表中有个环存在时，相当于这两个人在围绕一个圈跑步，那么跑得快的总会在某一时刻追上那个跑得慢的。 /判断是否为循环链表 bool Link::isLoop() { Note *s,*f;//快慢指针 s=head->next; f=head->next->next; while (s!=NULL && f!=NULL && f->next!=NULL) { if (s == f) return true; s = s->next; f = f->next->next; } return false; } 本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/a116291770.html,/kllmctrl/archive/2010/08/21/5828194.asp x 5.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里（代码？） 假设数组Card[0 - 53]中的54个数对应54张牌，从第一张牌（i = 0）开始直到倒数第二张牌（i = 52），每次生成一个[ i, 53]之间的数r，将Card[i]和Card[r]中的数互换 生成指定范围内的随机数： rand()%(n-m) + m 6.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？） 参考atoi函数 7.给出一个函数来输出一个字符串的所有排列 采用递归的思路，每一层递归的任务是输出当前string[begin, end]的每一个字母，在输出char a = string[begin]之后，对string[begin+1, end]进行递归调用。递归调用结束之后再输出string[begin, end]的第二个字母。然后对string[begin+2, end]进行递归调用。 例如"1234": 第一层递归遍历"1234"，并且输出'1'，之后对"234"进行递归。 第二层递归遍历"234", 这时候用首字母'2'代替在第一层递归中'1'后面的'\0'，然后在'2'后面添加一个'\0'，于是输出"12"。 第三层递归输出"123" 第四层递归输出"1234"。 然后退回到第三层递归。在将'4'添加到"123"后面被输出之后，本来依次输出'4'之后的元素，但是'4'已经是结尾，于是退回到第二层。在第二层中，out之中已有"12"，而且已经输出了"12"后的第一个元素'3'，所以下一步是输出"12"后的第二个元素'4'，所以下一个输出"124"。 以此类推。 其中还需要防止输出完全相同的的子串。如果是"1224"，不能输出两次"124"(分别是第2个'2'和第3个'2')。所以在处理的时候需要判断之前是否已经出现过和当前元素一样的元素。如果有则说明当前元素的工作已经被之前同样的元素做了，不需要再做。这个判断的区间是[rec, i](i为当前元素下标, rec为本层递归需要被轮番代替的那个位置)。 #include using namespace std; void Combine(char in[], char out[], int length, int rec, int start) { int i, j; bool flag; for(i = start; i < length; i++) { flag = false; if (i > start) { for (j = i-1; j >=rec; j--) { if (in[j] == in[i]) { flag = true; break; } } if (flag) { continue; } } out[rec] = in[i]; out[rec+1] = '\0'; cout << out << endl; if(i < length -1) { Combine(in, out, length, rec+1, i+1); } } } 本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/a116291770.html,/jiangyi711/archive/2010/08/22/5830737.a spx本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/a116291770.html,/jiangyi711/archive/2010/08/22/5830737.a spx 8.请编写实现malloc()内存分配函数功能一样的代码（忽略） 9.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。 10.怎样编写一个程序，把一个有序整数数组放到二叉树中 struct student { int value; struct student *lchild; struct student *rchild; }; void arraytotree(int *a, int len, struct student **p) { if(len) { *p = (struct student*)malloc(sizeof(struct student)); (*p)->value = a[len/2]; arraytotree(a, len/2, &((*p)->lchild)); arraytotree(a+len/2+1, len-len/2-1, &((*p)->rchild)); } else { *p = NULL; } } 11.怎样从顶部开始逐层打印二叉树结点数据？请编程 12.怎样把一个链表掉个顺序，单链表的反序（也就是反序，注意链表的边界条件并考虑空链表）？ void reverselist(type &phead1){ type phead2,pbuffer; phead2=null; pbuffer=phead1; while (pbuffer!=null){ phead1=phead1->next; pbuffer->next=phead2; phead2=pbuffer; pbuffer=phead1; } phead1=phead2; } 本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/a116291770.html,/DORIS1984/archive/2008/10/20/3110466.as px ×××××××××××××××××××××××××××××××××××××××××××××××8 https://www.doczj.com/doc/a116291770.html,/notebook/cc-os-data-structure-quest ions-related-to-surface-aggregate/ 1.class和struct有啥区别？struct和union有啥区别？ 2.为什么析构函数经常是虚函数？ 3.static这个关键字有哪些不同的用途？ 4.构造函数可不可以是虚函数？ 5.变量的定义与声明有什么区别？变量定义放在头文件中会带来什么 问题？ 声明变量不分配空间，定义变量要分配空间。多个文件include某个头文件，编译这些文件引起变量重复定义 6.实现函数atoi (或itoa, strcpy, strcmp, memcpy, strstr, strchr 等等不一而足) void itoa(int n, char s[]) { int i, sign; if ((sign=n) <0) n=-n; i=0; do { s[i++]=n%10+ '0 '; }while ((n/=10)> 0); if(sign <0) s[i++] = '- '; s[i]= '\0 '; reverse(s); } char * strcpy(char* dest, const char * src) { char * szRet; memset(szRet, 0, sizeof(szRet)); if(NULL == dest && NULL == src) { return NULL; } *szRet = dest; while((*dest++ = *src++) != '\0'); return szRet; } int strcmp (const char * src, const char * dst) { int ret = 0 ; while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) ++src, ++dst; if ( ret < 0 ) ret = -1 ; else if ( ret > 0 ) ret = 1 ; return( ret ); } void * memcpy (void *destaddr, void const *srcaddr, size_t len) { char *dest = destaddr; char const *src = srcaddr; while (len-- > 0) *dest++ = *src++; return destaddr; } static const char* _strstr(const char* s1, const char* s2) { assert(s2 && s1); const char* p=s1, *r=s2; while(*p!='\0') 《结构体与链表程序设计》实验解答 1、改错题 （1） #include 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 第四阶段（结构体与链表） 1.对候选人得票的统计程序。设有三个候选人，每次输入一个得票的候选人的 名字，要求最后输出各候选人得票结果。本题应该先定义一个结构体，结构体中包含姓名和票数两个变量。 2.建立一个描述个人信息的结构体，包括ID号，姓名，性别，年龄等信息，定 义该结构体数组并初始化，将按年龄分成三个部分（小于18岁，18－60岁，大于60岁），每一部分放在一起打印。 3.建立一个描述个人信息的结构体，包括ID号，姓名，性别，年龄等信息，定 义该结构体数组并初始化，将按年龄分成三个部分（小于18岁，18－60岁，大于60岁），然后定义一个该结构体的二维数组，二维数组的每一行按年龄分别存放同一部分的个人信息。 4.定义一个关于学生成绩的结构体，结构体中包含学生学号，姓名，英语成绩， 数学成绩，总分等信息，你可以定义该结构体的数组并初始化，总分可以通过程序获得，然后按总分为第一关键字，英语成绩为第二关键字将学生成绩信息从高到低排列并存到原数组中。（尽量不要定义新的数组）。 5.在屏幕上模拟显示一个数字式时钟（不要求1秒钟为频率）。结构体中应当定 义三个int变量，hour,minute,second。如何让second加1呢？这个可以使用延时程序，如： Delay() { Int I,j; For(i=0;i<1000;i++) For(j=0;j<1000;j++) {} } 这个延时程序不一定是1秒，只要模拟一下数字时钟就可以了。同时，你可能要用到形式如printf(“%d\r”)的打印，”\r”表示打印时又重新回到本行开头处打印，因为你每更新一次数据时都需要打印，打印的位置没有变化才会像一个电子时钟。 6.设计一结构体，包括ID号（int型），名称（字符串），请定义该结构体的数 组，并给这些数组赋初值，根据ID号将数组进行排序，把ID从小到大排序，不能再定义新的数组。比如：数组的第一个元素的ID号放ID号最小的值，并将这个ID号对应的名称也放在第一个元素的名称中。 7.给定单链表头结点，删除链表中倒数第K个结点。请实现函数struct node* del(struct node *head,int k)；返回新链表的头结点。 HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能学生姓名 学生学号 专业班级 指导老师李晓鸿 完成日期 设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略 二、概要设计 实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include 数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率：O(N2) 3. 插入排序 insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out 数据结构中的排序算法及性能分析 一、引言 排序（sorting ）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。 在此首先明确排序算法的定义： 假设n 个记录的序列为 { 1R ，2R ，…n R } （1） 关键字的序列为： { 1k ，2k ，…，n k } 需要确定1，2，…，n 的一种排列：12,n p p p ，…，使（1）式的序列成为一个按关键字有序的序列： 12p p pn k k k ≤≤≤… 上述定义中的关键字Ki 可以是记录Ri （i=1,2，…，n ）的主关键字，也可以是记录i R 的次关键字，甚至是若干数据项的组合。若在序列中有关键字相等的情况下，即存在i k =j k （1,1,i n j n i j ≤≤≤≤≠），且在排序前的序列中i R 领先于j R 。若在排序后的序列中Ri 仍领先于j R ，则称所用的排 序方法是稳定的；反之若可能使排序后的序列中j R 领先于i R ，则称所用的排序方法是不稳定的。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。 在刚才提到的时间频度中，n 称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。 数据结构各种排序方法的综合比较 结论: 排序方法平均时间最坏时间辅助存储 简单排序O(n2) O(n2) O(1) 快速排序O(nlogn)O(n2)O(logn) 堆排序O(nlogn)O(nlogn)O(1) 归并排序O(nlogn)O(nlogn)O(n) 基数排序O(d(n+rd))O(d(n+rd))O(rd) PS:直接插入排序、冒泡排序为简单排序，希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为 最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法 课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 数据结构-各类排序算法总结 原文转自： https://www.doczj.com/doc/a116291770.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可 能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到 ` 课题：内部排序算法比较… 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： ! |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ~ 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 、 第三章系统设计 （I）友好的人机界面设计：（如图所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| ： （） 1.直接插入排序 //InsertSort.cpp //This function is to sort SqList # include 一、选择题 1、在说明一个结构体变量时系统分配给它的存储空间是（）． A）该结构体中第一个成员所需的存储空间 B）该结构体中最后一个成员所需的存储空间 C）该结构体中占用最大存储空间的成员所需的存储空间 D）该结构体中所有成员所需存储空间的总和。 2．设有以下说明语句，则以下叙述不正确的是( ) struct stu {int a;float b;}stutype; A. struct 是结构体类型的关键字 B. struct stu 是用户定义的结构体类型 C. stutype 是用户定义的结构体类型名 D. a 和b 都是结构体成员名 3、以下对结构体变量stu1中成员age的合法引用是（） #include 习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 数据结构实验报告 实验名称：实验四——排序 学生姓名：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、去掉已做过根节点的元素继续生成小顶堆 int main() { pNode pHead = NULL; // 定义初始化头节点，等价于struct Node *pHead == NULL int data; // 作为Insert_Node函数的第三个参数 int num; // 作为Inset_Node函数第二个参数 int choose; int return_val; pHead = CreateList(); // 创建一个非循环单链表，并将该链表的头结点的地址付给pHead printf("你输入的数据是："); TraverseList(pHead); // 调用遍历链表函数 printf("是否还要进行如下操作：\n"); printf("1.插入数据 2.删除数据\n"); printf("请输入："); scanf("%d",&choose); switch (choose) { case 1: { printf("请输入要在第几个节点前插入数据："); scanf("%d",&num); printf("请输入要插入的数据："); scanf("%d",&data); if(Insert_Node(pHead,num,data) == true) { printf("插入成功\n插入后的数据是：\n"); TraverseList(pHead); } else { printf("插入失败\n"); } printf("操作完成后的数据是："); TraverseList(pHead); break; } case 2: { printf("请输入要删除第几个节点的数据："); scanf("%d",&num); return_val = Del_Node(pHead,num); if (return_val == 0) { 数据结构实训报告 实验名称：数据结构 题目：内部排序比较 专业：班级：姓名：学号：实验日期： 一、实验目的：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。 二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。 三、实验内容 1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种； 2 、待排序的元素的关键字为整数； 3 、比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。 4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。 5、最后要对结果作简单的分析。 6、测试数据：用伪随机数产生程序产生。 四、实验编程结果或过程： 1. 数据定义 typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; 2. 函数如下，代码详见文件“排序比较.cpp” int Create_Sq(SqList &L) void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序 void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法 void QuickSort(SqList &L) void ShellInsert(SqList &L,int dk)//希尔排序 void ShellSort(SqList &L,int dlta[ ]) 3. 运行测试结果，运行结果无误，如下图语速个数为20 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include 几种常见的排序算法之比较 2010-06-20 14:04 数据结构课程 摘要： 排序的基本概念以及其算法的种类，介绍几种常见的排序算法的算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度，然后以表格的形式，清晰直观的表现出它们的复杂度的不同。在研究学习了之前几种排序算法的基础上，讨论发现一种新的排序算法，并通过了进一步的探索，找到了新的排序算法较之前几种算法的优势与不足。 关键词：排序算法复杂度创新算法 一、引言 排序算法，是计算机编程中的一个常见问题。在日常的数据处理中，面对纷繁的数据，我们也许有成百上千种要求，因此只有当数据经过恰当的排序后，才能更符合用户的要求。因此，在过去的数十载里，程序员们为我们留下了几种经典的排序算法，他们都是智慧的结晶。本文将带领读者探索这些有趣的排序算法，其中包括介绍排序算法的某些基本概念以及几种常见算法，分析这些算法的时间复杂度，同时在最后将介绍我们独创的一种排序方法，以供读者参考评判。 二、几种常见算法的介绍及复杂度分析 1.基本概念 1.1稳定排序(stable sort)和非稳定排序 稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 1.2内排序( internal sorting )和外排序( external sorting) 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 #include"stdio.h" #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) #define maxsize 20 typedef int keytype; typedef struct{ keytype key; }RedType; typedef struct{ RedType r[maxsize+1]; int length; }Sqlist; //直接插入排序 void insertsort(Sqlist &L){ int i,j; for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }//if }//insertsort //折半插入排序 void BInsertSort(Sqlist &L) { int i,j,low,high,m; for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low=1; high=i-1; while(low<=high){ m=(low+high)/2; if(LT(L.r[0].key,L.r[m].key)) high=m-1; else low=m+1; }//while for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for实验九 结构体与链表程序设计(解答)
数据结构课程设计(内部排序算法比较_C语言)
结构体和链表编程题目
数据结构各种排序算法的时间性能
数据结构实验八内部排序
数据结构 各种排序算法
数据结构中的内部排序算法及性能分析
数据结构各种排序方法的综合比较
数据结构课程设计(内部排序算法比较 C语言)
数据结构-各类排序算法总结
南邮数据结构上机实验四内排序算法的实现以及性能比较
数据结构课程设计(内部排序算法比较-C语言)
各种排序算法,数据结构中的排序算法
结构体与链表习题 附答案
数据结构第九章排序习题及答案
大数据结构实验四题目一排序实验报告材料
链表的插入、删除实例,C语言 结构体
数据结构内部排序比较分析
数据结构内排序实验报告
数据结构中几种常见的排序算法之比较
数据结构各种常用排序算法综合
相关主题
文本预览