数据结构实验四：顺序表的排序实验.doc

实验题目 实验四：顺序表的排序实验 设计算法将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。要求算法的时间尽可能少。 问题分析 本程序要求实现将一个整型数组调整为这样的数组：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。根据题目要求，可以用顺序表来实现。程序所能达到的是将顺序表中的元素根据被3整除的情况有规则的输出。 数据的输入形式和输入值的范围：输入的顺序表的个数为大于0且小于顺序表最大长度的整型数据，而顺序表的元素为整型。 结果的输出形式：程序正确运行后，应输出顺序表中的元素是：所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。 测试数据： 顺序表长度i：4，顺序表元素：33,45,78,99 顺序表长度i：5，顺序表元素：-12，-4,10,39,93 顺序表长度i：6，顺序表元素：25，43,8,99,45,32 概要设计 1，为了实现以上程序功能，需要： 建立一个含有i个元素的顺序表 对顺序表的元素进行分区，将所有3的倍数在最左边，所有除以3余1的数在中间，而所有除以3余2的数在最左边。 在屏幕上输出分区后的顺序表元素。 2，本程序包含3个函数 主函数main() 顺序表输入函数sqlset() 顺序表分区函数dispart() 详细设计 顺序表类型定义： 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-lengthi;L-length++) scanf(%d,L-r[L-length]); } 3，分块函数伪代码： recordlist *dispart(recordlist *L,int m){ // m为顺序表的长度 int i; for(i=0;im;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;iL-a;i++) printf(%d ,L-x[i]); printf(\t\t); for(i=0;iL-b;i++) printf(%d ,L-y[i]); printf(\t\t); for(i=0;iL-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(ilist_size)