搜档网
当前位置:搜档网 › 数据结构课程设计独立题目

数据结构课程设计独立题目

数据结构课程设计独立题目
数据结构课程设计独立题目

题目2:运动会分数统计

1.问题描述

参加运动会有n个学校,学校编号为1……n。比赛分成m个男子项目,和w个女子项目。项目编号为男子1……m,女子m+1……m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m<=20,n<=20)

2.功能要求

1)可以输入各个项目的前三名或前五名的成绩;

2)能统计各学校总分;

3)可以按学校编号、学校总分、男女团体总分排序输出;

4)可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校。

存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。

题目6:哈夫曼编/译码器

1.问题描述

利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。

2.功能要求

I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。

E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件htmTree 中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile 中。

D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。

P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中。

T:印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。

题目9:构造可以使n个城市连接的最小生成树

1.问题描述

给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。

2.功能要求

城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。

输入:表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)

输出:最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。

题目10:哈希表设计

1.问题描述

针对自己的班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。

2.功能要求

假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构照,用链表法处理冲突。测试数据读取熟悉的30个人的姓名。

题目11:走迷宫游戏

1.问题描述

程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

2.功能要求

1) 老鼠形象可辨认,可用键盘操纵老鼠上下左右移动;

2) 迷宫的墙足够结实,老鼠不能穿墙而过;

3) 正确检测结果,若老鼠在规定时间内走到粮仓处,提示成功,否则提示失败;

4) 添加编辑迷宫功能,可修改当前迷宫,修改内容:墙变路、路变墙;

5) 找出走出迷宫的所有路径,以及最短路径。

利用序列化功能实现迷宫地图文件的存盘和读出等功能

题目12:任意长的整数加法

1.问题描述

设计一个程序实现两个任意长的整数的求和运算。

2.功能要求

利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。如:1,0000,0000,0000,0000。

题目13:括号匹配问题

1.问题描述

假设一个算术表达式中可包含三种括号:圆括号,方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算,编写判别给定表达式中所含括号是否正确配对出现的算法。

题目14:关键路径问题

1.问题描述

设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

2.功能要求

1)对一个描述工程的AOE网,应判断其是否能够顺利进行。

2)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。

题目17:利用栈求表达式的值,可供小学生作业,并能给出分数。

功能要求

建立试题库文件,随机产生n个题目;题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价

题目18:约瑟夫环

1.问题描述

编号为1,2… n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个开始重新从1报数,如此下去,直至所有人全部出列为止,设计一个程序求出出列顺序。

2.功能要求

A利用单循环链表作为存储结构模拟此过程;

B键盘输入总人数、初始报数上限值m及各人密码;

C按照出列顺序输出各人的编号。

题目22:家谱管理

编写程序采用一棵二叉树表示一个家谱关系,要求程序具有如下功能:

(1)文件操作功能:记录输入、记录输出、家谱记录存盘;

(2)家谱操作功能:用括号表示法和凹入表示法输出家谱二叉树,查找某人所有的儿子,查找某人的祖先。

题目23:哈夫曼编码应用

本设计要求对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串,要求程序实现以下几个方面的功能:

(1)哈夫曼树的建立(提示:还要设计一个实现统计输入电文字符串中各种字符出现的频率以及字符的种类的算法,假设电文中仅含有大写字母);

(2)哈夫曼编码的生成;

(3)编码文件的译码

题目25:银行业务模拟

客户业务分两种:一是从银行借款或取款,二是向银行存款或还款。银行有两个窗口,相应的有两个队列。客户到达银行先排第一个队。若客户属第一种,且申请额超过银行现存资金总额而得不到满足时,则立即排入第二个队等候,直到满足时才离开银行;否则业务完成后立即离开银行。每接待完一个第二种业务的客户,则顺序检查和处理(如果可能)第二个队列中的客户,对能满足的申请者予以满足,不能满足者重新排到第二个队列的队尾。注意,在此检查过程中,一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额,或者本次已将第二个队列检查或处理了一遍,就停止检查(因为此时已不可能还有能满足者)转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。

利用动态存储结构实现模拟写一个上述银行业务的事件驱动模拟系统,通过模拟方法求出客户在银行内逗留的平均时间。

题目26:文学研究助手

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为“文学研究助手”

英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号。

以您的C源程序模拟小说,C语言的保留字集作为待统计的词汇集。

题目27:散列表的设计与实现

设计散列表实现电话号码查找系统,把数据保存在文件中,充分利用顺序表和链表完成以下功能:

