【原】数据结构与算法设计基础

文章目录

1 数据结构的研究内容

数据结构的研究内容为：

研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。

数据结构课程的形成和发展：

• 形成阶段：
  60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。
• 发展阶段：
  数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。
  70年代后期，我国高校陆续开设该课程。

数据结构地位

介于数学、计算机硬件和计算机软件三者之间的一门核心课程

数据结构在计算机学科中的地位

2 基本概念和术语

基本概念

1、数据（data)：所有能输入到计算机中去的描述客观事物的符号：

• 数值性数据
• 非数值性数据（多媒体信息处理）

2、数据元素（data element）：数据的基本单位，也称结点（node）或记录（record）
3、数据项（data item）:有独立含义的数据最小单位，也称域(field)

三者之间的关系：数据 > 数据元素 > 数据项
4、数据对象(Data Object)：相同特性数据元素的集合，是数据的一个子集

• 整数数据对象
  N = { 0, 1, 2, … }
• 学生数据对象
  学生记录的集合

5、数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

数据结构的两个层次：

逻辑结构

数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。

划分方法一：

（1）线性结构
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。
例如：线性表、栈、队列、串

（2）非线性结构
一个结点可能有多个直接前趋和直接后继。
例如：树、图

划分方法二：

存储结构（物理结构）

数据元素及其关系在计算机存储器中的存储方式。

存储结构分为：

• 顺序存储结构——借助元素在存储器中的相对位置来表示

  • 数据元素间的逻辑关系
    

• 链式存储结构——借助指示元素存储地址的指针表示数据

  • 元素间的逻辑关系 可以连续 可以不连续

3 抽象数据类型的表示与实现

数据类型

定义：在一种程序设计语言中，变量所具有的数据种类

FORTRAN语言：整型、实型、和复数型
C语言：
　基本数据类型： char int float double void
　构造数据类型：数组、结构体、共用体、文件
　
数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称

抽象数据类型(ADT: Abstract Data Types)

• 更高层次的数据抽象
• 由用户定义，用以表示应用问题的数据模型
• 由基本的数据类型组成, 并包括一组相关的操作
  

4 算法与算法分析

• 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列

• 算法的描述：
  自然语言
  流程图
  程序设计语言
  伪代码

• 算法的特性：
  输入 有0个或多个输入
  输出 有一个或多个输出(处理结果)
  确定性 每步定义都是确切、无歧义的
  有穷性 算法应在执行有穷步后结束
  有效性 每一条运算应足够基本

• 算法的评价
  正确性
  可读性
  健壮性
  高效性（时间代价和空间代价）

• 算法的效率的度量
  1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分

  • 缺点：
    • 必须先运行依据算法编制的程序
    • 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣

  2.事前分析估计：
  一个高级语言程序在计算机上运行所消耗的时间取决于：

  • 依据的算法选用何种策略
  • 问题的规模
  • 程序语言
  • 编译程序产生机器代码质量
  • 机器执行指令速度

  同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———使用绝对时间单位衡量算法效率不合适