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

发表于 分类于 ， ， 阅读时长 ≈ 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表示

七 图示