数据结构课程设计报告

题目柒排序。

学生姓名专业班级软件

指导教师职称讲师

所在单位工学部。

教学部主任。

完成日期 2024年01月08日。

数据结构课程设计》报告。

data structure experiment designing

课程编号：030160学时： 40学时。

适用专业：软件工程专业授课单位：信息学院。

一、数据结构课程设计目的及要求。

目的：数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。

学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。

要求：1. 分析问题，给出数学模型，设计相应的数据结构。

2. 算法设计。

1．用测试数据去验证算法及程序的正确性。

2．算法分析。

3．提高上机编程能力。

二、实验类型。

综合类型。三、实验学时。

40学时。四、实验设备。

微型计算机、windows98以上版本的操作系统、turbo c2.0 软件一套。

五、 c语言课程参考教材：

1.严蔚敏吴伟民著，《数据结构(c语言版)》，清华大学出版 2024年第一版。

2.陈一华等编，《数据结构---使用c 语言》，电子科技大学出版社 2024年第一版。

课程设计(报告)任务书。

任务及要求：

1. 设计（研究）内容和要求。

研究内容：排序的算法分析与设计。

任务和要求：

1）．学习数据结构基础知识，掌握数据结构典型的算法的使用。

2）．对指导教师下达的题目进行系统分析。

3）．根据分析结果完成系统设计。

4）．编程：在计算机上实现题目的**实现。

5）．完成对该系统的测试和调试。

6）．提交课程设计报告。

7）．指标：

要求完成课程设计报告以上(约二十页)。

完成若干综合性程序设计题目，综合设计题目的语句行数的和在100行语句以上。

2.原始依据。

结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序**中的错误并且修改。

3.参考文献。

1] 严蔚敏吴伟民著。《据结构(c语言版)，清华大学出版， 2024年第一版。

2] 陈一华等编。数据结构---使用c 语言，电子科技大学出版社， 2024年第一版。

3] 谭浩强。c语言程序设计（第二版）.北京：高等教育出版社，2002

指导教师签字：

2024年 12月21日。

目录。题目一： 1

1.需求分析 1

2.概要设计 1

3.详细设计 1

4.调试分析 1

5.测试结果及运行效果 1

参考文献 2

附录全部** 3

排序的算法分析与设计。

以无歧义的陈述说明程序设计的任务，强调的是程序要做什么并明确规定：

1) 输入的形式和输入值的范围；

输入的形式：（随机输入）逻辑结构：数组。

物理结构：顺序存储。

输入值的范围：-32768～32767

2) 输出的形式：输出连续的有序数组。

3) 程序所能达到的功能：

排序，又称分类，是计算机程序设计中一种重要运算，。根据排序过程中所涉及的存储器可分为内部排序和外部排序。它的功能是将一组任意序列的数据元素进行按由小到大的顺序（升序）排列。

这些数据可以是数值型，也可以是为字符型，若为数值型，则按数值大小排列，若为字符型，则按其ascii码的顺序排列。

(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确的输入：49 38 65 97 76 13 27 49 55 04

输出结果：04 13 27 38 49 49 55 65 76 97

含有错误的输入：-32779 49 38 65 97 76 13 27 49 55

输出结果：13 27 38 49 49 55 65 76 97 32757

说明本程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次(调用)关系。

数据类型：一维数组。

进入主菜单—>选择排序类型(包括插入类型、交换类型、选择类型和归并类型)—>

选择具体排序方法—>输出结果。

实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图 n -s 图进行描述，画出函数和过程的调用关系图。

内容包括：a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；

解决方法：查阅资料、书籍和老师的指导，反复阅读示例文档。

实现：反复修改、调试。

b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；

直接插入排序。

1．时间复杂度：最好情况：正序 o（n）；最坏情况：逆序 o（n2）

2．空间复杂度o（1）

3．稳定性：稳定。

4．基本思想：

直接插入排序是一种比较简单的排序方法。它的基本思想是一次将记录序列中的每一个记录插入到有序段中，是有许多的长度不断地扩大。首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，……以此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第i个记录，则应该将这个记录插入到由前i-1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，知道所有记录都插入到有序段中。

一共需要讲过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。

5．基本操作：

void insertsort (rectype r对数组r中的记录进行直接插入排序*/

int i,j;

for(i=2;i<=n;i待插入记录为r[2]，…r[n]*/

{ r[0]=r[i将待插入的记录r[i]放入r[0]中*/

j=i-1;

while(r[0].keyr[j+1]=r[j将排序码大于r[i].key的记录后移*/

r[j+1]=r[0插入r[i]*/

希尔排序。1．时间复杂度： o（n1.5）

2．空间复杂度： o（1）

3．稳定性：不稳定。

4．基本思想：

希尔排序方法又称为缩小增量排序，其基本思想是将待排序的记录划分成几组，从而将少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。假设待排序的记录为n个，先取整数d5．基本操作：

void shellinsert(rectype r,int d) /按步长d进行分组，每一组分别。

做直接插入排序*/

int i,j;

for (i=d+1;i<=n;i++)

r[0]=r[i];j=i-d将r[i]暂存在r[0]*/

while(j>0&&r[j].key>r[0].key)

r[j+d]=r[j];

j=j-d记录后移，查找插入位置*/

r[j+d]=r[0插入记录*/

整个希尔排序算法的c函数：

void shellsort(rectype r，int d,int t) /d[0]~d[t-1]为每一趟分组的步长*/

int k;

for(k=0;k shellinsert(r,d[k]);

起泡排序。1. 时间复杂度： o（n2）

2. 空间复杂度： o（1）

3. 稳定性：稳定。

4. 基本思想：l

起泡排序是交换排序中一种简单的排序方法。它是对所有相邻记录的关键字值进行比较，如果是逆序，则将其交换，最终达到有序化。器处理过程为：

（1）将整个待排序的记录序列划分成有序区和无序区，初始状态为空，无序区包括所有待排序的记录。（2）对无序区从前次向后依次将相邻记录的关键字进行比较，若逆序将其交换，从而使得关键字值小的记录向上“漂浮”（左移）关键字值大的记录好像石块，向下“堕落”（右移）。每经过一趟起泡排序，都是无序区中关键字值最大的记录进入与序曲，对于由n个记录组成的记录序列，最多经过n-1趟起泡排序，就可以将这n个记录重新按关键字顺序排列。

5. 基本操作：

void bubblesort(rectype r采用起泡排序对r数组的记录进行排序*/

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了