长江大学数据结构课程设计报告

1、 1 概述数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。课程设计是加强实践能力的一个强有力手段，通过这次课程设计力争达到以下几个目标：（1）能够模块化地设计一个综合程序（2）加深对数据结构与算法的理解（3）巩固与拓展自己的编程视野，为将来的编程学习做准备。为了达到以上目标，同时结合个人学习的兴趣，选定以下题目作为本次课设的任务：（1）内部排序算法比较；（2）基于单链表的班级通讯录；（3）表达式求解；（4）平衡二叉树；（5）最小生成树；（6）哈夫曼编码/译码器；（7）四叉树编码。2 算法设计与实现首先为了整个程序能够展示出其模块性我特地设计了一个可以将各个模块连接到一起的主函数，并且设计了一个主菜单。（1）主函数int main()int choice;while (choice = InitAll() & choice != 8)printf(nt程序在进行n);switch (choice)case 1:Sort(); system(pause); system(cls); continue;case 2:system(cls);

2、TxunL(); system(pause); system(cls); continue;case 3:AVL(); system(pause); system(cls); continue;case 4:BDS(); system(pause); system(cls); continue;case 5:MIN(); system(pause); system(cls); continue;case 6:HFF(); system(pause); system(cls); continue;case 7: system(pause); system(cls); continue;default:break;/以下写你的判断代码printf(n程序结束，感谢您的使用谢谢n);system(pause);（2）菜单int InitAll()int choice, confirm;printf(nt|-数据结构课程设计-|tnt|*|tnt|1:内部排序 |tnt|2:学生链表通讯录 |tnt|3:平衡二叉树 |tnt|4:表达式求解 |tnt|5:最小生成树 |tnt|6:哈夫曼树 |

3、tnt|7:四叉树编码（没有设计成功） |tnt|8:退出程序（销毁对象） |tnt|*|tnn);printf(t请输入你想进行的操作：);scanf_s( %d, &choice);while (confirm = getchar() != n)continue;/输入检测while (choice 8）printf(t您的输入: %d 有误!请重新输入：, choice);scanf_s( %d, &choice);return choice;2.1 内部排序算法的比较2.1.1 需求分析（1）以顺序表作为待排序表的存储结构，其中表长（即关键字个数）不小于100，表中数据随机产生，至少用5组不同数据作比较。（2）至少实现起泡排序（Bubble）、直接插入排序（Insert）、简单选择排序（Select）、快速排序（Quick）、希尔排序（Shell）、堆排序（Heap）几种基本排序算法。（3）输出比较结果。分别输出采用各种排序算法对每组数据进行排序前的待排序序列和排序后的排序结果序列；分别输出对应5组数据，各类算法比较的结果表。2.1.2 概要设计本程序包括4个模块：主程序模块、

4、函数排序模块、计算模块、顺序表存储模块。主程序模块（由于模块化设计的原因，为保证只有一个主函数，特定义一个函数作为一个代替main的主函数执行该部分主程序）：是整程序的入口和出口，接受用户从终端发出的指令，根据指令执行对应的操作，当接受到退出指令后，程序结束。伪代码如下：void Sort() 初始化与赋值; For循环 调用排序函数；进行相关计算；打印排序表格；排序函数模块：各种不同的排序方式的算法，要比较的部分随着函数的之心数值也发生着变化。计算模块：进行最后的平均值计算。顺序表存储模块：要排序的数据输入后放入此模块各模块之间调用关系如下：主程序模块顺序表模块计算模块排序函数模块 图1 模块调用关系图2.1.3 详细设计（1）顺序表模块顺序表存储结构的定义：#include#include#include/exit molloc#define MAXSIZE 101#define OK 1#define ERROR 0typedef int Status;typedef struct Status *key;int length;int listsize;SqList;int co

5、mp56;/记录比较次数int move56;/记录移动次数顺序表存储功能的定义：Status InitList(SqList* L);/初始化顺序表void DestroyList(SqList* L);/销毁顺序表Status ListInput(SqList*L,int n);/数据输入顺序表中Status Traverse(SqList L,int n);/遍历（2）内部排序模块内部排序函数：void InsertSort(SqList *L,int a);直接插入排序void ShellInsert(SqList *L, int dk, int a);void ShellSort(SqList *L, int *dt, int t,int a);/希尔排序void BubbleSort(SqList *L,int a);/冒泡排序int Partition(SqList *L, int low, int high,int a);void Qsort(SqList *L, int low, int high,int a);void QuickSort(SqList *L,int

6、 a);/快速排序void SelectSort(SqList *L,int a);/选择排序void HeapAdjust(SqList *L, int s, int m,int a);void CreatHeap(SqList*L,int a);void HeapSort(SqList*L,int a);/堆排序（3）主程序模块 int Sort() int i, n, a;int ave16, ave26;int dt3 = 5,3,1 ,t=3;SqList L,L1, L2, L3, L4, L5, L6; srand(unsigned)time(0);/时间播种-真随机 for (a = 0; a 5; a+) InitList(&L); n = 101; ListInput(&L, n); L1 = L; InsertSort(&L1, a); L2= L; ShellSort(&L2, dt, t, a); L3 = L; BubbleSort(&L3, a); L4 = L; QuickSort(&L4, a); L5 = L; HeapSort(&L5, a); L6 = L; SelectSort(&L6,a); printf(|-内部排序各算法比较表-|n); printf(|-|-比较次数-|-移动次数-|n); printf(| 分组|Insert|Bubble|Shell |Quick |Heap |Select|Insert|Bubble|Shell |Quick |Heap |Select|n); for (a = 0; a 5; a+) printf(| %d|, a + 1); for (i = 0; i 6; i+) printf(%6d|, compai); for (i = 0; i 6; i+) printf(%6d|, moveai); printf(n); printf(| 平均|);ave(ave1,ave2); for (a = 0; a 6; a+) printf(%6d|, ave1a); for (a = 0; a 6; a+) printf(%6d|, ave2a);printf(

《长江大学数据结构课程设计报告》由会员咩西分享，可在线阅读，更多相关《长江大学数据结构课程设计报告》请在金锄头文库上搜索。