数据结构课程设计迷宫

数据结构课程设计迷宫（共7篇）

数据结构课程设计迷宫 篇1

燃烧室新型迷宫复合冷却结构的设计与换热分析

燃烧室迷宫复合冷却结构是一种集冲击、对流换热和近似发散冷却于一身,兼具冲击冷却、对流换热冷却和席壁冷却结构优点的.创新性冷却结构.本文在研究该结构冷却机理的基础上,从实用的角度出发,以某型现役发动机燃烧室改型设计为例,对瓦块式迷宫冷却结构进行设计,并进行换热分析和壁温计算.初步研究表明,该冷却结构的冷却性能优于全气膜冷却结构.

作 者：何立明 张立志 原和朋 李名魁 金涛 陈鑫 蒋永健 HE Li-ming ZHANG Li-zhi YUAN He-peng LI Ming-kui JIN Tao CHEN Xin JIANG Yong-jian  作者单位：空军工程大学,工程学院,陕西,西安,710038 刊 名：空军工程大学学报（自然科学版）  ISTIC PKU英文刊名：JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY (NATURAL SCIENCE EDITION) 年，卷(期)：2005 6(5) 分类号：V23 关键词：瓦块   迷宫复合冷却结构   换热分析   冷却性能  

数据结构课程设计迷宫 篇2

迷宫密封又称疏齿密封, 属于非接触式密封, 即人为的在泄漏通道内加设许多齿或槽来增加泄漏流动中的阻力, 使造成泄漏的压差急骤的损失以达到密封目的[1,2]。迷宫压缩机采用了非接触式迷宫密封, 不仅做到排气绝对无油, 而且压缩机气缸内不产生任何粉尘磨屑, 同时对压缩介质中混入的杂质颗粒不敏感, 在易燃易爆烃类气体及氧气装置中, 或在超高温、超低温工况及压缩绝对干燥气体 (如氮气) 时使用具有极高的安全可靠性, 且很可能是唯一的选择。由于迷宫压缩机密封副不接触, 不用像接触环式压缩机那样频繁更换摩擦元件, 其易损件少、使用寿命长、维修费用低、摩擦功耗小, 故其综合经济性能占有较大优势。

2010年, 攀枝花华益能源有限责任公司焦炉煤气合成液化天然气及蒽油加氢三废综合利用、节能减排工程正式启动, 其中甲烷化循环高温压缩机由沈阳远大压缩机股份有限公司承制, 甲烷化循环工艺要求压缩机最高排气温度达298℃, 鉴于工况的特殊性, 受四氟密封元件使用温度的限制, 普通活塞环密封压缩机已无法满足使用要求, 针对此技术难点, 沈阳远大压缩机在装备制造业率先开展了高温迷宫压缩机攻关试验研究。

1压缩机设计基本要求

1) 压缩机机组在规定的工况下能有效、安全可靠地连续运行操作。压缩机组按照最低20年的使用寿命进行设计和制造, 并可以不间断运行3年 (易损件除外) 。

2) 压缩机为单层布置, 采用无油润滑迷宫密封结构, 两列两缸一级压缩, 气缸为立式双作用。

3) 压缩机组安装于焊接公用底盘上, 该撬装结构紧凑, 占地面积小, 现场安装方便快捷。

4) 主要性能参数 (如表1所示) 。

2高温压缩机技术特点

2.1 耐高温材料的选择

由于压缩介质工作温度较高, 排气温度高达300℃, 高温情况下金属材料在有持续的应力作用时会发生蠕变, 通常碳素钢温度超过300℃即可能发生蠕变, 而非金属材料高温时也会出现融化的现象, 所以该压缩机对于材料的要求非常苛刻[4]。

2.1.1 缸体、缸盖及活塞体材料选择

由于高温条件下金属材料强度降低, 塑性增大, 且易发生蠕变现象, 普通的铸铁材料无法满足设计工况下的使用要求, 而普通耐热钢或耐热铸铁虽然能够满足使用温度的要求, 但其线膨胀系数过大, 由于迷宫压缩机的特点, 气缸与活塞之间留有一定间隙, 当材料膨胀系数较大时, 将会导致在高温工况下工作时活塞与缸体径向间隙变小, 容易造成活塞刮缸, 影响压缩机的使用。奥氏体不锈钢同样存在上述问题, 虽然耐热性能优良, 但其线膨胀系数过大, 同样无法作为缸体、活塞使用。针对此技术难点, 沈阳远大压缩机与子公司辽宁远宇重工机械有限公司合作, 共同自主研发了高温球墨铸铁YDQ-350G, 可以满足铸件在350℃所需的机械性能, 同时控制350℃时其线膨胀系数约为奥氏体不锈钢的1/2, 解决了由于膨胀系数过大导致刮缸的问题, 气缸体、缸盖、活塞等过流铸铁零部件均采用此材料。

2.1.2 填料环材料选择

填料的作用为阻止气缸内的高压气体向曲轴箱泄漏。迷宫压缩机的填料环与活塞杆之间采用浮动式迷宫形式密封, 填料密封环材料需要满足高温条件下工作所需的强度以及密封要求, 材料选择的好坏直接影响填料密封环的加工性、密封性和耐热性。针对这些要求, 我们选择的材料是线性膨胀系数较低的浸渍锑合金 (M254D) , 该材料的使用温度范围广, 最高可达到400℃, 具体性能如表2:

2.1.3 气阀材料的选择

气阀的作用是实现压缩气体在气缸内自动的吸入和排出, 气阀是往复压缩机中最为关键的一个部件, 气阀的升程、弹簧力的大小需要根据运行工况进行精确的计算, 气阀性能的好坏直接影响压缩机的排气量、功耗以及运转的可靠性。本机气阀设计不仅要考虑上述的计算需要, 还要考虑高温条件下阀片及弹簧的使用性能。目前广泛使用的PEEK阀片最高使用温度为200℃, 不能满足350℃的设计要求, 所以本机阀片需采用金属阀片, 材料为30Cr13, 弹簧材料则选用瑞典进口的耐高温性能优良的沉淀硬化不锈钢17-7PH。

2.2 关键零部件结构设计 (如图1所示)

