数据结构
第一章:绪论
1.1数据结构的基本概念
1.数据:数据是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。
2.数据元素:数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。
3.数据对象:数据对象是具有相同性值的数据元素的集合,是数据的一个子集。
4.数据类型:数据类型是一个值的集合和定义再此集合上的一组操作的总称。
- 考纲
- O1:数据结构与算法的概述
- 识记:运算的概念、存储结构和运算实现、算法分析
- 掌握:数据、数据元素、数据项、数据类型、数据结构、抽象数据类型
- O1:数据结构与算法的概述
1. 数据:**描述客观事物的数和字符的集合**。 2. 数据元素:数据元素是数据的**基本单位**,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。 3. 数据项:具有独立含义的数据**最小单位** 4. 数据对象: 数据对象是具有相同性值的数据元素的集合,是数据的一个子集。 5. 数据类型: 数据类型是一个值的集合和定义在此集合上的一组操作的总称。 6. 数据结构:是指所有数据元素以及元素之间的的关系 (包含**逻辑结构、存储结构、运算**) 7. 抽象数据类型(ADT):用户在进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,不考虑具体的存储结构和运算的具体实现


- 应用:算法及其描述
O2:线性表
- 识记:线性结构的概念、线性表的概念
- 掌握:线性表的链式存储结构、顺序表与链表的比较
1. 线性结构:是指该结构中的数据元素之间存在**一对一的关系**。
2. 线性表:是指具有相同特性的数据元素的一个有限序列。 3. 顺序表:**线性表的顺序存储结构(数组)** 4. 链表:**线性表的链式存储结构**。 5. 头节点:有头节点,插入和删除都可以一致,也统一了空表和飞控表的处理过程 6. 比较:顺序表适合查找,因为是线性表的直接映射具有随机存取的特性,查找第i个元素时间复杂度为O(1),链表没这个特性,但是链表通过指针链接,插入和删除时只需要修改指针域就行,所以适合删除和插入- 应用:线性表的顺序存储结构,插入、删除和定位运算在单链表上的实现
O3:栈和队列
- 识记:栈的定义、队列的定义
- 掌握:栈的顺序实现、栈的链接实现、队列的顺序实现
1. 栈:是**一种只能在一端进行插入或删除的线性表(LIFO)后进先出**。
2. 后缀表达式,两个字符数组exp中缀和postexp后缀和运算符栈,从exp中取值遇到操作数放到postexp,遇到运算符op放到栈中,如果栈顶为空直接放,如果op的优先级高于栈顶元素也放,优先级低或相同的话就让栈顶元素先出栈放到postexp中,再让op进栈 3. 判空条件: - 顺序栈:栈顶指针指向-1;链栈:栈顶指针指向NULL - 队列:头尾指针指向一致:链队:头尾指针有一个指向NULL 4. 判满条件: - 顺序栈:栈顶指针指向MaxSize-1;队列:(rear+1)%MaxSize == font 5. 出队先动头指针再取元素值
- 应用:循环队的组织方法及在其上进行入队、出队运算的方法和队满、队空的条件。
O4:串
- 识记:串的定义
- 掌握:串的定长顺序实现
1. 串:是由零个或多个字符组成的有限序列。
2. 串的三种表现形式:**定长顺序存储表示、堆分配存储表示以及块链顺序存储表示**O5:数组与广义表
- 识记:数组元素地址的计算、广义表的特点和结构
- 掌握:特殊矩阵的压缩存储
1. <br />
2. <br />O6:树和二叉树
- 识记:树形结构的基本概念和术语、树和森林、二叉树的定义、二叉树的顺序存储结构
- 掌握:二叉树的链式存储结构、哈夫曼树的概念、构造哈夫曼树的方法
1. <br />
2. <br />- 应用:二叉树的遍历
O7:图
- 识记:树形结构的基本概念和术语、树和森林
- 掌握:图的遍历,拓扑排序、关键路径、图的概念、图的存储结构最小生成树
1. <br />
2. <br />- 应用:Prime算法、迪杰斯特拉方法的基本思想
O8:查找
- 识记:查找表的基本概念
- 掌握:静态查找表的实现、二叉排序树的查找算法及其基本思想
1. <br />
2. <br />- 应用:哈希表、在开散列表上实现查找、插入和删除运算的思想和算法
O9:排序
- 识记:排序的基本概念、归并排序
- 掌握:堆的定义、堆的调整方法和“筛选”过程,建堆的方法、冒泡排序算法、直接选择排序基本思想
1. 线性结构:是指该结构中的数据元素之间存在**一对一的关系**。
2. <br />- 应用:直接插入排序的算法和性能、折半插入排序算法、快速排序的算法和性能
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 咻咻咻小陈的空间!