软件设计师 http://www.educity.cn/jiaocheng/zg7.html
软件设计师考试考点分析与真题详解（第4版）
第 1 章 数据结构基础
数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为：S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点及结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。
数据结构按逻辑结构的不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。
按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。 1.常用数据结构
数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树、平衡树、线索树、堆）、图等的定义、存储和操作。 Hash（存储地址计算，冲突处理）。 2.常用算法
排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关算法。
算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性。
本章主要讨论有关数据结构的问题。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
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）查找运算
在线性表中查找具有给定键值的结点。 2）插入运算
在线性表的第i（0≤i≤n–1）个结点的前面或后面插入一个新结点。 3）删除运算
删除线性表的第i（0≤i≤n –1）个结点。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
4）其他运算
统计线性表中结点的个数； 输出线性表各结点的值； 复制线性表； 线性表分拆； 线性表合并； 线性表排序；
按某种规则整理线性表。 2.线性表的存储
线性表常用的存储方式有顺序存储和链接存储。 1）顺序存储
顺序存储是最简单的存储方式，通常用一个数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中，即线性表的第i个结点存储在数组的第i（0≤i≤n–1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。
顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点，缺点主要有两个，一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。 2）链接存储
链接存储是用链表存储线性表（链表），最简单的是用单向链表，即从链表的第一个结点开始，将线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息，还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
点的先后次序关系。
链表存储线性表的优点是线性表中每个结点的实际存储位置是任意的，这给线性表的插入和删除操作带来了方便，只要改变链表有关结点的后继指针就能完成插入或删除的操作，不需移动任何表元。链表存储方式的缺点主要有两个，一是每个结点增加了一个后继指针成分，要花费更多的存储空间；二是不便随机访问线性表的任一结点。 3.线性表上的查找
线性表上的查找运算是指在线性表中找某个键值的结点。根据线性表中的存储形式和线性表本身的性质差异，有多种查找算法，例如顺序查找、二分法查找、分块查找、散列查找等。其中二分法查找要求线性表是一个有序序列。 4.在线性表中插入新结点 1）顺序存储
设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。完成插入主要有以下步骤： 检查插入要求的有关参数的合理性；
把原来的第n–1个结点至第i个结点依次往后移一个数组元素位置； 把新结点放在第i个位置上； 修正线性表的结点个数。
在具有n个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，则在顺序存储线性表中插入一个新结点，平均移动次数为n/2. 2）链接存储
在链接存储线性表中插入一个键值为x的新结点，分为以下4种情况：
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
在某指针p所指结点之后插入；
插在首结点之前，使待插入结点成为新的首结点； 接在线性表的末尾；
在有序链表中插入，使新的线性表仍然有序。 5.删除线性表的结点 1）顺序存储
在有n个结点的线性表中，删除第i（0≤i≤n–1）个结点。删除时应将第i+1个结点至第n–1个结点依次向前移一个数组元素位置，共移动n–i–1个结点。完成删除主要有以下几个步骤：
检查删除要求的有关参数的合理性；
把原来第i+1个表元至第n–1个结点依次向前移一个数组元素位置； 修正线性表表元个数。
在具有n个结点的线性表上删除结点，其时间主要花费在移动表元的循环上。若删除任一表元的概率相等，则在顺序存储线性表中删除一个结点，平均移动次数为（n-1）/2. 2）链接存储
对于链表上删除指定值结点的删除运算，需考虑几种情况，一是链表为空链表，不执行删除操作；二是要删除的结点恰为链表的首结点，应将链表头指针改为指向原首结点的后继指点；其他情况，先要在链表中寻找要删除的结点，从链表首结点开始顺序寻找。若找到，执行删除操作，若直至链表末尾没有指定值的结点，则不执行删除操作。完成删除由以下几个步骤组成：
如链表为空链表，则不执行删除操作；