高温迷宫压缩机气缸工作腔的温度为高温介质, 但曲轴箱隔室工作腔温度却不允许过高, 否则将导致润滑油温升高, 造成由于润滑油的粘度降低而烧瓦等事故。由于填料存在一定泄漏, 且曲轴箱与气缸间会有热量传递, 所以, 该压缩机结构设计的难点在于如何避免高温部件将温度传导到低温部件, 同时也要考虑如何导走热量, 降低运动部件温度, 避免温度持续升高, 使压缩机能够安全稳定运行。

1) 为阻止高温从气缸传递至曲轴箱, 气缸与曲轴箱连接面设置导热腔, 内通导热油进行循环冷却, 导热油最高使用温度应不低于300℃, 配置专门的导热油循环系统。

2) 为改善填料的工作条件, 提高密封环的使用寿命, 填料设置冷却腔, 通入导热油进行冷却, 与导热腔共用导热油系统。

3) 为降低活塞杆工作温度, 改善活塞杆热应力状况, 活塞杆内设置冷却腔, 通入润滑油进行冷却。

4) 气缸与曲轴箱之间的隔室设置充氮口, 持续通入常温氮气置换由填料泄漏出来的微量压缩介质, 保证机组运行的安全性, 同时起到隔热、导热的作用, 保证曲轴箱内润滑油温在正常工作范围内。

5) 导向轴承通水冷却, 用于降低刮油环与活塞杆产生的摩擦热, 利于导向轴承润滑油膜的形成, 延长导向轴承的使用寿命。

6) 金属在高温条件下会有较大的热膨胀量, 产生较大的热应力, 所以承受高温的零部件设计均应考虑热应力的影响, 如螺栓紧固部位应采用自锁防松垫圈, 工艺气管路应设置弹簧支座或波纹管膨胀节吸收热变形量等。

7) 压缩机进出口缓冲器应具有足够的缓冲容积, 至少应为每转活塞排量的14倍, 以降低气流脉动。支座应考虑吸收热膨胀量, 可采用弹簧支座。容器及工艺气管线应进行保温防烫处理, 避免高温对现场操作人员造成伤害。

3 结语

由于迷宫压缩机制造技术难度较大, 原材料选用严格, 机械加工与装配精度要求特别高, 目前国际上只有瑞士、日本等为数不多的几个国家能够制造生产, 而对于设计温度为350℃的迷宫式压缩机来说, 国际上目前也没有可借鉴的运行案例, 其高温材料的试验研究和选用、导热结构设计仍是技术关键和难点。远大压缩机通过攻关试验, 已成功的设计制造了国内首台高温迷宫压缩机, 目前已顺利投入工艺运行, 正为用户创造着显著的经济效益。

沈阳远大压缩机通过自主创新形成了企业自主知识产权, 并填补了国内空白。企业也因此掌握积累了宝贵的高温迷宫机的设计、工艺和制造经验, 为今后更好开拓高温领域装备技术奠定了基础。此项攻关项目的完成, 对实现国内重大装备技术的国产化, 满足国家经济建设的需要和促进装备制造业的技术进步以及企业技术水平、创新能力的提升均具有重大意义。

摘要：文章以沈阳远大压缩机股份有限公司实际设计制造出的高温迷宫压缩机为例, 阐述了高温压缩机在设计中的基本要求和技术特点, 并提出了关键零部件结构设计时需要注意的材料选取和工作温度等问题。为我国高温迷宫机的设计、工艺制造乃至更好开拓高温领域装备技术提供参考。并且该实例的成功, 促进装备制造业的技术进步以及企业技术水平。

关键词：迷宫式压缩机,高温压缩机,结构设计

参考文献

[1]郁永章.活塞式压缩机设计[M].北京:机械工业出版社, 1981.

[2]石华鑫.活塞式压缩机设计[M].西安:西安交通大学, 1964.

[3]郁永章.姜培正.孙嗣莹.压缩机工程手册[M].北京:中国石化出版社, 2011.

数据结构课程设计迷宫 篇3

长期以来，具有迷宫般身世的艾米莉·勃朗特被称为英国文学中的“斯芬克斯”，她唯一的小说《呼啸山庄》则成为文学史上的“斯芬克斯之谜”。在这部迷离奇幻的小说中，多视角的迷宫式叙事结构，使作品弥漫着浓郁的迷宫意识。

关键词《呼啸山庄》狄达勒斯迷宫意识叙事结构。

作为现代人类生存状况的隐喻和象征的“迷宫意识”，已成为20世纪西方文学中普遍蔓延的主导意识。正如美国学者克里斯托夫·纳什(Cristopher Nash)在总结当代文学中大量出现的迷宫母题时指出，“迷宫也许代表着整个创造行为”。

迷宫之为迷宫的最大特征在于普遍认可的交通规则的消失，迷宫中的每条道路都包含着含混和歧义，每一条路都指向不只一个可能的方向，“其中的迂回曲折，使进到里面去的任何人都会迷惑地眼花缭乱”。如果说迷宫意象是现代主义文学经常采用的创作手段和文学标志，那么艾米莉·勃朗特的《呼啸山庄》则是西方文学中较早具有迷宫意识从而使作品呈现出现代性景观的一部小说。长期以来，具有迷宫般身世的艾米莉·勃朗特被称为英国文学中的“斯芬克斯”，她唯一的小说《呼啸山庄》则成为文学史上的“斯芬克斯之谜”。在这部迷离奇幻的小说中，充满谜语色彩的地名与人名，多视角的迷宫式叙事结构，双重性格的形象塑造，歧义丛生的文本主题，无不使作品弥漫着浓重的迷宫意识，从而使作品呈现出现代性意蕴。本文试图从叙事结构方面来解读这部作品的迷宫意识。

叙述视角是指叙述故事的着眼点和角度，是文学作品叙事策略的关键。因此，珀西·卢柏克说：“小说技巧中，全部复杂的方法问题，我认为都从属于视点问题——即叙述者与故事的关系问题。”在《呼啸山庄》中，艾米莉一反19世纪以前传统的叙述视角，创造性地撷取了一个异常独特的视角模式：她既没有采用像《简·爱》那样以自传体第一人称“我”的“自知视角”来观察、叙述情节，也不像《傲慢与偏见》用第三人称“全知视角”来讲述故事，而是借小说中次要人物的视角展开叙述：即由房客洛克乌德和女管家丁耐莉分别以第一人称“我”来承担叙述任务，整个小说的宏观结构是由洛克乌德透过丁耐莉的视角来讲述的。为了保证故事的衔接，在故事情节线中断的地方，又常常穿插其他人物的叙述，来补充洛克乌德和丁耐莉有限的视角感知范围以外的信息，以使故事情节尽可能完整。因此，众多叙述者的叙述按着“洛克乌德的叙述→丁耐莉的叙述→其他人的叙述”这样一种层层包容的关系展开，构成了套盒式结构模式，从而构筑起多视角立体框架式结构的叙事迷宫。

