第一章 绪论
第一章 绪 论
第一章绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1算法 1.4.2算法设计的要求 1.4.3算法效率的度量 1.4.4 算法的存储空间的需求 数据猪物
数据结构 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求
1.1什么是数据结构 “数据结构”作为一门计算机专业基础课，是编译 原理，操作系统，数据库等课程的基础。也是设 计及实现系统程序和大型应用程序的重要基础。 “数据结构”的主要内容是研究数据的逻辑结构， 存储结构及对每种结构所定义的运算。 程序设计的实质是数据表示和数据处理 1)数据表示-把原始数据从机外表示转化为机内 表示。 2)数据处理-一编写程序，对机内的数据进行各种 操作，获得所需结果。 数据猪构
数据结构 1.1 什么是数据结构 “数据结构”作为一门计算机专业基础课，是编译 原理，操作系统，数据库等课程的基础。也是设 计及实现系统程序和大型应用程序的重要基础。 “数据结构”的主要内容是研究数据的逻辑结构， 存储结构及对每种结构所定义的运算。 程序设计的实质是数据表示和数据处理 1)数据表示-把原始数据从机外表示转化为机内 表示。 2)数据处理-编写程序，对机内的数据进行各种 操作， 获得所需结果
例1、职工档案管理问题 工作证号 姓名 性别 出生日期 职称 0001 刘晓军 男 19491001 工程师 0003 张红 女 19650506 助工 0007 李华 女 19461118 高工 数据猪拘
数据结构 例1、职工档案管理问题 工作证号 姓名 性别 出生日期 职称 0001 刘晓军 男 19491001 工程师 0003 张 红 女 19650506 助工 0007 李 华 女 19461118 高工 . . . .
每位职工的档案由五个项目构成，所有职工的档案组成一 张数据表。要管理这张表，至少可进行以下操作（运算）： 查找、读取、插入、删除、更新、排序等。 用计算机解决上述管理问题，设计人员要完成二项任务： 第一，将档案表转化为机内表示，让计算机直接处理； 一一数据表示 第二，编写计算机程序实现人工管理的要求。 一一数据处理 在大多数情况下，这些数据并不是没有组织，数据之间往 往具有重要的结构关系，这就是数据结构的内容。那么， 什么是数据结构呢？先看以下几个例子。 数据猪构
数据结构 每位职工的档案由五个项目构成，所有职工的档案组成一 张数据表。要管理这张表，至少可进行以下操作(运算)： 查找、读取、插入、删除、更新、排序等。 用计算机解决上述管理问题，设计人员要完成二项任务： 第一，将档案表转化为机内表示，让计算机直接处理； ——数据表示 第二，编写计算机程序实现人工管理的要求。 ——数据处理 在大多数情况下，这些数据并不是没有组织，数据之间往 往具有重要的结构关系，这就是数据结构的内容。那么， 什么是数据结构呢？先看以下几个例子
例1：学籍管理问题：某班学生基本情况表，记录了 每个学生的学号，姓名，专业，政治面貌，表中的记录 是按学生的学号顺序排列的。 学号 姓名 专业 政治面貌 001 王丽 计算机 党员 002 孙文 计算机 团员 003 谢小军 计算机 团员 004 李辉 计算机 团员 线性 005 刘慧 计算机 党员 表 006 余军 计算机 团员 007 李力 计算机 团员 008 张爱东 计算机 团员 001 002 003 004 005 006 007 008 在这类文档管理的数学模型中，计算机处理的对象 之间通常存在着一种最简单的线性关系，这类数学 模型称为线性的数据结构。 数据猪物
数据结构 例1：学籍管理问题：某班学生基本情况表，记录了 每个学生的学号，姓名，专业，政治面貌，表中的记录 是按学生的学号顺序排列的。 001 002 003 004 005 006 007 008 在这类文档管理的数学模型中, 计算机处理的对象 之间通常存在着一种最简单的线性关系, 这类数学 模型称为线性的数据结构。 线性 表 学号 姓名 专业 政治面貌 001 王 丽 计算机 党员 002 孙 文 计算机 团员 003 谢小军 计算机 团员 004 李 辉 计算机 团员 005 刘 慧 计算机 党员 006 余 军 计算机 团员 007 李 力 计算机 团员 008 张爱东 计算机 团员
例2、人机对奕问题 树 数据猪构
数据结构 例2 、人机对奕问题 . . . . . . 树
例3、多叉路口交通灯管理问题 AB B BA B DC ED 图 可见：描述这类非数值计算问题的数学模型不再是数学方程， 而是线性表、树和图之类的数据结构。简言之，数据结构是一 门研究非数值计算的程序设计问题中计算机的操作对象以及它 们之间的关系和操作等等的学科。 数据猪物
数据结构 例 3、 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 可见：描述这类非数值计算问题的数学模型不再是数学方程， 而是线性表、树和图之类的数据结构。简言之，数据结构是一 门研究非数值计算的程序设计问题中计算机的操作对象以及它 们之间的关系和操作等等的学科。 图
1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机 科学中是指所有能输入到计算机中并被计算机程 序处理的符号的总称。 数据元素(Data Element):是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处 理。 一个数据元素可由若干个数据项组成。数据项是 数据的不可分割的最小单位。 数据对象(Data Object):是性质相同的数据元 素的集合。是数据的一个子集。 数据对象可以是有限的，也可以是无限的。 数据猪构
数据结构 1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算机 科学中是指所有能输入到计算机中并被计算机程 序处理的符号的总称。 数据元素(Data Element):是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑和处 理。 一个数据元素可由若干个数据项组成。数据项是 数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元 素的集合。是数据的一个子集。 数据对象可以是有限的，也可以是无限的
例：整数的数据对象是{.-3，-2，-1,0,1， 2,3,.} 英文字符类型的数据对象是{A,B,C,D,E, F,} 结构(Structure):是数据之间彼此存在的相互关系。 数据结构(Data Structure)：:是相互之间存在一种或 多种特定关系的数据元素的集合。 这种关系体现在三个方面： 1、数据之间的逻辑关系 2、数据在计算机内的存储方式 3、数据在计算机内的运算 数据的结构主要指逻辑结构和物理结构 数据猪物
数据结构 例：整数的数据对象是{.-3，-2，-1，0，1， 2，3，.} 英文字符类型的数据对象是{A，B，C，D，E， F，.} 结构（Structure):是数据之间彼此存在的相互关系。 数据结构(Data Structure)：是相互之间存在一种或 多种特定关系的数据元素的集合。 这种关系体现在三个方面： 1、数据之间的逻辑关系 2、数据在计算机内的存储方式 3、数据在计算机内的运算 数据的结构主要指逻辑结构和物理结构