数据结构课程设计 多关键字排序 高考排序
淮 海 工 学 院 计算机工程学院
课程设计报告
设计名称： 选题名称： 姓 名： 专业班级： 系 （院）： 设计时间： 设计地点：
数据结构课程设计 多关键字排序
周宣 学 号： 110821120 网络工程 081
计算机工程学院 2009.12.28~2010.1.12 软件工程实验室、教室
指导教师评语：
成绩：
签名：
年月日
数据结构课程设计报告
第 1 页，共 页
1．课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序 求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水 平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
2．课程设计任务与要求：
任务
题目：多关键字的排序
【问题描述】 多关键字的排序有其一定的实用范围。例如：在进行高考分数处理时，除了需对总分进行排序外， 不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求 排出考生录取的次序。 【基本要求】 （1）假设待排序的记录不超过 10000，表中记录的关键字数不超过 5，各个学科关键字的范围均为 0 至 100，总分关键字的范围是 0-300。按用户给定的进行排序的关键字的优先关系，输出排序结果。 （2）约定按 LSD 法进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用 稳定的内部排序法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。 【测试数据】 由随机数产生器生成。 【实现提示】 由于是按 LSD 方法进行排序，则对每个关键字均可进行整个序列的排序，但在利用通常的内部排序 方法进行排序时，必须选用稳定的排序方法 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计 实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准 备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加 大代码的重用率。 2、.设计的题目要求达到一定工作量（300 行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用 C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于 10 页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。
数据结构课程设计报告
第 2 页，共 页
3．课程设计说明书
一 需求分析 1）选题功能分析
【题目的意义】 1、 对高考分数按照总分和不同学科的分数按照优先级顺序排出考生录取的次序，以满足 不同专业对单科分数的要求。 2、 对不同排序策略进行综合比较。
【实现的功能】 1、 用 C 语言设计实现一个高考成绩排序系统。 2、 创建模拟的高考考生成绩表，存放到 txt 文档中。考生考号为 1，2，3…用伪随机数生成器 生成各考号学生的各个学科成绩，并计算总分成绩。 3、 由于实际中高考考生成绩表是已知的（模拟创建的 txt 文档），程序能从文件中读取数据。 从创建的考生成绩表中读取数据，并对数据处理 4、 按照学科的优先级顺序，对学生的成绩排序。既可以以某一学科的单科成绩优先级最高排 序，也可以先按总分优先级最高来排序。 5、 在对各个关键字即单科成绩进行排序的时候，分别用稳定的内部排序法（冒泡法）以及“‘分 配’和‘搜集’”的方法进行排序。 6、 能够对冒泡法排序策略和“‘分配’和‘搜集’”方法排序策略进行的执行时间进行比较。 7、 输入数据：1 各科英文首字母的代号，字符型，如 smce 2 整型数，0-10000 1 输出程序用两种方法进行排序的进程和执行时间 2 输出前 n 名学生的信息
二 概要设计
1、 伪随机生成的数据包含语文、数学、英语三科成绩。总成绩为语文、数学、英语三科成绩的 和。学号按成绩数组的下标赋值，生成学生成绩记录，将该记录保存到 txt 文档中
2、 从上面的 txt 文档中读取数据到一个二维数组中，以便对学生信息进行处理
3、 给出排序的优先关系，根据优先关系由低位向高位逐个关键字进行排序。
4、对单科成绩进行排序的时候，单科成绩虽然是 0-100，但总成绩是 0-300，所以要建 301 个队
列进行排序，先按“分配”和“搜集”的方法进行一趟“基数排序”；然后再按照稳定的内
部排序法（冒泡法）进行排序。将搜集好的或排序好的序列存储，以进行对次优先级的关键
字进行再排序。
5、将排序好的学生成绩按照用户提出的提取人数的要求，保存到另一个 txt 文档中，并输出到
屏幕
6、系统用到的抽象数据类型定义 double BubTime1, //按第一个关键字代表的学科成绩用冒泡法排序执行的时间
BubTime2,
BubTime3,
BubTime4, BubTimeSum, DCTime1, 行的时间
//冒泡法排序的总时间 //按第一个关键字代表的学科成绩用分配和收集的方法执
DCTime2,
DCTime3,
数据结构课程设计报告
第 3 页，共 页
DCTime4,
DCTimeSum;
//分配和收集法排序的总时间
int score[10000][5], //随机创建的模拟学生记录源数组
bubble[10000][5], //进行冒泡法排序时用来存放学生记录源数组，并且随排序
进行数组中的记录发生交换
copy[10000][5]; //从模拟的学生记录源 txt 文件中读取学生记录到该数组
struct LSD d[301];
//分配数组，该处考虑到把总分（0-300）也列入优先级序
列中，因此建立了 301 个队列
int *c[10000];
//用来存放收集到的学生记录
char x[5];
//存放有优先关系的学科代号序列
7、系统中的各个函数模块
1：void CreatScore(int score[10000][5]);
//随机创建学生记录表 score。正常
高考中该表是已知的，不必创建
2：void Collect(struct LSD d[301],int *c[10000]); 分配好的记录收集到 c 指针数组保存
3：void InitDivide(struct LSD d[301]); 一次收集后必须做的工作
//LSD 法排序中的收集函数，即将 //用于初始化临时分配数组，在每
4：double DCSort(struct LSD d[301],int *c[10000],int n); //分配（Divide）和收集（Collect） 排序的方法
5：double BubbleSort(int score[10000][5],int n); 6：void Print(); 出到屏幕上
//冒泡法排序 //将排序结果文件中的记录数据输
7：void savesources(int score[10000][5],int n); 存放到文件中
//将模拟创建的高考学生信息记录
8：void saveresults(int score[10000][5],int n); 的学生记录），将这 n 条学生的记录存放到新的文件中
9:void load(int score[10000][5]); 取记录到该二维数组中
//按照用户的要求（总成绩在前多少名 //从学生高考记录源文件中读
8、 各函数之间的调用关系 1:主函数可以调用除子函数 2 之外的所有函数 2：子函数 4 可以调用子函数 2 和 3
【功能模块图】
数据结构课程设计报告
第 4 页，共 页
InitDivide(d)
CreateScore(score)
M
Savesources(score.10000)
A
I
Lode(copy)
N
返回执行时间
Collect(d,c)
Print()
DcSort(d,c,0)
返回执行时 间 BubbleSort(bubble,0)
Saveresults(bubble,n)
InitDivide(d)
三 详细设计
1.抽象数据类型：
该数据类型是在分配和收集的时候存放分配成绩数组
1’ 抽象数据类型 struct LSD
struct LSD//队列的结构类型，链表存储结构类型 {
int *cur;//当前位置 struct LSD *next;//队列中下一个位置 };
2’ CreatScore(int score[RecordNumber][KeyNumber])函数
/*创建一个含有 RecordNumber 名学生成绩记录的 score,包含语文、数学、英语、总分和学号,随机生成语 文、数学、英语的成绩。
*传递的参数是成绩数组 score，无返回值
*/
void CreatScore(int score[RecordNumber][KeyNumber])
{
/*伪随机生成语文、数学、英语的成绩*/
for(i=0;i< RecordNumber;i++)
{
for(j=0;j<3;j++)
{ score[i][j]=rand()%101;
//成绩的范围是 0-100
}
}
/*总分成绩初始化*/
for(i=0;i< RecordNumber;i++)
{
数据结构课程设计报告
第 5 页，共 页
score[i][3]=score[i][0]+score[i][1]+score[i][2]; //总成绩为各科成绩之和
} /*学号的初始化*/
for(i=0;i< RecordNumber;i++) score[i][4]=i+1;
//学号是按从前到后的顺序依次赋值的
}
start
创建 Score[1000][5] 含语文、 数学、英语、总分和学号
伪随机生成语文、数学、英 语的成绩
初始化总分
生成学号，按从前到后顺序
结束
3’收集函数 Collect(struct LSD d[QueueNumber],int *c[RecordNumber])
/*将分配好的成绩数组 d，收集到 c 指针数组保存 * 传递的参数为分配好的数组 d 和收集的指针数组 c，无返回值
*/
void
{
struct LSD *p;
for(i=QueueNumber-1; i>=0; i--)
{ if(d[i].cur!=NULL)
//当前队列不空，即有学生的成绩分配到该队列
{
p=&d[i]; while(p->cur!=NULL)
//当前位置有学生的成绩
{
c[j]=p->cur;
//收集到 c 指针数组中
j++; p=p->next;
//指针 p 指向该队列的下一个位置
}
}
}
}
当
前
位
置
有
学
生
的
成
绩
数据结构课程设计报告
开始
第 6 页，共 页
初始化指针数组
建立 300 个队列
Y 队列为空 N 当前位置学生的成绩收集到指 针数组中
指针 p 指向该队列的下一个位置 结束
4’初始化分配数组 InitDivide(struct LSD d[QueueNumber])
数据结构课程设计报告
第 7 页，共 页
/*初始化 d 数组即置空，在每一次收集后必须做的工作 *传递的参数是 struct LSD d[QueueNumber]，无返回值
*/
void InitDivide(struct LSD d[QueueNumber])
{
for(int i=0;i
d[i].cur=NULL;
d[i].next=NULL;
}
}
5’" 分 配 " 和 " 收 集 " 方 法 排 序 double DCSort(struct LSD d[QueueNumber],int
*c[RecordNumber],int n)
/*"分配"和"收集"方法排序 *分配数组为 d，收集数组为 c *进行排序的关键字所代表的学科成绩 n 在分配数组中的位置就是 n *传递的参数是分配数组 struct LSD d[QueueNumber]，用来收集的指针数组 int *c[RecordNumber]，关键 字代表的学科在数组中的下标
*/
double DCSort(struct LSD d[QueueNumber],int *c[RecordNumber],int n)
{ /*按关键字代表的学科成绩将成绩分配到 d 中*/
for(j=0;j
//学生的成绩就是队列号 //当前队列为空
{ d[temp].cur=c[j];
//将 c[j]代表的学生的成绩添加到该队列中
p=&d[temp];
p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL;
p->next=p1; } else {
p=&d[temp];
//初始化刚刚添加了学生记录的队列 //当前队列不为空
/*循环，一直到队列的结尾*/ while(p->cur!=NULL)
p=p->next; p->cur=c[j];
//将 c[j]代表的学生的成绩添加到该队列中
p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL;
//新申请一个空间来存放学生成绩
p->next=p1; } }
//分配完毕
Collect(d,c); InitDivide(d);
//将分配好的成绩序列收集到 c 中 //初始化分配数组
return time;
//返回执行时间
}
6’冒泡法排序 double BubbleSort(int bubble[RecordNumber][QueueNumber])
数据结构课程设计报告
第 8 页，共 页
/*冒泡法排序 *传递的参数是学生成绩记录 int bubble[RecordNumber][KeyNumber]，关键字所代表学科成绩在数组中的 下标
*/
double BubbleSort(int bubble[RecordNumber][KeyNumber],int n)
{
for(int i=0;i
for(int j=0;j
if(bubble[j][n]
for(int m=0;m
temp=bubble[j][m];
bubble[j][m]=bubble[j+1][m];
bubble[j+1][m]=temp;
}
}
}
}
return time; }返回执行的时间
}
//返回排序执行的时间
7’ Print()函数
/*从排序结果存放的文件 recordresults.txt 中读取记录输出到屏幕上 */ void Print() {
FILE *fp;
if((fp=fopen("D:\\recordresults.txt","rb"))==NULL) printf("文件打开失败!\n");
else printf("文件打开成功!\n");
char t;
while(fscanf(fp,"%c",&t)&&!feof(fp)) {
if(t!=EOF)
printf("%c",t);
}
//如果读到结束符，循环结束，输出结束
fclose(fp);
//关闭文件
}
8’ savesources(int score[RecordNumber][KeyNumber],int n)
/*保存学生记录的函数 *参数为要保存的学生记录和记录条数
*无返回值
*/
void savesources(int score[RecordNumber][KeyNumber],int n)
{
FILE *fp;
//指向文件的指针
数据结构课程设计报告
第 9 页，共 页
if((fp=fopen("D:\\recordsources.txt","wb"))==NULL) //只写
{ printf("文件打开失败!\n");
exit(1);
}
fprintf(fp,"%d",n); fprintf(fp,"\r\n");
//将记录条数写入文件 //将换行符号写入文件
for(i=0;i
fprintf(fp,"%-10d%-10d%-10d%-10d%-10d",
score[i][4],score[i][0],score[i][1],score[i][2],score[i][3]);//格式写入记录
fprintf(fp,"\r\n");
//将换行符号写入文件
}
fclose(fp); }
9’ saveresults(int score[RecordNumber][KeyNumber],int n)
/*保存学生记录的函数 *参数为要保存的学生记录和记录条数 *无返回值
*/
void saveresults(int score[RecordNumber][KeyNumber],int n)
{
FILE *fp;
//指向文件的指针
if((fp=fopen("D:\\recordresults.txt","wb"))==NULL) 写数据
{ printf("文件打开失败!\n");
exit(1);
}
//只写,打开或建立一个二进制文件，只允许
fprintf(fp,"%d",n); fprintf(fp,"\r\n");
//将记录条数写入文件 //将换行符号写入文件
for(i=0;i
fprintf(fp,"%-10d%-10d%-10d%-10d%-10d", score[i][4],score[i][0],score[i][1],score[i][2],score[i][3]);//格式写入记录
fprintf(fp,"\r\n");
//将换行符号写入文件
}
fclose(fp); }
10’ load(int score[RecordNumber][KeyNumber])
/*读入函数，把文件中的记录度入到二维数组中 *参数为结构体数组 */ void load(int score[RecordNumber][KeyNumber]) {
FILE *fp;
if((fp=fopen("D:\\recordsources.txt","rt"))==NULL)
//打开文件
数据结构课程设计报告
{ printf("文件打开失败!\n"); exit(1);
}
第 10 页，共 页
fscanf(fp,"%d",&n); for(i=0;i
fclose(fp); }
11’算法分析
//读入记录数 //按格式读入记录
1）LSD 算法：
这是一种“低位优先”的排序方法，借助一趟基数排序的方法，先按最低位的值 对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。以此类推，有低位到 高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有的记录进行排序，直至 最高位，这样就完成了基数排序的全过程。
从算法中可以看出，对于 n 个记录(每个记录含 d 个子关键字，每个子关键字的 取值范围为 RADIX 个值)进行链式排序的时间复杂度为 O(d(n+RADIX)),其中每一趟分配算 法的时间复杂度为 O(n)，每一趟收集的算法的时间复杂度为 O(RADIX)，整个排序进行 d 趟 分配和收集，所需辅助空间为 2*RADIX 个队列指针。由于需要链表作为存储结构，则相对 于其他以顺序结构存储记录的排序方法而言，还增加了 n 个指针域的空间。
2） 冒泡法排序：
该排序是比较简单的交换类排序方法，通过相邻数据元素的交换，逐步将带排序 列变成有序序列的过程。
最坏情况下，待排序的记录按关键字的逆序进行排列，此时，每一趟冒泡排序需 要进行 i 次比较，3i 次移动。经过 n-1 趟冒泡排序后，总的比较次数为 N=∑i=n(n-1)/2,n=1， 2，…，n-1.总的移动次数为 3n(n-1)/2 次，因此该算法的时间复杂度为 O(n*n)，空间复杂 度为 O(1)。另外，冒泡排序法是一种稳定的每部排序法。
四 测试成果
数据结构课程设计报告
第 11 页，共 页
数据结构课程设计报告
第 12 页，共 页
五 附录（源程序清单）
#include
struct LSD 命名为 LSD {
int *cur; struct LSD *next; };
//抽象类型定义，队列的结构类型，由于是按 LSD 法进行的排序，所以 //当前位置
#define LENGTH sizeof(struct LSD)
void CreatScore(int score[10000][5]);
//随机创建学生记录表 score。正常高考中该表是
已知的，不必创建
void savesources(int score[10000][5],int n);
//将模拟创建的高考学生信息记录存放到文件中
void load(int score[10000][5]);
//从学生高考记录源文件中读取记录到该二
维数组中
void Collect(struct LSD d[301],int *c[10000]);
//LSD 法排序中的收集函数，即将分配好的记录
收集到 c 指针数组保存
void InitDivide(struct LSD d[301]);
//用于初始化临时分配数组，在每一次收集
后必须做的工作
double DCSort(struct LSD d[301],int *c[10000],int n);//分配（Divide）和收集（Collect）排序的方法
double BubbleSort(int score[10000][5],int n);
//冒泡法排序
void saveresults(int score[10000][5],int n);
//按照用户的要求（总成绩在前多少名的学生记录），
将这 n 条学生的记录存放到新的文件中
void Print();
//将排序结果文件中的记录数据输出到屏幕
上
int main()
数据结构课程设计报告
第 13 页，共 页
{
double BubTime1, //按第一个关键字代表的学科成绩用冒泡法排序执行的时间
BubTime2,
BubTime3,
BubTime4, BubTimeSum, DCTime1,
//冒泡法排序的总时间 //按第一个关键字代表的学科成绩用分配和收集的方法执行的时间
DCTime2,
DCTime3,
DCTime4, DCTimeSum;
//分配和收集法排序的总时间
int score[10000][5],//随机创建的模拟学生记录源数组
bubble[10000][5], //进行冒泡法排序时用来存放学生记录源数组，并且随排序进行数组中的记 录发生交换
copy[10000][5];
//从模拟的学生记录源 txt 文件中读取学生记录到该数组
struct LSD d[301]; //分配数组，该处考虑到把总分（0-300）也列入优先级序列中，因此建立了
301 个队列 int *c[10000];
//用来存放收集到的学生记录
char x[5];
//存放有优先关系的学科代号序列
/*初始化 c，使其与 score 函数"同步"*/ for(int i=0;i<10000;i++)
c[i]=score[i];
InitDivide(d);
//初始化队列
/*在实际中全部学生的高考记录是存放在一个文件中的，程序运行时是从该文件中读取的源记录数
据。
*本程序要求随机模拟创建该文件，所以下面要创建每个学生的记录（CreatScore()）并保存到一个
文件中（save()）
*调用这两个函数后就生成了全部学生的记录
*/ CreatScore(score);
//伪随机生成各科成绩，并将考号和总成绩一并生成在 score 数
组中
savesources(score,10000); 行的时候是不变的
//将随机生成的记录信息保存在 record.txt 中，该文件在程序运
load(copy);
//从源记录文件 record.txt 中读取学生记录到数组 copy 中
/*为了防止改变源记录，在进行冒泡法排序的时候用 bubble 这个数组*/
for(i=0;i<10000;i++)
for(int j=0;j<5;j++) bubble[i][j]=copy[i][j]; //将源记录赋值给 bubble 数组
printf("请输入您要按照哪种优先级顺序对学生成绩进行排序：比如（总分，数学，语文，英语）\n
就请输入 smce(即各科的英文首字母序列)");
scanf("%s",x);
//输入进行排序的关键字的优先序列
for(i=3;i>=0;i--)
{
printf("\n\n 现在程序正在按%c 代表的学科进行成绩分配，请稍后…",x[i]);
switch(x[i])
{
case 'c':
//Chinese
回时间
DCTime1=DCSort(d,c,0);
//按语文这个关键字用分配和收集法排序，并返
BubTime1=BubbleSort(bubble,0); //按语文这个关键字用冒泡法排序
break;
case 'm':
//Math
DCTime2=DCSort(d,c,1);
BubTime2=BubbleSort(bubble,1);
数据结构课程设计报告
第 14 页，共 页
break;
case 'e':
//English
DCTime3=DCSort(d,c,2);
BubTime3=BubbleSort(bubble,2);
break;
case 's':
//Sum
DCTime4=DCSort(d,c,3);
BubTime4=BubbleSort(bubble,3);
break;
default: printf("您输入的科目代号错误\n"); //输入代号错误提示
break;
}
}
DCTimeSum=DCTime1+DCTime2+DCTime3+DCTime4; //分配排序法的总时间等于按照各个关键字 进行排序的分时间的和
BubTimeSum=BubTime1+BubTime2+BubTime3+BubTime4; printf("\n 用分配和收集的方法排序，执行的总时间为：%.3f\n",DCTimeSum); printf("用冒泡法排序,执行的总时间为：%.3f\n",BubTimeSum); printf("\n 请问您要提取多少条学生的成绩信息（0-10000）：");
int n; scanf("%d",&n); saveresults(bubble,n); 中
Print();
//将前 n 名学生的记录保存在结果文件 recordresults.txt //从结果文件 recordresults.txt 中读取记录到屏幕上
return 0; }
/*创建一个含有 10000 名学生成绩记录的 score,包含语文、数学、英语、总分和学号,随机生成语文、数 学、英语的成绩。
*传递的参数是成绩数组 score，无返回值
*/
void CreatScore(int score[10000][5])
{
int i,
j;
srand(time(NULL)); 数
//利用时间设置随机种子产生随机
/*伪随机生成语文、数学、英语的成绩*/ for(i=0;i<10000;i++) {
for(j=0;j<3;j++) {
score[i][j]=rand()%101; } }
//成绩的范围是 0-100
/*总分成绩初始化*/ for(i=0;i<10000;i++) {
score[i][3]=score[i][0]+score[i][1]+score[i][2]; }
//总成绩为各科成绩之和
/*学号的初始化*/ for(i=0;i<10000;i++)
score[i][4]=i+1;
//学号是按从前到后的顺序依次赋值的
数据结构课程设计报告
}
第 15 页，共 页
/*保存学生记录的函数 *参数为要保存的学生记录和记录条数
*无返回值
*/
void savesources(int score[10000][5],int n)
{
printf("\n 程序正在模拟创建 10000 条高考成绩记录并保存到文件 D:\\recordresources.txt 中，\n 请稍 后…\n"); //输出提示信息
int i;
FILE *fp;
//指向文件的指针
if((fp=fopen("D:\\recordsources.txt","wb"))==NULL) 写数据
{ printf("文件打开失败!\n");
exit(1);
}
//只写,打开或建立一个二进制文件，只允许
fprintf(fp,"%d",n); fprintf(fp,"\r\n");
//将记录条数写入文件 //将换行符号写入文件
for(i=0;i
fprintf(fp,"\r\n");
//将换行符号写入文件
}
fclose(fp); printf("文件创建并保存成功!\n 您可以通过路径 D:\\recordsources.txt 进行查看。\n\n\n");
}
/*读入函数，把文件中的记录度入到二维数组中 *参数为结构体数组 */ void load(int score[10000][5]) {
int i, n;
FILE *fp;
if((fp=fopen("D:\\recordsources.txt","rt"))==NULL) {
printf("文件打开失败!\n"); exit(1); }
//打开文件
fscanf(fp,"%d",&n); for(i=0;i
fclose(fp);
//读入记录数 //按格式读入记录
数据结构课程设计报告
第 16 页，共 页
printf("******************************** 排 序 系 统 开 始 运 行
********************************\n"); printf("首先是从模拟高考成绩源文件 recordsources.txt 中读取数据!\n 正在读取数据，请稍后…\n"); printf("成功从源文件中读取 %d 条记录到排序系统中\n\n", n);
}
/*将分配好的成绩数组 d，收集到 c 指针数组保存 * 传递的参数为分配好的数组 d 和收集的指针数组 c，无返回值 */ void Collect(struct LSD d[301],int *c[10000]) {
int i, j=0;
struct LSD *p;
for(i=300; i>=0; i--) 队列为 0-300
{ if(d[i].cur!=NULL) { p=&d[i]; while(p->cur!=NULL) { c[j]=p->cur; j++; p=p->next; } }
} }
//因为包含总成绩（0-300）的优先级，所以共分配的
//当前队列不空，即有学生的成绩分配到该队列
//当前位置有学生的成绩 //收集到 c 指针数组中
//指针 p 指向该队列的下一个位置
/*初始化 d 数组即置空，在每一次收集后必须做的工作 *传递的参数是 struct LSD d[301] */ void InitDivide(struct LSD d[301]) {
for(int i=0;i<301;i++) {
d[i].cur=NULL; d[i].next=NULL; } }
/*"分配"和"收集"方法排序 *分配数组为 d，收集数组为 c *进行排序的关键字所代表的学科成绩 n 在分配数组中的位置就是 n *传递的参数是分配数组 struct LSD d[301]，用来收集的指针数组 int *c[10000]，关键字代表的学科在数 组中的下标
*/
double DCSort(struct LSD d[301],int *c[10000],int n)
{
double time; clock_t t_start; clock_t t_end;
//时间记录的开始 //时间记录的结束
t_start=clock();
//获取排序开始的时间
int j, temp;
数据结构课程设计报告
struct LSD *p,*p1;
第 17 页，共 页
/*按关键字代表的学科成绩将成绩分配到 d 中*/ for(j=0;j<10000;j++) {
temp=c[j][n]; if(d[temp].cur==NULL) {
d[temp].cur=c[j]; p=&d[temp];
//学生的成绩就是队列号 //当前队列为空
//将 c[j]代表的学生的成绩添加到该队列中
p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL;
p->next=p1; } else {
p=&d[temp];
//初始化刚刚添加了学生记录的队列 //当前队列不为空
/*循环，一直到队列的结尾*/ while(p->cur!=NULL)
p=p->next; p->cur=c[j];
//将 c[j]代表的学生的成绩添加到该队列中
p1=(struct LSD *)malloc(LENGTH); p1->cur=NULL; p1->next=NULL;
//新申请一个空间来存放学生成绩
p->next=p1; } }
//分配完毕
printf("\n 分配完毕，下面开始进行收集，请稍后…\n");
Collect(d,c);
//将分配好的成绩序列收集到 c 中
printf("收集完毕。\n");
InitDivide(d);
//初始化分配数组
t_end = clock();
time=(double)(t_end-t_start)/CLOCKS_PER_SEC; printf("本次分配和收集用时: %.3f s\n",time);
//获取结束测试点的时间
return time; }
//返回执行时间
/*冒泡法排序 *传递的参数是学生成绩记录 int bubble[10000][5]，关键字所代表学科成绩在数组中的下标 */ double BubbleSort(int bubble[10000][5],int n) {
printf("\n 下面开始用冒泡法进行排序，请稍后…\n"); double time; clock_t t_start; clock_t t_end; t_start=clock();
int temp; for(int i=0;i<10000;i++) {
数据结构课程设计报告
for(int j=0;j<9999-i;j++) {
if(bubble[j][n]
temp=bubble[j][m]; bubble[j][m]=bubble[j+1][m]; bubble[j+1][m]=temp; } } } }
第 18 页，共 页
t_end = clock();
time=(double)(t_end-t_start)/CLOCKS_PER_SEC; printf("本次冒泡法排序用时: %.3f s\n\n",time);
return time; }
//返回排序执行的时间
/*保存学生记录的函数 *参数为要保存的学生记录和记录条数 *无返回值
*/
void saveresults(int score[10000][5],int n)
{
int i;
FILE *fp;
//指向文件的指针
if((fp=fopen("D:\\recordresults.txt","wb"))==NULL) 写数据
{ printf("文件打开失败!\n");
exit(1);
}
//只写,打开或建立一个二进制文件，只允许
fprintf(fp,"%d",n); fprintf(fp,"\r\n");
//将记录条数写入文件 //将换行符号写入文件
for(i=0;i
式写入记录
fprintf(fp,"\r\n");
//将换行符号写入文件
}
fclose(fp); }
/*从排序结果存放的文件 recordresults.txt 中读取记录输出到屏幕上 */ void Print() {
FILE *fp;
if((fp=fopen("D:\\recordresults.txt","rb"))==NULL) printf("文件打开失败!\n");
数据结构课程设计报告
else printf("文件打开成功!\n");
第 19 页，共 页
char t;
while(fscanf(fp,"%c",&t)&&!feof(fp)) {
if(t!=EOF)
printf("%c",t);
}
//如果读到结束符，循环结束，输出结束
fclose(fp);
//关闭文件
}
六 用户手册
本程序的运行环境为 DOS 系统，执行文件为“LSDSort.exe”
进入程序后的界面如下：
用户此时可以按路径 D:\\recordresources.txt 文档中查看模拟高考成绩表 自动计算出分配收集法和冒泡法分别所需要的时间，综合比较两种方法
多关键字排序_数据结构-设计
数据结构课程设计报告 题目：多关键字排序 多关键字排序 【问题描述】 多关键字的排序有一定的实用范围。例如：在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录 取的次序。 【基本要求】 （1）假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100.。 按用户给定的进行排序的关键字的优先关系，输出排序结果。 （2）约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。 【测试数据】 由随机数产生器生成。 C语言源程序 #include
score sr[N]; void Merge( score R[],int low,int m,int high,int keynum) {//将两个有序的R[low..m)和R[m+1..high]归并成一个有序的R[low..high] int i,j,k; i=low,j=m+1,k=0; score *R1; R1=(score*)malloc((high-low+1)*sizeof(score)); //临时申请空间 if(!R1) return; //申请空间失败 while(i<=m&&j<=high) //两子文件非空时取较大者复制到R1[k]上 {if (R[i].key[keynum]>=R[j].key[keynum]) R1[k++]=R[i++]; else R1[k++]=R[j++]; } while(i<=m) //若第1个数组非空，则复制剩余记录到R1中 R1[k++]=R[i++]; while(j<=high) //若第2个数组非空，则复制剩余记录到R1中 R1[k++]=R[j++]; for(k=0,i=low;i<=high;k++,i++) R[i]=R1[k]; //归并完成后将结果复制回R[low..high] } void MergeSort(score R[],int low,int high,int keynumber) {//对R[low..high]进行二路归并排序 int mid; if(low 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月 三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。 目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6) 一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 一、数据结构课程设计要求 1.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 3.课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上2小时的上机来调试C 或C++语言设计的程序，总共至少要上机调试程序20小时。属教师安排上机时间学生不得缺席。 二、数据结构课程设计题目 1. 运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分， 3) 可以按学校编号或名称、学校总分、男女团体总分排序输出； 4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 飞机订票系统（限1 人完成） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 淮 海 工 学 院 计算机工程学院 数据结构课程设计报告 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 《数据结构与算法》课程设计报告 学号： 班级序号： 姓名： 指导教师： 成绩： 中国地质大学信息工程学院地理信息系统系 2011年12 月 1．需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能： （1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。 （3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。 （4）程序使用命令行方式运行 压缩命令：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时，给出提示。 （5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。 2．总体分析与设计 （1）设计思想： 1、压缩准备：1> 读文件，逐个读取字符，统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程： 1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 福建工程学院课程设计 课程：数据结构课程设计 题目： 1.综合应用 2.折半查找 3.快速排序 专业：软件工程 班级：1101 座号：3110305129 姓名：潘聪 2012 年 6 月26 日 设计题目1：综合应用 一、问题描述 有N名学生，每名学生含有如下信息：学号、姓名、某四门课的成绩，并计算其总分，用一结构数组表示之。然后实现以下功能： （1）将这些数据存放至文件stuf.dat中； （2）将文件中的数据读出至结构数组中，并显示之； （3）输出总分最高分和最低分的名字； （4）输出总分在340分，单科成绩不低于80分的名单； （5）求出各科平均分数； （6）按总分排名； （7）输出补考名单。 二、解决问题的算法思想描述 （1）子函数：首先确定需要的子函数，总共7个，对应的功能分别是题目要求的七项（2）主函数：主函数中，要设计出易于使用的人机界面，就必须要用到switch 。 （3）文件的存放读取，必须要用到文件的函数，fopen，fread，fclose等。 （4）把每个学生的信息定义在一个结构数组中，利用结构数组更加方便。 （5）各科成绩排名用冒泡排序即可。 （6）输出总分，补考名单，各科的平均分都比较简单。 三、设计 1. 数据结构的设计和说明 //定义结构体 typedef struct { int num; //学号 char name[10]; //姓名 int score1; //语文 int score2; //数学 int score3; //物理 int score4; //化学 }student; student stu[MAX]; //结构数组 2．模块结构图及各模块的功能： 目录 一．设计题目 (2) 二．需求分析 (2) 1.程序设计问题描述 (2) 2.基本要求 (2) 3.流程图 (2) 三．详细设计 (3) 1.数据结构定义 (4) 2.主要算法设计 (5) 3.函数调用关系图 (8) 4.程序主要流程 (8) 四．调试分析 (13) 五．用户手册 (15) 六．测试结果 (19) 七．源代码（带注释） (21) 八．参考文献 (26) 一．设计题目 多关键字排序 二．需求分析 1.程序设计问题描述 多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。 2.基本要求 (1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。 (2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用"分配"和"收集"的方法。并综合比较这两种策略。 （3）测试数据由随机数生成器产生。 3.流程图 三．详细设计 本程序是对语文，数学，英语，体育，综合这5门成绩按照此顺序进行优先排序。各科分数为0～100。 由于本实验约定按LSD进行多关键字的排序。在对个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。所以在一个程序里实现了这两种排序方法。 第一种排序方法由于要使用稳定的排序方法，故参考书上的几种排序方法后，选用了冒泡排序和静态链表存储方式，每一趟排序后，找出最高分。第二种排序方法利用“分配”与“收集”的基数排序算法，用静态链表存储分数，在一趟排序中，将结点分配到相应的链 一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列｛r[0],r[1],…，r[n-i]｝中，从头至尾依次比较相邻的两个记录r[j] 与r[j+1]（0<=j<=n-i-1）,若r[j].key>r[j+1].key，则交换位置； 3)i=i+1； 4)重复步骤2）和3），直到步骤2）中未发生记录交换或i=n-1为止； 要实现上述步骤，需要引入一个布尔变量flag，用来标记相邻记录是否发生交换。 快速排序的基本思想是：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。 快速排序步骤： 1)设置两个变量i、j，初值分别为low和high，分别表示待排序序列的起始下 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 <<数据结构>> 课 程 设 计 班级:111004 姓名:董丽美 学号:111004122 指导教师:史延新 完成日期:2013 _07 _10 题目一:约瑟夫环问题 【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1,2，…,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 【测试数据】m的初值为20；n=7,7个人的密码依次为：3,1,7,2，4,8,4，首先m值为6（正确的出列顺序应为：6,1,4,7,2,3,5） 一 .需求分析 1．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。 2．环中总人数和节点信息由用户输入，且均为正整数。3．在窗口界面输出出列顺序的编号。 二．概要设计 1.设定链表的抽象数据类型定义： ADT List{ 数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0} 数据关系：R1={ 第7章查找 【例7-1】有序表按关键字排列如下：7，14，18，21，23，29，31，35，38，42，46，49，52，在表中查找关键字为14和22的数据元素，并画出折半查找过程的判定树。 解：折半查找的过程描述如下： ①low=1；high=length；//设置初始区间 ②当low>high时，返回查找失败信息//表空，查找失败 ③low≤high，mid=(low+high)/2; //取中点 a. 若kx 《数据结构》课程设计报告 专业 班级 姓名 学号 指导教师 起止时间 课程设计：排序综合 一、任务描述 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 要求：根据以上任务说明，设计程序完成功能。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： （1）随机生成N个整数，存放到线性表中； （2）起泡排序并计算所需时间； （3）简单选择排序并计算时间； （4）希尔排序并计算时间； （5）直接插入排序并计算所需时间； （6）时间效率比较。 2、数据对象分析 存储数据的线性表应为顺序存储。 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; //设排序码为整型量 typedef int InfoType; typedef struct { //定义被排序记录结构类型 KeyType key ; //排序码 I nfoType otherinfo; //其它数据项 } RedType ; typedef struct { RedType * r; //存储带排序记录的顺序表 //r[0]作哨兵或缓冲区 int length ; //顺序表的长度 } SqList ; //定义顺序表类型 四、功能设计 （一）主控菜单设计 编号 课程设计 题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题 二级学院计算机科学与工程学院 专业计算机科学与技术 班级 2011级 37-3班 学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师 时间 1、一元稀疏多项式计算器 【实验内容】 一元稀疏多项式计算器。 【问题描述】 设计一个一元稀疏多项式简单计算器。 【需求分析】 其基本功能包括： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相减，建立多项a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做）； 【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb)； void sort(dnode *h) dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】 （1）输入多项式： （2）输出多项式（多项式格式为：c1x^e1+c2x^e2+…+cnx^en）： （3）实现多项式a和b相加： （4）实现多项式a和b相减： （5）计算多项式在x处的值： 2、模拟浏览器操作程序 【实验内容】 模拟浏览器操作程序 【问题描述】 标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈，追踪可以后退和前进而能够到达的网页。在本题中，要求模拟实现这一功能。 【需求分析】 需要支持以下指令： BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面，使它成为当前页。若“后退栈”是空的，忽略该命令。 FORWARD：将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面，使它成为当前页。如果“前进栈”是空的，忽略该命令。 VISIT 精品文档 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档 郑州工业应用技术学院 课程设计说明书 题目：手机信息数据检索 姓名：王港 院（系）：信息工程学院 专业班级：16级计算机科学与技术6班 学号：1601110241 指导教师：王礼云 成绩： 时间：2018 年 1 月 2 日至2018 年 1 月12 郑州工业应用技术学院 课程设计任务书 题目手机信息数据检索 专业、班级16级计算机科学与技术6班学号1601110241姓名王港 主要内容： 开发一个手机信息数据检索，使管理员可以很好的管理回收的手机，避免平时废旧手机没有作用，不知道如何去处理旧的手机等问题。减轻废旧手机资源的浪费。本废旧手机回收系统利用单链表实现了基本信息的添加。管理员能够对各种信息进行修改，例如手机信息添加，手机信息删除，密码修改，退出系统。 基本要求： 1、巩固并加深学生对数据结构基本算法的理解； 2、认识面向过程和面向对象两种设计方法的区别； 3、进一步掌握和应用VC++6.0 集成开发环境； 4、提高运用对于数据结构的理解，增强了我解决实际问题的能力； 5、初步掌握开发小型实用软件的基本方法。 主要参考资料： [1]谭浩强. C语言基础课程[M].北京:清华大学出版社,2009. [2]刘振安. C程序设计课程设计[M].北京:机械工业出版社,2016. [3]滕国文. 数据结构课程设计[M].北京:清华大学出版社, 2010. [4]吴伟民. 数据结构[M].北京:清华大学出版社, 2017. 完成期限：2018.1.2-2018.1.12 指导教师签名： 课程负责人签名： 2018 年1 月12 日 摘要 21世纪以来，经济高速发展，人们生活发生了日新月异的变化，特别是手机普及到每个人生活的各个领域。但对于手机的回收越来越不适应现在社会的发展。计算机技术的飞速发展，也为我们带来了巨大的便利。为了适应现代人们回收旧手机方便的愿望。手机信息管理系统软件能够为我们现如今手机回收带来巨大的便利。 我国现如今已经成为手机产品的生产消费大国，伴随着通信技术的迅猛发展，手机更新换代的速度不断提高。特别是追求时尚潮流的大学生群体手机的更换频率增加更快。随着智能手机产品不断推陈出新，手机更新换代的周期也在缩短。据业内人士估计，我国存量闲置手机至少以亿计，但旧手机的回收率却不到2%，旧手机的处置成为一大问题。 中国目前废旧手机的回收现状和回收模式，造成我国手机回收效率低下，更是对垃圾回收产业带来了巨大的冲击，同时目前，我国年废旧手机产生量约上亿部，大部分闲置家中，未能有效回收利用。既浪费了资源，又威胁居民身心健康，造成环境污染。在分析我国废旧手机回收利用现状的基础上，提出了完善废旧手机回收的法律制度、增强消费者环保意识、构建绿色环保废旧手机回收利用新模式等建议。本手机信息数据检索为回收手机的人管理废旧的手机使用，使用单链表实现，对于信息的增加删除效率比较高，可以很方便的进行各种信息管理，对于数据的管理可以让我们更好的面对管理手机的繁杂工作。 关键字：信息检索；冒泡算法；单链表 排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i]数据结构课程设计
数据结构课程设计报告模板
数据结构课程设计题目2010
数据结构课程设计 多关键字排序 高考排序
课程设计报告
设计名称： 选题名称： 姓 名： 专业班级： 系 （院）： 设计时间： 设计地点：
数据结构课程设计 多关键字排序
周宣 学 号： 110821120 网络工程 081
计算机工程学院 2009.12.28~2010.1.12 软件工程实验室、教室
指导教师评语：
成绩：
签名：
年月日
第 1 页，共 页
1．课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序 求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水 平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
2．课程设计任务与要求：
任务
题目：多关键字的排序
【问题描述】 多关键字的排序有其一定的实用范围。例如：在进行高考分数处理时，除了需对总分进行排序外， 不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求 排出考生录取的次序。 【基本要求】 （1）假设待排序的记录不超过 10000，表中记录的关键字数不超过 5，各个学科关键字的范围均为 0 至 100，总分关键字的范围是 0-300。按用户给定的进行排序的关键字的优先关系，输出排序结果。 （2）约定按 LSD 法进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用 稳定的内部排序法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。 【测试数据】 由随机数产生器生成。 【实现提示】 由于是按 LSD 方法进行排序，则对每个关键字均可进行整个序列的排序，但在利用通常的内部排序 方法进行排序时，必须选用稳定的排序方法 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计 实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准 备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加 大代码的重用率。 2、.设计的题目要求达到一定工作量（300 行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用 C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于 10 页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。数据结构课程设计(内部排序算法比较_C语言)
数据结构课程设计报告
数据结构实验总结报告
数据结构课程设计
数据结构-多关键字排序课设报告
数据结构课程设计-排序
数据结构课程设计报告模板
数据结构课程设计
查找排序习题讲解
数据结构课程设计排序实验报告
数据结构课程设计报告
最新数据结构实训总结
数据结构课程设计
数据结构课程设计排序算法总结