《呼啸山庄》全书共由34章组成，艾米莉别出心裁地采用了当时罕见的“戏剧性结构”，即倒叙和顺叙相结合的方法：故事从中间叙述，然后向两边展开：对过去的回忆用倒叙，而未来的发展用顺叙。整部小说的叙述时间跨度是31年，即从1771年孤儿希刺克厉夫从利物浦被带至呼啸山庄，到1802年秋小凯瑟琳和哈里顿成为一对情侣为止，作者把叙述的起点安排在1801年的冬天。

前三章是洛克乌德以第一人称的视角采用顺序的方式叙述的，洛克乌德是小说中的次要人物，作为“局外人”，他只能以一个不知内情人的陌生眼光来观察、猜测和客观地评判所看到的一切。但在叙述结构上，洛克乌德是个举足轻重的“聚焦人物”（focal character)，读者要借助他的视角“进入”《呼啸山庄》的迷宫世界。洛克乌德深夜翻看到的凯瑟琳·恩萧的日记，以及所作的荒诞离奇的恶梦构成了这部小说的最大悬念，这些悬念统领着整部小说。因此，从小说的总体布局上说，这3章是开启“迷宫”大门的一把钥匙。第四章至第三十章基本上是对于过去的回忆，采用的是倒叙手法。是丁耐莉应病中的洛克乌德的请求，把呼啸山庄和画眉山庄两家三十年来的恩恩怨怨一段又一段地讲给他听，再由洛克乌德以第一人称的语气向读者转达，丁耐莉的叙述对上述悬念起解码和释疑作用。作家在总体采用双重叙述模式之外，为了保证故事的衔接，在故事情节中断的地方，还巧妙运用第一人称多重视角进行插叙和补叙。如凯瑟琳的日记，伊莎贝拉私奔后写给丁耐莉的信，山庄女仆齐拉向丁耐莉讲述的山庄情形等。第三十一章和三十二章基本上是顺叙，也是整个故事的高潮：是洛克乌德叙述的，作品最后两章由丁耐莉讲述，洛克乌德先生收尾。在小说的结尾，希刺克厉夫在对凯瑟琳的极度思念和“顿悟”中神秘地死去；小凯瑟琳和哈里顿喜结良缘，欢爱重回人间。这样作者应用多层次、多视角的叙事模式，突破了单一的第一人称手法的局限，使情节显得扑朔迷离、峰回路转，使整个故事更加丰满地呈现在读者面前。

过去许多评论家指责作品“充满着缺点的结构”。就连十分赞赏这部小说的英国著名小说家毛姆，也这样评说：“《呼啸山庄》的结构臃肿笨拙，……她要讲的是一个牵涉到两代人的复杂的故事。这是一桩很困难的事，……艾米莉做得不成功。”他甚至说：“讲《呼啸山庄》这个故事，一个有经验的小说家可能会找到一个更好的方法。”深入研究这部作品，我们可以看出《呼啸山庄》之所以能跻身于世界一流文学作品的艺术地位，很大程度上取决于它的貌似“臃肿笨拙”、实则匠心独具的叙述结构。作家择取洛克乌德、丁耐莉两个人物的双重视角的相互转换来结构小说，使得一个繁杂的故事变得简洁而明晰。如果按传统的叙述手法就会显得更加芜杂、零乱且容易出现与小说主留无关紧要的游离成分，就像布斯所说：“故事无法从一个始终如一的视角来写，否则就要拖到现有长度的三倍。”另外，多视角叙述还成功地避免了作家对外部世界感知经验上的缺陷。最突出的例子是希刺克厉夫出走在外的三年，是希刺克厉夫的性格发展过程就留下一个缺环，形成了故事情节链条上的一个断裂带。但艾米莉巧妙地选择丁耐莉这一“有限的全知”（limited-omniscient)视角来叙述就成功地避免了作者视角必须详尽交代清楚的缺陷，这一缺环由于丁耐莉知识与视野上的局限而被“合情合理”地省去了，反而使希刺克厉夫这个人物性格内涵更为浓缩与丰富，达到了出人意料的艺术效果，这是艾米莉多视角叙述所具有的价值与意义的又一次凸显。

我们之所以说艾米莉的多视角叙事结构具有迷宫意识，是因为无论是不知内情的“局外人”洛克乌德，还是长年生活在封闭偏僻的山庄对外界自然缺乏感知能力的的女仆丁耐莉，都无法让我们相信他们叙述的真实性。作者本人也不直接参与叙述，而是作为局外人巧妙地隐藏于幕后，避开了直接主观评价的局限，令读者无法判断作者的道德价值取向究竟是什么。因此，只有凭借读者自己的判断才能真正破译谜底，走出作者精心设置的叙事迷宫。《呼啸山庄》中多视角叙述模式的运用，是对传统“全知视角模式”的突破与超越，在人类文学史上具有划时代意义，是20世纪现代叙事学的先驱。

参考文献

[1]刘永杰.《呼啸山庄》中地名和人名的意蕴解读.佳木斯大学社会科学学报，6（2004），79-81.

[2]克利夫斯.呼啸山庄的主题,风格及其结构.晓凤译.文化译丛，1988.

[3]袁若娟.《呼啸山庄》的主旋律：人性的扭曲与复归.外国文学研究，4（1992）.

[4]方平.为什么顶楼上藏着一个疯女人——<简·爱><呼啸山庄>研究及其他.上海：上海译文出版社，1994.

[5]向晓红.一个超现实的文本.西南民族学院学报，6(2000)，67-70.

[6]蒲若茜.对《呼啸山庄》中希刺克厉夫和凯瑟琳的爱的原型分析.暨南大学学报，2( 1997)，107－116.

[7]Nash,Cristopher.World Postmodern Fiction:A Guide.NewYork:Longman,1994.

