《数据结构教程绪论》由会员分享，可在线阅读，更多相关《数据结构教程绪论（21页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第一章 绪言,1.1 什么是数据结构程序=数据结构+算法 例1 书目自动检索系统,书目文件,例2 人机对奕问题,例2 人机对奕问题,课程先后关系的图形描形式：,计算机专业必修课程开设先后关系,多叉路口交通灯管理问题,特点l 课程之间的先后关系用图结构描述；l 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是数
2、据结构这门课程研究的主要内容。,数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,1.2 基本概念和术语 数据（data)所有能输入到计算机中去的描述客观事物的符号 数据元素（data element）数据的基本单位，也称节点（node）或记录（record） 数据项（data item）有独立含义的数据最小单位，也称域(field) 数据结构（data structure)数据元素和数据元素关系的集合,定义:,由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure = D, RD 是某一数据对象，R 是该对
3、象中成员之间的关系的有限集合。例如： 编制学校的科研课题小组的管理程序，首先要为程序的操作对 象课题小组设计一个数据结构 。假设每个小组由1位教 师、13名研究生及16名本科生组成，小组成员的关系是： 教师指导研究生，每位研究生指导一至两名本科生，则定义如下数据结构 Group=( P,R ),数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,数据类型高级语言中指数据的取值范围及其上可进行的操作的总称（值的集合及值集上的一组操作）,数据类型： 原子类型
4、（C中的 int、float、char，枚举等）结构类型 数组、结构体、共用体、链表等,因此：从某种意义上讲：数据结构可以看成是一组具有相同结构的值，而数据类型则是由一种数据结构和定义在其上的一组操作组成。,抽象数据类型（abstract data type,简称ADT）是指一个数据模型以及定义在该模型上的一组操作，定义取决于逻辑特性，而与内部存储无关,抽象数据类型的定义,抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。信息隐蔽和数据封装，使用与实现相分离 抽象数据类型可以有以下三元组表示( D ，S，P ) 本书中采用以下格式定义抽象数据类型：ADT 抽象数据类型 数据对象： 数
5、据对象的定义 数据关系： 数据关系的定义 基本操作： 基本操作的定义 ADT 抽象数据类型名 其中，数据对象和数据关系用位代码描述，基本操的格式定义为基本操作名（参数表）/ 参数有两种： 赋值参数，引用参数初始条件：初始条件描述 操作结果：操作结果描述,用户自定义类型,typedef struct int num;char name20;float score; STUDENT; STUDENT stu1,stu2, *p;,1.3 算法的描述和算法分析简介算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性,算法的评价标准(1) 正确性：要求算法能够正确地执
6、行预先规定的功能，并达到所期望的性能要求。(2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。(3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。(4) 时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。,算法效率用依据该算法编制的程序在计算机上执行所消耗的 时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适,时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n) 空间复杂度：s(n)=O(f(n),例1：NXN矩阵相乘 for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0; for(k=1;k=n;k+)cij=cij+aik*bkj;,
