没有合适的资源?快使用搜索试试~ 我知道了~
笔记-公共基础&计算机基础.pdf
需积分: 0 0 下载量 196 浏览量
2023-02-10
09:11:14
上传
评论
收藏 1.51MB PDF 举报
温馨提示
试读
21页
笔记-公共基础&计算机基础.pdf
资源推荐
资源详情
资源评论
公共基础
第一章 数据结构与算法
§1.1 算法
1. 算法的定义:是指解题方案的准确而完整的描述。(算法不等于程序,程序的设计不可
能优于算法的设计)
2. 算法的基本特征:可行性、确定性、有穷性、足够的情报。
3. 算法的基本要素:
① 对数据对象的运算和操作:
算术运算、逻辑运算、关系运算、数据传输。
② 算法的控制结构:
a.算法中各操作之间的执行顺序;
b.描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等;
c.一个算法一般可以用顺序、选择(分支)、循环(重复)三种基本结构组合而成。
4. 算法的时间和空间复杂度:
① 时间复杂度:是指执行算法所需要的计算工作量,可以用算法所执行的基本运算次
数度量。
② 空间复杂度:是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以
及算法执行过程中需要的额外空间。
③ 算法的时间复杂度和算法的空间复杂度相互独立。
§1.2 数据结构的基本概念
1. 数据:需要处理的数据元素的集合,一般来说,这些数据元素,具有某个共同的特征。
a.数据元素是数据的基本单位,即数据集合中的个体。
b.有时一个数据元素可有若干数据项组成。数据项是数据的最小单位。
2. 结构:是集合中各个数据元素之间存在的某种关系(或联系)。
3. 数据结构:是指相互有关联的数据元素的集合。
4. 数据结构的分类:
① 逻辑结构:线性结构(线性表、栈、队列);非线性结构(树、图)。
② 存储结构:顺序存储;链式存储。
③ 运算:插入、删除、查找、排序。
5. 逻辑结构:反应数据元素间的逻辑关系(即前后件关系)的数据结构。
① 线性结构(线性表):(举例:春→夏→秋→冬)
a.有且只有一个根节点,它无前件;
b.每一个节点最多有一个前件,也最多有一个后件。
② 非线性结构:
a.不满足以上两个条件的数据结构就称为非线性结构;
b.非线性结构主要是指树形结构和网状结构。
6. 存储结构:又称为数据的物理结构,是数据的逻辑结构在计算机存储空间中的存放方式
① 顺序存储结构:主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理
上相邻的存储单元里。
② 链式存储结构:每一个结点至少包含一个指针域,用指针的指向来体现数据元素之
间在逻辑上的联系。
§1.3 线性表及其顺序存储结构
1. 线性表:
线性表是 n(n≥0)个数据元素构成的有限序列,表中除第一个元素外的每一个元素,
有且只有一个前件,除最后一个元素外,有且只有一个后件。
举例:英文字母表、地理学中的四向、表格
2. 线性表的顺序存储结构:
① 通常,线性表可以采用顺序存储和链式存储,但一般使用顺序存储结构。线性表的
顺序存储又叫做顺序表(顺序分配)。
② 特点:
a.线性表中所有元素所占的存储空间是连续的;
b.线性表中数据元素在存储空间中是按逻辑顺序依次存放的;
c.可以随机访问数据元素;
d.做插入、删除时需移动大量元素,因此线性表不便于插入和删除元素。
§1.4 栈和队列
1. 栈:栈是限定在一端进行插入和删除的线性表。
特点:★
① 栈是只能在栈顶进行插入和删除;
② 栈的修改原则是“先进后出”或“后进先出”;
③ 栈底指针 boottom,栈顶指针 top,入栈,栈满,出栈;
④ 栈底指针不变,栈中元素随栈顶指针的变化而动态变化;
⑤ 栈具有记忆功能;
⑥ 栈支持子程序调用。
2. 队列:队列是指允许在一端进行插入,而在另一端进行删除的线性表。
特点:
① 队列只允许在队尾进行插入,而在队头进行删除;
② 队列的修改原则是“先进先出”或“后进后出”;
③ 队头指针 front,队尾指针 rear,入队,出队;
④ 队列中元素随队头指针和队尾指针的变化而动态变化。
3. 循环队列:是讲队列存储空间的最后一个位置绕道第一个位置,形成逻辑上的环状空间
rear>front:s=rear-front
rear<front:s=容量+rear-front
rear=front:s=1 或者 s=0
§1.5 线性链表
1. 线性链表:
① 线性表可以采用顺序存储和链式存储。线性表的顺序存储叫做顺序表,线性表的链
a.一种逻辑结构可以有多种存储结构
b.不同的存储结构其数据处理的效率不同
式存储结构叫做线性链表。
② 特点:
a.各数据结点的存储空间可以不连续;
b.各数据元素的存储顺序和逻辑循序可以不一致;
c.线性表的链式存储所占存储空间大于顺序存储结构;
d.查找结点时链式储存要比顺序存储慢;
e.链式存储插入删除元素比顺序存储灵活。
③ 线性链表的操作:在线性链表中进行插入与删除,不需要移动链表中的元素。
2. 线性表:
① 线性表顺序存储结构;
② 线性表链式存储结构(还包括双向链表、循环链表)。★
§1.6 树与二叉树(★)
1. 树:
① 是 n(n>0)个元素的有限集合。它有且仅有一个称为根的元素;其余元素是互不相
交的子树。
② 常用术语:
a.父结点、子结点;
b.根结点、叶子结点;
c.结点的度、树的度(所有结点中最大的度称为树的度);
d.树的深度;
e.子树(以某个结点的一个子结点为根构成的树称为该结点的一颗子树)。
2. 二叉树:
① 是一个有限的结点集合,该集合或者为空,或者有一个根结点及其两颗互不相交的
左右二叉子树所组成。
② 特点:
a.非空二叉树只有一个根结点;
b.每一个结点最多有两颗子树,且分别称为该结点的左子树与右子树.
③ 五种基本形态:
a.空二叉树;
b.只有一个结点的二叉树;
c.只有左子树的二叉树;
d.只有右子树的二叉树;
e.左右子树双全的二叉树。
3. 特殊二叉树:
① 满二叉树:除最后一层外,每一层上的结点数均达到最大值。
② 完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺
右边的若干结点。
满二叉树是完全二叉树,但是完全二叉树不一定是满二叉树。
4. 二叉树特点:★
非空二叉树只有一个根结点,每个结点最多有两颗子树,分别称为左子树和右子树
① 在二叉树的第 K 层上,最多有 2
k-1
个结点;
② 深度为 m 的二叉树最多有 2
m
-1 个结点;
③ 度为 0 的结点(叶子结点)总比度为 2 的结点多一个;
④ 有 n 个结点的二叉树深度至少为[log
2
𝑛]+1。
5. 二叉树的遍历:
(按照一定的顺序访问二叉树中的结点,每个结点只被访问一次)
① 前序遍历:ABDGECF
访问根结点、前序遍历左子树、前序遍历右子树(根左右)
② 中序遍历:DGBEAFC
中序遍历左子树、访问根结点、中序遍历右子树(左根右)
③ 后序遍历:GDEBFCA
后序遍历左子树、后序遍历右子树、访问根结点(左右根)
§1.7 查找技术
1. 顺序查找:对于长度为 n 的线性表,平均要进行 n/2 次比较,在最坏的情况下进行 n 次
比较。
顺序查找适用于无序表或链式线性表(不管无序还是有序)(适用于所有的线性表)
2. 二分查找:适用于顺序存储的有序表,对长度为 n 的线性表,在最坏的情况下进行log
2
𝑛次
比较。
注意:即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
§1.8 排序技术
1. 排序:
排序
平均时间
最坏情况(★)
交换类
冒泡排序
n(n-1)/2
n(n-1)/2
快速排序
n(n-1)/2
n(n-1)/2
插入类
插入排序
n(n-1)/2
n(n-1)/2
希尔排序
nlog
2
𝑛
n
1.5
选择类
选择排序
n(n-1)/2
n(n-1)/2
堆排序
nlog
2
𝑛
nlog
2
𝑛
2. 快速排序:
基本思想:在要排序的序列中找一个数作为基准数(通常为第一个数);
通过交换将这个序列中所有比基准数大的数放在右边,比基准数小的数放在左边;
以基准数为分割线分为两个子表,对两个子表重复上述步骤。
第一章总结:
剩余20页未读,继续阅读
资源评论
酷酷de张潇洒
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功