[8]方平.希望在人间——论《呼啸山庄》（译序）.艾米莉·勃朗特著，方平译.上海：上海译文出版社，1993.

穿越迷宫教学设计 篇4

本课以“小猫”穿越“迷宫”抓“老鼠”为故事情节，编写程序，共分为三大部分。第一部分：设置舞台和角色；第二部分：编写“小猫”穿越“迷宫”抓“老鼠”的程序；第三部分：穿越迷宫。

学情分析

学生对于程序的流程并不是很了解，所以在课堂上教师要引导学生把程序分成几个小的部分，各部分逐一突破，这样学生的学习过程会比较轻松愉快。预设教学目标

1.理解侦测与判断的含义。2.运用侦测与判断创作故事或游戏。教学重点 理解侦测与判断的含义。教学难点

运用侦测与判断创作故事或游戏。课时安排： 1课时 预设教学过程：

一、激趣导入 师：上一次我们观赏了马戏团小丑的表演，同学们还记得吗？那么他们还有什么表演呢？一起去看一看吧！

二、设置舞台和角色

师：今天小猫要给大家表演穿越迷宫捉老鼠，感兴趣吗？ 师：想要看小猫穿越迷宫捉老鼠的表演，首先要把舞台设计成迷宫，并且要增加老鼠的角色。师示范操作：

①打开scratch软件。②把舞台设置成迷宫。

③导入老鼠角色，设置好小猫和老鼠的大小以及位置。知识屋：

程序通过颜色判断是否碰到障碍，因此迷宫尽量用一种颜色表示。师：下面请同学们设计一个自己喜欢迷宫作为舞台背景。生操作，师巡视指导。

三、迷宫抓老鼠 师：刚才老师看到同学们都已经把你们的迷宫阵给布置好了呢。那我们希望小猫通过跟随鼠标指针在迷宫中前进，如果碰到障碍就后退，再重新前进，最终在规定的时间内捉到老鼠，这样表演就视为成功，否则表演为失败，程序执行结束。该怎么设置呢？ 师示范操作：

1、设置起点

① 选择角色小猫，单击“脚本”。②单击模块，拖动到脚本区。③单击模块，拖动 到脚本区，并设置数 值。

④单击模块，拖动到脚本区。⑤单击模块，拖动 到脚本区，并选中。

迷宫景观的设计研究论文 篇5

迷宫景观设计构成要素主要包含出入口、中心、路径、材料、设计高度等几个方面。

1.1出入口设计

出入口对迷宫景观设计有着重要的意义。首先景观出入口设计是把两个分割的空间联系在一起的重要媒介，迷宫景观的出入口相当于整个景观内部与外部连接的门窗。另外，出入口设计的巧妙与否关乎整个迷宫景观娱乐性的强弱。出入口设计可以在形式和个数上两个角度变换设计，从而营造趣味性更强的迷宫景观。常见的入口形式有3种：“I”字型、“T”字型、“十”字型。体验者选择进入迷宫景观的方式，随着入口设计形式的变换而变化。入口不仅在形式上变换，还在数量上有选择的设计。由于出入口数量和位置设计的不同，迷宫景观的体验难度系数也随之加大。因此，迷宫景观出入口设计的合理性，可以提高体验者游玩迷宫的兴趣和挑战。

1.2中心设计

中心景点凝结了整个迷宫景观文化底蕴，表达景观核心主题，不论是古代还是现代的迷宫景观都寄予故事传说，每条路径和每个景点设计都是在编织着美丽的故事。体验者带着无限的遐想和憧憬寻找迷宫的中心。

1.3路径布置

路径是整个迷宫景观设计的精髓所在。路径设计首先要考虑的问题是，路径与中心景点的位置关系，主要分为路径经过中心景点、路径围绕中心景点、路径远离中心景点。几种形式的路径在景观设计中交叉使用进而形成路径网络，其中路径在交点处主要有3种基本形式：“十”字型交叉岔口、“Y”字型岔口和“米”字型岔口。错综复杂的路径迷惑或干扰体验者到达中心景点的选择。每1种选择并非绝对错也不一定绝对正确，只是选择不同到达中心景点的路径不同，这个过程中伴随着无限的神秘感和趣味性。甬道宽度设计：根据整体迷宫景观大小、规模和形式设计甬道宽度。迷宫一般多为圆形、方形和不规则形。甬道通常设计宽一般为0.8…m、1…m和1.2…m。每条甬道设计2～3个回合，迷惑体验者，增加景观娱乐性。

1.4墙体高度设计

迷宫墙的高度对迷宫游戏难易程度起着至关重要的作用，并与之成正比关系。围合迷宫的墙体越高难度越大，体验者越不容易找到中心景观甚至迷失方向。迷宫墙体的高度设定应该参照体验者视线高度而分类设定。

1.5材料选择

迷宫材料构成了围合迷宫的“墙体”，是迷宫景观最不可或缺的一部分。材料的选择和组合设计在很大程度上影响着迷宫景观效果。目前已有的迷宫景观设计应用的材料主要分为3大类：软质材料、硬质材料和混合材料。软质材料中植物应用最多。西方许多植物迷宫沿袭了文艺复兴时期园林风格，兼有巴洛克和勒诺特式造园形式，多选用一些易修剪、易成形的树种，如黄杨、紫杉、米心树、疏花鹅耳枥树等。软质材料还包括水、气模等材料的迷宫。硬质材料主要是建筑石材，除此之外还有玻璃、木头、镜子等。混合材料的迷宫在现代设计中比较多见。例如玛莎施瓦茨设计的迷宫园就是多种材料混合。

2景观类型

迷宫景观的形成受宗教色彩和地域性文化影响深刻。纵观西方各时期的迷宫，景观设计形式多样，具有不同特色。迷宫在形状构成上大体可分为：圆形迷宫、方形迷宫、不规则形迷宫3种类型。童寯先生在《造园史纲》中提到，迷阵Maze和Labyrinth是绿篱划隔的回纹狭路，使进入的游人循路曲折摸索，有时误入死胡同，易进难出，以为戏乐。迷宫按照难易程度大体分为易进难出、易出难进、难出难进3种类型(见表3)。这3种形式的迷宫分别有各自的特点，易进难出和易出难进的两种形式相对简单，中心点一般只设置1～2个，人们寻找目标明确，并在娱乐的基础上稍加难度，来激发人们的游玩兴趣。难出难进形式的迷宫路径错综复杂，目标不明确，体验游玩的人们很容易迷失方向，到达中心点比较困难。

