[从业资格考试]2软件基础知识.doc

2.1 数据结构基础 2.1.1 主要知识点 掌握线情表、多维数组、阵列、栈、树、二叉树，图的定义、存储和操作以及常见的排序和查找算法。重点是二叉树和图以及与其相关的算法。 2.1.1.1 数据结构概述 数据结构是指数据对象及其相互关系和构造方法，一个数据结构B形式上可以用一个二元组表示为B=(A，R)。其中，A是数据结构中的数据(称为结点)的非空有限集合，R是定义在A上的关系的非空有限集合。数据结构按逻辑关系的不同分为线性结构和非线性结构两大为，共中非线性结构又可分为树形结构和图结构，树形结构又可分为树结构和二叉树结构。2.1.2 线性表 数据结构中，线性结构习惯称为线性表。线性表是最简单也是最常用的一咱数据结构，它是由相同类型的结点组成的有限序列。一个由n个结点e0，e1，…en-1组成的线性表记为(e0，e1，…en-1)。线性表的结点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一个结点，en-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两个相邻结点ei-1和ei，称前者是后者的前驱结点，后者是前者的后继结点。线性表最重要的性质是线性表中结点的相对位置是确定的。 线性表的结点也称为表元，或称记录，要求线性表的结点是同一类型的任何数据。线性表的结点可由若干个成分组成，其中能唯一标识表元的成分称为了，简称键。线性表包含的表元个数可以动态增加或减少，可以在任何位置插入或删除表元。 线性表常用的运算可分成4类：查找运算、插入运算、删除运算和其他运算。每类又包括若干种运算。如查找运算就有两种，一种是查找线性表中某个结点的值，另一种是在线性表中查找具有给定键值的记录。 有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。 (1)线性表的顺序存储 线性表的顺序存储是最简单的存储方式。程序通常使用一个足够在的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。用数组元素的顺序存储来体现线性表中结点的先后次序关系。其最大优点是能直接访问线性表中的任意一个结点。 (2)线性表的链接存储 用单链表存储线性表是线性表的链接方存储方式。从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除了要存储线性表结点的信息外，还要有一个成分用来存储其后继结点的指针。 2.1.1.3 栈和队列 栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另 一端为栈底。若有栈S=(s0，s1，…，sn-1)，则s0为栈底结点，sn-1为栈顶结点。习惯称插入栈的结点为进栈，删除栈的结点为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的的特性。可以用顺序存储线性表来表示栈，栈也可以用链表实现，用链表实现的栈称为链接栈。 队列是只允许在一端进入插入，另一端进行删除运算的线性表。允许删除运算的一端称为队首，允许插入运算的端为队尾。习惯称插入队列结点为进队，删除队列结点为出队。若有队列Q=(q0，q1，…，qn-1)q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出 队，所以队列具有先进先出的特性。可以用顺序存储线性表来表示队列，也可以用链表实现，用链表实现的栈称为链接队列。 2.1.1.4 数组和字符串 数组是最常用的数据结构之一，一般用来顺序存储线性表。数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，数组元素的下标个数称为数组的维数。在C语言中，约定数组的第1个元素的下标为0，其余依次类推，由n个元素组成的数组，其最后一个元素的下标为n-1。数组元素可以是任何类型的，当元素本身又是数组时，就构成多维数组。 多维数组是一维数组的推广，多维数组中最常用的是二维数组。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的数组元素排在一个线性序列里，常用的排列次序有行优先顺序和列优先顺序两种。对于多维数组，C语言按行优先顺序存放。 字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。不包含任何字符的字符串称为空字符串。字符串所包含的有效字符数称为字符串长度。一个字符串中任意连续的子序列称为该字符串的子串。 2.1.1.5 树 树和二叉树是非线性数据结构，用它们能很好地描述有分支和层次特性的数据集合。习惯称树和二叉树数据结构为树形结构。在许多算法中，都经常使用树形结构描述问题的求解过程或表示求解的对策等。由于二叉树有确定的分支个数，又可以为空，有良好的递归性质，与一般树相比较，特别适宜于程序设计，因此也常将树转换成二叉树进行