高等数据结构与算法.ppt

1、数据结构,教材： 数据结构(C语言版) 严蔚敏 清华大学出版社 参考书： 数据结构使用C语言 朱战立 西安交通大学出版社 数据结构与算法 齐德昱 清华大学出版社 数据结构与算法C+版(第2版) Adam Drozdek 清华大学出版社 课程与考试安排： 第8、11、12章不作要求 有*号的小节不作要求 期末成绩和平时成绩各占60和40,第一章 绪言,1.1.1 什么是数据结构 程序设计=数据模型+算法 程序设计：为计算机处理问题编制的一组指令集 数据模型：现实问题的抽象 算法：处理问题的策略 数值计算问题数学模型是一组线性或非线性的代数方程组或微分方程组 非数字计算问题(包括管理、控制、数据处

2、理等)数学模型是数据结构,例1 书目自动检索系统,书目文件,例2 人机对奕问题,多叉路口交通灯管理问题,数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 1.1.2 为什么要学数据结构 程序设计的需要 计算机专业基础课 编译程序、操作系统、数据库系统和大型应用程序,1.1.3 学什么 掌握各种类型的数据结构 掌握查找和排序操作 学会用算法去处理问题 学会用C语言去实现算法 1.1.4 怎么学 重视实践环节，包括编程和上机,1.2 基本概念和术语 数据(data)所有能输入到计算机中去的描述客观事物的符号，数据是信息的载体 数据元素(data

3、 element)数据的基本单位，数据中的一个“个体” 数据项(data item)数据的最小单位，数据元素是数据项的组合，有组合项和原子项之分 数据对象(data object)性质相同的数据元素的集合，如整数、所有书目信息等 数据结构(data structure)数据元素和数据元素关系的集合，数据元素相同而关系不同的数据结构是不同的数据结构,数据结构的形式定义为： 数据结构是一个二元组Data_Structures = ( D,S ) 其中：D是数据元素的有限集，S是D上关系的有限集。,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现

4、,数据元素的实现 数值321 可用位串 101000001 表示，字母A可用位串 001000001 表示 关系的实现,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,不同的编程环境中，数据存储结构可有不同的描述方法： 以上用的是计算机的编码及内存来描述 还可用高级程序语言提供的数据类型来描述 关系 顺序存储结构 int Long_int3; 链式存储结构 int *Long_int3; 数据元素 Long_int0=4234;,1.3 抽象数据类型 数据类型(data type)一个值的集合和定义在此集合上的一组操作的总称 抽象数据类型(abstra

5、ct data type,ADT)一个数学模型以及定义在此数学模型上的一组操作 抽象不同语言不同处理器相同的数学特征（即已定义的数据类型） 设计软件时自定义的数据类型 ADT有两个重要特征： 数据抽象：用ADT描述程序处理的实体时，强调的是其本质特征和外界使用它的方法 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型包含定义、表示和实现三部分。 抽象数据类型的形式描述为：ADT = ( D，S，P )其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集。,typedef struct int num; char name20; f

6、loat score; STUDENT; STUDENT stu1,stu2, *p;,1.抽象数据类型的定义 ADT形式定义为：ADT 抽象数据类型名 数据对象： 数据对象的定义 数据关系： 数据关系的定义 基本操作： 基本操作的定义 ADT 抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以float imagpart; complex;/ 基本操作的函数原型说明void Assign( complex ,1.4 算法的描述和算法分析简介 算法

7、（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性,算法的描述采用类C语言 算法的评价衡量算法优劣的标准 正确性(correctness) 可读性(readability) 健壮性(robustness) 效率与低存储量,算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本 身的优劣 2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的

8、规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适,时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n)，表示随问题规模n的增大，算法执行时间的增长率和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; ,语句的频度：该语句重复执行的次数,除特别指明，若算法的执行时间依赖于特定的输入，则按最坏情况考虑 对时间复杂度而言，只需要取

9、最高项，并忽略常数系数,void bubble_sort(int a, int n)/ 将a中整数序列重新排列成自小至大有序的整数序列。for (i=n-1,change=TRUE;i1change = TRUE / bubble_sort算法执行次数随输入数据不同而不同，概率相等时考虑平均值，概率不明时考虑最坏情况。,#include main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); ,例2 对n个整数的序列进行起泡排序,时间复杂度均为O (n2) 。,空间复杂度：s(n)=o(f(n) 算法的储存量包括： 输入数据所占空间 程序本身所占空间 辅助变量所占空