数据结构课程设计题目

《数据结构课程设计题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计大纲学院：　计算机科学与技术学院　　　　专业：计算机应用、信息应用时间：　19、20周　　　　　　　学分：2一、课程设计的目的和任务1、提高对数据逻辑结构的特点以及存储表示方式的认识，培养在具体应用中选择合适的数据结构和存储结构的能力；2、熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等阶段的基本任务和技能方法；3、培养学生的算法设计和算法分析能力，提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具

2、备的科学的工作方法、作风和相互合作的精神。二、课程设计的主要内容与要求1.课程设计选题（每人一个题目，共计14题）[1]文章编辑　　功能：输入一页文字，程序可以统计出文字、数字、空格的个数。　　静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。　　存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。　　

3、输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；[2]、迷宫问题1)问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。012345678901111111111入口(1,

4、1)出口(6,8)图1迷宫示意图，其中1代表有障碍，0代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下110111011112110101111131010000011410111011115110011000161011001101711111111112)基本要求(1)设计数据结构存储迷宫；(2)设计存储结构保存从入口到出口的通路；(3)设计算法完成迷宫问题的求解；(4)分析算法的时间复杂度。3)设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方

5、向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x,y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]

6、中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向v(0≤v≤7)到达新点（i，j）的坐标：i=x+move[v].x；j=y+move[v].y。算法用伪代码描述如下：1.栈初始化；2.将入口点坐标(x,y)及该点的方向d（设为-1）入栈；3.当栈不空时循环执行下述操作：3.1(x,y,d)<==栈顶元素出栈；3.2求出下一个要试探的方向d++;3.3沿顺时针试探每一个方向，执行下述操作：3.3.1如果方向d可走，则3.3.1.1将(x,y,d)入栈；

7、3.3.1.2求新点坐标(i,j)；3.3.1.3将新点(i,j)切换为当前点(x,y)；3.3.1.4若(x,y)是终点，则算法结束；否则，重置d=0；3.3.2否则，试探下一个方向d++；[3]顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。要求

8、：1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况[4]集合运算1)问题描述使用链表来表示集合，完成集合的合并，求交集等操作。2)基本要求（1）用链表表示两个集合（2）对两个集合分