数据结构导论

章节摘录

插图：第1章 概 论用数字式计算机解决任何问题都离不开程序设计。程序设计的实质是数据表示和数据处理，而这种表示和处理应通过一个渐进的过程逐步完成。数据结构课程主要讨论这个过程中的一些基本问题。本章将概括地介绍有关的基本概念、基本思想、基本原理及实际背景。1.1 引 言今日世界，能被计算机解决的问题种类繁多，确实达到了令人眼花缭乱的地步。然而，说到底，用数字式计算机解决问题的实质是对数据的加工处理。“数据”是计算机加工处理的对象，没有数据，计算机解题就变成“无米之炊”。但是，数据要能被计算机加工处理，首先必须能够存储在机器中，成为能被机器直接操作的对象。数据在计算机存储器中的这种存在形式称为机内表示。显然，数据的机内表示与数据在现实生活和实际问题中的表现形式（姑且称为“机外表示”）是不同的。因此，为了让计算机去加工处理数据，必须首先将数据从机外表示转化为机内表示。这项任务称为数据表示。另外，一个实际问题通常不仅包括数据，还包括处理要求。因此仅仅把数据转化为机内表示并不能完全解决问题，还要用适当的可执行语句编制程序，以便让计算机去执行对数据机内表示的各种操作，从而实现处理要求，即得到所需的结果。这项工作称为数据处理。因此，对计算机专业人员来说，无论面对的具体问题是什么，必须完成的两项基本任务是：数据表示和数据处理。下面用一个简单的例子来说明这两项任务。【例1-1】 考虑某单位职工档案管理问题。为了简单起见，假定每个职工的档案只包括以下五个项目：工作证号码、姓名、性别、出生日期和职称。一般地说，档案管理人员很可能将这些档案组织成表格形式，如图1-1所示。表中每一行反映了一个职工五个方面的情况，在本例的假设下构成一个职工的档案。由所有职工的档案组成的这张表格就是本问题中的数据。

前言

当您开始阅读本书时，人类已经迈入了二十一世纪。这是一个变幻难测的世纪，这是一个催人奋进的时代。科学技术飞速发展，知识更替日新月异。希望、困惑、机遇、挑战，随时随地都有可能出现在每一个社会成员的生活之中。抓住机遇，寻求发展，迎接挑战，适应变化的制胜法宝就是学习——依靠自己学习、终生学习。作为我国高等教育组成部分的自学考试，其职责就是在高等教育这个水平上倡导自学、鼓励自学、帮助自学、推动自学，为每一个自学者铺就成才之路。组织编写供读者学习的教材就是履行这个职责的重要环节。毫无疑问，这种教材应当适合自学，应当有利于学习者掌握、了解新知识、新信息，有利于学习者增强创新意识、培养实践能力、形成自学能力，也有利于学习者学以致用、解决实际工作中所遇到的问题。具有如此特点的书，我们虽然沿用了“教材”这个概念，但它与那种仅供教师讲、学生听，教师不讲、学生不懂，以“教”为中心的教科书相比，已经在内容安排、形式体例、行文风格等方面都大不相同了。希望读者对此有所了解，以便从一开始就树立起依靠自己学习的坚定信念，不断探索适合自己的学习方法，充分利用已有的知识基础和实际工作经验，最大限度地发挥自己的潜能，以达到学习的目标。欢迎读者提出意见和建议。祝每一位读者自学成功。

后记

本大纲是根据全国高等教育自学考试指导委员会电子电工与信息类专业委员会制定的“高等教育自学考试计算机及应用专业（专科）考试计划”和全国高等教育自学考试指导委员会《关于修订高等教育自学考试课程自学考试大纲的几点意见》的精神制定的。本大纲提出初稿后，曾聘请专家通审，并由电子电工与信息类专业委员会在合肥市组织召开审稿会进行审稿，根据审稿会意见由编者做了修改。最后由电子电工与信息类专业委员会定稿。本大纲由陈小平副教授（中国科技大学）负责编写和修改。参加审稿并提出修改意见的有金志权教授（南京大学，主审）、赵保华教授（中国科技大学，参审）、谢荣传教授（安徽大学，参审）。对参加本大纲编写和审稿的教授表示感谢。

书籍目录