3迷宫在景观中的应用现状

3.1迷宫在古典景观中的应用

西方古典迷宫景观中多应用植物迷宫和建筑迷宫两种形式。迷宫都被赋予浓郁的宗教色彩，象征着复杂而多变的人生旅程，迷宫的中心往往隐喻死亡和生命的永恒，其曲折蜿蜒的路径都是信徒们朝圣的必经之路，迷宫被看作是一个与神零距离接触的圣地。古埃及人在金字塔下建造迷宫，用以防止盗墓者侵犯法老的墓室，盗取给他们陪葬的财宝。迷宫，我们自然联想到中国古代用于战争或武林界的天门阵、八卦阵。新疆伊犁特克斯县被民间称作“八卦城”，它的布局是依据易经八卦建造的，以文化广场为轴心，延伸出八条主街，分别代表8个方向“乾、坤、震、坎、巽、艮、离、兑”，通过4条环形的道路相连，是真正的四通八达。这种类型的城市布局看上去像迷宫，但是布局规整。江南狮子林的布置形式也与迷宫有着异曲同工之妙，利用山石堆叠形成假山，与园中景观巧妙结合，山石和迷宫融为一体。

3.2迷宫在现代景观中的应用

随着时代的进步，人们与环境的关系也随之发生改变，不仅仅停留在美的欣赏之中，还体现在参与其中的感知和乐趣。同时，人们面对生活、工作等各方面的压力，需要有空间去缓解、释放这种压力。因此，当今的迷宫景观主要应用于农业观光、主题公园、医院、校园、商业等方面。

3.2.1农业观光园…蔬菜迷宫成为农业观光园的一种新形式，设计者们利用多姿多彩的植物，搭配设计在较大的空间上，形成美丽的农业景观。这将生产、生活和生态相结合，为体验者提供了休闲化、体验化的空间。例如2007年4月昌平区小汤山镇土沟村的四季蔬菜观光主题园——“京承碧园”，蔬菜迷宫占地约…0.13…hm2。以竹竿为主体材料，由高到低为主体层次，内设凉亭、手动遮阳设备，种植作物达30多种。利用蔬菜名称、种类和形状等特点打造蔬菜迷宫。

3.2.2商业空间…商业空间迷宫景观的应用，可增添娱乐气氛。如加拿大的Kensington商业街，每周都会出现1个不同的Labyrinth迷宫，供行人儿童玩耍。国内近几年商业街也出现这种形式的微型迷宫，沈阳市中街可口可乐公司创作的迷宫，在圣诞节期间，吸引很多行人游玩，不仅起到节日娱乐气氛，同时也是一种无形而有效的广告。卓展商场中厅，以熊猫为主题的迷宫也引起许多小朋友和家长的兴趣，购物的同时体验到亲子互动的乐趣。

3.2.3学校、医院…迷宫景观在娱乐性的主题景观外，还是具有冥想、缓解压力的场所。最初起源于美国，很多医院和康复中心都采用迷宫治疗法。迷宫景观还可以作为一种纪念载体。例如美国波士顿大学中的1个Labyrinth迷宫，用来寄托哀思和悼念911事件中的逝者。人们利用迷宫中的冥想、静走来抚平灾难所带来的伤痛。

4结语

数据结构课程设计报告 篇6

数据结构课程设计报告

课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级

专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师

数据结构课程设计

迷宫

题目一

1.设计内容 1.1问题描述

求迷宫从入口到出口的所有路径。1.2设计要求

1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。

1.3开发环境

Visual C++6.0的集成化环境 1.4研究思路

对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。

经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。

2.设计步骤

2.1 需求分析

（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和

1-1数据结构课程设计

迷宫

在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。

2.3 详细设计（1）主菜单伪代码：

while(flag1){

}

{shuru();//输入行列数

printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++)

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数

数据结构课程设计

迷宫

和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。

（2）算法的时空分析：

由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。

链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。

3.用户使用说明

运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。

图数据结构课程设计

迷宫

图1-2

图1-3 退出

5.总结与心得体会

本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。

{ }

mg[i][j]=1;//初始化

矩阵,将最外围置为1

printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2);

}mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量

}

void showplay(int mg[][M+2])//迷宫输出

{

n“);

for(i=1;i<=m;i++){

printf(”n“);for(j=1;j<=n;j++)

printf(”%d “,mg[i][j]);

int i,j;

printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计

迷宫

} } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){

}

printf(”n“);for(j=1;j<=n;j++){

} if(mg[i][j]==0)printf(”

if(mg[i][j]==1)printf(“

if(mg[stack->row][stack->col+1]==

p->next=stack;

stack=p;{

p=(mlink 可通)：n”);0)//下面位置可通

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■

//入栈

mg[stack->row][stack->col]=1;//将

} else

访问过的标记为1 int Mazepath(int mg[][N+2]){

mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p;

//将入口

mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&

if(mg[stack->row][stack->col-1]==0)//上面可通

//入栈

stack=p;

p->next=stack;

{

p=(mlink *)malloc(sizeof(mlink));

*)malloc(sizeof(mlink));

p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问

&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口

{

mg[stack->row][stack->col]=1;//将

访问过的标记为1

数据结构课程设计

迷宫

void tonglu()//将坐标的顶点输出 {

始化

printf(“(%d%3d)n”,q->row,q->col);

情况

else printf(“□”);//0的 } q=stack;{

} for(i=0;i

for(j=0;jrow-1][q->col-1] q=q->next;

=

while(q!=NULL)//循环条件 q=q->next;for(j=0;j

情况

}

void create(int mg[][N+2])//创建和菜单

{

int i,j,x,choice,flag1=1;chushi();while(flag1){ }

printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件

printf(“

##

printf(”#

n“);

*********选择菜单**********

#n”);

printf(“

##

printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫

{

shuru();

printf(”手动建立for(i=1;i<=m;i++)

n“);

printf(”# 1-手动生成迷

宫

2-自动生成迷宫

3-退出

#n“);0;//将路径中的点赋给辅助数组a 形的界面输出

迷宫矩阵(0表示可通1表示障碍):n”);

for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);

数据结构课程设计

航班信息查询与检索系统

题目二

1.设计内容 1.1问题描述

设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。

1.2设计要求

（1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能：  创建

 修改（插入、添加、删除、更新） 查询  浏览  退出管理系统（3）航班信息包括：

 航班号：字符序列，具体字符表达的意思上网查询  起点站和终点站：字符串  班期：指一周中哪些天有航班

 起飞时间：可将时间定义成一个时、分组成的序列  到达时间：可将时间定义成一个时、分组成的序列  机型：字符序列，具体字符表达的意思上网查询  票价：整型数，具体值可上网查询

（4）创建是指从文件中读取数据，并存入所定义的顺序表中。

（5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。

（6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。

（7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。

数据结构课程设计

航班信息查询与检索系统

typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane {

};（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数：

do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”);

printf(“*

1.创建

2.修改

3.查询

4.浏览

5.表长

6.文件

0.退出

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”);

scanf(“%d”,&opt);switch(opt){

case 1:Initlist(L);break;

case 2:handle(L);break;

case 3:search(L);break;

case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break;

数据结构课程设计

航班信息查询与检索系统

} }while(opt!=0);}

（4）文件操作： void File(Sqlist &L){

int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“*

*n”);

printf(“* 1.保存信息到文件

2.从文件读取信息

0 退出 *n”);

printf(“*

*n”);

printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”);

printf(“请输入选项n”);

scanf(“%d”,&ch);

switch(ch)

{

case 1:SaveList(L);break;

} }while(ch!=0);case 2:ReadList(L);break;

