软件技术基础复习总结1
- 格式：docx
- 大小：38.55 KB
- 文档页数：3
软件技术基础复习总结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）。
data
可以添加头节点h
next由于是以链接方式存储，所有数据元素是离散存放，可以充分利用存放空间，提高了处理速度，但需要从头节点访问。9、双链表：
在单链表的基础上，在双链表的节点上增加一个指向列表中每个元素的直接前导的指针字段，可以实现前后搜索和双向搜索
priordatanext知道任一节点的指针可以访问整个链表。已占用较大的内存空间来给计算带来方便。10、循环链表：
单链表或双链表的最后一个节点的指针字段指向头节点，形成循环链表或双向循环链表。11.堆叠
仅限在一端实现线性表的插入和删除。通常称插入和删除的这一端称为栈顶，另一端称为栈底。保持后进先出的原则。有顺序栈和链式存储结构的栈。12、队列
只允许在线性表的一端插入数据元素，在另一端删除数据元素。其中，允许插入的一端称为团队的尾部，另一端称为团队的负责人。需要两个队列指针来说明。一个是队列头指针，它总是指向队列头元素的前一个位置，另一个是队列尾指针，它总是指向队列尾元素的存储位置。保持先进先出的特性
顺序队列在进行入队操作时会出现假逸现象，解决方法是采用循环队列，首尾相接。
13.堆栈和队列的应用
根据处理数据的需要，如果处理的数据具有fifo（先来的先处理）特性，则用队列结构，如果具有lifo（后来的先处理）特性，则用栈结构。栈结构的典型运用：程序设计中子程序调用与返回的断点和现场数据的处理。递归算法14、数组
阵列中有两个基本操作：
（1）给定一组下标，找到与之相应的数据元素。
（2） 给定一组下标，访问或修改相应数据元素中数据项的值。 数组的存储结构：（1）顺序存储结构
让每个阵列元素占用每个阵列的存储单元。在行首存储中，二维数组中每个元素的存储地址可以通过以下公式计算：
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、字符串
由零到多个字符组成的连续有限序列
一个串中任意多个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串，一个字符在串中的序号称为该字符在串中的位置。当一个字符在串中多次出现时，该字符在串中的位置指的是该字符在串中第一次出现的位置。子串在主串中的位置指的是该子串的第一个字符在主串中的位置。称两个串是相等的即是指两个串中的字符序列一一对应相等。
