数据结构课程设计题目.docx

数据结构课程设计题目

第一篇：数据结构课程设计题目数据结构课程设计题目以下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值，从他在顺时针方向上的下一个人起重新自