数据结构课程设计题目_数据结构课程设计答案
数据结构课程设计题目由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计答案”。
数据结构课程设计题目 以下8个题目任选其一。
1．排序算法比较
利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且（1）统计每一种排序上机所花费的时间。
（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。（3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动)。
（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。2．图的深度遍历
对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。画出搜索顺序示意图。3．图的广度遍历
对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。画出搜索顺序示意图。4．二叉树的遍历
对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。5．链表操作
利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。画出搜索顺序示意图。6．一元稀疏多项式简单计数器（1）输入并建立多项式
（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。用带头结点的单链表存储多项式。测试数据：
（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．实现两个链表的合并 基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。
（2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线性表C，使得：
当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm 当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn 输出线性表C：
（1）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。测试数据：
（1）A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2）A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）8．哈夫曼编码的实现与应用
（1）从文件中读入任意一篇英文短文（至少含3000个字符，文件为ASCII编码的文本文件）
（2）统计不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码。
（4）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率
（5）根据相应哈夫曼编码，对编码后的文件进行解码，恢复成ASCII编码的英文短文后输出。
分析及设计步骤（供参考）
1.分析问题，给出数学模型，设计相应的数据结构。
1)分析问题特点，用数学表达式或其它形式描述其数学模型。2)选择能够体现问题本身特点的一种或几种逻辑结构。
3)依据逻辑结构和问题特点，设计并选择相应的存储结构（顺序存储结构和链式存储结构对应的算法实现有区别）。
2.算法设计
1)确定所需模块：对于复杂的程序设计，要充分利用模块化程序设计方法和面向对象思想，自顶向下，逐步细化。
2)各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。3)模块之间的调用关系：给出算法各模块之间的关系图示。3.上机实现程序
为提高工作效率，充分利用上机调试时间，在上机之前应列出程序清单。
4.用有代表性的各种测试数据去验证算法及程序的正确性
5.算法分析及优化
经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度，如有可能对程序进行优化改进。
课程设计报告范例（参考）
约瑟夫环问题。
问题描述：设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，抱m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。基本要求：
（1）初始报数上限值m和测试数据在程序中确定；（2）用带头结点的单循环链表作数据元素的存储结构；（3）把带头结点的单循环链表作为抽象数据类型设计。测试数据：
n = 7，七个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m = 20 算法思想：
JesephRing()函数是实现问题要求的主要函数，其算法思想是：从1至m对带头结点的单循环链表循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。模块划分：
（1）带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。
（2）void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。这是对带头结点的单循环链表抽象数据类型SCLinList，补充本问题需要的一个操作函数。（3）void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。
（4）void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。数据结构：
（1）数据类型DataType定义如下： typedef struct { int number;int cipher;} DataType;
（2）带头结点单循环链表抽象数据类型SCLinList。
（3）带头结点单循环链表抽象数据类型的结点结构定义如下：
typedef struct node { DataType data;struct node *next;} SCLNode;源程序：
源程序存放在两个文件中，文件SCLinList.h是带头结点单循环链表抽象数据类型，文件Exam3-9.c是主程序。
文件SCLinList.h： typedef struct node { DataType data;struct node *next;} SCLNode;/*结点结构定义*/ void SCLLInitiate(SCLNode **head)/*初始化*/ { if((*head =(SCLNode *)malloc(sizeof(SCLNode)))== NULL)exit(1);(*head)->next = *head;} int SCLLInsert(SCLNode *head, int i, DataType x)/*插入一个结点*/ { SCLNode *p, *q;int j;p = head->next;j = 1;while(p!= head && j data = x;q->next = p->next;p->next = q;return 1;} int SCLLDelete(SCLNode *head, int i, DataType *x)/*删除一个结点*/ { SCLNode *p, *q;int j;p = head;j = 0;while(p->next!= head && j next;p->next = p->next->next;*x = q->data;free(q);return 1;} int SCLLGet(SCLNode *head, int i, DataType *x)/*取一个结点数据元素值*/ { SCLNode *p;int j;p = head;j = 0;while(p->next!= head && j next;j++;} if(j!= i){ printf(“取元素位置参数错！”);return 0;} *x = p->data;return 1;} int SCLLNotEmpty(SCLNode *head)/*链表非空否*/ { if(head->next == head)return 0;else return 1;} 文件Exam3-9.c： #include #include typedef struct { int number;int cipher;} DataType;/*定义具体的数据类型DataType*/ #include “SCLinList.h” /*包含SCLinList抽象数据类型*/ void SCLLDeleteAfter(SCLNode *p)/*删除p指针所指结点的下一个结点*/ { SCLNode *q = p->next;p->next = p->next->next;free(q);} void JesephRing(SCLNode *head, int m)/*对带头结点单循环链表head，初始值为m的约瑟夫环问题函数*/ { SCLNode *pre, *curr;int i;pre = head;curr = head->next;while(SCLLNotEmpty(head)== 1){ for(i = 1;i next;if(curr == head){ pre = curr;curr = curr->next;} }
printf(“ %d ”, curr->data.number);m = curr->data.cipher;curr = curr->next;if(curr == head)curr = curr->next;SCLLDeleteAfter(pre);} } void main(void){ DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}};int n = 7, m = 20, i;SCLNode *head;SCLLInitiate(&head);/*初始化*/ for(i = 1;i
各种排序比较结果（参考）
直接插入的比较图表***030002500直接插入的移动图表比较次数2000系列1******4738291100次数移动次数2000系列1******4738291100次数 冒泡的比较次数***00冒泡的移动图表***00比较次数移动次数*********1100执行次数系列*********91100次数系列1
SHELL的比较次数12001000800***01200SHELL的移动图表比较次数移动次数******1100执行次数系列******564738291100次数系列1
快速排序的比较次数800700600快速排序的移动图表540520500比较次数移动次数******4738291100执行次数系列******8291100次数简单选择的移动图表350300250系列1
简单选择的比较次数***0比较次数移动次数300025002000******4738291100执行次数堆排序的比较次数107010601050系列1200系列1******8291100次数 堆排序的移动图表***0比较次数移动次数*********00执行次数系列117401720******65564738291100次数系列1
一、表达式求值（2-3人） 问题描述：从键盘上输入中缀算数表达式，计算出表达式的值。 基本要求：1.程序对所输入的表达式做简单的判断，如果表达式有错，能给出适当的提示。2.能处理+、－......
数据结构课程设计一、教学目的和要求课程设计是加强学生实践能力的一个强有力手段。综合课设1主要针对数据结构和c/c++语言开展的实践性课程。要求学生掌握数据结构的应用、......
数据结构课程设计题目1.运动会分数统计（限1 人完成）任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不......
数据结构课程设计题目1.飞机订票系统（限1 人完成）任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个......
数据结构课程设计一、考核方法和内容根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩......
