实验八 顺序表的排序实验报告

计算机科学与技术系

实 验 报 告

专业名称 计算机科学与技术 课程名称 数据结构与算法 项目名称实验八顺序表的排序实验

班 级

学 号 1 姓 名

同组人员

实验日期

实验八 顺序表的排序实验

实验题目：为希尔排序设计建表函数和主函数，要求输出每一趟排序的结果，

并通过运行来验证

1.问题分析

本程序要求为希尔排序设计建表函数和主函数，要求输出每一趟排序的结果，并通过运行来验证

完成该实验需要以下4个子任务： 1定义一个顺序表的存储结构 ○

2建立顺序表 ○

3定义ShellSort()函数对顺序表L按增量序列di[0]-di[n-1]进行希尔排序 ○

4定义ShellInsert()函数对顺序表L做一趟希尔插入排序 ○

5在主函数中调用函数完成操作 ○

测试数据设计如下：

49 52 65 97 35 13 27 50

2.概要设计

1定义一个顺序表的结构○2建立一个顺序表输为了实现上述程序功能，需要：○

3定义ShellSort()ShellInsert()函数实现入表的长度，再输入表中的元素○

简单顺序查找算法，在ShellSort()函数调用ShellInsert()函数实现排序。4在主函数中调用函数实现操作 返回L○

本程序包含3个函数：

1.主函数:main()

2.建顺序表：SqLset() 3.希尔排序:ShellSort() 4.ShellInsert()函数

各函数关系如下：

Sqlset() Main ()

ShellSort() ShellInsert()

3、 详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出了算法和代码，主程序和模块都需要代码。 （1）顺序表

#define maxlen 50 typedef struct{ //定义顺序表 int r[maxlen]; int last; }Seqlist;

Sequenlist *L;

(2) 建立一个顺序表,输入表的长度，再输入表中的元素 void SqLset(Seqlist *L){ //输入表的长度，再输入表中的元素 int i;

L->last=-1;

printf(\请输入表长:\ scanf(\ if(i>0){

printf(\请输入表中元素:\\n\

for(L->last=1;L->last<=i;L->last++) scanf(\ }

}

(3）定义ShellSort()函数对顺序表L按增量序列di[0]-di[n-1]进行希尔排序 Seqlist *ShellSort(Seqlist *L,int di[],int n){ int i,j;

for(i=0;i<=n-1;i++){

ShellInsert(L,di[i]);

printf(\第%d趟希尔排序，增量为%d，排序之后的结果\\n\

for(int j=1;jlast;j++)

printf(\ printf(\

}

return L; }

（4）定义ShellInsert()函数对顺序表L做一趟希尔插入排序

void ShellInsert(Seqlist *L,int delta){ int i,j,k; for(i=1;i<=delta;i++){ for(j=i+delta;jlast;j=j+delta){ L->r[0]=L->r[j]; k=j-delta; while(L->r[0]r[k] && k>0){ L->r[k+delta]=L->r[k]; k=k-delta; } L->r[k+delta]=L->r[0]; } } }

（5）在主函数中调用函数完成操作 int main()

{

Seqlist *L;

int b[3]={4,2,1};

L=(Seqlist *)malloc(sizeof(Seqlist)); SqLset(L);

L=ShellSort(L,b,3);

printf(\最终希尔排序之后的结果\\n\ for(int i=1;ilast;i++) printf(\

return 0;

}

4、调试分析 编译无错误

5、用户使用说明

程序名为class2.exe，在DEBUG文件夹里面。运行环境Visual c++ 6.0。

6、测试结果

7、附录

#include \#include \#define maxlen 50 typedef struct{ //定义顺序表 int r[maxlen]; int last; }Seqlist;

void SqLset(Seqlist *L){ //输入表的长度，再输入表中的元素

int i; L->last=-1; printf(\请输入表长:\ scanf(\ if(i>0){ printf(\请输入表中元素:\\n\ for(L->last=1;L->last<=i;L->last++) scanf(\ } }

void ShellInsert(Seqlist *L,int delta){ //对顺序表L做一趟希尔插入排序，delta为该趟排序的增量 int i,j,k; for(i=1;i<=delta;i++){

for(j=i+delta;jlast;j=j+delta){ L->r[0]=L->r[j]; k=j-delta; while(L->r[0]r[k] && k>0){ L->r[k+delta]=L->r[k]; k=k-delta; } L->r[k+delta]=L->r[0]; } } }

Seqlist *ShellSort(Seqlist *L,int di[],int n){ //对顺序表L按增量序列di[0]-di[n-1]进行希尔排序 int i,j; for(i=0;i<=n-1;i++){ ShellInsert(L,di[i]); printf(\第%d趟希尔排序，增量为%d，排序之后的结果\\n\ for(int j=1;jlast;j++) printf(\ \ printf(\ } return L; }

int main() { Seqlist *L; int b[3]={4,2,1}; L=(Seqlist *)malloc(sizeof(Seqlist)); SqLset(L); L=ShellSort(L,b,3); printf(\最终希尔排序之后的结果\\n\ for(int i=1;ilast;i++) printf(\ \ return 0; }

for(j=i+delta;jlast;j=j+delta){ L->r[0]=L->r[j]; k=j-delta; while(L->r[0]r[k] && k>0){ L->r[k+delta]=L->r[k]; k=k-delta; } L->r[k+delta]=L->r[0]; } } }

Seqlist *ShellSort(Seqlist *L,int di[],int n){ //对顺序表L按增量序列di[0]-di[n-1]进行希尔排序 int i,j; for(i=0;i<=n-1;i++){ ShellInsert(L,di[i]); printf(\第%d趟希尔排序，增量为%d，排序之后的结果\\n\ for(int j=1;jlast;j++) printf(\ \ printf(\ } return L; }

int main() { Seqlist *L; int b[3]={4,2,1}; L=(Seqlist *)malloc(sizeof(Seqlist)); SqLset(L); L=ShellSort(L,b,3); printf(\最终希尔排序之后的结果\\n\ for(int i=1;ilast;i++) printf(\ \ return 0; }

本文来源：https://www.bwwdw.com/article/z6q8.html