数据结构c语言版1-绪论.pptVIP

数据结构 (C语言版) 计算机发展简史 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题 早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算 计算机发展简史 近三十年来，电子计算机的发展异常迅猛 表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降 更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域 计算机发展简史 与此相应，计算机的处理对象也从 简单的纯数值性信息 发展到 非数值性的和具有一定结构的信息 计算机发展简史 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 数据结构 1 “数据结构”在计算机科学中是一门综合性的专业基础课。 2 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 3 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 1.1 什么是数据结构 一个课题的解决原则 需求分析 总体设计 模块分割 建立数学模型 设计解数学模型的算法 程序编制 调试 结果 数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法 1.1 什么是数据结构 1.1 什么是数据结构 程序：main(){ int len, wide ,area ;scanf (“%d %d%\n”, len,wide);area=len*wide ;printf (“area=%d”,area);} 可见，对于数值问题，对象之间的关系通常可以用方程或函数表达，只要能列出表达对象之间关系的方程或函数，找到求解方程或函数的方法，就可以编写程序了 1.1 什么是数据结构 电话号码查询系统 学籍档案管理 特点 举例3——输出n个对象的全排列 解决 举例4——制定教学计划 课程先后关系的图形描述形式 特点 1.1 什么是数据结构 1.1 什么是数据结构 1.1 什么是数据结构 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 家族树的二元组表示（D，S） 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 1.2 基本概念和术语 (3)数据类型并不局限于高级语言,它实际上是一个广义的概念. 例如:”教师”就是一个数据类型,他有值”教龄”,有操作” 教书”等;如果具体说小学教师,大学教师,可以看作时一个具体的类型. (4) 可以撇开计算机不考虑,现实中任何一个问题都可以定义为一个数据类型---称为抽象数据类型 §1.3 抽象数据类型 什么是类C语言? *类C语言 *类C语言 *类C语言 * C的数据类型 例 某班40个学生的数学成绩，可以用有40个数组分量 的整型数组变量存储。 Typedef int SCoreType[40]; SCoreType class1; * C的数据类型 * C的数据类型 * C的数据类型 例 一本书可以用有2个数据成员（数据域）结构变量存储。 Typedef struct { int no; char title[40]; }BookType; BookType book1; * C的数据类型 * C的数据类型 §1.3 抽象数据类型 §1.3 抽象数据类型 §1.3 抽象数据类型 §1.3 抽象数据类型 二.数据类型的实现 一个问题抽象为一个抽象数据类型后,仅是形式上的抽象定义,还没有达到问题解决的目的 要实现这个目标,就要把抽象的变成具体的,即抽象数据类型在计算机上的实现,变为一个具体的数据类型. §1.3 抽象数据类型 §1.4 算法与算法分析 若采用自然语言描述,则如下列步骤所示: (1)给10个元素a[0]-a[9]输入数值; (2)把第一个元素a[0]赋给用于保存最大值元素的变量max; (3)把表示下标的变量i赋初值1; (4)如果i=10,则向下执行,否则输出最大值max后结束算法; (5)如果a[i]max,