《数据结构》实验报告——排序（精选4篇）
实验题目：
输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。
实验所使用的数据结构内容及编程思路：
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的记录和枢轴记录互相 1 交换，重复这两不直至low=high为止。
具体实现上述算法是，每交换一对记录需进行3次记录移动（赋值）的操作。而实际上，在排列过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即low=high的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存在r[0]的位置上，排序过程中只作r[low]或r[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。
整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。
3.简单选择排序：其操作为，通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。
显然，对L.r[1„n]中的记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作。可以看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3（n-1）。然后，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为n(n-1)/2。
程序清单： 1．插入排序： #include
for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例：
输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 2快速排序： #include
for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例：
输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 3选择排序： #include
intselectminkey(structsqlist *l,int a){ inti,j=a;for(i=a;i<=l->length;i++)if(l->key[i]
for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例：
输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98
编程感想： 本次编程总共使用了三种排序方法，而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻的了解。
首先，三种排序中，我们都像查表那样，设置了哨兵，而哨兵的使用可以减少对整个表的验空操作，使程序更加节省空间。
其次，对于插入排序，每次都要对一段序列进行检索，每排一次所要检索的序列长度减一，其时间发杂度为O（n^2）。
接着，对于快速排序，这个程序是比较复杂的，总共是3个函数，并且使用了递归的方法，这是但是，这种算法却是最优越的，平均性能也是最好的，我在编这个程序时，对其排序的思想有了进一步的了解，并努力拿他与冒泡排序进行比较，看出了些许其优越性。
还有，就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样，都是O（n^2），性能不如快速排序。
一、实验目的
1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二、实验要求及内容
要求编写的程序所能实现的功能包括：
1、从键盘输入要排序的一组元素的总个数
2、从键盘依次输入要排序的元素值
3、对输入的元素进行快速排序
4、对输入的元素进行折半插入排序
三、实验代码及相关注释
#include
typedef struct { int key;}RedType;
typedef struct { RedType r[100];int length;}SqList;
//1 快速排序的结构体
typedef struct {
int data[100];
int last;}Sequenlist;//2 折半插入排序的结构体
int Partition(SqList &L, int low, int high)
//1 寻找基准
{
L.r[0]=L.r[low];//子表的第一个记录作基准对象
int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： 输入三个整数x,y,z，请把这三个数由小到大输出。输入: 输入数据包含3个整数x,y,z，分别用逗号隔开。输出: 输出由小到大排序后的结果，用空格隔开。样例输入 2,1,3 样例输出2 3 #include int main() { int *p1,p,*p2,*p3,a,b,c; scanf(“%d,%d,%d”,&a,&b,&c); p1=&a; p2=&b; p3=&c; if(*p1>*p2) {p=*p1;*p1=*p2;*p2=p;} if(*p1>*p3) {p=*p1;*p1=*p2;*p2=p;} if(*p2>*p3) {p=*p2;*p2=*p3;*p3=p;} if(*p1>*p3) {p=*p1;*p1=*p2;*p2=p;} if(*p2>*p3) {p=*p2;*p2=*p3;*p3=p;} printf(“%d %d %dn”,a,b,c); return 0; 课程名：数据结构 实验名：线性表及其操作 姓名： 班级： 学号： 撰写时间：2014.09.24 一 实验目的与要求 1.掌握线性表的实现 2.掌握线性表的基本操作的实现 二 实验内容 • 分别完成线性表的顺序表示及链式表示 • 在两种表示上, 分别实现一些线性表的操作, 至少应该包括 – 在第i个位置插入一个元素 – 删除第i个元素 – 返回线性表长 – 返回第i个元素的值 三 实验结果与分析 #include { printf(“%d, ”,(*p).value); p=(*p).next;//指针指向下一个结构体 } printf(“n”);} void Link(){ struct V*head;head=(struct V*)malloc(sizeof(struct V));//开辟一个长度为size的内存 (*head).value=-100;//表头为-100(*head).next=NULL;printf(“------------线性表链式表示------------n”); int i,n=10;struct V*p=head;printf(“10个数据:n”);for(i=0;i (*p).next=(struct V*)malloc(sizeof(struct V)); p=(*p).next; (*p).value=2*i; (*p).next=NULL;} PrintLink(head);//调用PrintLink函数 printf(“删除第四个数据:n”);int k=4;p=head;for(i=1;i p=(*p).next;} struct V*temp=(*p).next;//k表示插入和删除的位置 (*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”); k=10;p=head;for(i=1;i p=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);} //---------线性表顺序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------输出数组元素------------printf(“-------------线性表顺序表示---------n”);for(i=0;i a[i]=i;} printf(“数组元素为:n”);for(i=0;i printf(“%3d”,a[i]);} printf(“n”);//--------插入一个数组元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i if(i { b[i]=a[i]; } else if(i==k) {b[i]=j;} else {b[i]=a[i-1];} } printf(“输出插入一个元素的数组:n”);for(i=0;i { if(i {c[i]=a[i];} else {c[i]=a[i+1];} } printf(“输出删除一个元素的数组:n”);for(i=0;i printf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k位置插入一个元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”); } int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;} 图1：实验结果截图 【《数据结构》实验报告——排序】推荐阅读： 福州大学数据结构实验报告-线性表06-24 实验数据结构与算法06-23 数据处理上机实验报告06-25 数据结构和算法06-10 数据结构课程总结06-27 数据结构课程简介05-26 《数据结构》课程教学反思06-07 大学数据结构考研真题06-29 数据结构试卷及参考答案06-03 数据库上机实验题06-30C语言实验题——三个数排序 篇3
数据结构线性表实验报告 篇4
