数据结构ds-1.ppt

1、数 据 结 构,徐 虹 ,说明,总学时： 48(学时)= 36（课时）+ 12（实验） 行课时间:第 1 9周 周学时:平均每周 4 学时 上机安排待定 考试时间：课程结束 第8、11、12 章的内容为自学内容； 目录中标有 * 的内容(除递归外)不作要求。,上机安排,指导老师: 时间： 地点:计算机学院机房,教材与参考书,严蔚敏，数据结构，清华大学出版社 Clifford A. Shaffer, 数据结构与算法分析，电子工业出版社 Sartaj Sahni, 数据结构、算法与应用,机械工业出版社 严蔚敏，数据结构题集，清华大学出版社,3.课程的内容与组织,1.数据结构的研究对象,课程简介,数

2、据是现实世界的数字化,研究数据在计算机中的表示、关联、存储与处理方法,2.课程的性质与定位,数据组织与结构是计算机科学最基本内容，是人才信息素质的脊梁,培养数据抽象能力，算法设计能力以及构造算法思维方法,1. 数据结构的研究对象,我们生活在一个物质的世界，计算机工作者又面对着数字的世界，如果将物质世界中的事与物数字化，那么它们在计算机中的表现均为数据。这些数据来源于现实，表征着具体的意义，而且在计算机中有着统一的表示方法，因而成为被计算机程序处理的符号集合。研究数据在计算机中的表示方法、关联方法、存储方法以及在其上的典型处理方法，就构成了数据结构课程的主要内容。,2. 数据结构课程的性质与地位

3、,由于数据是计算机处理的对象，使用计算机的过程就是对数据进行加工处理的过程，因而数据的组织与结构被确立为计算机科学中最为基本内容。 80年代初, 数据结构课程就已成为国内计算机专业教学计划中的核心课程。,人类解决问题的思维方式可分为推理方式和算法方式两大类。推理方式凭借公理系统思维方法通过数学训练得到。算法方式则是凭借构造性思维，从具体操作规范入手，通过操作过程的构造实施来解决特定问题。,数据结构的学习过程，是算法构造性思维方法的训练过程，技能培养的重要程度不亚于知识传授。本门课程教学难点在于让学生理解、习惯算法构造思维方法。培养学生的数据抽象能力，算法设计能力以及创造性思维方法，才能够举一反

4、三、触类旁通，从而达到应用知识解决复杂问题的目的。,数据结构是重要的专业基础课，是计算机科学的核心课程，是计算机理论与技术的重要基石。 该课程具有承上启下的重要作用，既要对前一年学习的软件技术进行总结提高，又要为后续专业课程提供基础。它贯通始终，是计算机科学与技术人才素质培养框架中的中坚课程，对学生的软件开发能力培养有至关重要的作用，将为学生今后的专业生涯打下牢固基础。,2.数据结构课程的性质与地位,3. 课程的内容与组织,以抽象数据类型为中心，采用面向对象的新观点，将教学内容分为基本概念、基本结构、基本算法三个层次，并贯穿了计算机科学中的一些重要的问题求解技术，符合认知规律。 使用熟悉的标准

5、C 作为算法描述的语言，使之与大多数院校讲授的第一语言衔接，便于将读者的注意力集中在算法的理解上。这就使数据结构的表示得以简化，突出了算法表示的实质。,例题、习题、典型题例、实习范例、课程设计全方位训练,4. 成绩计算,平时成绩:30% 考勤+课堂表现+作业+课堂测验+上机考察 考试成绩:70%,学生的考核资格按下述原则审查： 学生有以下情况之一者，不能参加课程成绩考核，该课程的考核成绩以零分处理。在确定学籍处理、授予学士学位时，该门课程以考核不及格门次参加统计。 全期旷课累计达该课程教学时数五分之一（含五分之一）以上者； 全期缺交该课程任课教师布置作业三分之一（含三分之一）以上者；或全期所交

6、该课程作业，虽达到任课教师布置作业三分之二以上，但所交作业的准确度、整洁度有二分之一不合格者； 全期缺做该课程实习、实验或缺交实习、实验报告达三分之一（含三分之一）以上者；或全期参加该课程实习、实验，所交实习、实验报告都在三分之二以上，但有二分之一不合格者； 未经批准或未办理选课手续，擅自修读该门课程者。,目 录,第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：树和二叉树 第七章：图 第九章：查找 第十章：内部排序,第一章 绪论,数据结构的有关概念 算法和算法分析,1. 1 什么是数据结构,数据结构的引论 例1 图书馆的书目检索系统自动化问题 在书目自

7、动检索系统中可以建立一张按等录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示：,特点：计算机按某个特定的要求进行查询.处理对象之间存在一种简单的线形关系,这类模型可以称为简单的线形数据结构.,按书名排列,按作者排列,按索引号排列,例2: 计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程.,*,例3: 多叉路口交通

8、灯的管理问题 可以把这类交通,道路的问题当作一种“图”的结构：一个顶点表示一条通道,而通道之间的矛盾的关系以两个顶点之间的连线表示.如下图所示:,结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构. 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科.,数据结构的地位 数据结构是计算机科学中一门综合性的专业基础课。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。,1. 2 基本概念,数据（Data) 客观事物的符号表示，能输入到计算机中并被计算 机中程序处理的