第1章 概论1.1 引言1.2 数据、逻辑结构和运算1.2.1 数据元素和数据项1.2.2 数据的逻辑结构1.2.3 运算和基本运算1.3 存储实现和运算实现1.3.1 存储实现1.3.2 运算实现1.4 算法分析1.5 数据结构及其评价和选择1.5.1 数据结构1.5.2 数据结构的评价和选择小结习题第2章 线性表2.1 线性表的基本概念2.1.1 线性结构2.1.2 线性表2.2 线性表的顺序实现2.2.1 顺序表2.2.2 基本运算在顺序表上的实现2.2.3 顺序实现的算法分析2.3 线性表的链接实现2.3.1 单链表2.3.2 单链表的简单操作2.3.3 基本运算在单链表上的实现2.4 其它运算在单链表上的实现2.4.1 建表2.4.2 清除重复结点2.5 其它链表2.5.1 循环链表2.5.2 双链表2.6 顺序实现与链接实现的比较2.6.1 空间性能的比较2.6.2 时间性能的比较2.7 串2.7.1 串的基本概念2.7.2 串的基本运算2.7.3 串的存储小结习题第3章 栈、队列和数组3.1 栈3.1.1 栈的基本概念3.1.2 栈的顺序实现3.1.3 栈的链接实现3.1.4 举例3.1.5 栈的简单应用和递归3.2 队列3.2.1 队列的基本概念3.2.2 队列的顺序实现3.2.3 队列的链接实现3.2.4 举例3.3 数组3.3.1 数组的逻辑结构和运算3.3.2 数组的存储结构3.3.3 矩阵的压缩存储3.4 综合应用示例小结习题第4章 树4.1 树的基本概念4.2 二叉树4.2.1 二叉树的基本概念4.2.2 二叉树的性质4.3 二叉树的存储结构4.3.1 二叉树的链式存储结构4.3.2 二叉树的顺序存储结构4.4 二叉树的遍历4.5 递归消除4.5.1 简单递归消除4.5.2 基于栈的递归消除4.6 树和林4.6.1 树的存储结构4.6.2 树的遍历4.6.3 树、林与二叉树的关系4.7 判定树和哈夫曼树4.7.1 分类与判定树4.7.2 哈夫曼树与哈夫曼算法小结习题第5章 图5.1 图的基本概念5.1.1 图的实际背景5.1.2 图的定义和术语5.2 图的存储结构5.2.1 邻接矩阵5.2.2 邻接表5.3 图的遍历5。3.1 连通图的深度优先搜索5.3.2 连通图的广度优先搜索5.3.3 图的连通分量计算5.4 最小生成树5.5 拓扑排序小结习题第6章 查找表6.1 基本概念6.1.1 集合的基本概念6.1.2 查找表的基本概念6.2 静态查找表的实现6.2.1 顺序表上的查找6.2.2 有序表上的查找6.2.3 索引顺序表上的查找6.3 树表6.3.1 二叉排序树6.3.2 平衡二叉排序树6.4 散列表6.4.1 散列函数的构造法6.4.2 动态查找表在开散列表上的实现6.4.3 动态查找表在闭散列表上的实现6.4.4 开散列表与闭散列表的比较小结习题第7章 文件7.1 基本概念7.1.1 文件结构7.1.2 外存储器简介7.2 顺序文件7.3 索引文件7.4 ISAM文件7.5 VSAM文件7.6 散列文件7.7 多关键字文件7.7.1 多重表文件7.7.2 倒排文件小结习题第8章 排序8.1 概述8.2 插入排序8.3 交换排序8.3.1 冒泡排序8.3.2 快速排序8.4 选择排序8.4.1 直接选择排序8.4.2 堆排序8.5 归并排序8.5.1 有序序列的合并8.5.2 二路归并排序8.6 外排简介小结习题参考文献数据结构导论自学考试大纲出版前言一、课程的性质与设置目的二、课程内容与考核目标第1章 概论第2章 线性表第3章 栈、队列和数组第4章 树第5章 图第6章 查找表第7章 文件第8章 排序三、有关说明与实施要求附录 题型举例后记

编辑推荐

《数据结构导论》：全高国等教育自学考试指定教材·计算机及应用专业(专科)

作者简介

《数据结构导论》系统地介绍了各种常用的数据结构，对基本概念、基本原理和基本方法做了深入浅出的介绍，对有关的算法设计做了详细和通俗的讲解，并对有关背景做了适当交待。每章附带小结和适量的习题。上述特点使《数据结构导论》特别适合于自学。

《数据结构导论》可供计算机及其应用专业自学考试学生及专业人员使用，也可作为高等院校数据结构课程的教科书或参考书。

图书封面

---

 数据结构导论下载

---