1) 设每个记录有下列数据项:电话号码、用户名、地址;

2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;

3) 采用一定的方法解决冲突;

4) 查找并显示给定电话号码的记录;

5) 查找并显示给定用户名的记录。

6) 设计不同的散列函数,比较冲突率;

7) 在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平

均查找长度的变化。

题目30:商店存货管理系统建立一商店存货管理系统,要求每次出货时取进货

时间最早且最接近保质期中止时间的货物。

分步实施:

(1)初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;(2)完成最低要求:建立一个文件,包括5个种类的货物情况,能对商品信息进行扩充(追加),修改和删除以及简单的排序;

(3)进一步要求:扩充商品数量,以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。

题目31:压缩器/解压器

为了节省存储空间,常常需要把文本文件采用压缩编码的方式储存。例如:一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节(每个x或每个y占用一个字节,两个字节用来表示串的结尾)。同样是这个文件,采用游程长度编码(run-length coding),可以存储为字符串1000x2000y,仅为10个字母,占用12个字节。若采用二进制表示游程长度(1000和2000)可以进一步节约空间。如果每个游程长度占用2个字节,则可以表示的最大游程长度为2*pow(16),这样,上例中的字符串只需要用8个字节来存储。当要读取编码文件时,需要对其进行解码。由压缩器(compressor)对文件进行编码,由解压器(decompressor)进行解码。

①(1)长度-游程编码的压缩/解压;+(2)LZW压缩/解压(散列);

②(1)长度-游程编码的压缩/解压;+(3)霍夫曼编码压缩/解压 (霍夫曼树)

要求选用二种压缩/解压策略实现压缩/解压器[(1)为必选]。输入的为本文文件(.txt),输出的为一种自定义的文件(.nz)。考虑当构成文本的字符集合为{a,b,c,……,z,0,1,2,…9}时,请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动?(压缩后的文本比原来的还要大)。扩充构成文本的字符集合以便使它适应更一般的情况。

数据结构课程设计参考题目

数据结构课程设计题目 数据结构课程设计题目(大题目).doc 一、公司销售管理系统 项目开发基本要求 1.客户信息管理:对客户的基本信息进行添加、修改和删除。 2.产品信息管理:对产品的基本信息进行添加、修改和删除。 3.供应商信息管理:对供应商的基本信息进行添加、修改和删除。 4.订单信息管理:对订单的基本信息进行添加、修改和删除。 二、高校科研管理系统 系统主要用于帮助高校或科研单位管理和维护各项科研相关资料 项目开发基本要求 1.系统用户管理模块:为系统新用户设置用户名及口令;操作员更改自己的系统口令。2.数据字典管理模块:管理项目性质包括:分为国家自然科学基金、863、部省科委及企业集团四种情况;范围包括:分为全国、国际、地方三种情况;检索源包括:分为EI、SCI、核心和一般四种情况。 3.项目参加人员管理模块包括:显示添加修改删除查询。 4.项目基本情况模块包括:显示添加修改删除查询。 5.项目获奖情况模块包括:显示添加修改删除查询。 6.期刊论文管理模块包括:显示添加修改删除查询。 7.著作管理模块包括:显示添加修改删除查询。 8.科研工作量统计模块:按照学校科研工作量计算办法,为每位科研人员进行科研工作量的计算和统计。 9.科研积分统计模块:按照学校科研积分计算办法,为每位科研人员进行科研计分的计算和统计。 三、网络五子棋对战 四、不同排序算法模拟 五、科学计算器 数据结构课程设计题目 1.运动会分数统计 任务:参加运动会有n个学校,学校编号为1……n。比赛分成m个男子项目,和w个女子项目。项目编号为男子1……m,女子m+1……m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m<=20,n< =20) 功能要求: 1)可以输入各个项目的前三名或前五名的成绩; 2)能统计各学校总分,

数据结构课程设计报告模板

《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月

三级项目报告注意事项 1. 按照项目要求书写项目报告,条理清晰,数据准确; 2. 项目报告严禁抄袭,如发现抄袭的情况,则抄袭者与被抄袭者均 以0分计; 3. 课程结束后报告上交教师,并进行考核与存档。 三级项目报告格式规范 1. 正文:宋体,小四号,首行缩进2字符,1.5倍行距,段前段后 各0行; 2. 图表:居中,图名用五号字,中文用宋体,英文用“Times New Roman”,位于图表下方,须全文统一。

目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一:项目成员 (6) 附录二:相关代码、电路图等 (6)

