二级公共基础知识
第一章 数据结构基础
内容提要
• 算法:算法的基本概念、算法复杂度 • 数据结构的基本概念：什么是数据结构、 数据结构的图
形表示、 线性结构与非线性结构 • 线性表及其顺序存储结构：线性表的基本概念、 顺序存
储结构、插入运算、删除运算 • 栈和队列：栈及其基本运算、队列及其基本运算 • 线性链表：基本概念、基本运算、循环链表及其基本运算 • 树与二叉树：树的基本概念、二叉树及其基本性质、 二
• 有且只有一个根结点； • 每一个结点最多有一个前件，也最多有一个后件。
– 常见的线性结构有：线性表、栈与队列、线性 链表
• 非线性结构
– 如果一个数据结构不是线性结构 – 常见的非线性结构有：树、二叉树、图
1.3 线性表及其顺序存储结构
1.3.1 线性表的基本概念
• 线性表：由n(n≥0)个相同类型数据元素构成的有 限序列：
1.1.2 算法复杂度
• n×n矩阵相乘算法：
• 时间复杂度为O(n3)。
1.1.2 算法复杂度
• 分析算法的工作量两种方法：
– 平均性态 – 最坏情况复杂性
1.1.2 算法复杂度
• 2．算法的空间复杂度
– 算法执行过程中所需的最大存储空间 – 存储量包括以下三部分
• 算法程序所占的空间 • 输入的初始数据所占的存储空间 • 算法执行过程中所要的额外空间
• 2．算法的基本要素 – 算法中对数据的运算和操作 • 算术运算:包括加、减、乘、除等） • 逻辑运算:包括“与”、“或”、“非”等运算） • 关系运算:包括“大于”、“小于”、“等于”、“ 不等于”等） • 数据传输:包括赋值、输入、输出等操作
1.1.1 算法的基本概念
• 3．算法设计的基本方法
– 提高数据处理的速度 – 尽量节省在数据处理过程中所占用的计算机存
储空间
1.2.1 什么是数据结构
• 1．数据结构研究的主要内容
– 数据的逻辑结构 – 数据的存储结构 – 对各种数据结构进行的运算
• 2．研究数据结构目的
– 提高数据处理的速度 – 尽量节省在数据处理过程中所占用的计算机存
储空间
1.2.1 什么是数据结构
1.2.1 什么是数据结构
• 4．数据的逻辑结构
– 对数据元素之间的逻辑关系的描述 – 只抽象地反映数据元素之间的逻辑关系，与计
算机中的存储无关 – 两个要素：
• 数据元素的集合，通常记为D； • 前后件关系，通常记为R
– 一个数据结构B可以表示为：
B=（D，R）
1.2.1 什么是数据结构
• 5．数据的存储结构
叉树的存储结构、二叉树的遍历 • 查找技术： 顺序查找、二分法查找 • 排序技术：交换类排序法、 插入类排序法、选择类排序
法
1.1 算法
1.1.1 算法的基本概念
• 算法是解题方案的准确而完整的描述，它不等于程序，也 不等计算方法。
• 1．算法的基本特征 – 可行性(effectiveness) – 确定性(definiteness) – 有穷性(finiteness) – 拥有足够的情报
– 数据的逻辑结构在计算机存储空间中的存放形式 ，它包括数据元素的存储方式和关系的存储方式 。
– 常用的存储结构：
• 顺序 • 链式 • 索引
– 一种数据结构可根据需要采用不同的存储结构。 采用不同的存储结构，其数据处理的效率是不同
1.2.2 数据结构的图形表示
• 数据结点：用方框表示
– 根结点、终端结点
• 线性表的结构特征
– 数据元素在表中的位置由序号决定，数据元素 之间的相对位置是线性的；
– 对 ，于 它一 无个 前非 件空，线有性且表只，有有一且个只终有端一结个 点a根n，结它点无a1 后件，除根结点与终端结点外，其他所有结点 有且只有一个前件，也有且只有一个后件。
1.1.2 算法复杂度
• 问题的规模函数
算法的工作量=f(n)
• 算法中基本操作重复执行的频率T(n)，是问题规 模n的某个函数f(n)，记作：
T(n)=O(f(n)) – 记号“O”读作“大O”。表示随问题规模n的增加，算法
执行时间的增长率和f(n)相应增加。
• 常见算法复杂度：
– O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶 – O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶
– 列举法 – 归纳法 – 递推 – 递归 – 减半递推技术 – 回溯法
1.1.2 算法复杂度
• 算法复杂度：时间复杂度、空间复杂度 • 1．算法的时间复杂度
– 执行算法所需要的计算工作量 – 与下列因素有关：
• 书写算法的程序设计语言 • 编译产生的机器语言，代码质量 • 机器执行指令的速度 • 问题的规模
– 算法空间复杂度可定义为： S(n)=O(f(n))
– 原地工作(in place)的算法：记作O(1) – 压缩存储技术
1.2 数据结构的基本概念
1.2.1 什么是数据结构
• 1．数据结构研究的主要内容
– 数据的逻辑结构 – 数据的存储结构 – 对各种数据结构进行的运算
• 2．研究数据结构目的
• n定义为线性表(a 的1 ,a 表2, 长,；a i, n=a 0n)时的线性表被称为空 表。称i为在线性表中的位序。
• 例如：
– 英文大写字母表
（A，B，C，D，E，F，…X，Y，Z）
– 同一花色的13张扑克牌
• (2,3,4,5,6,7,8,9,10,J,Q,K,A)
1.3.1 线性表的基本概念
ቤተ መጻሕፍቲ ባይዱ
线性表
A．线性结构 栈
队 1．数据的逻辑结构
数 据 结
树形结构 B．非线性结构
构
图形结构
的
三 个
2、数据的存储结构 A 顺序存储
方 面
B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
1.2.1 什么是数据结构
• 3．数据结构的定义 – 相互有关联的数据元素的集合 – 数据元素之间的关系可以用前后件关系 来描述 – 一个数据结构应包含以下两方面信息： • 表示数据元素的信息 • 表示各数据元素之间的前后件关系
• 前后件关系：用有向线段表示
春
夏
秋
冬
父亲
• 基本运算：
– 插入运算
(a)一年四季数据结构
儿子
女儿
(b)家庭关系数据结构
– 删除运算
– 查找、分类、合并、分解、复制、修改、……
1.2.3 线性结构与非线性结构
• 空的数据结构：一个数据元素都没有 • 线性结构
– 如果一个非空数据结构满足下列两个条件：