数据结构实验报告(C语言)顺序表排序

数据结构实验报告C语言顺序表排序

计算机科学与技术系

实验报告

专业名称计算机科学与技术课程名称数据结构与算法项目名称排序班级计科一班

学号

姓名

实验日期

格式要求

实验报告注意格式规范，要求在word中编写，文中不要有空行，统一使用A4页面。

页边距：上2.5cm、下2cm、左2.5cm、右2cm。

标题：宋体、四号字、加粗、1.5倍行距。

正文：宋体、小四号字、1.2倍行距。

一、实验目的与要求：

（一）实验目的

1．理解排序算法基本思想。

2．掌握在顺序表上各种排序算法的实现。

3．对线性表排序算法的时间复杂度进行分析。

4．理解顺序表数据结构的特点（优缺点）和适用环境。

（二）实验要求

1．将实验中所要求的每个功能用一个函数实现。

2．每个输入前要有输入提示，每个输出数据都要求有内容说明（如：280和100的和是：380。）。

3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。

二、实验方法：（代码）

#include "stdafx.h"

#include "stdio.h"

#include "malloc.h"

#define MAXSIZE 20

typedef struct{

int r[MAXSIZE+1];

}SqeList;

int InitList();

int CreateList(SqeList *L,int n);

int PrintList(SqeList *L);

//初始化顺序表

int InitList(){

SqeList *L;

L=(SqeList*)malloc(sizeof(SqeList));

if(!L) return -1;

L->length=0; int length;

return 1; }

//创建顺序表

int CreateList(SqeList *L,int n){ int e;

int i;

printf("请输入元素: "); for(i=1;i<=n;i++){

scanf("%d",&e);

L->r[i]=e;

}

L->length=n;

return 1;

}

/*输出顺序表中的元素*/

int PrintList(SqeList *L){ int i;

for(i=1;i<=L->length;i++) printf("%3d",L->r[i]); return 1;

}

//直接插入排序

void InsertSort(SqeList *L){ int i,j;

} for(i=2;i<=L->length;i++){ L->r[0]=L->r[i]; } j=i-1; while(L->r[0] < L->r[j]){ L->r[j+1]=L->r[j]; } L->r[j+1]=L->r[0]; j=j-1;

//希尔排序

void ShellInsert(SqeList *L,int delta){

}

void ShellSort(SqeList *L,int n){

}

//冒泡排序

void BubbleSort(SqeList *L){

int i,j,n,x,change; n=L->length; change=1; for(i=1;i<=n-1 && change;++i){ change=0; for(j=1;j<=n-i-1;++j) if(L->r[j] > L->r[j+1]){ x=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=x; change=1; int i,di; //di代表增量序列，并通过for循环依次计算出di=n/2的值 for(di=n/2;di>0;di/=2){ for(i=0;i<di;i++) } int i,j,k; } for(j=i+delta;j<L->length;j+=delta){ } L->r[0]=L->r[j]; k=j-delta; while(L->r[0]<L->r[k] && k>0){ } L->r[k+delta]=L->r[0]; L->r[k+delta]=L->r[k]; k=k-delta; for(i=1;i<=delta;i++){ ShellInsert(L,di);

}

} }

//快速排序

int Partition(SqeList *L,int left,int right){ int x,low,high;

}

void QuickSort(SqeList *L,int low,int high){

}

//直接选择排序 int mid; if(low<high){ } mid=Partition(L,low,high); QuickSort(L,low,mid-1); x=L->r[left]; low=left; high=right; while(low<high){ } L->r[low]=x; return low; while(L->r[high] >= x && low<high) } while(L->r[low] < x && low<high) } low++; L->r[high]=L->r[low]; high--; high--; L->r[low]=L->r[high]; low++; if(low<high){ if(low<high){ QuickSort(L,mid+1,high);

void SelectSort(SqeList *L){

}

//二路归并