一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能: 1)利用数据结构的知识独立完成一个应用系统设计 2)程序正常运行,能够实现基本的数据增加、删除、修改、查询等功能3)体现程序实现算法复杂度优化 4)体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能: (结合本系统预期具体实现,描述出对应基本要求(增、删、改、查等)的具体功能) 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 (基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现) 模块一: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

数据结构实验总结报告

数据结构实验总结报告 一、调试过程中遇到哪些问题? (1)在二叉树的调试中,从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰,处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题,从而在代码上花了不少时间调试。 目前的设计是: Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子:a(b((),f),c(d,e)) 这样便消除了歧义,保证只有一个孩子的节点和叶节点的处理中不存在问题。 (2)Huffman树的调试花了较长时间。Huffman编码本身并不难处理,麻烦的是输入输出。①Huffman编码后的文件是按位存储的,因此需要位运算。 ②文件结尾要刷新缓冲区,这里容易引发边界错误。 在实际编程时,首先编写了屏幕输入输出(用0、1表示二进制位)的版本,然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性,哪些地方有待改进? (1)压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界,因此可能有几个多余的0,而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案: ①在压缩文件头部写入源文件的总长度(字节数)。需要四个字节来存储这个信息(假定文件长度不超过4GB)。 ②增加第257个字符(在一个字节的0~255之外)用于EOF。对于较长的文件,

会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值,需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值,因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 (2)压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率,减少系统调用次数,增加了8KB的输入输出缓存窗口 这样一来,每写一位二进制位,就要在内部进行两次函数调用。如果将这些代码合并起来,再针对位运算进行一些优化,显然不利于代码的可读性,但对程序的执行速度将有一定提高。 (3)程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性,可以考虑加入其他人性化的功能。 三、调研常用的压缩算法,对这些算法进行比较分析 (一)无损压缩算法 ①RLE RLE又叫Run Length Encoding,是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效,但它有的时候却非常有用(例如,JPEG就使用它)。 变体1:重复次数+字符 文本字符串:A A A B B B C C C C D D D D,编码后得到:3 A 3 B 4 C 4 D。

数据结构课程设计报告

《数据结构与算法》课程设计报告 学号: 班级序号: 姓名: 指导教师: 成绩: 中国地质大学信息工程学院地理信息系统系 2011年12 月

1.需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小,减少存储空间。但是,这要求在首先对一个现有文件进行编码行成新的文件,也就是压缩。在文件使用时,再对压缩文件进行解压缩,也就是译码,复原原有文件。试为完成此功能,写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能: (1)压缩准备。读取指定被压缩文件,对文件进行分析,建立哈夫曼树,并给出分析结果(包括数据集大小,每个数据的权值,压缩前后文件的大小),在屏幕上输出。 (2)压缩。利用已建好的哈夫曼树,对文件进行编码,并将哈夫曼编码及文件编码后的数据一起写入文件中,形成压缩文件(*.Haf)。 (3)解压缩。打开已有压缩文件(*.Haf),读取其中的哈夫曼编码,构建哈夫曼树,读取其中的数据,进行译码后,写入文件,完成解压缩。 (4)程序使用命令行方式运行 压缩命令:SZip A Test.Haf 1.doc 解压缩命令:SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时,给出提示。 (5)使用面向对象的思想编程,压缩/解压缩、哈夫曼构建功能分别构建类实现。 2.总体分析与设计 (1)设计思想: 1、压缩准备:1> 读文件,逐个读取字符,统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程: 1> 建立一个新文件,将储存权值和字符的对象数组取存储在文件头

数据结构课程设计题目选择

