数据结构课程设计-单链表.doc
《数据结构课程设计-单链表.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计-单链表.doc(12页珍藏版)》请在咨信网上搜索。
1、数据结构课程设计目录1 选题背景22 方案与论证32.1 链表的概念和作用32。3 算法的设计思想42.4 相关图例52。4。1 单链表的结点结构52。4.2 算法流程图53 实验结果63。1 链表的建立63。2 单链表的插入63。3 单链表的输出73。4 查找元素73.5 单链表的删除83。6 显示链表中的元素个数(计数)94 结果分析104。1 单链表的结构104。2 单链表的操作特点104.2。1 顺链操作技术104。2.2 指针保留技术104。3 链表处理中的相关技术105 设计体会及今后的改进意见11参考文献12附录代码:131 选题背景陈火旺院士把计算机60多年的发展成就概括为五个
2、“一:开辟一个新时代-信息时代,形成一个新产业信息产业,产生一个新科学-计算机科学与技术,开创一种新的科研方法-计算方法,开辟一种新文化计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。2 方案与论证2。1 链表的概念和作用链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存
3、储方法。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表)单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素.因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i单链表1、链接存储方法链接方式存储的线性表简称为链表(Linked List)。链表的具体存储表示为: 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) 链表中结点的逻辑次序和物理次序不一定相同
4、.为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)注意:链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构.2、链表的结点结构data next data域-存放结点值的数据域next域存放结点的直接后继的地址(位置)的指针域(链域)注意:链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的.每个结点只有一个链域的链表称为单链表(Single Linked List).3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋
5、结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。注意:链表由头指针唯一确定,单链表可以用头指针的名字来命名。终端结点无后继,故终端结点的指针域为空,即NULL.2。2 实验的基本要求(软硬件) 用VC+6.0软件平台,操作系统:Windows XP 硬件:内存要求:内存大小在256MB,其他配置一般就行。 2。3 算法的设计思想(a)定义一个创建链表的函数,通过该头插法创建一个带头结点的链表,在接下来的链表操作中使用.(b)定义输出链表的算法 ,遍历结点的指针域判断是否为空,如果不为空则输出其数据域,直到指针域为空为止。(c)定义一个遍历查找的算法,通过遍历的数据域,分别
6、与要查询的元素进行比较,如果查找到则返回并输出,如入查找失败则返回错误提示信息.(d)定义插入结点的算法,首先查找指针域为空的结点,并申请空间插入在结点的后边,并且将其指针域置空。 (e)定义删除节点的操作,这个算法用于对链表中某个多余节点的删除工作,其关键在于前驱结点的保留,查找到需删除的结点,将其删除,并将其后继结点连到其前驱结点.2。4 相关图例2。4。1 单链表的结点结构如图21所示,为单链表的结点结构示意图:Data域 Next域图2-1 单链表的结点结构2。4。2 算法流程图如图22所示,为此算法流程图: 开始定义结构体Node构建各种对链表操作的函数(插入、删除、查找、输出),并
7、写出相应的算法及实现过程创建一个单链表,用于之前所定义的函数对其进行操作按要求输出结果结束图22 算法流程图3 实验结果3。1 链表的建立图 3-1 链表的建立3。2 单链表的插入图3 2单链表的插入3.3 单链表的输出图33 输出单链表元素3。4 查找元素图3-4查找成功图3-5 查找失败3。5 单链表的删除图36 删除成功图3-6 删除失败3。6 显示链表中的元素个数(计数)图3-7输出长度4 结果分析4.1 单链表的结构 一般情况下,使用链表,只关心链表中结点间的逻辑顺序,并不关心每个结点的实际存储位置,因此通常情况下用箭头来表示链域中的指针,于是链表就可以更直观的画成用箭头链接起来的结
8、点序列,如下图所示:ABCDE H图4-1 单链表的示例图4.2 单链表的操作特点4。2。1 顺链操作技术 从“头”开始,访问单链表L中的结点i(p指向该节点)时,由于第i个结点的地址在第i-1个结点(pre指向该结点,为p的前驱)的指针域中存放,查找必须从单链表的“首结点开始(p=L);通过p=p-next并辅助计数器来实现。4。2.2 指针保留技术 通过对第i个结点进行插入、删除等操作时,需要对第i1个结点的指针域进行链址操作(pre-next),因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系,将这种技术称为“指针保留技术”。4。3 链表处理中的相关技术1)单链表与多重链表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 单链表
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。