9、符号的总称。 数据元素 (Data element) 数据的基本单位，可由数据项组成。 数据类型 (Data Type) 是和数据结构密切相关的一个概念，在高级语言中，用以刻画（程序）操作对象的特性。是一个值的集合和定义在这个值集上的一组操作的总称。,数据对象 (Data Object) 性质相同的数据元素的集合，是数据的子集。 数据结构 (Data Structure) 相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构： （1）集合（2）线形结构（3）树形结构（4）图状结构(网状结构）。,数据结构类型 数据的逻辑结构 数据结构的形式定义： D

10、ata_Structure=D,S,P 其中： D是数据元素的有限集 S是上下关系的有限集 P是对数据对象的基本操作 数据的物理结构（存储结构），数据结构基本操作的实现； 数据的存储结构：位、元素和数据域 数据结构的存储形式有： 顺序存储 链式存储,数据类型综述 数据类型可以分为 原子类型值不可以分解 结构类型值由若干成分按某种结构组成。 抽象数据类型（ADT） ADT是一个值的集合和定义在这个值集上的一组操作的总称。包括：原子类型、固定聚合类型和可变聚合类型。,数据操作描述 数据的基本操作： 插入：在数据结构的指定位置添加新的数据元素。 删除：去掉数据结构中某个指定的数据元素。 更新：改变数

11、据结构中某个数据元素的值。 查找：在数据结构中寻找某个满足特定要求的数据元素。 排序：重新安排数据元素的逻辑顺序关系，使之值按从小到大或从大到小的顺序排列。,操作的分类 加工型操作操作改变了（操作之前的）结构的值。 引用型操作不改变值，只是查询或求得结构的值。 操作的描述,1. 3 抽象数据类型的表示与实现,语言的描述 预定义常量和类型 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 Status是函数的类型，其值是函数结果状态代码 typedef int Status; 数据结构的表示用类型定义（typedef）

12、描述，数据元素类型约定为ElemType，可以是C语言中任何数据类型。,基本操作的算法用以下形式函数来描述 函数类型函数名（函数参数表） / 算法说明 语句序列 /函数名 C语言中操作的描述 赋值语句 循环语句 选择语句 注释 结束语句 输入和输出语句 逻辑运算约定,1. 4 算法与算法分析,算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 一个算法就是一个有穷规则的集合，规则规定了解决某特定问题的运算序列。 算法的特性：有穷性、确定性、可行性、输入、输出。,算法设计的两个目标 易读、易编码和调试（软件工程） 充分利用计算机资源（算法和数据结构） 算法的设计要求 正确性： 程序不含语法

13、错误； 程序对于几组输入数据能够得出满足要求的结果； 程序对于精心选择的典型、苛刻的输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能够得出满足要求的结果。 可读性 健壮性 效率与低存储量要求,最佳、最差、平均情况分析 对于不同的输入情况，算法的时间代价不同 例如:在一个数组中查找元素K 分为最佳、最差、平均情况分析,算法效率的度量 算法效率需通过该算法编制的程序在计算机上运行所消耗的时间多少以及所需辅助空间的大小来度量。 频度：某语句重复执行的次数。 时间复杂度：从算法中选取一个对于所研究的问题来说是基本操作的源操作，以该基本操作重复执行的次数作为算法的时间量度。 T（n）=

14、O（f（n）。 它表示随着n的增大，算法执行时间的增长率和 f ( n ) 的增长率相同。,空间复杂度： 一个上机执行的程序除了需要存储空间来积存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间。辅助空间的大小反映了该算法的空间复杂性。 S（n）= O（f（n）。,大O 表示法的运算规则 单位时间 简单布尔或算术运算 赋值 简单I/O 函数返回 加法规则: f1(n)+f2(n)=(max(f1(n), f2(n) If结构， switch结构 乘法规则: f1 (n) f2(n) = (f1(n)f2(n) for, while,

15、do-while结构,程序段一： +x; s=0; 程序段二： for(i=1;i=n;+i) +x; s+=x; 程序段三： for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x; ,例1：求下面程序的时间复杂度。,该程序中“+x”是基本操作语句，其频度为n2，其时间复杂度为O(n2)，为平方阶。,该程序中“+x”是基本操作语句，其频度为1，其时间复杂度为O(1)，为常量阶。,该程序中“+x”是基本操作语句，其频度为n，其时间复杂度为O(n)，为线性阶。,课堂作业分析程序中各语句的频度,Ex( ) int i , j , t ; (1) for( i=1 ; i1

16、0 ; i+) (2) printf(“n %d” , i ); (3) for(i=1; i=2; i+) (4) printf(“n”); (5) for(i=1; i=9; i+) (6) for(j=1; j = i ; j+) (7) t = i * j ; printf(“%5d”,t); (8) for(j=1; j3 ; j+) (9) printf(“n”); ,Ex( ) int i , j , t ; (1) for( i=1 ; i10 ; i+) /n =10 (2) printf(“n %d” , i ); /n =9 (3) for(i=1; i=2; i+) /

17、n =3 (4) printf(“n”); /n =2 (5) for(i=1; i=9; i+) /n =10 (6) for(j=1; j = i ; j+) /n =54 (7) t = i * j ; printf(“%5d”,t); /n =45 (8) for(j=1; j3 ; j+) /n =27 (9) printf(“n”); /n =18 ,运行时间估计 例：假设CPU每秒处理106 个指令，对于输入规模为= 108的问题，时间代价为T(n)=2n2的算法要运行多长时间？ 操作次数为T(n)=T(108)=2(108)2=21016 运行时间为21016/106 = 21010秒 每天有86,400秒，因此需要231,480 天(634年),例：假设CPU每秒处理106 个指令，对于输入规模为n = 108的问题，时间代价为T(n)=nlogn的算法要运行多长时间？ 操作次数为