《高等数据结构与算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《高等数据结构与算法优秀PPT.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、高等数据结构与算法第一页，本课件共有26页教材：数据结构(C语言版)严蔚敏 清华大学出版社参考书：数据结构使用C语言 朱战立 西安交通大学出版社数据结构与算法 齐德昱 清华大学出版社数据结构与算法C+版(第2版)Adam Drozdek 清华大学出版社课程与考试安排：第8、11、12章不作要求有*号的小节不作要求期末成绩和平时成绩各占60和40第二页，本课件共有26页第一章 绪言1.1.1 什么是数据结构程序设计=数据模型+算法程序设计：为计算机处理问题编制的一组指令集数据模型：现实问题的抽象算法：处理问题的策略数值计算问题数学模型是一组线性或非线性的代数方程组或微分方程组非数字计算问题(包括
2、管理、控制、数据处理等)数学模型是数据结构第三页，本课件共有26页例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表第四页，本课件共有26页例2 人机对奕问题树.第五页，本课件共有26页多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图第六页，本课件共有26页数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科1.1.2 为什么要学数据结构程序设计的需要计算机专业基础课v编译程序、操作系统、数据库系统和大型应用程序第七页，本课件共有2
3、6页1.1.3 学什么掌握各种类型的数据结构掌握查找和排序操作学会用算法去处理问题学会用C语言去实现算法1.1.4 怎么学重视实践环节，包括编程和上机第八页，本课件共有26页1.2 基本概念和术语数据(data)所有能输入到计算机中去的描述客观事物的符号，数据是信息的载体数据元素(data element)数据的基本单位，数据中的一个“个体”数据项(data item)数据的最小单位，数据元素是数据项的组合，有组合项和原子项之分数据对象(data object)性质相同的数据元素的集合，如整数、所有书目信息等数据结构(data structure)数据元素和数据元素关系的集合，数据元素相同而关
4、系不同的数据结构是不同的数据结构第九页，本课件共有26页根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图数据结构的形式定义为：数据结构是一个二元组Data_Structures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。第十页，本课件共有26页数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：顺序存储结构借助元
5、素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系数据元素的实现数值321 可用位串 101000001 表示，字母A可用位串 001000001 表示关系的实现第十一页，本课件共有26页元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储第十二页，本课件共有26页1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存存储地址地址 存存储内容内容
6、指指针 1345 元素元素1 1400 1346 元素元素4 .1400 元素元素2 1536 .1536 元素元素3 1346 链式存储链式存储 h第十三页，本课件共有26页不同的编程环境中，数据存储结构可有不同的描述方法：不同的编程环境中，数据存储结构可有不同的描述方法：v以上用的是计算机的编码及内存来描述v还可用高级程序语言提供的数据类型来描述关系顺序存储结构 intLong_int3;链式存储结构 int*Long_int3;数据元素Long_int0=4234;第十四页，本课件共有26页1.3 抽象数据类型数据类型(data type)一个值的集合和定义在此集合上的一组操作的总称抽象
7、数据类型(abstract data type,ADT)一个数学模型以及定义在此数学模型上的一组操作l抽象不同语言不同处理器相同的数学特征（即已定义的数据类型）l设计软件时自定义的数据类型vADT有两个重要特征：l数据抽象：用ADT描述程序处理的实体时，强调的是其本质特征和外界使用它的方法l数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节第十五页，本课件共有26页抽象数据类型包含定义、表示和实现三部分。抽象数据类型的形式描述为：ADT=(D，S，P)其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集。typedefstructintnum;c
8、harname20;floatscore;STUDENT;STUDENTstu1,stu2,*p;第十六页，本课件共有26页1.抽象数据类型的定义ADT形式定义为：ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名基本操作名（参数表）（参数表）初始条件：初始条件：初始条件描述操作结果：操作结果：操作结果描述基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件描述了操作执行之前数据结构和
9、参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则可省略之。操作结果操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。第十七页，本课件共有26页例：抽象数据类型复数的定义为：ADT Complex 数据对象：数据对象：D=e1,e2|e1,e2RealSet数据关系：数据关系：R1=|e1是复数的实部，e2是复数的虚部 基本操作：基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)初始条件：复数已存在。操作结果：复数Z被销毁。GetReal(Z,&re
10、alPart)初始条件：复数已存在。操作结果：用 realPart 返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用 ImagPart 返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1，z2 是复数。操作结果：用sum返回两个复数z1，z2的和值。ADT Complex第十八页，本课件共有26页2.抽象数据类型的表示和实现抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现。第十九页，本课件共有26页例：利用C语言实现的复数类型如下描述：/存储结构的定义存储结构的定义typedef struct fl
11、oat realpart;float imagpart;complex;/基本操作的函数原型说明基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval);/构造复数 Z，其实部和虚部分别被赋以参数 realval 和 imagval 的值void add(complex z1,complex z2,complex&sum);/以 sum 返回两个复数 z1，z2 的和/基本操作的实现void add(complex z1,complex z2,complex&sum)/以 sum 返回两个复数 z1，z2 的和sum.realp
12、art=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;第二十页，本课件共有26页1.4 算法的描述和算法分析简介算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性算法的描述采用类C语言算法的评价衡量算法优劣的标准v正确性(correctness)v可读性(readability)v健壮性(robustness)v效率与低存储量第二十一页，本课件共有26页算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统
13、计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本 身的优劣 2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适第二十二页，本课件共有26页l时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n)，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同例1：NXN矩阵相乘for(i=1;i=n;i+)for(
14、j=1;j=n;j+)cij=0;for(k=1;k1&change;-i)change=FALSE;for(j=0;jaj+1)w=aj;aj=aj+1;aj+1=w;change=TRUE/bubble_sort算法执行次数随输入数据不同而不同，概率相等时考虑平均值，概率不明时考虑最坏情况。#includemain()inta11,i,j,t;printf(Input10numbers:n);for(i=1;i11;i+)scanf(%d,&ai);printf(n);for(j=1;j=9;j+)for(i=1;iai+1)t=ai;ai=ai+1;ai+1=t;printf(Theso
15、rtednumbers:n);for(i=1;i11;i+)printf(%d,ai);例例2对n个整数的序列进行起泡排序时间复杂度均为O(n2)。第二十四页，本课件共有26页l空间复杂度：s(n)=o(f(n)l算法的储存量包括：u输入数据所占空间u程序本身所占空间u辅助变量所占空间l若所需辅助空间相对输入数据量来说是常量，则称为原地工作算法l若算法所需存储量依赖于特定的输入，则按最坏情况考虑第二十五页，本课件共有26页练习一.确定每个语句的频度，分析算法的时间复杂度1.i=1;while(i=n)i=i*2;2.k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;第二十六页，本课件共有26页