数据结构 第 1 章 绪论

《数据结构 第 1 章 绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、绪论数据结构1、为什么要学习数据结构？教学内容2、数据结构的基本概念数据、数据元素、数据对象、数据结构和抽象数据类型等概念。3、算法及算法分析性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量。占据了当今计算机应用的绝大多数。数值计算：加工处理的对象——纯粹的数值。非数值计算计算机应用工业检测过程控制管理系统数据处理……加工处理的对象字符表格图象声音……具有一定的结构逻辑结构存储结构算法有效地组织计算机存贮研究对象的特性及其相互之间的关系有效地实现对象之间的“运算”关系《数据结构》的研究内容为什么要学数据结构

2、为什么要学数据结构1.1什么是数据结构抽象数学模型计算机解题步骤设计算法编程、调试、运行分析问题提取操作对象找出操作对象之间的关系用数学语言描述数据结构什么是数据结构什么是数据结构例1：计算机电话号码查询系统。法学院8523101国贸学院8522105工商学院8523150计算机学院8521088会计学院8525789统计学院8528136…………8521088计算机学院8522105国贸学院8523101法学院8523150工商学院8525789会计学院8528136统计学院…………算法：查询、插入、修改、删除……线

3、性结构线性表操作对象：{单位名，号码}{号码，单位名}关系：线性关系例2：计算机和人对弈问题。非线性结构树操作对象：格局（棋盘状态）关系：非线性关系（由比赛规则决定）算法：插入、修改、删除……例3、多叉路口交通灯的管理问题。在多叉路口需设几种颜色的交通灯才能使车辆相互之间不碰撞，又能达到最大流通量。ABCDE非线性结构图操作对象：通路关系：非线性关系（由问题的要求决定）ABACADBADCEDBCBDDADBEAEBEC程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。瑞士著名的计算机科学家、Pasc

4、al语言发明者沃思(N.Wirth)教授提出：《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算的一门学科。数据结构是问题的数学模型。算法（解决问题的方法）处理的对象就是数据。算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。程序=算法+数据结构要想有效地使用计算机，就必须学习数据结构。数据结构的发展史“数据结构”作为一门独立的课程在国外是从1968年才开始设立的，由美国唐·欧·克努特教授开创其最初体系，他所著的《计算机程序设计技巧》第一卷《

5、基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。我国于1978年开设本课程。数据结构发展史数据结构发展史数据结构的地位1、数据结构在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和应用程序的重要基础。▲数据结构的地位数据结构的地位是对信息的一种符号表示——人们利用文字符号、数字符号以及其他规定的符号

6、对现实世界的事物及其活动所做的描述。数据(Data)1.2基本概念和术语在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称——包括数值型数据和非数值型数据（包括文字、表格、图象、声音等，都称为数据）。它是计算机操作对象的总称。数据是个集合，可用集合的表示方法来写：数据={x

7、x是计算机操作的对象}数据结构的基本概念数据结构的基本概念数据元素(DataElement)：(也称结点)是数据(集合)中的一个“个体”，是数据的“基本单位”，在计算机程序中通常作为一个整体进行考虑和处理。数据项(dataitem)

8、：是数据结构中讨论的“最小单位”。两类数据元素不可分割的“原子”型数据元素如：整数“5”，字符“N”等；由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。如描述一个学生的信息的数据元素可由3个数据项组成。其中的出生日期又可以由三个数据项：“年”、“月”和“日”组成，则称“出生日期”为“组合项”，而其它不可分割的数据项为“原子项”。姓名出生日期成绩年月日数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。例：整数数据对象的集合可表示为N={0,±1,±2,…}，字母字符数据对象的集合可

9、表示为C={‘A’,’B’,…,’Z’}。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。结构：数据元素之间的相互关系。意为x和y之间存在“x领先于y”的次序关系。长整数“321465879”可用a1=321，a2=465和a3=879的集合表示，且三者之间的次序关