数据结构课程设计题目 说明: (1)选用语言:C或Java语言; (2)需要注明3人(可少于3人)小组各自承担和完成的任务(据此给予成绩); (3)如下带“*”的题目,“*”越多,难度越大一些,分值权重更高---要得到更高分数,推荐选择。 要求: (1) 用中文给出设计说明书(含重要子函数的流程图); (2) 给出测试通过、能实现相应功能的源代码; (3) 测试报告。 0、小学数学四则混合运算试题出题、评价、题库自动生成与组卷系统(****)---已经有2组选择 任务: (1)将随机给出的四则混合运算表达式显示在计算机显示器上,要求应试者给出答案;并且使用堆栈对该表达式求值,同给出的答案进行比较,判断 正确和错误。给出鼓励信息和嘉奖信息; (2)保存多人在不同时间应试的题目与他(或她)给出的答案,评价所出题目的难易程度(通过多人回答正确与否的情况给出),形成题库; (3)按照用户给出的题目难易程度指标(例如让50人的得分满足怎样的正态分布,如90分以上10%,80分以上30%,70分以上30%,60分以上20%,60分 以下10%),从题库中抽取不同的题目,组成试卷。 要求:随机产生的题目中,参加运算的数据随机、运算符随机。题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价。 1、集合的并、交和差运算---已经有1组选择 任务:编制一个能演示执行集合的并、交和差运算的程序。 要求: (1) 集合的元素限定为小写字母字符[…a?..?z?] 。 (2) 演示程序以用户和计算机的对话方式执行。 实现提示:以链表表示集合。 选作内容: (1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。 (3) 集合的混合运算表达式求值。 (4) 集合的元素类型推广到其他类型,甚至任意类型。 2、停车场管理------已经有2组选择 任务:设停车场是一个可以停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次有北向南排列(大门在最南端,最先到达的第一车停放在车场的最北端),若车场内已停满n辆车,那么后来的车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 要求:以栈模拟停车场,以队列模拟车场外的便道。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停车不收费)。栈以顺序存储结构实现,队列以链表结构实现。 3、哈夫曼码的编/译码系统(**)---已经有1组选择

数据结构课程设计独立题目

题目2:运动会分数统计 1.问题描述 参加运动会有n个学校,学校编号为1……n。比赛分成m个男子项目,和w个女子项目。项目编号为男子1……m,女子m+1……m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m<=20,n<=20) 2.功能要求 1)可以输入各个项目的前三名或前五名的成绩; 2)能统计各学校总分; 3)可以按学校编号、学校总分、男女团体总分排序输出; 4)可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校。 存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。 。 题目6:哈夫曼编/译码器 1.问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 2.功能要求 I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件htmTree 中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile 中。 D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T:印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。 题目9:构造可以使n个城市连接的最小生成树 1.问题描述 给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。 2.功能要求 城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。

数据结构课程设计报告模板

课程设计说明书 课程名称:数据结构 专业:班级: 姓名:学号: 指导教师:成绩: 完成日期:年月日

任务书 题目:黑白棋系统 设计内容及要求: 1.课程设计任务内容 通过玩家与电脑双方的交替下棋,在一个8行8列的方格中,进行棋子的相互交替翻转。反复循环下棋,最后让双方的棋子填满整个方格。再根据循环遍历方格程序,判断玩家与电脑双方的棋子数。进行大小判断,最红给出胜负的一方。并根据y/n选项,判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境:vc++6.0 实现目标: (1)熟悉的运用c语言程序编写代码。 (2)能够理清整个程序的运行过程并绘画流程图 (3)了解如何定义局部变量和整体变量; (4)学会上机调试程序,发现问题,并解决 (5)学习使用C++程序来了解游戏原理。 (6)学习用文档书写程序说明

摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋,计算机下棋是人工智能领域中的一个研究热点,多年以来,随着计算机技术和人工智能技术的不断发展,计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的,多的一方为胜,少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时,程序采用削弱对手行动力战术,即尽量减少对手能够落子的位置;在游戏终局时则采用最大贪吃战术,即尽可能多的吃掉对手的棋子;而四角优先战术则是贯穿游戏的始终,棋盘的四角围稳定角,不会被对手吃掉,所以这里是兵家的必争之地,在阻止对手进角的同时,自己却又要努力的进角。 关键词:黑白棋;编程;设计

数据结构课程设计题目及要求

实验一~实验四任选一题;实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的: (1)熟练掌握线性表的两种存储方式 (2)掌握链表的操作和应用。 (3)掌握指针、结构体的应用 (4)按照不同的学校,不同项目和不同的名次要求,产生各学校的成绩单、团体总分报表。 二、实验内容: 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目,项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大,有些项目取前五名,得分顺序为7,5,3,2,1;还有些项目只取前三名,得分顺序为5,3,2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单,内容包括各校所取得的每项成绩的项目号、名次(成绩)、姓名和得分;产生团体总分报表,内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n=4,m=3,w=2,编号为奇数的项目取前五名,编号为偶数的项目取前三名,设计一组实例数据。 【实现提示】 可以假设m≤20,m≤30,w≤20,姓名长度不超过20个字符。每个项目结束时,将其编号、类型符(区分取前五名还是前三名)输入,并按名次顺序输入运动员姓名、校名(和成绩)。 【选作内容】 允许用户指定某些项目可采取其他名次取法。

