北邮数据结构实验四-排序

数据结构实验报告实验名称：实验四排序（题目1）学生姓名：班级：班内序号：学号：日期：2013年12月19日1．实验要求实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容：使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对2的结果进行分析，验证上述各种算法的时间复杂度。

编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构程序采用的存储机构是顺序存储，如下图所示：2.2 关键算法分析2.2.1 插入排序插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。

一趟直接插入排序的C++描述过程如下：①将待插入纪录赋值给哨兵r[0]：r[0]=r[i];②从后向前进行顺序查找：for(j=i-1;r[0]<r[j];j--);③元素后插：r[j+1]=r[j];④插入记录：r[j+1]=r[j];性能分析：原序列正序时直接插入排序达到最好的时间性能，比较次数为n-1，移动次数为0。

原序列逆序时直接插入排序达到最差时间性能，比较次数为，移动次数为。

直接插入排序的平均时间复杂度为，空间复杂度为。

直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。

2.2.2 希尔排序希尔排序的基本方法是将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。

希尔排序的整个过程如下：for(int d=n/2;d>=1;d=d/2) //以d为增量//在子序列中进行插入排序{for(int i=d+1;i<=n;i++) //一趟希尔排序{if(r[i]<r[i-d]){r[0]=r[i];for(int j=i-d;j>0&&r[0]<r[j];j=j-d)//每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序r[j+d]=r[j];r[j+d]=r[0];}}}性能分析：希尔排序的时间复杂度在和之间，空间复杂度为，是一种不稳定的排序算法。

本章共8道实验题目。

一、直接插入排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行直接插入排序（InsertSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序:#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;//此处定义直接插入排序函数int a[20];int main(){int InsertSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}二、折半插入排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行折半插入排序（BInsertSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;//此处定义折半插入排序函数int a[20];int main(){int BInsertSort ;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}三、希尔排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行希尔排序（ShellSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int ShellSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}四、冒泡排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行冒泡排序（BubbleSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int BubbleSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}五、快速排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行快速排序（QuickSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int QuickSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort (a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}六、简单选择排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行简单选择排序（SelectSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int SelectSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}七、堆排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行堆排序（HeapSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;Status InitList(SqList &L){L.length=0;return 0;}Status CreateList(SqList &L,int n){if(!L.r||n<1||n>MAXSIZE) return ERROR;//cout<<"\n请输入"<<n<<"个元素（用空格隔开）：";for(int i=1;i<=n;i++)cin>>L.r[i].key;L.length=n;return OK;}void ListTraverse(SqList L){//cout<<"L=(";for(int i=1;i<=L.length;i++)cout<<L.r[i].key<<' ';//if(L.length) cout<<'\b';//cout<<")";cout<<endl;}void HeapSort(SqList &L){int value = 0;for(int i = 0;i<L.length;i++)for(int j = 0;j<L.length-i;j++){if(L.r[j].key>L.r[j+1].key){value = L.r[j].key;L.r[j].key= L.r[j+1].key;L.r[j+1].key = value;}}int main(){SqList L;InitList(L);CreateList(L,10);ListTraverse(L);HeapSort(L);ListTraverse(L);return 0;}八、归并排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行二路归并排序（MergeSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef structKeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;Status InitList(SqList &L){L.length=0;return 0;}Status CreateList(SqList &L,int n){if(!L.r||n<1||n>MAXSIZE) return ERROR;//cout<<"\n请输入"<<n<<"个元素（用空格隔开）：";for(int i=1;i<=n;i++)cin>>L.r[i].key;L.length=n;return OK;}void ListTraverse(SqList L){//cout<<"L=(";for(int i=1;i<=L.length;i++)cout<<L.r[i].key<<' ';//if(L.length) cout<<'\b';//cout<<")";cout<<endl;}void MSort(){}void Merge(){}void MergeSort(SqList &L){int value = 0;for(int i = 0;i<L.length;i++)for(int j = 0;j<L.length-i;j++){if(L.r[j].key>L.r[j+1].key){value = L.r[j].key;L.r[j].key= L.r[j+1].key;L.r[j+1].key = value;}}}int main(){SqList L;InitList(L);CreateList(L,10);ListTraverse(L);MergeSort(L);ListTraverse(L);return 0;}。

