数据结构

在线课程 MOOC浙江大学数据结构课程

第一讲 基本概念

1.1 什么是数据结构

数据结构: 数据对象在计算机中的组织方式。分为两种:

  • 逻辑结构: 树,图等
  • 物理结构: 在计算机中怎么放,列表,数组等

数据类型: 数据是按照数据结构分类的,具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型

抽象数据类型: 它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起,进行封装。也就是包含两个部分:

  • 数据对象集
  • 数据集合相关联的操作集

1.2 什么是算法

算法的评价指标:

  • 空间复杂度S(n): 根据算法写成的程序执行时占用存储单元的长度
  • 时间复杂度T(n): 根据算法写成的程序执行时耗费时间的长度
  • 最坏情况复杂度T_worst(n)(一般看这个,因为平均复杂度不好得到)
  • 平均复杂度T_avg(n)

一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else结构的算法复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度,总体复杂度取三者中最大

1.3 应用实例: 最大子列和问题

第二讲 线性结构

2.1 线性表及其实现

抽象数据类型名称: 线性表(List)

数据对象集: 线性表是n个元素构成的有序序列

操作集: ~

实现方式:

  • 利用数组的连续存储空间顺序存放线性表的各元素
  • 利用链式存储来实现。不要求逻辑上相邻的两个元素物理上也相邻,通过链建立起数据元素之间的逻辑关系。

广义表: 线性表的推广
对于线性表而言, n个元素都是基本的单元素
广义表中,这些元素不仅可以是单元素也可以是另一个广义表

多重链表: 链表中的节点可能同时隶属于多个链
多重链表中节点的指针域会有多个
但包含两个指针表的链表并不一定是多重链表,比如双向链表不是多重链表

2.2 堆栈(Stack)

后缀表达式: 从左向右扫描,逐个处理运算数和运算符号。好处是不再需要考虑运算符号优先级,也就可以遇到符号就运算而不是等所有数据都出来再判断优先级。先记住运算数,一旦遇到运算符号就拿出最后两个运算数进行运算。因此需要有种存储方法, 能顺序存储运算数,并在需要时倒序输出。

堆栈(Stack): 具有一定操作约束的线性表。只在一端(栈顶,Top)做插入、删除

插入数据: 入栈(Push)
删除数据: 出栈(Pop)
后入先出: Last In First Out(LIFO)

中缀表达式转化为后缀表达式:

2.3 队列

队列(Queue): 具有一定操作约束的线性表。只能在一端插入,而在另一端删除。

数据插入: 入队列(AddQ)
数据删除: 出队列(DeleteQ)
先进先出: FIFO