实验二停车场管理 一、实验目的: (1)熟练掌握栈顺存和链存两种存储方式。 (2)掌握栈的基本操作及应用。 (3)以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。 二、实验内容: 【问题描述】 设停车场是一个可停放n辆汽车的长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车信放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场院,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。 【测试数据】 设n=2,输入数据为:(A,1,5),(A,1,15),(A,3,20),(A,4,25),(A,5,30),(D,2,35),(D,4,40),(E,0,0)。其中:A表示到达(Arrival);D表示离去(Departure);E表示输入结束(End)。 【实现提示】 需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:汽车的牌照号码和进入停车场的时刻。 【选作内容】 (1)两个栈共享空间,思考应开辟数组的空间是多少? (2)汽车可有不同种类,则他们的占地面积不同收费标准也不同,如1辆客车和1.5辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积。(3)汽车可以直接从便道开走,此时排在它前面的汽车要先开走让路,然后再依次排到队尾。 (4)停放在便道上的汽车也收费,收费标准比停放在停车场的车低,请思考如何修改结构以满足这种要求。

数据结构课程设计题目

《数据结构》课程设计题目 1. 排序算法的性能分析 问题描述 设计一个测试程序,比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 (1)对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进行比较。 (2)待排序表的表长不小于100,表中数据随机产生,至少用5组不同数据作比较,比较指标:关键字参加比较次数和关键字的移动次数(关键字交换记为3次移动)。 (3)输出比较结果。 选做内容 (1)对不同表长进行比较。 (2)验证各算法的稳定性。 (3)输出界面的优化。 2. 排序算法思想的可视化演示—1 基本要求 排序数据随机产生,针对随机案例,对冒泡排序、箱子排序、堆排序、归并算法,提供排序执行过程的动态图形演示。 3. 排序算法思想的可视化演示—2 基本要求 排序数据随机产生,针对随机案例,,对插入排序、选择排序、基数排序、快速排序算法,提供排序执行过程的动态图形演示。 4. 线性表的实现与分析 基本要求 ①设计并实现线性表。 ②线性表分别采取数组(公式化描述)、单链表、双向链表、间接寻址存储方 式 ③针对随机产生的线性表实例,实现线性表的插入、删除、搜索操作动态演示(图 形演示)。 5. 等价类实现及其应用 问题描述:某工厂有一台机器能够执行n个任务,任务i的释放时间为r i(是一个整数),最后期限为d i(也是整数)。在该机上完成每个任务都需要一个单元的时间。一种可行的调

度方案是为每个任务分配相应的时间段,使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。 基本要求: 使用等价类实现以上机器调度问题。 等价类分别采取两种数据结构实现。 6. 一元稀疏多项式计算器 问题描述 设计一个一元稀疏多项式简单计算器。 基本要求 一元稀疏多项式简单计算器的基本功能是: (1)输入并建立多项式; (2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,…,c n,e n,其中n是多项式的项数,c i,e i,分别是第i项的系数和指数,序列按指数降序排序; (3)多项式a和b相加,建立多项式a+b; (4)多项式a和b相减,建立多项式a-b; (5)计算多项式在x处的值; (6)计算器的仿真界面(选做) 7. 长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储,并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作,即实现算法来求解a+b mod n, a-b mod n, a?b mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 8. 敢死队问题。 有M个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。排长是不愿意去的,假设排长为1号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求:至少采用两种不同的数据结构的方法实现。 9. 简单计算器

数据结构课程设计报告

编号 课程设计 题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题 二级学院计算机科学与工程学院 专业计算机科学与技术 班级 2011级 37-3班 学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师 时间 1、一元稀疏多项式计算器 【实验内容】 一元稀疏多项式计算器。

【问题描述】 设计一个一元稀疏多项式简单计算器。 【需求分析】 其基本功能包括: (1)输入并建立多项式; (2)输出多项式,输出形式为整数序列为:n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数,ci,ei分别是第i项的系数和指数,序列按指数降序排序;(3)多项式a和b相减,建立多项a+b; (4)多项式a和b相减,建立多项式a-b; (5)计算多项式在x处的值; (6)计算器的仿真界面(选做); 【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb); void sort(dnode *h)

dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】 (1)输入多项式:

(2)输出多项式(多项式格式为:c1x^e1+c2x^e2+…+cnx^en): (3)实现多项式a和b相加: (4)实现多项式a和b相减: (5)计算多项式在x处的值:

