杭电-数据结构课程设计报告模板(内附C代码)

数据结构课程设计报告数据结构课程设计报告 学院专业 学院专业 软件工程软件工程 班班 级 级 学学 号 号 学生姓名 学生姓名 指导老师 指导老师 彭伟民彭伟民 日日 期 期 2016 01 012016 01 01 目录目录 1猴子吃桃子问题猴子吃桃子问题 3 1 1需求分析 3 1 2程序设计思想 3 1 3程序源代码 3 1 4程序运行结果 5 2进制数转化问题进制数转化问题 5 2 1需求分析 5 2 2程序设计思想 6 2 3程序源代码 6 2 4程序运行结果 7 3长整数运算长整数运算 8 3 1需求分析 8 3 2程序设计思想 8 3 3程序源代码 8 3 4程序运行结果 12 4学生成绩管理系统学生成绩管理系统 13 4 1需求分析 13 4 2程序设计思想 13 4 3程序源代码 14 4 4程序运行结果 20 5哈夫曼编码应用哈夫曼编码应用 22 5 1需求分析 22 5 2程序设计思想 22 5 3程序源代码 23 5 4程序运行结果 24 6学校超市选址问题学校超市选址问题 26 6 1需求分析 26 6 2程序设计思想 26 6 3程序源代码 26 6 4程序运行结果 30 7学生成绩管理系统学生成绩管理系统 30 7 1需求分析 30 7 2程序设计思想 30 7 3程序源代码 30 7 4程序运行结果 36 8排序综合排序综合 37 8 1需求分析 37 8 2程序设计思想 38 8 3程序源代码 38 8 4程序运行结果 46 9课程设计总结课程设计总结 47 1猴子吃桃子问题猴子吃桃子问题 1 1 需求分析 有一群猴子摘了一堆桃子 他们每天都吃当前桃子的一半且再多吃一个 到 了第 10 天就只余下一个桃子 用多种方法实现求出原来这群猴子共摘了多 少个桃子 1 2 程序设计思想 已知第十天只余下 1 个桃子 第一天开始每天都吃当前桃子一半再多 一个 那么就只需要从第十天开始倒推即可 用链表 数组 递推 常规方法都可以采用这种思路实现计算第一天桃子数量 1 3 程序源代码 include using namespace std 有一群猴子摘了一堆桃子 他们每天都吃当前桃子的一半且再 多吃一个 到了第 10 天就只余下一个桃子 用多种方法实现求出原 来这群猴子共摘了多少个桃子 链表方法实现 typedef struct int base int top Stack void InitStack Stack if s base s top s base else printf 空间分配错误 n exit 0 入栈 void PushStack Stack 出栈 int PopStack Stack int main int peach 0 void shuZu int digui int i int j int changgui shuZu peach digui 1 1 cout 递归方法实现结果 peach 1 data PopStack s 出栈一个元素保存在 data 中 PushStack s 2 data 1 再将 2 data 1 入栈 最后栈中剩余的那个元素就是第 1 天摘的桃子数 cout 链表方法实现结果 PopStack s endl cout 常规方法实现结果 changgui 0 i peach i peach i 1 1 2 cout 数组方法实现结果 peach 0 endl int digui int i int j 递归方法实现 static int peach i static int day j if day 10 return peach else peach digui peach day 1 2 return peach int changgui int peach 1 for int i 1 i 10 i peach peach 1 2 return peach 1 4 程序运行结果 2进制数转化问题进制数转化问题 2 1 需求分析 任意给定一个 M 进制的数 x 请实现如下要求 1 求出此数 x 的 10 进制值 用 MD 表示 2 实现对 x 向任意的一个非 M 进制的数的转换 3 至少用两种或两种以上的方法实现上述要求 用栈解决 用数组解 决 其它方法解决 2 2 程序设计思想 假如 N 为输入的数 n 为要转换为的进制 若要将十进制 231 转 换为 8 进制数 过程如下 N N n N n 231 28 7 28 3 4 3 0 3 则输出为 347 可以看出 首先得到的应该是 7 然后才是 4 最 后是 3 但是要逆序显示 自然就类似压栈出栈的数据结构了 所以 只需要初始化栈后 将 N n 不断的压入栈底 需要注意的是如 果要转换为 16 进制 则需要对大于 9 的数字作字符处理 2 3 程序源代码 include include include include void TransIntoDec double M int X void TransIntoAny int X char p NULL int len 0 int i int sum 0 int by 1 printf 十进制数为 p char malloc 32 itoa X p 10 len strlen p for i 0 i len i by pow M len i 1 by p i 0 sum by by 1 printf d n sum TransIntoAny sum void TransIntoAny int X int r int temp 32 int i 0 printf 请输入转化进制 n scanf d while X temp i X r X r printf 经转化为 while i printf d temp i printf n void main int m int x int i int length char p NULL printf 请输入数字及确定其进制 n scanf d d p char malloc 32 itoa x p 10 length strlen p for i 0 i m break if i length TransIntoDec m x else printf Input error n return 2 4 程序运行结果 3长整数运算长整数运算 3 1 需求分析 设计一个程序实现两个任意长的整数求和运算 提示 可利用双项循环链表实现长整数的存储 每个结点含一个整型 变量 3 2 程序设计思想 定义双链表的节点结构 每个节点存储一个 4 位的数 比如 1 0031 0056 存入链表后就是 1 31 56 三个节 输出的时候再补 0 输出 由此完成长整数加法或减法运算 3 3 程序源代码 include include include 以下是双链表的节点结构 每个节点存储一个 4 位的数 比如 1 0031 0056 存入链表后就是 1 31 56 三个节 输出的时候再补 0 输出 typedef struct node int n struct node next struct node prev node node p char num1 1024 num2 1024 int conv char a int n 0 i for i 0 a i i n 10 n a i 0 return n int main char c 2 int i f node q p node malloc sizeof node p next p prev 0 q p num1 0 num2 0 printf 请输入第一个数字 n scanf s num1 1 for i strlen num1 i 0 i if num1 i num1 i 0 q next node malloc sizeof node q next prev q q next next 0 q q next q n conv num1 i 1 q next p p prev q printf 请输入运算符号 n scanf s c c c 0 1 printf 请输入第二个数字 n scanf s num2 1 q p f 0 if c for i strlen num2 i 0 i if num2 i num2 i 0 if q next p q next node malloc sizeof node q next next p q next prev q q next n 0 p prev q next q q next q n conv num2 i 1 f if q nn 10000 if f if q next p q next node malloc sizeof node q next next p q next prev q q next n 1 else while q next p q q next q n 1 if q nn 0 f 1 if f q next node malloc sizeof node q next next p q next prev q q next n 1 printf d p prev n for q p prev prev q p q q prev printf 04d q n else for i strlen num2 i 0 i if num2 i num2 i 0 if q next p q next node malloc sizeof node q next next p q next prev q q next n 0 p prev q next q q next q n conv num2 i 1 f if q n 0 f 0 else f 1 q n 10000 if f if q next p q n 10000 else while q next p q q next q n 1 if q n 0 f 0 break else q n 10000 f 1 if f q n 10000 printf d p prev n for q p prev prev q p q q prev printf 04d q n return 0 3 4 程序运行结果 4学生成绩管理系统学生成绩管理系统 4 1 需求分析 现有学生成绩信息文件 1 1 txt 内容如下 数据可以自拟 姓名 学号 语文 数学 英语 张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 学生成绩信息文件 2 2 txt 内容如下 姓名 学号 语文 数学 英语 陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77 试编写一管理系统 要求如下 1 实现对两个文件数据进行合并 生成新文件 3 txt 2 抽取出三科成绩中有补考的学生并保存在一个新文件 4 txt 3 对合并后的文件 3 txt 中的数据按总分降序排序 至少采用两种 排序方法实现 4 输入一个学生姓名后 能查找到此学生的信息并输出结果 至少 采用两种查找方法实现 5 要求使用结构体 链或数组等实现上述要求 4 2 程序设计思想 建立学生信息保存在文本文档中 具体对学生信息进行插入删除查询 操作时 将保存在文本文档中的学生信息提取出来保存在自己定义的 数据结构中 然后再对该数据结构进行操作 所有操作完成后或者在 相应的命令后再将学生信息保存到文本文档中 数据类型主要是 char int float 等数据类型 内容包括学号 姓名等数据 4 3 程序源代码 include include include using namespace std char top 50 成绩文件顶部的标题用 top 保存 typedef struct student 单个学生成绩的记录 char name 10 姓名 int number 学号 int chinese 语文 int math 数学 int english 英语 struct student next student gradelist gradelist fileread char adress 读取成绩文件 FILE fp if fp fopen adress r NULL 打开文件 printf 文件打开出错 exit 0 gradelist file student malloc sizeof student 申请空间 file next NULL student p file 操作指针 int n 0 循环标记 具体作用是在第一次循环时方便处理标 题 while feof fp if n 0 fgets top 50 fp 处理标题 并且文件指针移到第 二行 if n 1 申请空间 p next student malloc sizeof student p p next p next NULL fscanf fp s d d d d p name 将文件的数据输入到链表中 n 1 if fclose fp 关闭文件 printf 文件关闭失败 exit 0 return file void FilePrint gradelist file 将成绩文件打印到屏幕上 student p file printf s n top 打印标题 while p next NULL printf 6s 2d d d d n p name p number p chinese p math p english 循环打印 p p next void merger 合并文件 char address1 F 1 txt address2 F 2 txt address3 F 3 txt gradelist file1 fileread address1 file2 fileread address2 FILE fp if fp fopen F 3 txt w NULL 先新建一个 3 txt 然后将 1 txt 和 2 txt 的内容输入到里面 printf 合并成绩文档失败 原因 建立文档出错 exit 0 student p1 file1 p2 file2 fprintf fp s top 先输入标题 while p1 next NULL fprintf fp 6s 2d d d d n p1 name p1 number p1 chinese p1 math p1 english 输入 1 txt p1 p1 next while p2 next NULL fprintf fp 6s 2d d d d n p2 name p2 number p2 chinese p2 math p2 english 输入 2 txt p2 p2 next if fclose fp printf 文件关闭失败 exit 0 void extract 抽取补考的成绩记录 char address4 F 4 txt address3 F 3 txt FILE fp if fp fopen F 4 txt w NULL 新建文件 4 txt printf 抽取补考学生成绩记录建立新文件失败 exit 0 gradelist file3 fileread address3 student p file3 fprintf fp s top 先输入标题 while p next NULL if p chinese math english name p number p chinese p math p english p p next if fclose fp printf 文件关闭失败 exit 0 void sort int i char address3 F 3 txt gradelist file3 fileread address3 先将 3 txt 读入链表 student p file3 if remove F 3 txt 由于排序后的内容也要保存到 3 txt 故删除 3 txt printf 删除文件出错 exit 0 int n 0 学生个数 FILE fp if fp fopen F 3 txt w NULL 新建一个空的 3 txt printf 新建文件出错 exit 0 fprintf fp s top 标题先输入 while p next NULL n p p next typedef struct int totalgrade char name 10 int number int chinese int math int english gradenote 成绩记录 typedef struct gradenote r 100 只初始化了 100 了空间 学生人数超过 100 就不能了 懒得动态分配了 grade list 待排序成绩表 grade list L p file3 int t k j k1 j1 for t 1 tnext 将链表的内容复制到结构数组里 strcpy L r t name p name L r t number p number L r t chinese p chinese L r t math p math L r t english p english L r t totalgrade p chinese p math p english if i 1 直接插入排序 for k 2 k n k if L r k totalgrade L r k 1 totalgrade L r 0 L r k L r k L r k 1 for j k 2 L r 0 totalgrade L r j totalgrade j L r j 1 L r j L r j 1 L r 0 if i 2 int m for k1 2 k1 n k1 L r 0 L r k1 int low 1 high k1 1 while low high m low high 2 if L r 0 totalgrade high 1 j1 L r j1 1 L r j1 L r high 1 L r 0 int q for q n q 1 q 将排序好的内容输入到 3 txt fprintf fp 6s 2d d d d n L r q name L r q number L r q chinese L r q math L r q english if fclose fp printf 文件关闭失败 exit 0 void search char name 按姓名查找 gradelist file fileread F 3 txt student p file while p next NULL if strcmp name p name 0 printf 6s 2d d d d n p name p number p chinese p math p english return p p next printf 查无此人 请确定名字输入正确 n exit 0 void main void int chioce gradelist file1 fileread F 1 txt file2 fileread F 2 txt printf 现有成绩记录文件 1 n printf n FilePrint file1 printf n printf 现有成绩记录文件 2 n printf n FilePrint file2 printf n printf 第一步 合并成绩记录文件 n merger printf 合并成功 n system PAUSE printf 现有合并后的成绩记录文件 3 n printf n gradelist file3 fileread F 3 txt FilePrint file3 printf n printf 第二步 抽取补考成绩记录 n extract system PAUSE printf 现有补考成绩记录文件 4 n printf n gradelist file4 fileread F 4 txt FilePrint file4 printf n printf 第三步 对文件 3 进行排序 n printf 请输入排序方式 1 2 n1 直接插入排序 n2 折半插入排 序 n scanf d if chioce 1 sort 1 else if chioce 2 sort 2 else printf 输入不合理 程序默认采用 1 方式 n sort 1 file3 fileread F 3 txt printf 现有按总分降序的成绩记录 3 n printf n FilePrint file3 printf n printf 第四步 查找学生信息 n char name 100 printf 请输入学生姓名 n scanf s name search name printf 按任意键结束程序 n getchar 4 4 程序运行结果 5哈夫曼编码应用哈夫曼编码应用 5 1 需求分析 问题要求 找一篇英文文章 统计出每个字符出现的次数 然后以他 们为权值 对每个字符进行编码 编码完成后对其编码进行译码 要求 a 输入一篇英文文章 根据字符出现的次数给出哈夫曼编码方式 b 对英文文章进行编码 c 对编码进行译码核对正确性 d 采用哈夫曼编码的思想 实现该文件的压缩和恢复功能 并提供压 缩前后的占用空间之比 5 2 程序设计思想 初始化 程序自动统计文章中的字符出现次数并赋予权值 编制哈夫曼码 根据权值选出两个权值最小值最为叶节点 其权值之和 为根节点 哈弗曼树从叶到根总体按照小到大原则生长 最终实现哈 弗曼树 编码 输入字符 输出哈夫曼码 译码 输入哈夫曼 输出字符代码 退出 结束进程 退出程序 5 3 程序源代码 include include 5 1 h using namespace std int main cout endl cout endl cout 哈夫曼编码译码器 endl cout 1 打开一篇英文文章或输入一篇文章 endl cout 2 根据字符出现的次数以他们为权值给出 哈夫曼编码方式 endl cout 3 对英文文章进行编码 endl cout 4 对编码进行译码核对正确性 endl cout endl cout endl endl system pause cout endl Huffman huffman huffman ReadTextFromFile F text txt cout 程序自动统计字符和权值 endl huffman CountCharsWeight cout endl cout 字符及对应权值 endl huffman PrintCharWeight cout endl system pause cout endl huffman MakeCharMap cout 字符及对应编码 endl huffman PrintCharCode cout endl system pause cout endl cout 对原文进行编码 endl cout 原文 endl huffman PrintText huffman Encode cout endl cout 编码 endl huffman PrintCode huffman SaveCodeToFile F code txt cout endl system pause cout endl cout 对编码进行解码 endl huffman ReadCodeFromFile F code txt cout 编码 endl huffman PrintCode huffman Decode cout endl cout 原文 endl huffman PrintText huffman SaveTextToFile F resulttext txt cout endl return 0 5 4 程序运行结果 6学校超市选址问题学校超市选址问题 6 1 需求分析 设计要求 对于某一学校超市 各学院 部门到超市的距离不同 同 时各部门人数不同 去超市的平均频度也不同 请为超市选址 要求 实现总体最优 6 2 程序设计思想 6 3 程序源代码 include include include include malloc h include using namespace std define TURE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW 1 define INF 32767 const int MAXVEX 100 typedef char Vextype typedef struct Vextype vexs MAXVEX MAXVEX 单位名称 顶点 信息 int adj MAXVEX MAXVEX 单位之间的相通情况 是否有边 int dis MAXVEX MAXVEX 单位间距离 边的长 度 int f MAXVEX 各单位去超市的频率 int n 顶点数和边数 int e Mgraph void CreatMgraph Mgraph G int i j k printf 请输入单位个数 n scanf d printf 请输入单位间的路径数 n scanf d printf 请输入单位名称 n for i 0 in i printf 请输入第 d 个单位名称 n i scanf s for i 0 in i 结构体的初始化 for j 0 jn j G adj i j 0 G dis i j 0 G f i 0 for k 0 ke k printf 请输入相通的两单位 输入格式 i j n scanf d d 在距离上体现为无向 printf 请输入相同两个单位间的距离 格式 dis n scanf d G adj i j 1 G adj j i 1 G dis j i G dis i j for k 0 kn k printf 请输入第 d 个单位去超市的相对频率 n k scanf d for i 0 in i 以距离和频率之 积作为权值 for j 0 jn j G dis i j G f i 最终权值非完全无 向 if G adj i j 0 void Floyed Mgraph G 带权有向图求最短路径 floyd 算法 int A MAXVEX MAXVEX path MAXVEX MAXVEX int i j k pre int count MAXVEX for i 0 in i 初始化 A 和 path 数组 for j 0 jn j 置初值 A i j G dis i j path i j 1 count i 0 for k 0 kn k k 代表运算步骤 for i 0 in i for j 0 jn j if A i j A i k A k j 从 i 经 j 到 k 的一条 路径更短 A i j A i k A k j path i j k cout endl Floyed 算法求解如下 endl for i 0 in i for j 0 jn j if i j cout i j if A i j INF if i j cout 不存在路径 n endl else cout 路径长度为 A i j n cout 路径为 i pre path i j while pre 1 cout pre n pre path pre j cout j endl 以下为选择总体最优过程 然后确址 for i 0 in i for j 0 jn j if A i j INF count i 0 else count i 1 for i 0 in i if count i for j 0 jn j A i 0 A i j for i 0 in i k 0 if count i if A k 0 A i 0 k i cout 超市的最佳地址为 vexs k endl int main Mgraph Gh NULL Gh Mgraph malloc sizeof Mgraph CreatMgraph Gh Floyed Gh return 0 6 4 程序运行结果 7学生成绩管理系统学生成绩管理系统 7 1 需求分析 实现功能 输入 输出 插入 删除 查找 追加 读入 显示 保 存 拷贝 排序 分类统计 退出 7 2 程序设计思想 编辑学生信息保存在文本文档中 具体对学生信息进行插入删除查询 操作时 将保存在文本文档中的学生信息提取出来保存在自己定义的 数据结构中 然后再对该数据结构进行操作 所有操作完成后或者在 相应的命令后再将学生信息保存到文本文档中 数据类型主要是 char int float 等数据类型 内容包括学号 姓名等数据 7 3 程序源代码 include include include include SeqList cpp using namespace std class Student public string num 学号 string name 姓名 string sex 性别 string born 出生日期 string p 政治面貌 string addr 住址 学籍管理类定义 class gxxjgl public gxxjgl gxxjgl void Insert void Delete1 void Update int Locate void Display private SeqList stu void Info int i void gxxjgl Insert Student temp char str1 10 str2 10 str3 10 str4 20 str5 10 str6 30 cout str1 temp num str1 cout str2 temp name str2 cout str3 temp sex str3 cout str4 temp born str4 cout str5 temp p str5 cout str6 temp addr str6 cout 插入位置 1 stu Length 1 i stu Insert i temp void gxxjgl Delete1 int i Locate stu Delete i void gxxjgl Update int i j char t 30 i Locate cout j cout t string ts t Student temp stu Get i switch j case 1 temp num ts break case 2 temp name ts break case 3 temp sex ts break case 4 temp born ts break case 5 temp addr ts break default cout Error n break stu Delete i stu Insert i temp int gxxjgl Locate cout str string t str for int i 1 i stu Length i if stu Get i pare t 0 Info i return i void gxxjgl Display for int i 1 i stu Length i cout stu Get i num data t cout stu Get i name data t cout stu Get i sex data t cout stu Get i born data t cout stu Get i addr data endl void gxxjgl Info int i cout endl cout 学号 stu Get i num data endl cout 姓名 stu Get i name data endl cout 性别 stu Get i sex data endl cout 出生年月 stu Get i born data endl cout 住址 stu Get i addr data endl cout endl 程序入口 void main gxxjgl o while 1 cout n t t 学生学籍管理系统 n endl cout t 1 插入 将某学生的基本信息插入到登记表中 endl cout t 2 删除 将满足条件的基本信息删除 endl cout t 3 修改 对基本信息的数据项进行修改 endl cout t 4 查询 查找满足条件的学生 endl cout t 5 输出 将登记表中的全部 或满足条件 基本信 息输出 endl cout t 6 退出程序 endl cout i switch i case 1 o Insert break case 2 o Delete1 break case 3 o Update break case 4 o Locate break case 5 o Display break case 6 exit 1 break default cout Error endl break system pause system cls include include SeqList h using namespace std SeqList 模板类实现 template SeqList SeqList T a int n if n MaxSize throw 参数非法 for int i 0 i n i data i a i length n template T SeqList Get int i if ilength throw 查找位置非法 else return data i 1 template int SeqList Locate T x for int i 0 i length i if data i x return i 1 return 0 template void SeqList Insert int i T x if length MaxSize throw 上溢 if ilength 1 throw 位置异常 for int j length j i j data j data j 1 data i 1 x length template T SeqList Delete int i if length 0 throw 下溢 if ilength throw 位置异常 T x data i 1 for int j i j length j data j 1 data j length return x template void SeqList PrintList 注意 可根据实际需求输出 for int i 0 i length i cout data i ends define SEQLIST Hconst define MaxSize 100 template class SeqList public SeqList length 0 无参构造函数 SeqList T a int n 带参数构造函数 SeqList 析构函数 int Length return length 求线性表的长度 T Get int i 按位查找 取线性表的第 i 个元素 int Locate T x 按值查找 求线性表中值为 x 的元素序号 void Insert int i T x 在线性表中第 i 个位置插入值为 x 的元 素 T Delete int i 删除线性表的第 i 个元素 void PrintList 遍历线性表 按序号依次输出各元素 private T data MaxSize 存放数据元素的数组 int length 线性表的长度 7 4 程序运行结果 8排序综合排序综合 8 1 需求分析 利用随机函数产生 N 个随机整数 20000 以上 对这些数进行多种方 法进行排序 要求 1 至少采用三种方法实现上述问题求解 提示 可采用的方法有插入 排序 希尔排序 起泡排序 快速排序 选择排序 堆排序 归并排 序 并把排序后的结果保存在不同的文件中 2 统计每一种排序方法的性能 以上机运行程序所花费的时间为准进 行对比 找出其中两种较快的方法 8 2 程序设计思想 快速排序 通过一趟排序将要排序的数据分割成独立的两部分 其中 一部分的所有数据都比另外一部分的所有数据都要小 然后再按此方 法对这两部分数据分别进行快速排序 整个排序过程可以递归进行 以此达到整个数据变成有序序列 插入排序 将一个数据插入到已经排好序的有序数据中 从而得到一 个新的 个数加一的有序数据 算法适用于少量数据的排序 时间复 杂度为 O n 2 是稳定的排序方法 插入算法把要排序的数组分成两 部分 第一部分包含了这个数组的所有元素 但将最后一个元素除外 让数组多一个空间才有插入的位置 而第二部分就只包含这一个 元素 即待插入元素 在第一部分排序完成后 再将这个最后元素 插入到已排好序的第一部分中 选择排序 它的工作原理是每一次从待排序的数据元素中选出最小 或最大 的一个元素 存放在序列的起始位置 直到全部待排序的 数据元素排完 冒泡排序 重复地走访过要排序的数列 一次比较两个元素 如果他 们的顺序错误就把他们交换过来 走访数列的工作是重复地进行直到 没有再需要交换 也就是说该数列已经排序完成 堆排序 利用大顶堆 小顶堆 堆顶记录的是最大关键字 最小关键字 这 一特性 使得每次从无序中选择最大记录 最小记录 变得简单 其基本思想为 大顶堆 1 将初始待排序关键字序列 R1 R2 Rn 构建成大顶堆 此堆为初始的 无须区 2 将堆顶元素 R 1 与最后一个元素 R n 交换 此时得到新的无序区 R1 R2 Rn 1 和新的有序区 Rn 且满足 R 1 2 n 1 R n 3 由于交换后新的堆顶 R 1 可能违反堆的性质 因此需要对当前无序 区 R1 R2 Rn 1 调整为新堆 然后再次将 R 1 与无序区最后一个元 素交换 得到新的无序区 R1 R2 Rn 2 和新的有序区 Rn 1 Rn 不断 重复此过程直到有序区的元素个数为 n 1 则整个排序过程完成 8 3 程序源代码 include 标准输入输出头文件 include 定义杂项函数及内存分配函数 include 字符串处理 include 定义关于时间的函数 define N 20000 clock t Start Now 时钟 void Wrong 错误输出 printf n 按键错误 请重新输入 n getchar 从标准输入获取字符并返回下一个字符 void change int a 十个一行输出 int i system cls 清除之前的操作 for i 0 i N i if i 1 9 printf n printf 7d a i 快速排序 void Sort efcr int a int p int t i j low high mid for i 2 i N i t a i low 1 high i 1 while lowt high mid 1 else low mid 1 for j i 1 j low j a j 1 a j a low t 插入排序 void Sort charu int a int p int i j temp for i 1 i0j 寻找位置插入 a j a j 1 交换 a j temp 选择排序 void sort xz int a int p int i j k for i 0 i N 1 i k i for j i 1 j N j 寻找最小的记录序号 if a j a k k j 记录 if k i int temp temp a k a k a i a i temp 交换 void sort mp int a int p int i j temp for i 0 ii j if a j a j 1 temp a j a j a j 1 a j 1 temp void creatheap int a int i int n 创建堆 int j int t t a i 堆顶元素暂存 j 2 i 1 1 while j n 堆顶元素下筛 if j n if t 0 i 在序列的中间位置找一个数做堆顶 creatheap a i n 1 for i n 1 i 1 i n 1 次筛选 t a 0 a 0 a i a i t creatheap a 0 i 1 插入排序时间 double TSort charu int a int p int i double time int b N for i 0 i N i b i a i 函数值的调用 Start clock Sort charu b p 执行算法 Now clock time double Now Start CLK TCK 执行算法前后的时间差 if p 6 change b getchar 如果用户输入选择不为计算时钟 则要选 择换行输出 printf n 用直接插入排序法用的时间为 f 秒 time FILE fp fp fopen F 直接插入排序 txt w 在 f 盘保存一个文本文件 for i 0 i N i fprintf fp d b i fclose fp return time 选择排序时间 double Tsort xz int a int p int i double time int b N for i 0 i N i b i a i Start clock sort xz b p 执行函数 if p 6 change b getchar Now clock time double Now Start CLK TCK 执行算法前后的时间差 printf n 用直接选择排序法用的时间为 f 秒 time FILE fp 文件指针 fp fopen F 直接选择排序 txt w 存档 for i 0 i N i fprintf fp d b i 读写一个文档 fclose fp return time 冒泡排序时间 double Tsort mp int a int p int i double time int b N for i 0 i N i b i a i Start clock sort mp b p Now clock time double Now Start CLK TCK 执行算法前后的时间差 if p 6 change