数据结构简明教程

所需积分/C币:38 2018-12-02 12:15:47 42.24MB PDF
收藏 收藏 6
举报

李春葆主编 【参考文献格式】 李春葆主编. 数据结构简明教程. 北京:清华大学出版社, 2014.01. 内容提要: 本书内容包括概论、线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序。
高等学校数据结构课程系列教材 数据结构简明教程 李春葆主编 方颖喻丹丹曾平编著 清华大学出版社 北京 内容简介 本书内容包括概论、线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序,附录中给出 书中部分算法清单、全国计算机专业数据结构2013年联考大纲、部分练习题的参考答案。 本书具有概念清楚、表述明晰、示例丰富、图示准确和内容完整的特点。 本书可用作高等院校计算机及相关专业本、专科生数据结构课程的教材,也适合计算机爱好者和参加 各类计算机考试人员研习。 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:010-6278298913701121933 图书在版编目(CIP)数据 数据结构简明教程/李春葆主编.一北京:清华大学出版社,2014 (高等学校数据结构课程系列教材) ISBN978-7-302-33618-1 Ⅰ.①数…Ⅱ.①李…Ⅲ.①数据结构一教材②C语言一程序设计一教材Ⅳ:①TP311.12 ②TP312 中国版本图书馆CIP数据核字(2013)第203882号 责任编辑:魏江江薛阳 封面设计:杨兮 责任校对:梁毅 责任印制:何芊 出版发行:清华大学出版社 网址http://www.tup.com.cn,http://www.wqbook.com 地址:北京清华大学学研大厦A座 邮编:100084 社总机:010-62770175 邮购:010-62786544 投稿与读者服务:010-62776969,c-service@tup.tsinghua.edu.cn 质量反馈:010-62772015,zhiliang@atup.tsinghua.edu.cn 课件下载:htbp://www.tup.com.cn,010-62795954 印装者:北京鑫丰华彩印有限公司 经销:全国新华书店 开本:185mm×260mm 印张:21 字数:526千字 版次:2014年1月第1版 印次:2014年1月第1次印刷 印数:1~2000 定价:34.50元 产品编号:054581-01 F INTRODUCTION 出版说明 随着国家信息化步伐的加快和高等教育规模的扩大,社会对计算机专业 人才的需求不仅体现在数量的增加上,而且体现在质量要求的提高上,培养 具有研究和实践能力的高层次的计算机专业人才已成为许多重点大学计算 机专业教育的主要目标。目前,我国共有16个国家重点学科、20个博士点一 级学科、28个博士点二级学科集中在教育部部属重点大学,这些高校在计算 机教学和科研方面具有一定优势,并且大多以国际著名大学计算机教育为参 照系,具有系统完善的教学课程体系、教学实验体系、教学质量保证体系和人 才培养评估体系等综合体系,形成了培养一流人才的教学和科研环境。 重点大学计算机学科的教学与科研氛围是培养一流计算机人才的基 础,其中专业教材的使用和建设则是这种氛围的重要组成部分,一批具有 学科方向特色优势的计算机专业教材作为各重点大学的重点建设项目成 果得到肯定。为了展示和发扬各重点大学在计算机专业教育上的优势,特 别是专业教材建设上的优势,同时配合各重点大学的计算机学科建设和专 业课程教学需要,在教育部相关教学指导委员会专家的建议和各重点大学 的大力支持下,清华大学出版社规划并出版本系列教材。本系列教材的建 设旨在“汇聚学科精英、引领学科建设、培育专业英才”,同时以教材示范各 重点大学的优秀教学理念、教学方法、教学手段和教学内容等。 本系列教材在规划过程中体现了如下一些基本组织原则和特点。 1.面向学科发展的前沿,适应当前社会对计算机专业高级人才的培养需 求。教材内容以基本理论为基础,反映基本理论和原理的综合应用,重视实 践和应用环节。 2.反映教学需要,促进教学发展。教材要能适应多样化的教学需要,正 确把握教茡内容和课程体系的改革方向。在选择教材内容和编写体系时注 意体现素质教育、创新能力与实践能力的培养,为学生知识、能力、素质协调 发展创造条件。 3.实施精品战略,突出重点,保证质量。规划教材建设的重点依然是专 业基础课和专业主干课;特别注意选择并安排了一部分原来基础比较好的优 秀教材或讲义修订再版,逐步形成精品教材;提倡并鼓励编写体现重点大学 数据结构简明教程 计算机专业教学内容和课程体系改革成果的教材。 4.主张一纲多本,合理配套。专业基础课和专业主干课教材要配套,同一门课程可以 有多本具有不同内容特点的教材。处理好教材统一性与多样化的关系;基本教材与辅助教 材以及教学参考书的关系;文字教材与软件教材的关系,实现教材系列资源配套。 5.依靠专家,择优落实。在制订教材规划时要依靠各课程专家在调查硏究本课程教材 建设现状的基础上提出规划选题。在落实主编人选时,要引入竞争机制,通过申报、评审确 定主编。书稿完成后要认真实行审稿程序,确保出书质量。 繁荣教材出版事业,提高教材质量的关键是教师。建立一支高水平的以老带新的教材 编写队伍才能保证教材的编写质量,希望有志于教材建设的教师能够加入到我们的编写队 伍中来。 教材编委会 FOREWORD 前言 用计算机解决实际问题时,必然涉及数据的组织及数据的处理,而数据 组织及数据处理正是数据结构课程的主要学习内容。 数据结构课程在计算机科学中是一门综合性的专业基础课。在计算机 科学中,数据结构内容不仅作为一般程序设计的必备知识,而且是设计编译 程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 数据结构的主要研究内容有:数据的逻辑结构描述即表示求解问题中的 数据和数据元素之间的逻辑关系;数据的存储结构设计即将数据逻辑结构在 计算机内存中表示;运算算法设计即实现求解问题的功能,如设计插入、删 除、修改、查询和排序算法等。 很多学习数据结构课程的学生都感觉数据结构比较抽象,算法理解比较 困难,这很大程度上是因为没有领会数据结构的特点造成的。首先,一个学 习计算机专业的学生必须具有某种计算机语言编程能力,能够将求解问题的 思路转换成计算机可以执行的程序代码,会编写基本的程序就像一个小学生 识字和掌握基本的词汇一样重要;其次,必须掌握用计算机求解问题的三个 层次,即提取求解问题中数据的逻辑结构、设计相应的存储结构和在存储结 构上实现求解问题的算法。在设计一个算法时,先要充分理解相关的存储结 构,试想一下,个图的邻接表存储结构还没有弄清楚,如何设计一个图的遍 历算法呢?所以在写算法时脑海里要准确地呈现数据的存储结构,这样才会 下笔有“神”,流畅地写出正确的代码,如同小学生在掌握相当的词汇和写作 技巧后才会写出高质量的作文。 本书是作者针对数据结构课程的特点,在总结长期教学经验的基础上编 写的,本书的“简明”性主要体现在两个方面。 一是内容上的简明性,本书内容涵盖了最新全国计算机专业联考大纲 (2013年)数据结构部分的知识点,省去了一些难度较大的应用和扩展内容, 如栈和队列中求表达式值和迷宫问题、串的KMP算法和广义表等。 二是写作上的简明性,作者在写作时遵循“简洁如 iPhone”的风格,具体体 现在以下几个方面 閡据结构简明教程 力求实现从CC++语言程序设计到数据结构算法设计的无缝对接,对算法设计中用 到的一些C++语言难点如指针、引用类型等,结合算法设计的特点予以充分地 讲述。 通过通俗易懂的示例简单明了地讲解数据结构解决问题的一般性思路,如一些综合 性示例统一从问题描述、设计存储结构、设计基本运算算法、设计主程序和程序运行 结果几方面来讲解,突出数据结构求解问题的三个层次。 采用大量图示描述算法设计的思路,如求最小生成树的Pim算法、求图中最短路径 的0 Dijkstra算法和各种内排序算法中都通过直观的图示,不仅描述这些算法的设计 思路,而且讲解这些算法为什么这样设计的精髓 ·注重算法设计的简洁和易懂特性,同一种算法可以有多种设计方法,本书中尽可能 采用简单的设计方法,如二叉排序树查找、删除等都用非递归算法来实现。 ·力求归纳数据结构算法设计的通用性方法,如单链表算法设计、递归算法设计、二叉 树的算法设计和图算法设计等,都相应地总结出通用求解的方法,读者只要灵活运 用这些通用方法,便可以举一反三自己设计求解较复杂问题的算法。 ·书中所有算法都用C++语言编写并上机调试,并配套有较完整的教学资源(含PPT 源程序、练习题参考答案、相关试题等),读者可以从清华大学出版社网站http://w tup. edu.cn免费下载,对于学习计算机专业的学生,直接阅读程序代码可能比看“伪 码”更简明。 全书分为9章,第1章为概论,介绍数据结构的基本概念,特别强调基本算法设计和分 析的方法;第2章为线性表,介绍线性表的概念、两种存储结构即顺序表和链表,线性表基 本运算的实现算法以及线性表的应用;第3章为栈和队列,介绍这两种特殊线性表的概念、 存储结构和相关应用;第4章为串,介绍串的概念、串的两种存储结构和应用;第5章为数 组和稀疏矩阵,介绍数组的概念,几种特殊矩阵的压缩方法,稀疏矩阵的定义和压缩存储结 构;第6章为树和二叉树,介绍树的概念和性质,二叉树的概念,二叉树的两种主要存储结 构,二叉树各种运算算法设计,哈夫曼树和哈夫曼编码,特别突出二叉树递归算法设计方法; 第7章为图,介绍图的概念、图的两种主要存储结构、图遍历算法以及图的各类应用;第8章 为查找,介绍各种查找算法的实现过程;第9章为排序,介绍各种主要的内排序算法设计方 法和基本的外排序过程。附录A给出了书中部分算法清单,附录B给出了全国计算机专业 数据结构2013年联考大纲,附录C给出书中每章的选择题和填空题的参考答案。 本书适合作为计算机及相关专业本科生“数据结构”课程的教材,也适合于各类计算机 考试人员参考。 本书的编写得到湖北省教育改革项目“计算机科学与技术专业课程体系改革”的资助, 清华大学出版社魏江江主任给予了大力支持,编者在此一并表示衷心感谢。 由于水平所限,尽管编者不遗余力,书中仍可能存在疏漏和不足之处,编者的邮箱为 licb1964@126.c0m,欢迎读者联系并批评指正 编者 2013年2月 CONTENT S 目录 第1章概论 1.1数据结构概述…… 1.1.1什么是数据结构…… 1.1.2逻辑结构…… 1.1.3存储结构 1.1.4数据运算 1.1.5数据结构、数据类型和抽象数据类型 1.2算法和算法分析 1.2.1算法及其描述 ::E::::aa:::::::a11:::::E:1::,图 1.2.2算法分析 ……14 1.3数据结构程序设计…………………………………………………………………………17 1.3.1数据结构程序设计步骤………………………………………………17 1.3.2应用程序的结构 ……18 小结……………………………………………………………………………………………20 练习题1… ::··:::::「*··:,·······:··················“·············+······“·“·“+··““ 21 上机实验题1 23 第2章线性表 24 2.1线性表的基本概念……………………………………………………24 2.1.1线性表的定义…… 24 2.1.2线性表的基本运算 25 2.2顺序表 t面音面a世世出当B吾鲁吾.甲.中·甲··着·:·,,自·,,.·,.,,·,·,.·「 26 2.2.1顺序表的定义 ““““; 面1重 ·.:·:·:““·““·:·· 26 2.2.2线性表基本运算在顺序表上的实现………………………27 2.2.3顺序表的插入和删除算法分析…………………………………30 2.2.4顺序表的应用示例 31 2.3单链表 ………33 Ⅵ 数据结构简明教程 2.3.1单链表的定义………………………………………………………33 2.3.2线性表基本运算在单链表上的实现 35 2.3.3循环单链表……………………………………………………48 2.4双链表………………………………… 54 2.4.1双链表的定义… ………………54 2.4.2线性表基本运算在双链表上的实现…… 2.4.3循环双链表 62 2.5线性表的应用 “··::..:aa …………………………………………67 25.1设计线性表应用程序的一般步骤 67 2.5.2线性表应用示例… 67 小结 果审,非排鲁申,·, 练习题2……… 72 上机实验题2 ,,,,,,,,,图!「,,B。虚「自1n,非1菲日4着目非福和(干着和,画 第3章栈和队列 75 3.1栈 国和和,看 …75 3.1.1栈的基本概念 …75 3.1.2栈的顺序存储结构…… 76 3.1.3栈的链式存储结构 80 3.1.4栈的应用示例……………………………………………………………………83 2队列……………………… ……………………85 3.2.1队列的基本概念……………………………………………………85 3.2.2队列的顺序存储结构………… 87 3.2.3队列的链式存储结构…… 92 3.2.4队列的应用示例………………………………………………………97 小结…………………………………………………………………………………101 练习题3 ·““““+““““;“+;““““““·“#“·“““““;“#“;4“;;;;;日“#;;,日;#;“ 101 上机实验题3 103 第4章串…………… 105 4.1串的基本概念………… .::·:·:“::·a·:··::· 和甲· ………………………105 4.1.1串的定义 ……………105 4.1.2线性表的基本运算…………………………,…………………106 4.2串的顺序存储结构 106 4.2.1顺序串的定义 106 4.2.2串基本运算在顺序串上的实现……………………………106 4,3串的链式存储结构 ………………………………………………112 4.3.1链串的定义………………………………………………………112 4.3.2串基本运算在链串上的实现… 113

...展开详情
试读 127P 数据结构简明教程
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 签到新秀

      累计签到获取,不积跬步,无以至千里,继续坚持!
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    数据结构简明教程 38积分/C币 立即下载
    1/127
    数据结构简明教程第1页
    数据结构简明教程第2页
    数据结构简明教程第3页
    数据结构简明教程第4页
    数据结构简明教程第5页
    数据结构简明教程第6页
    数据结构简明教程第7页
    数据结构简明教程第8页
    数据结构简明教程第9页
    数据结构简明教程第10页
    数据结构简明教程第11页
    数据结构简明教程第12页
    数据结构简明教程第13页
    数据结构简明教程第14页
    数据结构简明教程第15页
    数据结构简明教程第16页
    数据结构简明教程第17页
    数据结构简明教程第18页
    数据结构简明教程第19页
    数据结构简明教程第20页

    试读已结束,剩余107页未读...

    38积分/C币 立即下载 >