void Merge(SqeList *R,SqeList *MR,int low,int mid,int high){

} int i,j,k; i=low; j=mid+1; k=low; while(i<=mid && j<=high){ } while(i<=mid) MR->r[k++]=R->r[i++]; MR->r[k++]=R->r[j++]; while(j<=high) if(R->r[i]<=R->r[j]){ } else{ } ++k; MR->r[k]=R->r[j]; ++j; MR->r[k]=R->r[i]; ++i; int i,j,n,k,x; n=L->length; for(i=1;i<=n-1;i++){ } k=i; for(j=i+1;j<=n;j++) } if(L->r[j] < L->r[k]) k=j; if(k!=i){ x=L->r[i]; L->r[i]=L->r[k]; L->r[k]=x;

void Mergepass(SqeList *R,SqeList *MR,int len,int n){

}

void MergeSort(SqeList *L){

}

//主函数

int main(int argc, char* argv[])

{

SqeList l; printf("******************************\n");

\n"); \n"); \n"); int n; printf("合肥学院 int len,n; SqeList *MR; MR=(SqeList *)malloc(sizeof(SqeList)); len=1; while(len<n){ } Mergepass(L,MR,len,n); len=2*len; int j,i=1; while(i+len*2-1<=n){ } if(i+len-1<n) else for(j=i;j<=n;j++) MR->r[j]=R->r[j]; Merge(R,MR,i,i+len-1,i+len*2-1); i=i+len*2; Merge(R,MR,i,i+len-1,n); n=L->length; Mergepass(MR,L,len,n); printf("计算机科学与技术 printf("数据结构与算法

printf("作业：查找 \n");

printf("姓名：王康静学号：1504081019\n");

printf("******************************\n");

printf("请输入元素的个数: "); /*输入元素个数*/ scanf("%d",&n);

if(n>0){

printf("\n1-请输入一组数据:\n"); InitList();

CreateList(&l,n);

printf("\n2-遍历线性表中的元素:\n"); PrintList(&l);

printf("\n5-冒泡排序结果为:\n");

printf("\n7-直接选择排序结果为:\n"); SelectSort(&l); PrintList(&l); printf("\n"); printf("\n8-二路归并结果为:\n"); MergeSort(&l); printf("\n6-快速排序结果为:\n"); QuickSort(&l,1,n); PrintList(&l); printf("\n"); BubbleSort(&l); PrintList(&l); printf("\n"); printf("\n4-希尔排序结果为:\n"); ShellSort(&l,n); PrintList(&l); printf("\n"); printf("\n3-直接插入排序结果为:\n"); InsertSort(&l); PrintList(&l); printf("\n"); printf("\n");

PrintList(&l); printf("\n");

}

else

printf("请输入大于0的值: "); return 0;

}

三、实验分析与小结

数据结构实验报告C语言顺序表排序

得分（百分制）

第二篇：数据结构实验四：顺序表的排序实验

一， 实验题目

实验四：顺序表的排序实验

设计算法将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。要求算法的时间尽可能少。

二， 问题分析

本程序要求实现将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。根据题目要求，可以用顺序表来实现。程序所能达到的是将顺序表中的元素根据被3整除的情况有规则的输出。

1，数据的输入形式和输入值的范围：输入的顺序表的个数为大于0且小于顺序表最大长度的整型数据，而顺序表的元素为整型。

2，结果的输出形式：程序正确运行后，应输出顺序表中的元素是：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。

3，测试数据：

（1）顺序表长度i：4，顺序表元素：33,45,78,99

（2）顺序表长度i：5，顺序表元素：-12，-4,10,39,93

（3）顺序表长度i：6，顺序表元素：25，43,8,99,45,32

三， 概要设计

1，为了实现以上程序功能，需要：

1）建立一个含有i个元素的顺序表

2）对顺序表的元素进行分区，将所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。

3）

在屏幕上输出分区后的顺序表元素。

2，本程序包含3个函数

1）主函数main()

2）

顺序表输入函数sqlset()

3）顺序表分区函数dispart()

四， 详细设计

1，顺序表类型定义：

typedef struct{

int r[list_size+1];

int length,a,b,c;

int x[list_size+1]; //用于存放能被3整除的数

int y[list_size+1]; //用于存放除以3余1的数

int z[list_size+1]; //用于存放除以3余2的数

}recordlist;

2，顺序表元素函数伪代码：

recordlist *sqlset(){

recordlist *L; int i;

L->length=-1; //初始化顺序表长度

L->a=0; //初始化存放能被3整除的顺序表的长度

L->b=0;

L->c=0;

scanf("%d",&i);

for(L->length=0;L->length<i;L->length++)

scanf("%d",&L->r[L->length]);

}

3，分块函数伪代码：

recordlist *dispart(recordlist *L,int m){ // m为顺序表的长度

int i;

for(i=0;i<m;i++){

if(L->r[i]%3==0){

L->x[L->a]=L->r[i];

L->a++;}

else if(L->r[i]%3==1) {

L->y[L->b]=L->r[i];

L->b++;}

else {

L->z[L->c]=L->r[i];

L->c++；}

}

for(i=0;i<L->a;i++) printf("%d ",L->x[i]); printf("\t\t");

for(i=0;i<L->b;i++) printf("%d ",L->y[i]); printf("\t\t");

for(i=0;i<L->c;i++) printf("%d ",L->z[i]); printf("\n");

return L;

}

五， 源程序

#include "stdio.h"

#include "malloc.h"

#define list_size 100

typedef struct{

int r[list_size+1];

int length,a,b,c;

int x[list_size+1]; //用于存放能被3整除的数

int y[list_size+1]; //用于存放除以3余1的数

int z[list_size+1]; //用于存放除以3余2的数

}recordlist;

recordlist *sqlset(){ //顺序表元素函数

recordlist *L; //定义一个recordlist型指针变量L

int i;

L=(recordlist*)malloc(sizeof(recordlist)); //为顺序表申请空间

L->length=-1; //初始化顺序表长度

L->a=0; //初始化存放能被3整除的顺序表的长度

L->b=0; //初始化存放除以3余1的顺序表的长度

L->c=0; //初始化存放除以3余2的顺序表的长度

printf("请输入顺序表的长度i(i<list_size):");

scanf("%d",&i);

printf("请输入%d个顺序表元素:",i);

for(L->length=0;L->length<i;L->length++)

scanf("%d",&L->r[L->length]);

return L;

}

recordlist *dispart(recordlist *L,int m){ //顺序表分区函数,m为顺序表的长度

int i;

for(i=0;i<m;i++) //循环条件，当未超出顺序表长度时

{

if(L->r[i]%3==0) //能被3整除的情况

{

L->x[L->a]=L->r[i];

L->a++;

} //把能被3整除的数放到顺序表中

else if(L->r[i]%3==1) //除以3余1的情况

{

L->y[L->b]=L->r[i];

L->b++;

} //把除以3余1的数放到顺序表中

else //除以3余2的情况

{

L->z[L->c]=L->r[i];

L->c++;

} //把除以3余2的数放到顺序表中

}

for(i=0;i<L->a;i++) //输出

printf("%d ",L->x[i]);

printf("\t\t");

for(i=0;i<L->b;i++)

printf("%d ",L->y[i]);

printf("\t\t");

for(i=0;i<L->c;i++)

printf("%d ",L->z[i]);

printf("\n");

return L;

}

void main(){

recordlist *A; //定义一个recordlist型指针变量A

A=sqlset(); //调用输入函数输入顺序表

A=dispart(A,A->length); //调用对元素进行分块输出函数，输出分块后的顺序表元素

}

六， 调试分析

1，在函数调用时弄错了实参的数据类型，导致出错，其中length没有用正确的格式，应该为A->length，而不能直接使用length作为顺序表的长度。

2，在输入顺序表函数中，应返回一个recordlist型的顺序表，而在编程时没有返回，故出现了一个小错误。

七， 使用说明

用户运行该程序后，首先提示用户“请输入顺序表的长度i：”，用户根据提示输入i个书序表元素，输入顺序表元素完毕后，则得到一个新的顺序表，其所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。先输入顺序表元素，再对其分区输出。

八， 测试结果

1，顺序表长度为5，顺序表元素有正有负且除以3后的情况下：

2，顺序表长度为4，顺序表元素均能被3 整除的情况：

2，顺序表长度为6，且除以3后的情况：

相关推荐

数据结构实验报告(C语言)顺序表 排序

第二篇：数据结构实验四：顺序表的排序实验

专栏推荐

数据结构实验报告(C语言)顺序表排序