您现在的位置：希赛网 > 云阅读 > 软件设计师考试考点分析与真题详解（第4版） > 线性表
第 1 章：数据结构基础 作者：希赛教育软考学院 来源：希赛网 2015年07月13日
线性表
第1章 数据结构基础
数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为：
S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集
合。在数据结构中，结点及结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称
为数据的存储结构。
数据结构按逻辑结构的不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形
结构和图结构，而树形结构又可分为树结构和二叉树结构。
按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。
1.常用数据结构
数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、
栈、树（二叉树、查找树、平衡树、线索树、堆）、图等的定义、存储和操作。
Hash（存储地址计算，冲突处理）。
2.常用算法
排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关
算法。
算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法
的复杂性。
本章主要讨论有关数据结构的问题。
1.1 线性表
线性表是最简单、最常用的一种数据结构，它是由相同类型的结点组成的有限序列。一个由n个
结点a0,a1,…，an–1组成的线性表可记为（a0,a1,…，an–1）。线性表的结点个数为线性表的长度，
长度为0的线性表称为空表。对于非空线性表，a0是线性表的第一个结点，an–1是线性表的最后一
个结点。线性表的结点构成一个序列，对序列中两相邻结点ai和ai+1,称ai是ai+1的前驱结点，ai+1
是ai的后继结点。其中a0没有前驱结点，an–1没有后继结点。
线性表中结点之间的关系可由结点在线性表中的位置确定，通常用（ai,ai+1）（0≤i≤n–2）表
示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中
出现的顺序不同，则它们是两个不同的线性表。
线性表的结点可由若干成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了
讨论方便，往往只考虑结点的关键字，而忽略其他成分。
1.线性表的基本运算
线性表包含的结点个数可以动态增加或减少，可以在任何位置插入或删除结点。线性表常用的
运算可分成几类，每类有若干种运算。
1）查找运算
在线性表中查找具有给定键值的结点。
