软件技术基础复习总结1.doc

软件技术基础复习总结1第1章 数据结构1、什么是数据结构？ 数据结构是讨论计算机系统中数据的组织形式及其相互关系。 *在计算机系统中数据不仅包含了通常数值的概念，还包括将客观事物采 用计算机进行识别，存储和加工所进行的描述。2、 研究数据结构的主要内容： （1）数据元素之间的逻辑关系 （2）选用什么样的存储结构 （3）用算法效率最高的操作3、 数据结构的基本概念：通常把运用数据结构来描述数据元素之间的逻辑关系，数据在计算机系统中的存储方式和数据的运算抽象成数据结构的三个层次：数据的逻辑结构，数据的存储结构，数据操作集合。数据逻辑结构：线性结构（有且仅有一个开始数据元素和一个终点数据元素，且所有数据元素仅有一个直接前驱和一个直接后继） 非线性结构（多个直接前驱和后继）数据的存储方法：顺序存储方法、链接存储法、索引存储法、散列存储法常用的数据处理与运算：遍历、插入、更新、删除、查找、排序。4、 算法的基本概念与算法效率 一个算法必须具备有穷性、确定性，数据输入、信息输出、可行性五项基本特征。 算法效率包括时间效率和空间效率。 程序=算法+数据结构5、 线性结构：线性表、堆栈、队列、数组、串 线性结构特点是数据元素有序并有限。顺序表6、 线性表双链表单向链表线性链表 线性表循环链表7、 顺序表： 设在顺序表中每个元素占用k个存储单元，索引号为1的数据元素a1的内存地址为Loc（a1），则索引号为i的数据元素ai的内存地址为： Loc（a1）=Loc（a1）+（i+1）*k 存储地址是该元素在表中索引号的线性函数。顺序表的存储结构是一种可以随机存取数据元素的结构，这样的存储结构适合用数组表征。 由于顺序表的随机存取特性，使得顺序表中对每一个元素的存储时间都很短，并且与其位置无关。顺序表的插入和删除操作所耗费的主要时间是在移动元素上。 缺点：运算效率低，数据元素最大个数需要预先确定。8、 单向链表: 单向链表的每个数据元素都由两部分组成：存储元素值的数据域（data）和存储直接后继元素存储地址的指针域（next）。 next data 可以加头结点h 由于是以链接方式存储，所有数据元素是离散存放，可以充分利用存放空间，提高了处理速度，但需要从头节点访问。9、双链表： 双链表在单链表的基础上在节点处增加了一个指向表中每个元素的直接前驱的指针域，这样可以实现从后向前搜寻，实现双向查找 Next Prior Data 知道任一节点的指针可以访问整个链表。 已占用较大的内存空间来给计算带来方便。10、 循环链表： 单链表或双链表的最后一个节点的指针域指向头结点，形成循环链表或双向循环链表。11、 栈 仅限在一端实现线性表的插入和删除。通常称插入和删除的这一端称为栈顶，另一端称为栈底。保持后进先出的原则。 有顺序栈和链式存储结构的栈。12、 队列 只允许在线性表的一端进行数据元素的插入操作，在另一端进行数据元素的删除操作。其中，允许插入的一端称为队尾，另一端称为队头。需要两个队列指针来说明，一个队头指针，总是指向队头元素的前一个位置，另一个是队尾指针，总是指向队尾元素所在的存储位置。保持先进先出的特性 顺序队列在进行入队操作时会出现假逸现象，解决方法是采用循环队列，首尾相接。13、 栈和队列的运用 根据处理数据的需要，如果处理的数据具有FIFO（先来的先处理）特性，则用队列结构，如果具有LIFO（后来的先处理）特性，则用栈结构。 栈结构的典型运用：程序设计中子程序调用与返回的断点和现场数据的处理。递归算法14、 数组 数组中两种最基本的操作： （1）给定一组下标，找到与之相应的数据元素。 （2）给定一组下标，存取或修改与其相对应的数据元素中某个数据项的值。 数组的存储结构： （1）顺序存储结构 设每个数组元素占S个存储单元，在行优先存储中，二维数组的每个元素的存储地址可用以下公式求出： Loc（aij）=loc（a11）+（i-1）*n+（j-1）*S在列优先顺序存储中，每个元素的存储地址可用以下公式求出： Loc（aij）=loc（a11）+（j-1）*m+（i-1）*S 优点是可以方便地随机存取数组的数据元素。缺点是 （2）压缩存储结构 特殊矩阵的压缩存储: 对称矩阵，只要存储矩阵中上三角或下三角的元素，让每一对对称的元素共享一个存储空间。这样能节约一半的存储空间。这种方式同样适合三角矩阵。 稀疏矩阵，设A是一个m*n的稀疏矩阵，其中非零元素个数为I，三元存储法可采用一个（I+1）*3的T来存储A。矩阵T的第一行是m，n，I；后面的每一行对应A矩阵中的一个非零元素，如某一行为i，j，x则对应A中第i行，第j列的值为x的非零元素。15、 字符串 由零到多个字符组成的连续有限序列 一个串中任意多个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串，一个字符在串中的序号称为该