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

一， 实验题目
实验四：顺序表的排序实验
设计算法将一个整型数组调整为这样的数组：所有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的数在最左边。
sqlset()
3） 在屏幕上输出分区后的顺序表元素。
main()
2，本程序包含3个函数
1） 主函数main()
dispart()
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后的情况：