青岛大学数据结构与算法——第1章

一 概述

• 前言
• 研究内容
• 基本概念和术语
• 抽象数据类型的表示与实现
• 算法和算法分析

二 前言

• 数据结构重要吗
• 好学吗
• 怎么才能学好这门课程

三 研究内容

3.1 数值计算

• 桥梁结构中第应力
• 预测人口增长情况

3.2 非数值计算

• 管理系统(线性表)
• 人机对弈问题(树)
• 文件系统等系统结构图(树)
• 地理信息-地图导航-最短路径(图)

四 基本概念和术语

4.1 基本概念

• 数据-Data
• 数据元素-Data Element
• 数据项-Data Item
• 数据对象-Data Object

4.2 数据结构

逻辑结构

方式一:

• 线性结构：线性表、栈、队列、串
• 非线性结构：树、图

方式2：集合、线性、树、图

存储结构/物理结构

• 顺序存储结构-数组
• 链式存储结构-指针
• 索引存储结构-通讯录
• 散列存储结构-散列表

4.3 数据类型

可用数据类型表示

• 基本数据类型：int、char、float、double
• 构造数据类型：数组、结构体、共用体、枚举
• 指针、void
• typedef自定义类型

不能直接用数据类型表示

• 栈
• 队列
• 树
• 图

4.4 抽象数据类型

• 形式定义：D-数据对象、S-关系集、P-对D的操作集
• 定义格式：ADT

五 抽象数据类型的表示和实现

• 圆(ADT)
• 复数(ADT)

六 算法和算法分析

6.1 算法的描述

• 自然语言
• 流程图
• 伪代码
• 程序代码

6.2 程序与算法

• 算法的特性：有穷性、确定性、可行性、输入、输出
• 算法设计要求：正确性、可读性、健壮性、高效性

6.3 算法效率

• 考虑：时间效率和空间效率
• 度量：事后统计和事前分析
• 表示：大O表示

七 图示