case 0:printf(“退出！n”);break;}

（5）浏览信息：就是循环使用输出函数，在此就不必多说了

2.4 调试分析

（1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。

（2）算法中有许多不是很优化的地方。3.用户使用说明

程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打

数据结构课程设计

航班信息查询与检索系统

图2-2 查询信息

图2-3插入

图2-4删除

数据结构课程设计

航班信息查询与检索系统

时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。

6.附录

#include #include #include typedef struct time { int hour;int min;

{ }

void search_key(Sqlist L)//按航班号查找

{ 号：“);

Time rh;Time lv;

scanf(”%s“,n);int i;

printf(”此航班的航班号，起点char n[20];

printf(“请输入要查找的航班

printf(”%dn“,L.length);//表长

}Time;typedef struct node {

}Pnode;struct Plane {

};typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;

终点，班期，起飞时间，到达时间，票价：n”);

if(strcmp(L.plane[i].key,n)==0)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length;

plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

0数据结构课程设计

航班信息查询与检索系统

printf(“此航班的航班号，起点

ted，{ 终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].lv.hour<=hour)

ted，L.plane[i].sche,L.plane[i].lv.hour,L.{

for(i=L.length-1;i>=0;i--){

printf(“%s %s %s %d:%d %

d:%d %dn”,L.plane[i].key,L.plane[i].s

L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

}

void search(Sqlist L){

int i;do {

printf(“* * * * * * * * * * * }

} printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane

} void search_rh(Sqlist L){

int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price);

* * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

printf(“* 1.航班号查询

2.起点终点查询

3.班期查询 4.起飞时间查询

5.到达时间查询

0.退出

*n”);

printf(“* * * * * * * * * *

* * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”);

scanf(“%d”,&i);

switch(i)

{

case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”);

if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){

1:search_key(L);break;

2数据结构课程设计

航班信息查询与检索系统

n“);

} else { } printf(”查找不成功。

i--;if(i==0)

{

char c[20];

printf(“输入修改后的scanf(”%s“,c);

内容：”);

strcpy(L.plane[i].sche,c);

printf(“修改成功！n”);}break;{

int a,b;

printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1:

printf(”修改成功！n“);printf(”修改成功！n“);{

char a[10];printf(”输入修改后的scanf(“%s”,a);

case 4:

内容：“);

char b[20];printf(”请输入修改后scanf(“%s”,b);

scanf(“%d:%d”,&a,&b);

L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“);

}break;{

int a,b;

printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{

case 5: case 2:

内容：“);

scanf(”%d:%d“,&a,&b);

L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break;

}break;{

int a;

case 6: case 3:

4数据结构课程设计

航班信息查询与检索系统

*n“);

printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“);

printf(”请输入选项n“);

scanf(”%d“,&ch);

switch(ch)

{

case 1:SaveList(L);break;case 2:ReadList(L);break;

L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane

[i].rh.hour,&L.plane[i].rh.min,&L.pl

}

void delet_Sq1(Sqlist &L){

char n[10];int i,j;

printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){

printf(“没有选项！n”);for(i=0;i

L.length++;

ane[i].price);

case 0:printf(“退出！n”);break;

}

void Initlist(Sqlist &L)//插入存储 {

“);

容：”);价n“);

scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i

班期

起飞时间

到达时间

票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内

int i,n;printf(“输入表中航班的数量：

} }while(ch!=0);

班号：”);

if(strcmp(L.plane[i].key,n)==0)

{

printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”);

printf(“n航班号

起点终点

printf(”%s %s %s %d:%d %d:%

d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane

[i].rh.hour,L.plane[i].rh.min,L.plane

[i].price);

6数据结构课程设计

航班信息查询与检索系统

n”);} printf(“无法打开文件！}

}while(opt!=0);

void insert_Sq(Sqlist &L){ 数量

价n”);

for(i=0;i

printf(“* * * * * * * * * * *

scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[

{

int a=get_Sq(L);

printf(”请输入要添加班机的scanf(“%d”,&n);

printf(“请输入要添加的班机printf(”n航班号

起点终点

int i,n;

//n表示添加的fprintf(fp,“航班号：%sn起点站：%s

终点站：%sn班期：%dn起飞时间：%d:%d

到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi

n“);} void delet_Sq(Sqlist &L){

int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price);

数量：“);

信息：n”);

班期

起飞时间

到达时间

票* * * * * * * * * *n“);

printf(”* 1.航班号删除

printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除

0.退出

*n”);* * * * * * * * * * *n“);

scanf(”%d“,&opt);

switch(opt){

case 1:delet_Sq1(L);break;

case 2:delet_Sq2(L);break;

case 0:printf(”退出。}

L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan

e[L.length].rh.min,&L.plane[L.length].price);

}

void handle(Sqlist &L){

}

L.length++;

数据结构课程设计正文 篇7

比较与实现

