数据结构笔记¶
课程介绍¶
- 每周实验作业
通过OJ平台进行线上答题
每周四16:00公布本周实验题目, 下周三23:59结束
每周四18:30-20:20 抽查上周实验作业与答疑本周实验题目.
不准使用各种库, String除外
- 每月课程竞赛(OJ)
10/11/12中旬 当堂完成.
第一章 绪论¶
什么是数据结构
-
描述非数值计算问题的数学模型, 而非数学方程, 而是诸如表, 树, 图之类的数据结构
-
数据结构是一门研究(非数值计算的)程序设计问题中出现的计算机操作对象以及它们之间关系和操作的学科.
基本概念¶
-
数据: 泛指概念
-
数据对象: 具有相同性质的数据元素的集合
-
数据元素(成员): 数据个体, 类似表格中的index
-
数据项: 数据个体的属性, 类似表格中的column
数据项 vs. 数据元素
数据项是 属性 , 单看某一列数据项的话是没有任何意义的
数据元素是 个体 , 一个个体具有多个属性.
数据结构设计三个方面
- 数据的逻辑结构---面向问题, 独立于计算机
- 数据的物理结构(存储结构)---面向计算机
- 相关操作及实现
例子: 学生表
- 逻辑结构: 线性表
- 物理结构: 数组/链表
- 操作: 插入, 删除, 查找
任何一个算法的 设计 取决于选定的逻辑结构, 而算法的 最终实现 依赖于采用的存储结构.
数据结构
数据结构由某一种数据元素的集合和该集合中数据元素之间的关系组成.记为Data_Structure = \{D, R\}.
数据结构的分类¶
-
线性结构
-
非线性结构:
-
层次结构: 树
-
群结构(所有的元素之间没有顺序关系): 集合
-
映像¶
关系的映像方法¶
- 顺序映像:
以相对的存储位置表示后继关系.
抽象数据类型 ADT¶
-
特点:
-
降低了软件设计的复杂性
-
调高了程序的可读性和可维护性
-
程序的正确性容易保证
-
数据结构与算法的关系
DataStructure + Algorithm = Programming
问题的数学模型 + 实现的途径
算法必须满足的特性
-
输入 有0个或多个输入
-
输出 有1个或多个输出
-
确定性 每步定义都是确切 无歧义
-
有穷性 算法应在执行有穷步后结束
-
有效性 每一条运算应足够基本
程序 vs. 算法
-
程序不一定满足有穷性. 如操作系统
-
程序中的指令必须是机器可执行的(指定语言), 而算法是通用的.
算法性能分析与度量¶
性能标准:
-
正确性
-
可使用性
-
健壮性
-
可读性
-
效率
算法的效率
包括时间代价和空间代价(所需的最大存储空间).
要精确的计算T(n)通常比较困难
引入渐进时间复杂度---在数量级上估计一个算法的执行时间, 也能得到分析算法的目的.
T(n) = O(f(n))
大O表示法
当且仅当存在正整数c, n_0, 使得T(n) < c*f(n)对所有n > n_0成立, 则称在该算法的时间增长率在O(f(n))中, 记为T(n) = O(f(n)).
常见的渐进时间复杂度
Question
Ans
2.O(n^{3\over 2})
第二章 线性表¶
线性表(LinearList)¶
定义
-
表头: 第一个表项 -
表尾 -
存储方式: 顺序表 / 链表
顺序表¶
定义: 元素相继存放在一个连续的存储空间中
特点:
-
各表项的逻辑顺序和物理顺序一致
-
对各个表项可以顺序访问, 也可以随机访问
静态存储: 开数组
动态存储: 用指针
单链表¶
连续存储方式(顺序表) vs. 链式存储方式(链表)
顺序表:
存储利用率高(不用记指针), 存取速度快
插入/删除等操作需要移动大量数据
链表:
适应表的动态增长和删除
需要额外的指针存储空间 访问速度慢
(单向)循环链表¶
把尾结点的指针指向头节点.
双向循环链表¶
举例: 多项式运算类¶
静态链表¶
为数组中的每一个元素附加一个链接指针(虚拟的, 只用指向数组下标).
EXAMPLE 题单0x03
error: operator=() does not handle self-assignment properly
第一句是非常重要的一句 : 如果写出a = a这样的情况, 那么直接完蛋(如果没有的话)!
Stackv Oerflow 里面的回答是很有价值的.