数据结构实验报告实验名称：实验四——排序学生：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、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; x=r[i]; r[i]=r[j]; r[j]=x; i=j; j=2*i; }}④将堆的根节点移至数组的最后： x=r[1]; r[1]=r[n-i+1]; r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出: for(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位： mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

数据结构实验报告-排序一、实验目的本实验旨在探究不同的排序算法在处理大数据量时的效率和性能表现，并对比它们的优缺点。

二、实验内容本次实验共选择了三种常见的排序算法：冒泡排序、快速排序和归并排序。

三个算法将在同一组随机生成的数据集上进行排序，并记录其性能指标，包括排序时间和所占用的内存空间。

三、实验步骤1. 数据的生成在实验开始前，首先生成一组随机数据作为排序的输入。

定义一个具有大数据量的数组，并随机生成一组在指定范围内的整数，用于后续排序算法的比较。

2. 冒泡排序冒泡排序是一种简单直观的排序算法。

其基本思想是从待排序的数据序列中逐个比较相邻元素的大小，并依次交换，从而将最大（或最小）的元素冒泡到序列的末尾。

重复该过程直到所有数据排序完成。

3. 快速排序快速排序是一种分治策略的排序算法，效率较高。

它将待排序的序列划分成两个子序列，其中一个子序列的所有元素都小于等于另一个子序列的所有元素。

然后对两个子序列分别递归地进行快速排序。

4. 归并排序归并排序是一种稳定的排序算法，使用分治策略将序列拆分成较小的子序列，然后递归地对子序列进行排序，最后再将子序列合并成有序的输出序列。

归并排序相对于其他算法的优势在于其稳定性和对大数据量的高效处理。

四、实验结果经过多次实验，我们得到了以下结果：1. 冒泡排序在数据量较小时，冒泡排序表现良好，但随着数据规模的增大，其性能明显下降。

排序时间随数据量的增长呈平方级别增加。

2. 快速排序相比冒泡排序，快速排序在大数据量下的表现更佳。

它的排序时间线性增长，且具有较低的内存占用。

3. 归并排序归并排序在各种数据规模下都有较好的表现。

它的排序时间与数据量呈对数级别增长，且对内存的使用相对较高。

五、实验分析根据实验结果，我们可以得出以下结论：1. 冒泡排序适用于数据较小的排序任务，但面对大数据量时表现较差，不推荐用于处理大规模数据。

2. 快速排序是一种高效的排序算法，适用于各种数据规模。

数据结构实验报告实验名称：实验四——链表的排序学生姓名：班级：班内序号：学号：日期：1．实验要求[内容要求]使用链表实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性代码要求1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2. 程序分析2.1 存储结构[内容要求]存储结构：双链表2.2 关键算法分析[内容要求]定义类：template <class T>class LinkList{public:LinkList(){front = new Node <T>;front->next=rear;front->prior=NULL;rear=newNode<T>;rear->next=NULL;rear->prior=front;}LinkList(T a[],int n);void BackLinkList(T a[]);//恢复原链表~LinkList();//析构函数void PrintList();//打印数列void InsertSort();//插入排序void BubbleSort();//冒泡排序Node <T>* Partion(Node <T> *i,Node <T> *j);//快速排序中寻找轴值的函数void Qsort(Node <T> *i,Node <T> *j);//快速排序void SelectSort();//选择排序Node<T>*front;Node<T>*rear;};成员函数包括：构造函数：单链表，打印单链表，插入排序，快速排序，冒泡排序，选择排序，析构函数公有成员：头指针和尾指针1、构造函数：LinkList<T>::LinkList(T a[],int n){front=new Node<T>;rear=new Node<T>;front->prior=NULL;front->next=rear;rear->next=NULL;rear->prior=front;Node <T>*s;for (int i=n-1;i>=0;i--){s=new Node<T>;s->data=a[i];s->next=front->next;front->next=s;s->prior=front;s->next->prior=s;}}2、析构函数LinkList<T>::~LinkList(){Node<T> *p=front->next;while(p->next!=NULL){delete p->prior;p=p->next;}delete rear;front=NULL;rear=NULL;}3、打印函数template <class T>void LinkList<T>::PrintList(){Node<T> *p=front->next;while(p->next!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;}4、插入排序template <class T>void LinkList<T>::InsertSort(){Node<T> *p=front->next->next;Node<T> *q;T temp;while (p->next!=NULL){if (p->data<p->prior->data){temp=p->data;MoveCount++;q=p->prior;while (temp<q->data){q->next->data=q->data;q=q->prior;CompareCount++;MoveCount++;}q->next->data=temp;MoveCount++;}CompareCount++;p=p->next;}}将链表分为有序区和无序区，分别将无序区的每一个元素插入到有序区的相应位置。

数据结构排序实验报告1. 引言数据结构是计算机科学中的重要概念，它涉及组织和管理数据的方式。

排序算法是数据结构中的重要部分，它可以将一组无序的数据按照一定的规则进行重新排列，以便更容易进行搜索和查找。

在本实验中，我们将对不同的排序算法进行研究和实验，并对其性能进行评估。

2. 实验目的本实验旨在通过比较不同排序算法的性能，深入了解各算法的特点，从而选择最适合特定场景的排序算法。

3. 实验方法本实验使用C++编程语言实现了以下排序算法：冒泡排序、选择排序、插入排序、快速排序和归并排序。

为了评估这些算法的性能，我们设计了一组实验来测试它们在不同数据规模下的排序时间。

4. 实验过程4.1 数据生成首先，我们生成了一组随机的整数数据作为排序的输入。

数据规模从小到大递增，以便观察不同算法在不同规模下的性能差异。

4.2 排序算法实现接下来，我们根据实验要求，使用C++编程语言实现了冒泡排序、选择排序、插入排序、快速排序和归并排序。

每个算法被实现为一个独立的函数，并按照实验顺序被调用。

4.3 性能评估我们使用计时器函数来测量每个排序算法的执行时间。

在测试过程中，我们多次运行每个算法，取平均值以减小误差。

5. 实验结果我们将在不同数据规模下运行每个排序算法，并记录它们的执行时间。

下表展示了我们的实验结果：数据规模（n）冒泡排序选择排序插入排序快速排序归并排序1000 2ms 3ms 1ms 1ms 1ms5000 20ms 15ms 10ms 3ms 5ms10000 85ms 60ms 30ms 5ms 10ms50000 2150ms 1500ms 700ms 10ms 15ms从上表我们可以观察到，随着数据规模的增加，冒泡排序和选择排序的执行时间呈指数级增长，而插入排序、快速排序和归并排序的执行时间则相对较稳定。

此外，当数据规模较大时，快速排序和归并排序的性能远优于其他排序算法。

6. 实验结论根据实验结果，我们可以得出以下结论：- 冒泡排序和选择排序是简单但效率较低的排序算法，仅适用于较小规模的数据排序。

数据结构实验报告排序姓名：13-计算机-舞学号：0000000000专业：计算机科学与技术班级：计算机13-2班日期：2014年6月6日星期五一、实验目的和要求通过编程实现直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序。

要求输入一些无序数，执行程序后使他们变成有序数并在窗口输出。

二、实验环境1、windows 72、c-free 5.0三、实验内容用五种排序算法对输入的数进行排序，并在屏幕中输出。

四、实验过程1、直接插入排序：即将所需要排序的数据分成两部分，其中一部分为已排好序部分，另一部分为未排序部分。

然后从未排序部分中选出一元素插入到一排序部分中，要求插入后已排序部分任然有序。

在编写该程序时，我将要排序的数据储存在一个数组中，并将第一个数划分为已经排序部分然后从下一个数开始不断和前边的最后一个数比较，知道找到插入位置。

2、希尔排序：希尔排序是建立在直接插入排序的基础之上的，他是通过将数据分成几组，在组内实现插入排序，使整个数据基本有序，最后再对整个数据实现插入排序。

这里同样将数据储存在数组中，分组的步长每次取之前步长的一半。

需要注意的是，移动元素时，下标不再是减1，而是减去步长。

3、冒泡排序：通过不断比较相邻的两个元素，发现倒序即交换，最终实现排序。

在这个程序中，我从后面开始向前比较。

每依次循环可以最终确定一个元素在其最终位置上，所以每次循环之后，元素间的两两比较次数减1.4、快速排序：选定一个元素作为中间元素，将整个数据分为比中间元素小的一组和比中间元素大的一组，并且小的在中间元素前，大的在中间元素后。

再分好的两组内再次重复上诉过程使所有元素排好序。

5、直接选择排序：将待排序数据存入数组中，扫描一遍数组，将其中最小的元素找出并放在第一位，再扫描一遍剩下的元素，找到最小的放在第二位。

如此不断重复知道扫描了n-1次。

由于不要再开新空间，所以找到最小元素时用交换的方式使其放在第一位。

比如第一遍扫描，假设第一个为最小元素，再扫描过程中，如果发现比它小的数，则把第一个元素和该位置的元素交换。

《数据结构》实验报告排序实验题目：输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。

实验所使用的数据结构内容及编程思路：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为止。

数据结构实验报告实验名称：________链表排序___________ 学生姓名：_____________________班级：________________班内序号：_________________________ 学号：________________日期：_______________1．实验要求使用链表实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试排序算法的正确性2. 程序分析2.1 存储结构双向链表2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)2.3 关键算法分析定义节点：struct Node{int data;Node* next;Node* period;};插入排序：void InsertionSort(Node*q,int n){Node*first=q;Node*teq=q;Node*p=q->next;Node*point=p;int w,time=0,compar=0;while(p!=NULL){compar+=1;if(p->data<p->period->data){w=p->data;teq=p->period;while(teq!=NULL){compar+=1;if(teq->data>w){teq->next->data=teq->data;time+=1;if(teq->period==NULL){teq->data=w;time+=1;}}else{teq->next->data=w;time+=1;break;}teq=teq->period;}compar-=1;}p=p->next;}cout<<"插入排序后序列：";while(first!=NULL){cout<<first->data<<" ";first=first->next;}cout<<"\n插入排序比较次数为:"<<compar<<endl;cout<<"插入排序移动次数为:"<<time<<endl;}将链表分为有序区和无序区，分别将无序区的每一个元素插入到有序区的相应位置。

实验4快速排序一、实验目的和要求1 在掌握各种排序方法的排序过程的基础上，完成快速排序算法程序设计。

2 能够对排序算法进行基本的复杂度分析。

二、实验内容排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。

快速排序在待排序记录序列中任取一个记录作为枢轴，以它作为比较的“基准”，将待排序划分为左右两个子序列，使行左边子序列中记录的关键字均小于等于枢轴，右边子序列中各记录的关键字都大于等于枢轴。

对所划分的两组分别重复上述过程，直到各个序列的记录个数为1时为止。

快速排序函数原型QuickSort(SeqList sq)。

设计一个算法，在顺序表存储结构上实现快速排序。

排序数据为学生的考试成绩单。

成绩单由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生的成绩单按照名次列打印出每个学生的名次、学号、姓名和成绩。

三、实验步骤1．输入待排序的记录2. 对自定义记录类型重载比较运算符3．排序1）并选择第一个记录作为pivotkey记录2）从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+13）.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-14）重复2),3)，直到low=high，将枢轴记录放在low(high)指向的位置5）重复2),3),4)，直到整个记录有序为止6) 输出排序记录，完成比较。