摘 要：本次课程设计主要研究几种常用查找算法的比较与实现，查找的算法有很多种：静态查找表的顺序表、有序表、索引顺序表等查找结构；动态查找表的二叉排序树、哈希查找等查找结构。本次的课程设计主要研究两种常见的查找算法：顺序查找和折半查找，分析比较它们的时间复杂度，并且在此基础上用C语言对它们进行算法编程、调试和运行。

关键词：C语言；顺序查找；折半查找;时间复杂度。

１ 引 言

“数据结构”在计算机科学中是一门综合性的专业基础课，“数据结构”的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，一遍查找和存取数据元素更为方便。因此，可以认为“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

课程设计是我们专业课程知识综合应用的实践训练，是实践性教学的一个重要环节。而数据结构的课程设计，更要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码薄中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。而同样地，在各种系统软件和应用软件中，也存在“查找”：如编译程序中符号表、信息处理表中相关信息的查找。所以，“查找”就是在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录）。

【1】在计算机中进行查找的方法也会随数据结构不同而不同。在此，引入“查找表”的概念：同类数据元素构成的集合。所以，这次的课程设计就可以从静态查找表的几种典型的算法来实现对数据元素的查找的算法和操作的实现和比较。

1.1课程设计背景

《数据结构》课程设计作为独立的教学环节，是计算机相关专业集中实践环节系列之一，是学习完《数据结构》课程后进行的一次全面的综合练习。所以需要我们了解并掌握数据结构与算法的设计方法，并且具备初步的独立分析和设计能力，同时要掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。所以这次课程设计的目的在于：加强学生对C语言的基本知识和技能；加深对数据结构基础理论和基本知识的理解，提高解决实际问题的实践能力；同时帮助调动学生的积极性和能动性，培养学生的自学、动手能力。

２

1.2课程设计目标

本次课程设计，我准备用不同的两种常见的查找方法：针对顺序查找表中查找方法，如顺序查找、折半查找等。并且通过用这些算法实现对某个“特定的”数据元素（关键字）的查找，分析这些操作的性能：它们各自的时间复杂度、空间复杂度和其它的一些性能，同时记录每种查找方法的优缺点，比较得出它们的查找效率和查找范围。

３ 设计概要

2.1 问题描述

对于不同的查找算法，它们各自的时间复杂度和空间复杂度不同，查找的思想和算法也明显不同，所以要分析它们的特点和效率，我们要多方面比较：要比较时间复杂度，我们可以从它们的查找长度侧面比较出来；而它们算法的实现就要熟悉它们的查找思想，熟练应用C语言编写合适的程序。

2.2 设计思路

静态查找表有顺序表和链式表两种表示方法，在这次的课程设计里，我用顺序存储表来表示这两种查找算法的程序。我的设计思路及步骤如下：

（1）熟悉两种算法的编程思想,画出流程图。

（2）先编写两种算法的子程序，再遍写主程序调用它们。

（3）分步调试子程序和主程序，直到不再出现错误，然后运行程序，检查是否和 自己当初的设想一样，一直到结果能让自己满意。（4）比较得出两种查找算法的优缺。

2.3 相关的知识点

（1）C语言表示静态查找表的顺序存储结构 typedef struct { ElemType *elem;

//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int length;

//表的长度

} SSTable;

４（2）查找算法的衡量指标

查找可能产生“成功”与“不成功”两种结果，但在实际应用的大多数情况下，查找成功的可能性比不成功的可能性大得多，特别是在记录数中n很大时，查找不成功的概率可以忽略不计。当查找不成功的情况不能忽视时，查找算法的平均长度应该是查找成功时的平均查找长度与查找不成功时的平均查找长度之和，平均查找长度为： ASL= picii1n

其中，n为元素的个数； ci是查找第i 个记录需进行的比较次数；pi是查找第i个记录的概率，一般可认为查找每个记录的概率是相等的，即p1=p2=„=pn=1/n。【2】

５ 算法分析及程序编写

3.1.顺序表的查找

（1）基本思想

从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。（2）顺序查找算法流程图

算法流程图如图3-1所示：

图3-1：顺序查找算法流程图

６（3）顺序查找算法代码如下

int Search_Seq(SSTable *table, ElemType key){

/*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/

table->elem[0]=key;

//设置哨兵 int result=0;

// 找不到时，返回0 int i;for(i=table->length;i>=1;i--)

{

//从后往前找

if(table->elem[i]==key)

{

} result=i;

//找到关键字的时候，该元素的位置 break;

}

return result;

//找不到时返回 } <4>顺序查找算法性能分析

对于顺序查找，不论给定值key为何值，查找不成功时和给定值进行比较的关键字个数均为n+1.假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则Pi=1/（2n）,此时顺序查找的平均查找长度为[3]：

ASL= (ni1ni1)+(1/2)(n+1)

=(3/4)(n+1)

<5>结论

顺序查找的优点是算法简单，且对表的结构没有任何要求。它的缺点是查找效率低，因此，当表中元素个数比较多时，不宜采用顺序查找。

７

3.2.折半查找

（1）使用折半查找必须具备两个前提条件

a：要求查找表中的记录按关键字有序(假设：从小到大有序)b：只能适用于顺序存储结构

（2）基本思想

先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找，直到查找成功，或者查找失败。

(3）查找流程图

流程图如图3-2所示：

８

图3-2：折半查找算法流程图

(4）折半查找算法的代码

int Search_Bin(SSTable *table, ElemType key){

/*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0.*/

int low=1;

int high=table->length;

//置区间初值

int result=0;// 找不到时，返回0 while(low <= high)

９

{

} return result;int mid=(low+high)/2;

//中间的数据元素 if(table->elem[mid]==key){ result=mid;break;}

//找到待查元素 else if(keyelem[mid]){ high=mid-1;}

//继续在前半区间进行查找 else { low=mid+1;}

//继续在后半区间进行查找

}[5]

（5）折半查找算法性能分析

在折半查找的过程中，每经过一次比较，查找范围都要缩小一半，所以折半查找的最大查找长度为

MSL=[log2 n]+1 当n足够大时，可近似的表示为log2(n)。（6）结论

折半查找要求查找表按关键字有序，而排序是一种很费时的运算；另外，折半查找要求表是顺序存储的，为保持表的有序性，在进行插入和删除操作时，都必须移动大量记录。因此，折半查找的高查找效率是以牺牲排序为代价的，它特别适合于一经建立就很少移动、而又经常需要查找的线性表。

