1.1 讨论的范畴
问题
构建数学模型
程序实现
算法+数据结构 = 程序设计
IT Education & Training
处
给
处编
理
出
问
问
题
题
的
的
策
数
略
学
理制
问出
题 用
的
计指
模
算令
型
. 机集
3
Date:June 11, 2020
1.1 讨论的范畴
IT Education & Training
• 例1 求小红C语言和数据结构两门语言的考试的平均成 绩成绩和总成绩。全省的呢？ • 例2 酒店管理中的客房分配问题。 • 例3 煤气管道的铺设问题。 • 等等……
• 线性结构的基本特点是节点之间满足线性关系。数组、链表、栈、 队列都属于线性结构。他们的共同之处，是节点中有且只有一个 开始节点和终端节点。他们分别属于几种不同的抽象数据类型实 现，它们之间的区别，主要就是操作的不同。
• 线性表是零个或者多个数据元素的有限序列，数据元素之间是有 顺序的，数据元素个数是有限的，数据元素的类型必须相同
(a )
(b )
.
14
Date:June 11, 2020
2.3 编程实战
IT Education & Training
•经典双向链表
主要操作：初始化头结点、添加、删除、获取元素、遍历
头 指 针 (a )
头 指 针
a 0
a 1
(b )
…
a n － 1
.
15
Date:June 11, 2020
第1天 习题
IT Education & Training
• Q1. 创建两循环单向链表并将它们合为一各链表？ • Q2. 头指针和头节点有什么区别？头结点和其他节点有什么区别？
.
16
Date:June 11, 2020
3.1 栈的特点
IT Education & Training
• 栈为一种可以实现“先进后出”的存储结构， 凡是对数据的处理具有“后进先出(LIFO)”的 特点，都可以用栈这种数据结构来操作。
1.3 逻辑和物理结构
IT Education & Training
逻辑结构
123 4
1
2
3
1 2
65
56
7
4
3
线性结构
树形结构
图形结构
物理结构
12345
1
3
52
4
顺序存储
链式存储
.
7
Date:June 11, 2020
1.4 相关概念
• 数学模型 • 集合和关系 • 数据和信息 • 数据元素 • 数据项 • 关键码 • 抽象数据类型
.
13
Date:June 11, 2020
2.1 编程实战
IT Education & Training
• 动态数组
数组到底应该有多大才合适，通常不得而知。所以希 望能够在运行时具有改变数组大小的能力。（基本操 作：创建、销毁、插入、删除、遍历打印）
• 单向链表
头 指 针
头 指 针
a 0
a 1
…a n － 1
通俗点讲，数据结构研究的是数据的存储和操作。
.
5
Date:June 11, 2020
1.3 三个方面
数据的逻辑结构 数据的存储结构
IT Education & Training
线性结构
线性表 栈 队列
非线性结构
树形结构 图形结构
顺序存储 链式存储
数据的运算：查找、排序、插入、删除、修改等
.
6
Date:June 11, 2020
执行次数函数
阶
非正式术语
12
O(1)
常数阶
2n+3
O(n)
线性阶
3n2+2n+1
O(n2)
平方阶
5log2n+20
O(logn)
对数阶
2n+3nlog2n+19 O(nlogn)
nlogn阶
6n3+2n2+3n+4 O(n3)
立方阶
2n
. O(2n)
指数阶
10
Date:June 11, 2020
1.6 时间复杂度举例
Date:June 11, 2020
IT Education & Training
数据结构
.
传智播客
--肖兴贵 1
Date:June 11, 2020
主要内容
• 1 概要 • 2 线性表 • 3 栈和队列 • 4 树和二叉树 • 5 查找和排序
.
IT Education & Training
2
Date:June 11, 2020
• 线性阶：O(n)
IT Education & Training
• 平方阶: O(n2)
.
11
Date:June 11, 2020
1.6 空间复杂度举例
• 空间复杂度：O(n)
IT Education & Training
.
12
Date:June 11, 2020
2.1 线性表概念
IT Education & Training
.
IT Education & Training
8
Date:June 11, 2020
1.5 算法的定义
IT Education & Training
• 算法是特定问题求解步骤的描述，在计算机中 表现为指令的有限序列，算法是独立存在的一 种解决问题的方法和思想。对于算法而言，语 言并不重要，重要的是思想。
• 数据结构和算法的关系：数据结构是专门研究 数据的存储问题，而对存储后的数据进行相应 的操作就是算法。
.
9
Date:June 11, 2020
1.5 算法效率的度量
IT Education & Training
• 我们通过大O表示法来表示算法的效率：时 间复杂度、空间复杂度。规则如下：
（1）只关注最高次项，常数项和次要项忽略； （2）时间复杂度是指最坏时间复杂度； （3）只有常数项记做1。
ห้องสมุดไป่ตู้
• 栈的链式存储
.
18
Date:June 11, 2020
3.4 队列的特点
IT Education & Training
• 队列为一种可以实现“先进先出”(FIFO)的存 储结构。
• 栈的特殊之处在于限制了这个线性表的插入和 删除的位置，它始终只在栈顶进行。
.
17
Date:June 11, 2020
3.2 编程实战
• 栈的顺序存储
利用一组地址连续的的存储单元依次存放 自栈底到栈顶的数据元素，同时附设指针 top只是栈顶元素在顺序表中的位置。
IT Education & Training
例子中的数学模型正是数据结构要讨论的问题。
.
4
Date:June 11, 2020
1.2 定义
IT Education & Training
•数据结构是一门讨论"描述现实世界实体的数学模型 及其上的操作在计算机中如何表示和实现"的学科。
a. 在解决问题时可能遇到的典型的逻辑结构（数据结构） b. 逻辑结构的存储映象（存储实现） c. 数据结构的相关操作及其实现。(算法)