2、模拟浏览器操作程序 【实验内容】 模拟浏览器操作程序 【问题描述】 标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是:使用两个栈,追踪可以后退和前进而能够到达的网页。在本题中,要求模拟实现这一功能。 【需求分析】 需要支持以下指令: BACK:将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面,使它成为当前页。若“后退栈”是空的,忽略该命令。 FORWARD:将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面,使它成为当前页。如果“前进栈”是空的,忽略该命令。 VISIT:将当前页推到“后退栈”的顶部。使URL特指当前页。清空“前进栈”。 QUIT:退出浏览器。 假设浏览器首先加载的网页URL是:http:

最新数据结构实训总结

精品文档 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。2、培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。4、通过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难,到最后把这个做出来,付出了很多,也得到了很多,以前总以为自己对编程的地方还不行,现在,才发现只要认真做,没有什么不可能。 编程时要认真仔细,出现错误要及时找出并改正,(其中对英语的要求也体现出来了,因为它说明错误的时候都是英语)遇到问题要去查相关的资料。反复的调试程序,最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议,在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议,正所谓当局者迷旁观者清,把各个注意的问题要想到;同时要形成自己的编写程序与调试程序的风格,从每个细节出发,不放过每个知识点,注意与理论的联系和理论与实践的差别。另外,要注意符号的使用,注意对字符处理,特别是对指针的使用很容易出错且调试过程是不会报错的,那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践,体验了一下离开课堂的学习,也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子,在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会,正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解,让我们的理解与记忆更深刻,对不懂的知识与不清楚的东西也做了一定的了解,也形成了一定的个人做事风格。 通过这次课程设计,让我对一个程序的数据结构有更全面更进一步的认识,根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型,有时用基本的一维数组,只要运用得当,也能达到相同的效果,甚至更佳,就如这次的课程设计,通过用for的多重循环,舍弃多余的循环,提高了程序的运行效率。在编写这个程序的过程中,我复习了之前学的基本语法,哈弗曼树最小路径的求取,哈弗曼编码及译码的应用范围,程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中,体现出自己单独设计模具的能力以及综合运用知识的能力,体会了学以致用、突出自己劳动成果的喜悦心情,也从中发现自己平时学习的不足和薄弱环节,从而加以弥补。 精品文档

数据结构课程设计题目表