4. 附加要求：不采用运算法重载的方式，而是定义compare函数指针，通过传给quicksort 函数指针，完成排序。

四、实验提示算法实现：#include "iostream.h"#define MaxSize 100typedef int DataType;class CRecord{public:int No;string name;int grade;}Typdef CRecord DataType;class SeqList{public:CRecord * data;int length;}//创建顺序表V oid SLCreat(SeqList & sq);{ CRecord x;length = 0;cout <<"请输入数据元素数”;cin>>sq.length;sq.data= new CRecord[sq.length];cout <<"请输入数据元素值: no, , name grade ";for(int i = 0; i < n; i++){cin >> sq.data[i].no>>sq .data[i].name>>sq. data[i]grade;}}//排序V oid Sort( SeqList & sq ){ SLCreat(sq);QuickSort(sq,0,sq.length);}//快速排序void QuickSort(SeqList & sq, int low, int high){ int pos;if(low < high){ pos = partition(sq,low, high);QuickSort(sq,low, pos-1);QuickSort(sq, pos+1, high);}}int partition(SeqList & list, int i, int j){ DataType pivotkey;pivotkey = list[i];while(i < j){ while(i < j&&list[j] >= pivotkey) --j;if(i < j) list[i++] = list[j];while(i < j&&list[i] <= pivotkey) ++i;if(i < j) list[j--] = list[i];}list[i] = pivotkeylreturn i;}//将顺序表显示在屏幕上void SLPrint(SeqList & sq){cout <<"快速排序结果: "’for(int i = 0; i <list.length; i++)cout<<i<<sq.data[i].no<<sq .data[i].name<<sq. data[i].grade<<endl;cout << endl;}void main( ){ SeqList myList;SLCreat(SeqList &mylist);Sort(mylist );SLPrint( );}。