可见在查找速度上，折半查找比顺序查找速度要快的多，这是它的主要优点[4]。

１０ 测试分析

1.输入元素有误

（1）：若输入的元素个数不合理，元素个数少于n，这种输入造成的的结果是系统一直等待元素的输入，即得不到结果。如图4-1所示：

图4-1：输入元素个数少时的运行情况

（2）若输入元素个数大于n时，系统将从第一个元素起，自动选取前n个元素作为有效元素，进行程序的后续运行。这种情况下的结果如图4-2所示：

图4-2：输入元素个数多时的运行情况

１１

2.查找失败

这种情况是指在n个元素中没有与关键字相同的元素存在，所以程序运行的结果是查找失败。运行结果如图4-3所示：

图4-3：查找失败时的运行情况

3.查找成功

若查找成功，即元素输入无误，且有关键字存在的情况，这个时候的运行结果如图4-4所示[5]：

图4-4：查找成功时的运行情况

１２ 总结和体会

5.1 课程设计总结

“书到用时方恨少”。在这次课程设计，我感触最深的当属查阅大量的设计资料了，为了让自己的设计更加完善，查阅这方面的设计资料是十分必要的，看着那么大叠的书籍、资料摆在自己的面前，有些时候还要上网查阅相关知识点，并且还要整理出有用的知识点，这对于我来说，是在是个不小的挑战。所以，以后一定要多看自己专业方面的书籍，增长自己的知识。而且，写程序是一件十分需要耐心的活，一个不小心，后果就可能是几个小时的思考和调试，幸好这次的课题我并不陌生，所以，并没有自己想象中的艰难。但是，用的时间和精力却绝对也不少。

5.2 心得与体会

这次课程设计，使我对《数据结构》这门课程有了更深入的了解。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。一个人的力量是有限的，要想把课程设计做的更好，就要学会参考一定的资料，吸取别人的经验，让自己和别人的思想有机的结合起来，得出属于你自己的灵感。

在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。程序的编写需要有耐心，有些事情看起来很复杂，但问题需要一点一点去解决，分析问题，把问题一个一个划分，划分成小块以后就逐个去解决。再总体解决大的问题。这样做起来不仅有条理也使问题得到了轻松的解决。

通过这两周的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。

１３

参考文献：

[1]严蔚敏，吴伟民.《数据结构:C语言版》 清华大学出版社，2012.5 [2]Mark Allen Weiss.数据结构与算法分析——C语言描述（英文版第二版）.北京：人民邮电出版社，2005 [3]李峰，谢中科.C语言程序设计.上海：复旦大学出版社，2011 [4]Baloukas, C., Risco-Martin, J.L., Atienza, D., et al.Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systems[J].Journal of Systems and Software, 2009, 82(4): 590-602.[5]李春葆，尹为民.数据结构教程上机指导（第三版）.北京：清华大学出版社,2008

１４

附录：程序源代码：

#include #include #include

using namespace std;typedef int ElemType;

//用C语言定义顺序存储结构

typedef struct {

ElemType *elem;

//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int length;

//表的长度 } SSTable;

void Create(SSTable *table, int length);

// 构建顺序表

void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);

void Traverse(SSTable *table, void(*visit)(ElemType elem));

void Create(SSTable **table, int length){

// 构建顺序表

SSTable *t =(SSTable*)malloc(sizeof(SSTable));

１５ t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));t->length=length;*table=t;} void FillTable(SSTable *table){

// 无序表的输入

ElemType *t=table->elem;for(int i=0;ilength;i++){

t++;

scanf(“%d”, t);

getchar();} } void Destroy(SSTable *table){

//销毁表

free(table->elem);free(table);} void PrintTable(SSTable *table){

// 打印查找表中的元素

int i;ElemType *t=table->elem;

１６ for(i=0;ilength;i++){ t++;printf(“%d ”, *t);

} } //顺序（哨兵）查找算法

int Search_Seq(SSTable *table, ElemType key){

/*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为零。*/

table->elem[0]=key;

//设置哨兵 int result=0;

// 找不到时，返回0 int i;for(i=table->length;i>=1;i--)

{

//从后往前找

if(table->elem[i]==key)

} {

} result=i;

//找到关键字的时候，该元素的位置 break;

return result;

//找不到时返回 }

１７

void Sort(SSTable *table){

// 排序算法

int i, j;ElemType temp;

for(i=table->length;i>=1;i--)

// 从前往后找 {

for(j=1;j

}

int Search_Bin(SSTable *table, ElemType key){ /*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元

} {

} if(table->elem[j]>table->elem[j+1]){

//从小到大排列

} temp=table->elem[j];table->elem[j]=table->elem[j+1];//元素后移 table->elem[j+1]=temp;素在表中的位置，否则为0.*/

int low=1;

１８

} int high=table->length;

//置区间初值

int result=0;// 找不到时，返回0 while(low <= high){

} return result;int mid=(low+high)/2;

//中间的数据元素 if(table->elem[mid]==key){ result=mid;break;}

//找到待查元素 else if(keyelem[mid]){ high=mid-1;}

//继续在前半区间进行查找 else { low=mid+1;}

//继续在后半区间进行查找

// 主函数

１９ int main(int argc, char* argv[]){

SSTable *table;

int r;

//元素的位置 int n;ElemType key;printf(“输入 n:”);scanf(“%d”,&n);

Create(&table, n);//建立表

cout<<“请输入”<

printf(“您输入的 %d 个值是：n”,n);

PrintTable(table);//打印无序表 cout<

printf(“顺序法查找运行结果如下：n ”);Search_Seq(table,key);//顺序（哨兵）查找算法 r=Search_Seq(table,key);

if(r>0)

printf(“ 关键字 %d 在表中的位置是： %dn”,key, r);

else

printf(“查找失败，表中无此数据。n”);

２０ Sort(table);//对无序表进行排序

printf(“数据排序后的顺序如下：n ”);PrintTable(table);//打印有序表 printf(“n”);

printf(“折半查找法运行结果如下：n ”);

r=Search_Bin(table,key);//折半查找算法 if(r>0)printf(“ 关键字 %d 在表中的位置是： %dn”,key, r);

else

{