文档介绍：数据结构
--肖兴贵
传智播客
1 概要
2 线性表
3 栈和队列
4 树和二叉树
5 查找和排序
主要内容
讨论的范畴
算法+数据结构= 程序设计
处理问题的策略
给出问题的数学模型
编制出的指令集
处理问题用计算机
问题
构建数学模型
程序实现
讨论的范畴
例1 求小红C语言和数据结构两门语言的考试的平均成绩成绩和总成绩。全省的呢?
例2 酒店管理中的客房分配问题。
例3 煤气管道的铺设问题。
等等……
例子中的数学模型正是数据结构要讨论的问题。
定义
数据结构是一门讨论"描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现"的学科。
a. 在解决问题时可能遇到的典型的逻辑结构(数据结构)
b. 逻辑结构的存储映象(存储实现)
c. 数据结构的相关操作及其实现。(算法)
通俗点讲,数据结构研究的是数据的存储和操作。
三个方面
数据的逻辑结构
数据的存储结构
数据的运算:查找、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队列
树形结构
图形结构
逻辑和物理结构
逻辑结构
物理结构
数学模型
集合和关系
数据和信息
数据元素
数据项
关键码
抽象数据类型
相关概念
算法是特定问题求解步骤的描述,在计算机中表现为指令的有限序列,算法是独立存在的一种解决问题的方法和思想。对于算法而言,语言并不重要,重要的是思想。
数据结构和算法的关系:数据结构是专门研究数据的存储问题,而对存储后的数据进行相应的操作就是算法。
算法的定义
算法效率的度量
我们通过大O表示法来表示算法的效率:时间复杂度、空间复杂度。规则如下:
(1)只关注最高次项,常数项和次要项忽略;
(2)时间复杂度是指最坏时间复杂度;
(3)只有常数项记做1。
执行次数函数
阶
非正式术语
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)
指数阶