专题九：数据结构知识.doc
25墨值下载
软件设计师(原高级程序员)复习资料
专题九：数据结构知识
数据结构是计算机软件的一门基础课程计算机科学各个领域及有关的应用软件都要用到各种数据结构．
语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、
多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，
如广义表、集合、搜索树及各种有向图等等。学习数据结构目的是要熟悉一些最常用的数据结构，明确数据结
构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态
性质及实际的执行算法，进一步提高软件计和编程水平。通过对不同存储结构和相应算法的对比，增强我们根
据求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。
软件设计师考试大纲对数据结构部分的要求是熟练掌握常用数据结构和常用算法，因此，本专题从数据结
构的概述出发，对基本的概念引出常用的数据结构类型的介绍和讲解，同时在讲解各种数据结构中间采用算法
与数据结构相结合的方式，在算法步骤中使用数据结构，对数据结构的重点、难点进行了分析，最后讲解了与
数据结构紧密相关的排序和查找算法，以及一些以往考试题的分析。
1.
数据结构概述
数据结构研究了计算机需要处理的数据对象和对象之间的关系；刻画了应用中涉及到的数据的逻辑组
织；也描述了数据在计算机中如何存储、传送、转换。
学习数据结构注意的问题：
系统掌握基本数据结构的特点及其不同实现。
了解并掌握各种数据结构上主要操作的实现及其性能（时间、空间）的分析。
掌握各种数据结构的使用特性，在算法设计中能够进行选择。
掌握常用的递归、回溯、迭代、递推等方法的设计
掌握自顶向下、逐步求精的程序设计方法。
掌握自顶向下、逐步求精的程序设计方法。
在学习数据结构的知识之前，我们要了解一下数据结构中的基本概念。
数据：对客观事物的符号表示，在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总
称。
数据项： 是数据的不可分割的最小单位；
数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项
组成。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
数据结构上的基本操作： ◆插入操作 ◆删除操作 ◆更新操作 ◆查找操作 ◆排序操作
数据结构是指数据对象及相互关系和构造方法，一个数据结构 形式上可以用一个二元组表示为
（，）。其中， 是数据结构中的数据（称为结点）的非空有限集合， 是定义在 上的关系的非
空有限集合。
根据数据元素之间的关系的不同特性，通常有下列 类基本结构。
集合——结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系。
线性结构——结构中的数据元素之间存在一个对一个的关系。
树形结构——结构中的元素之间存在一个对多个的关系。
图状结构或网状结构——结构中的元素之间存在多个对多个的关系。
数据结构中，结点与结点间的相互关系是数据的逻辑结构。数据结构在计算机中的表示（又称为映
象）称为数据的物理结构，也称存储结构。
数据元素之间的关系在计算机中有两种不同的表示方式：顺序映象和非顺序映象，并由此得到两种不
同的存储结构：顺序存储结构和链式存储结构。
任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。
数据的逻辑结构分为两类：
线性结构：线性表、栈、队列和串
非线性结构：树、图
数据的存储方法有四类：
顺序存储方法
链接存储方法
索引存储方法
散列存储方法
2.
常用数据结构
2.1
线性表
共 25 页 第 页
1
软件设计师(原高级程序员)复习资料
在数据结构中，线性结构常称为线性表，是最简单、最常用的一种数据结构，它是由 个相同数据类型
的结点组成的有限序列。
其特点是：在数据元素的非空有限集合中，
◆存在唯一的一个被称做“第一个”的数据元素
◆存在唯一的一个被称做“最后一个”的元素数据元素
◆除第一个之外，集合中的每个数据元素均只有一个前驱
◆除最后一个之外，集合中每个数据元素均只有一个后继
一个由 个结点 ，， 组成的线性表记为：（，，）。线性表的结点个数称为
线性表的长度，长度为 的线性表称为空的线性表，简称空表。对于非空线性表， 是线性表的第一个
结点，
是线性表的最后一个结点。线性表的结点构成了一个序列，对序列中两个相邻结点
和
，
称前者是后者的前驱结点，后者是前者的后继结点。
线性表最重要的性质是线性表中结点和相对位置是确定的。
线性表的结点也称为表元，或称为记录，要求线性表的结点一定是同一类型的数据。线性表的结点可
由若干个成分组成，其中唯一标识表元的成分成为关键字，简称键。
线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。对线性表的基本运算如下：
（）初始化操作
（） 求长度函数
（，） 取元素函数
（，）求前驱函数
（，） 求后继函数
（，） 定位函数
（，，）插入操作
（，） 删除操作
有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。根据存储方式的
不同，其上述的运算实现也不一样。
◆ 顺序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使
用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。
顺序存储方式优点：能直接访问线性表中的任意结点。
线性表的第 个元素 !的存储位置可以使用以下公式求得： （
）（）"（）#
式中 （）是线性表的第一个数据元素 的存储位置，通常称做线性表的起始位置或基地址。
顺序存储的缺点：
$ 线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；
执行线性表的插入和删除操作要移动其他元素，不够方便；
◆链式存储
线性表链接存储是用链表来存储线性表。
单链表（线性链表）：
从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除要存储线
性表结点的信息以外，还要有一个成分来存储其后继结点的指针。
线性链表的特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一
个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值；链表非空时，头指针指向第一
个节点。
链式存储的缺点：
$ 由于要存储地址指针，所以浪费空间；
直接访问节点不方便；
循环链表：
循环链表是另一种形式的链式存储结构，是单链表的变形。它的特点就是表中最后一个结点的指针域
指向头结点，整个链表形成一个环。因此，从表中任意一个结点出发都可以找到表中的其他结点。
循环链表和单向链表基本一致，差别仅在于算法中循环的条件不是结点的指针是否为空，而是他们的
指针是否等于头指针，
循环链表最后一个结点的 link 指针不为 %&NULL$，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例：
带表头结点的循环链表 ：
共 25 页 第 页
2
of 25
25墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论