课程内容

什么是数据结构

相同的数据对象,采用不同的结构/关系,需要采取不同的算法和操作

抽象来说,数据结构研究对象之间的关系与操作


数据结构基本概念与术语

数据结构


以上定义是一种逻辑上的定义,我们又称之为数据的逻辑结构。仅仅知道数据的逻辑结
构是不够的,我们还必须知道这种逻辑结构在计算机中是如何表示的。我们将数据的逻辑结构在计算机中的表示《映象)叫做数据的物理结构(又称存储结构)

数据的逻辑结构在计算机中有两种映射方式:顺序映象和非顺序映象。由此得到两经不同的存储结构:顺序存储结构和链式存储结构。

顺序存储结构

逻辑上相邻的两个元素,在存储器中依然相邻

链式存储结构

抽象数据类型

其中,D是数据对象,S是D上的关系集,P是D上的操作集

抽象数据的表示和实现

为了便于表示,采用类C语言作为描述工具

算法和算法分析

定义

对特定问题求解步骤的一种描述,它是指令的有限序列

特性

  • 有穹性(算法不能做无穷大,也不能做无穷多步骤)
  • 确定性
  • 可行性
  • 输入、输出

设计的要求

  • 正确性
  • 可读性
  • 健壮性
  • 效率与低存储量需求

算法效率的量度

  1. 计算时间
  2. 算法的规模

时间复杂度

算法中基本操作的次数,通常用