2020年数据结构(C语言描述).ppt

课程内容框架
数 据 结 构
基础数据结构
应用数据结构
栈
队
列
线
性
表
线性结构
非线性结构
串
查
找
内
部
排
序
外
部
排
序
文
件
动
态
存
管
理
储
数
组
广
义
表
树
二
叉
树
图
数据结构(C语言描述)
2021/1/12
1

基本概念
1.2基本概念和术语
数据、数据元素、数据项、数据对象
结构
*集合：松散的关系
*线性结构：一对一的关系
*树形结构：一对多的关系
*网状结构：多对多的关系
数据结构
Data_Structure=（D，S）

数据结构(C语言描述)
2021/1/12
2

数据结构的分类
1.2基本概念和术语（续）
逻辑结构：
数据元素之间的逻辑关系（本来的关系）
存储结构：
数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。
分类：
*顺序存储结构
*链式存储结构
描述方式：
用高级语言中的“数据类型”来描述

数据结构(C语言描述)
2021/1/12
3

算法
1.3算法和算法分析
内涵:
是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
特性:
*有穷性：有穷步+有穷时间/每一步
*确定性：指令的语义无二义性
*可行性：算法能用基本操作完成
*输入：零个或多个输入
*输出：一个或多个输出

数据结构(C语言描述)
2021/1/12
4

算法设计的要求
1.3算法和算法分析（续）
正确性（Correctness）
可读性（Readablity）
健壮性（Robustness）
高时间效率与低存储量需求

数据结构(C语言描述)
2021/1/12
5

算法时间效率的度量
1.3算法和算法分析（续）
算法时间效率度量的基本做法
在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
一般而言，这个基本操作是最深层循环内的语句中的原操作。
算法时间复杂度
T(n)=O (f(n)) 称为算法的渐近时间复杂度，简称时间复杂度。

数据结构(C语言描述)
2021/1/12
6

算法存储空间的度量
1.3算法和算法分析（续）
算法存储空间度量的基本做法
用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。
算法空间复杂度
S(n)=O (f(n)) 称为算法的空间复杂度。

数据结构(C语言描述)
2021/1/12
7

2.线性表
3.栈、队列和串
第一部分 线性数据结构
数据结构(C语言描述)
2021/1/12
8

线性数据结构的特点
2.1线性表的逻辑结构
在数据元素的非空有限集中
存在唯一的一个被称作“第一个”的数据元素；
存在唯一的一个被称作“最后一个”的数据元素；
除第一个之外，集合中的每一个数据元素均只有一个前驱；
除最后一个之外，集合中每一个数据元素均只有一个后继。

数据结构(C语言描述)
2021/1/12
9

基本概念和术语
2.1线性表的逻辑结构（续）
线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。
表长：线性表中元素的个数n(n>=0)。
空表：n=0时的线性表称为空表。
位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。

数据结构(C语言描述)
2021/1/12
10