北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。

二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。

具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。

2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。

具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。

3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。

具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。

4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。

具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。

5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。

具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。

数据结构实验报告实验名称：学生姓名：班级：班内序号：学号：日期：实验描述：使用链表实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他一．程序分析1.存储结构：双向链表2.关键算法分析：a)插入排序：⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。

用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；⒊重复第二步，共进行n-i次插入处理，数列全部有序。

b)冒泡排序：1.比较相邻的元素。

如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

c)快速排序：一趟快速排序的算法是：1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；5.重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。

找到符合条件的值，进行交换的时候i，j指针位置不变。

另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

d)简单选择排序：设所排序序列的记录个数为n。

i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。

[键入公司名称]数据结构实验报告——排序实验四一、实验目的和要求：1.掌握各种排序方法的排序过程；2.了解一些排序算法的实现，如插入排序、选择排序、冒泡排序、快速排序、堆排序等。

二、实验原理：1.排序的相关术语：内部排序：对内存中的数据进行排序，即排序不涉及数据内、外存交换。

外部排序：按照某种策略将外存数据分批调入内存进行排序，从而达到整体有序。

排序时涉及数据的内、外存交换。

关键字：用于标识记录的数据项。

排序方法的稳定性：具有相同关键字的记录之间相对次序保持不变的排序方法是稳定的，否则是不稳定的。