《数据结构》课程设计课题表 课题1:设计出链表结构的相关函数库,以便在程序设计中调用。要求: (1)包括线性表的各种基本函数以及常用函数(自己确定函数、函数形式及理由)。 (2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。 (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。 课题2:设计出顺序表结构的相关函数库,以便在程序设计中调用。要求: (1)包括线性表的各种基本函数以及常用函数(自己确定函数、函数形式及理由)。 (2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。 (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。 课题3:设计程序以实现任意两个高次多项式的加法和乘法运算。 要求: (1)所设计的数据结构应尽可能节省存储空间。 (2)程序的运行时间应尽可能少。 课题4:设计一个模拟计算器的程序,要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。 要求:要检查有关运算的条件,并对错误的条件产生报警。 课题5:设计出二叉链表结构的相关函数库,以便在程序设计中调用。要求: (1)包括二叉树的各种基本函数以及常用函数(自己确定函数、函数形式及理由)。 (2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。 (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。 课题6:设计出树结构的相关函数库,以便在程序设计中调用。要求: (1)包括树结构的存储结构及各种基本函数以及常用函数(自己确定函数、函数形式及理由)。 (2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。 (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。 课题7:选择合适的存储结构表示广义表,并能实现下列运算要求: (1)用大写字母表示广义表,用小写字母表示原子,并提供设置广义表的值的功能。 (2)取广义表L的表头和表尾的函数head(L)和tail(L)。

数据结构课程设计报告

数据结构课程设计 设计说明书 TSP 问题 起止日期:2016 年 6 月27 日至2016 年7 月 1 日 学生姓名 班级 学号 成绩 指导教师( 签字) 2016 年7 月 1 日

目录 第1 章需求分析.................................................................................1... 1.1 简介 (1) 1.2 系统的开发背景 (1) 1.3 研究现状 (1) 第2 章概要设计.................................................................................2... 2.1 系统开发环境和技术介绍 (2) 2.2 系统需求分析 (2) 2.2.1 总体功能分析 (2) 2.2.2 核心功能分析 (3) 第3 章详细设计...................................................................................4... 3.1 系统开发流程 (4) 3.2 系统模块设计 (4) 3.3 系统结构 (6) 3.2 系统流程图 (6) 第4 章调试分析...................................................................................7... 4.1 程序逻辑调试 (7) 4.2 系统界面调试 (8) 第5 章测试结果...................................................................................9... 5.1 测试环境 (9) 5.2 输入输出测试项目 (9) 5.3 测试结果 (10) 结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2..

关于数据结构课程设计心得体会范文

关于数据结构课程设计心得体会范文 心得体会是指一种读书、实践后所写的感受性文字。是指将学习的东西运用到实践中去,通过实践反思学习内容并记录下来的文字,近似于经验总结。下面是小编搜集的关于数据结构课程设计心得体会范文,希望对你有所帮助。 关于数据结构课程设计心得体会(1) 这学期开始两周时间是我们自己选题上机的时间,这学期开始两周时间是我们自己选题上机的时间,虽然上机时间只有短短两个星期但从中确实学到了不少知识。上机时间只有短短两个星期但从中确实学到了不少知识。 数据结构可以说是计算机里一门基础课程,据结构可以说是计算机里一门基础课程,但我觉得我们一低计算机里一门基础课程定要把基础学扎实,定要把基础学扎实,然而这次短短的上机帮我又重新巩固了 c 语言知识,让我的水平又一部的提高。数据结构这是一门语言知识让我的水平又一部的提高。数据结构这是一门知识,纯属于设计的科目,它需用把理论变为上机调试。 纯属于设计的科目,它需用把理论变为上机调试。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。来说具有一定的难度。它是其它编程语言的一门基本学科。我选的上机题目是交叉合并两个链表,对这个题目,我选的上机题目是交叉合并两个链表,对这个题目,我觉得很基础。刚开始调试代码的时候有时就是一个很小的错觉得很基础。 刚开始调试代码的时候有时就是一个很小的错调试代码的时候误,导致整个程序不能运行,然而开始的我还没从暑假的状导致整个程序不能运行,态转到学习上,每当程序错误时我都非常焦躁,态转到学习上,每当程序错误时我都非常焦躁,甚至想到了放弃,但我最终找到了状态,一步一步慢慢来,放弃,但我最终找到了状态,一步一步慢慢来,经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件! 同时,通过此次课程设计使我了解到,必然具备的条件! 同时,通过此次课程设计使我了解到,硬件语言必不可缺少,要想成为一个有能力的人,必须懂得件语言必不可缺少,要想成为一个有能力的人,硬件

数据结构课程设计题目

数据结构课程设计 一、考核方法和容 根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。 评分标准: 优秀:答辩所有问题都能答出+报告良好 或报告良好+实现“提高部分”的功能; 良好:答辩所有问题都能答出+报告一般; 或报告一般+实现“提高部分”的功能; 中等:答辩大部分问题能答出+报告良好; 及格:答辩大部分问题能答出+报告一般; 以下四种,都不及格: 1)答辩几乎答不出问题; 2)报告几乎都是代码; 3)雷同部分达到60%; 4)课设报告与数据结构和c/c++关联不大。 课设报告的装订顺序如下: 任务书(签名,把题目要求贴在相应位置,注意下划线)-----目录(注意目录的格式,页码)-----1、设计任务(题目要求)-----2、需求分析(准备选用什么数据逻辑结构?数据元素包含哪些属性?需要哪些函数?为什么要这样设计?最后列出抽象数据类型定义)-----3、系统设计(设计实现抽象数据类型,包含选择什么物理存储方式?数据元素的结构体或类定义,以及各函数的设计思路,算法,程序流程图等)----4、编码实现(重要函数的实现代码)-----5、调试分析(选择多组测试数据、运行截图、结果分析)-----6、课设总结(心得体会)-----7、谢辞-----8、参考文献; 课设报告打印要求: B5纸打印,报告总页数控制在10—15页,报告中不能全是代码,报告中代码总量控制在3页。版式:无页眉,有页码,页码居中 字号:小四,单倍行距 字体:宋体+Times new Romar 截图:截图要配图的编号和图的题目,如:“图1 Insert函数流程图” 二、课程设计的题目 1.长整数的加法运算 2.通讯录管理系统的设计与实现——顺序表 3.广义表的应用 4.学生成绩管理系统的设计与实现 5.家谱管理系统的设计与实现

数据结构课程设计报告-学生成绩管理系统[]

武汉理工大学华夏学院课程设计报告书 课程名称:数据结构课程设计 题目:用C语言实现成绩统计程序的设计系名:信息工程系 专业班级:计算机1121 姓名:吴涛 学号:10210412104 指导教师:司晓梅 2016年3 月20日

武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称:数据结构课程设计指导教师:司晓梅班级名称:计算机1121 开课系、教研室:信息系计算机 一、课程设计目的与任务 《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的:学习数据结构课程,旨在使学生学会分析研究数据对象的特性,学会数据的组织方法,以便选择合适的数据的逻辑结构和存储结构以及相应操作,把现实世界中的问题转换为计算机内部的表示和处理,这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握基本知识、基本技能,提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。 任务:根据题目要求,完成算法设计与程序实现,并按规定写出课程设计报告。 二、课程设计的内容与基本要求 设计题目:用C语言实现成绩统计程序的设计 〔问题描述〕给出n个学生的m门课程的考试成绩信息,每条信息由姓名、课程代号与分数组成,要求设计算法: (1)输入每个人的各门课程的成绩,计算每人的平均成绩; (2)按平均成绩的高低次序,打印出个人的名次,平均成绩相同的为同一名次; (3)按名次列出每个学生的姓名和各科成绩; 〔基本要求〕学生的考试成绩必须通过键盘输入,且需对输出进行格式控制; 〔算法提示〕可以用选择排序、冒泡排序等多种排序算法求解; 具体要完成的任务是: A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书; 三、课程设计步骤及时间进度和场地安排 时间:1周地点:现代教育中心 具体时间安排如下: 第一天:布置题目,确定任务、查找相关资料 第二天~第四天:功能分析,编写程序,调试程序、运行系统; 第五天上午:撰写设计报告; 第五天下午:程序验收、答辩。 四、课程设计考核及评分标准

数据结构课程设计排序算法总结

排序算法: (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 (1)直接插入排序;它是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好的序的有序表中,从而得到一个新的、记录数增加1的有序表。 (2)折半插入排序:插入排序的基本操作是在一个有序表中进行查找和插入,我们知道这个查找操作可以利用折半查找来实现,由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同,从时间上比较,折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变。 (3)冒泡排序:比较相邻关键字,若为逆序(非递增),则交换,最终将最大的记录放到最后一个记录的位置上,此为第一趟冒泡排序;对前n-1记录重复上操作,确定倒数第二个位置记录;……以此类推,直至的到一个递增的表。 (4)简单选择排序:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进,基本思想是,通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列,在堆排序的算法中先建一个“大顶堆”,即先选得一个关键字为最大的记录并与序列中最后一个记录交换,然后对序列中前n-1记录进行筛选,重新将它调整为一个“大顶堆”,如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,这种排序称为2-路归并排序。 【算法实现】 (1)直接插入排序: void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i]L.elem[0];j--) L.elem [j+1]=L.elem [j]; L.elem [j+1]=L.elem[0]; } } (2)折半插入排序:

数据结构课程设计题目

数据结构课程设计题目 题目一考试报名系统(必做) 项目简介: 考试报名工作给各高校报名工作带来了新的挑战,给教务管理部门增加了很大的工作量。本项目是对考试报名管理的简单模拟,用控制台选项的选择方式完成下列功能:输入考生信息;输出考生信息;查询考生信息;添加考生信息;修改考生信息;删除考生信息。 项目功能要求: 本项目的实质是完成对考生信息的建立,查找,插入,修改,删除等功能。其中考生信息包括准考证号,姓名,性别,年龄和报考类别等信息。项目在设计时应首先确定系统的数据结构,定义类的成员变量和成员函数;然后实现各成员函数以完成对数据操作的相应功能;最后完成主函数以验证各个成员函数的功能并得到运行结果。(建议采用链表实现) 系统示例 题目二约瑟夫生者死者游戏

项目简介 约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只得统一这种方法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9人,便将他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。 项目功能要求:(要求采用单循环链表) 本游戏的数学建模如下:假如N个旅客排成一个环形,依次顺序编号1, 2, …, N。从某个指定的第S号开始。沿环计数,每数到第M个人就让器出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下K个旅客为止。 本游戏要求用户输入的内容包括: 1、旅客的个数,也就是N的值; 2、离开旅客的间隔书,也就是M的值; 3、所有旅客的序号作为一组数据要求存放在某种数据结构中。 本游戏要求输出的内容是包括: 1.离开旅客的序号; 2.剩余旅客的序号。 系统示例 题目三勇闯迷宫游戏 项目简介: 迷宫只有两个门,一个门叫入口,另一个门叫出口。一个骑士骑马从入口进入迷宫,迷宫设置很多障碍,骑士需要在迷宫中寻找通路以到达出口。

相关主题