堆：关键字K1，K2，…Kn构成堆当且仅当排序满足如下性质：（1）Ki<=K2i且Ki<=K2i+1或Ki>=K2i且Ki>=K2i+1(1<=i<=n/2)就地排序：排序算法所需的辅助空间不依赖于问题的规模n.2.排序方法：插入排序：a.直接插入排序b.希尔排序：将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

交换排序：a.冒泡排序b.快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小。

然后分别对这两部分记录继续进行排序，以达到整个序列有序。

选择排序：a.简单选择排序b.堆排序归并排序：将两个或两个以上的有序表组合成一个新的有序表。

三、实验内容：学生成绩由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生信息实现：（1）按分数的高低排序，打印每个学生在考试中的排名，分数相同的为同一名次，同一名次的同学按学号从小到大排列。

（2）按照名次列出每个学生的名次、学号、姓名和成绩。

四、程序设计：（1）程序设计思想：建立一个学生类：其中包含学生的基本信息：学号、姓名成绩以及名次。

主函数包括：学生信息输入函数：要求从键盘上输入学生的学号、姓名、以及成绩。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

数据结构实验报告实验名称：实验四——排序学生姓名：1．实验要求实验目的：通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

题目2：使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：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、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; x=r[i]; r[i]=r[j]; r[j]=x; i=j; j=2*i; }}④将堆的根节点移至数组的最后： x=r[1]; r[1]=r[n-i+1]; r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出: for(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位：mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

实验报告实验目的：1.掌握各种排序方法的排序过程；2.了解一些排序算法的实现。

实验内容：学生的考试成绩表由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生信息实现：1.按分数高低排序，打印出每个学生在考试中的排名，分数相同的为同一名次，同一名次的学生按学号从小到大排列。

2.按照名次列出每个学生的名次、学号、姓名、成绩。

实验原理：排序分为插入排序、交换排序、选择排序、归并排序等。

插入排序又分为直接插入排序、其他插入排序和希尔排序；交换排序分为冒泡排序和快速排序；选择排序又分为简单选择排序和堆排序。

不同的排序方法各有利弊，根据具体的情况选择合适的排序方法。

设计思想:本程序采用简单选择排序的方法。

程序中定义一个stu结构和student类。

类中定义creat 创建函数，selectgrade成绩排序函数，samegrade、selectnum成绩相同的按学号排序函数，print输出函数。

按照选择排序的思想，先对成绩按照从高到低进行排序；然后寻找成绩相同的部分，对该局部元素的学号从小到大进行排序。

然后调用输出函数，输出名次、学号、姓名、成绩。

实现部分:源代码：#include<iostream.h>struct stu{int num;char name[100];int grade;};class student{ struct stu s[100];int length;int start,end;public:student(){length=0;}void creat();void selectgrade();void samegrade();void selectnum();void print();};//创建顺序表void student::creat(){cout<<"请依次输入学生的学号、姓名、成绩。

输入#结束:"<<endl; int num;cin>>num;while(num){s[length].num=num;cin>>s[length].name;cin>>s[length].grade;cin>>num;length++;}}//对成绩进行选择排序void student::selectgrade(){stu temp;int i,j,k;for(i=0;i<length;i++){k=i;for(j=i+1;j<length;j++){if(s[j].grade>s[k].grade)k=j;}if(k!=i){temp=s[i];s[i]=s[k];s[k]=temp;}}}//对成绩相同的学号进行选择排序void student::samegrade(){int i,j;for(i=0;i<length;i++){if(s[i].grade==s[i+1].grade){for(j=length-1;;j--){if(s[j].grade==s[i].grade)break;}start=i;end=j;i=j;}selectnum();}}//对学号进行选择排序void student::selectnum(){stu temp;int i,j,k;for(i=start;i<=end;i++){k=i;for(j=i+1;j<=end;j++){if(s[j].num<s[k].num)k=j;}if(k!=i){temp=s[i];s[i]=s[k];s[k]=temp;}}}void student::print(){int i,j=0,k=0;cout<<"成绩从高到低依次为（成绩相同按学号从小到大排列）"<<endl;cout<<"名次学号姓名成绩"<<endl;for(i=0;i<length;i++){ if(i==0)cout<<k+1<<" "<<s[i].num<<" "<<s[i].name<<""<<s[i].grade<<endl;else{if(s[i].grade==s[i-1].grade){j++;k=i-j;}else {j=0;k=i-j;}cout<<k+1<<" "<<s[i].num<<" "<<s[i].name<<" "<<s[i].grade<<endl;} }}int main(){student ss;ss.creat();ss.selectgrade();ss.samegrade();ss.print();}测试用例1.实验小节：通过本程序的练习，对各种排序方法的排序过程有了更深的了解，对各种排序算法的实现特别是选择排序有了更深的认识。

数据结构实验报告排序数据结构实验报告：排序引言：排序是计算机科学中常见的算法问题之一，它的目标是将一组无序的数据按照特定的规则进行排列，以便于后续的查找、统计和分析。

在本次实验中，我们将学习和实现几种常见的排序算法，并对它们的性能进行比较和分析。

一、冒泡排序冒泡排序是最简单的排序算法之一，它通过不断交换相邻的元素，将较大（或较小）的元素逐渐“冒泡”到数组的一端。

具体实现时，我们可以使用两层循环来比较和交换元素，直到整个数组有序。

二、插入排序插入排序的思想是将数组分为两个部分：已排序部分和未排序部分。

每次从未排序部分中取出一个元素，插入到已排序部分的适当位置，以保持已排序部分的有序性。

插入排序的实现可以使用一层循环和适当的元素交换。

三、选择排序选择排序每次从未排序部分中选择最小（或最大）的元素，与未排序部分的第一个元素进行交换。

通过不断选择最小（或最大）的元素，将其放置到已排序部分的末尾，从而逐渐形成有序序列。

四、快速排序快速排序是一种分治的排序算法，它通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素都小于等于基准元素，另一个子数组的所有元素都大于基准元素。

然后对两个子数组分别递归地进行快速排序，最终将整个数组排序。

五、归并排序归并排序也是一种分治的排序算法，它将数组划分为多个子数组，对每个子数组进行排序，然后再将排好序的子数组合并成一个有序的数组。

归并排序的实现可以使用递归或迭代的方式。

六、性能比较与分析在本次实验中，我们对以上几种排序算法进行了实现，并通过对不同规模的随机数组进行排序，比较了它们的性能。

我们使用了计算排序时间的方式，并记录了每种算法在不同规模下的运行时间。

通过对比实验结果，我们可以得出以下结论：1. 冒泡排序和插入排序在处理小规模数据时表现较好，但在处理大规模数据时性能较差，因为它们的时间复杂度为O(n^2)。

2. 选择排序的时间复杂度也为O(n^2)，与冒泡排序和插入排序相似，但相对而言，选择排序的性能稍好一些。

实验十五排序1.实验目的（1）掌握各种排序的基本思想。

（2）掌握各种排序算法实现方法。

2.实验内容随机函数产生若干个随机数，用直接插入、冒泡、快速等排序方法排序。

3.实验要求（1）根据实验内容编写程序，上机调试并获得运行结果（2）撰写实验报告4.关键步骤与算法(1)直接插入算法步骤；1）将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列的第一个记录，无序区包括所有剩余待排序的记录。

2）将无序区的第一个记录插入到有序区的合适位置，从而使无序区减少一个记录，有序区增加一个记录。

3）重复执行第（2）步，直到无序区中没有记录为止。

算法如下；1.//插入排序2.void SortC(SqList *L){3.int i, j;4.for (i = 2; i <= L->length;i++){5. L->R[0] = L->R[i];6. j = i - 1;7.while(LT(L->R[0].key,8. L->R[j].key)){9. L->R[j + 1] = L->R[j];10. j--;11. }12. L->R[j + 1] = L->R[0];13. }14.}(2)冒泡排序算法步骤；冒泡排序的基本思想是对所有相邻记录的关键字进行比效，如果是逆序（a ［i］＞a［j＋1］），则将其交换，最终达到有序化，其处理过程如下。

1）将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区则包括所有待排序的记录。

2）对无序区从前往后依次将相邻记录的关键字进行比较，若逆序，则将其交换，从而使得关键字小的记录向上“飘浮”（左移），关键字大的记录好像石块，向下“坠落”（右移）。

每经过一趟冒泡排序，都使无序区中关键字最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。

数据结构实验报告实验名称：实验4——题目4——哈夫曼树学生姓名：班级：班内序号：学号：日期：2017年1月6日1．实验要求利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析2.1 存储结构本实验的存储结构为哈夫曼树与哈夫曼编码表哈夫曼树：存储结构：struct HNode//哈夫曼树的结点结构{int weight;//结点权值int parent;//双亲指针int LChild;//左孩子指针int RChild;//右孩子指针};哈夫曼编码表：struct HCode//编码表的结点结构{char data;//字符char code[10];//编码int k;//码长};存储结构：2.2 关键算法分析一、初始化：步骤：1、设立数组，记录每一个字符出现的次数与字符对应的ASCII码2、以字符不是回车或换行遍历输入的字符数组3、将存储出现次数大于0的字符存储进叶子节点数组4、相对应的，存储叶子结点的数据域字符出现的次数。

时间复杂度：O（n）空间复杂度：O（n）二、创建哈夫曼树步骤：1、创建2n-1个数节点2、将权值数组依次赋值进0到n-1的权值节点中3、从0到i-1（最开始等于n-1）选择两个权值最小的节点x、y，将其连接为i节点的左右孩子，改变x、y的双亲指针为i节点4、I++，循环步骤4直到2n-1时间复杂度：O（n^2）空间复杂度 O（n）三、创建哈夫曼编码表步骤：1、创建n个编码表节点2、依次将叶子节点的字符放入编码表节点数据域中3、对每个编码表对应的树结点，向根节点开始回溯（为父节点的左孩子编码值为0，右孩子为1，不断上移，直到根节点）4、进行倒置时间复杂度O（n）空间复杂度 O（n）四、编码步骤：1、新建编码数组2、从源码第一个字符开始在编码表中寻找到相应字符后将编码复制进编码数组3、计算压缩比时间复杂度O（n+e） n为源码 e为编码数组长度空间复杂度O（n）五、解码步骤：1、从根节点开始，按照编码串寻找（0为左子树，1为右子树）2、直到该节点无子树，将该节点（也就是叶子节点）字符放入解码串中3、重复步骤1、2直到编码串结束时间复杂度O（n） n为编码串长度空间复杂度O（e） e为原串长度六、打印哈夫曼树步骤：1、从根节点开始第m层前方空m个格2、叶子结点先输出数据域再在下一行输出权值3、重复输出，递归调用，直到叶子。