数据结构与算法设计PPT (2).pdf

《数据结构与算法设计PPT (2).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (2).pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 绪论1.3 抽象数据类型及其表示定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.-数据类型中值的特征-数据在存储器中的编码形式-存储空间的大小和值的范围-对数据可以进行的运算种类基本数据类型int x=100,y=200;int z1=x+y;int z2=x*y;int z3=x%y;C语言中的数据类型char int float double void字符型 整型 浮点型 双精度型 无值int x x可以进行多少种运算?基本数据类型 高级语言的数据类型使我们编写代码时不必考虑每一种数据在计算机内部的表示细节和运算的实现细节 可以直接按照数据类型的外部抽象数据特

2、征来使用数据，方便了程序设计 信息封装是计算机硬件系统和软件系统中使用的基本原则，信息封装可以简化用户对概念的理解。用户在使用数据类型时，可以不必了解内部的实现细节。基本数据类型 复合数据类型是由基本数据类型组合而成的数据类型.复合数据类型本身又可以参与定义结构更为复杂的数据元素类型 数据元素的类型不限于基本数据类型，也可以根据应用需要灵活进行定义数据元素的类型：复合数据类型class studentstring number;string name;date birthday;int class;int grade;string colleage;string major;public:st

3、udent();void set();void modify();void display()const;student();数据元素的类型：复合数据类型class studentstring number;string name;date birthday;int class;int grade;string colleage;string major;public:student();void set();void modify();void display()const;student();抽象：简化问题，忽略非本质问题，目的是隐藏实现细节和内部数据结构，提高复用的力度和粒度 用户定义，

4、用以表示应用问题的数据模型 由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离抽象数据类型(ADTs:Abstract Data Types)数据类型的定义只涉及数据模型的逻辑特征，不涉及该模型的具体实现细节 不管内部采用什么技术方法来实现这个抽象数据类型，只要模型的数学特性不变，都不会影响它的外部使用。抽象的目的就是让人们集中精力把握问题的实质，研究解决问题的算法核心，抛开繁复的实现细节，从而使得问题得到简化 抽象可以按照一定的层次逐步提高，抽象的程度，层次越高细节就越少，使用就越方便。抽象数据类型(ADTs:Abstract Data Types)抽

5、抽象象数数据据类类型型查找插入删除修改学 生 记 录 由三元组表示ADT抽象数据类型名数据对象D数据关系S数据操作P 用数学方法定义对象集合和运算集合，仅通过运算的性质刻画数据对象，独立于计算机中的可能的表示方法 本课程中用C的template表示抽象数据类型 模板重点描述数据元素之间的关系、存储方式和对数据的操作ADT的格式template class dataList private:Type*Element;int ArraySize;void Swap(const int m1,const int m2);int MaxKey(const int low,const int high)

6、;模板参数为数据表中元素的类型数据表模板类的定义定义数据结构的取值类型和取值空间定义数据结构存储方式public:dataList(int size=10):ArraySize(size),Element(new Type Size)dataList()delete Element;void Sort();friend ostream&operator (ostream&outStream,const datalist&outList);friend istream&operator (istream&inStream,const datalist&inList);#endif定义对数据的操作

7、 模板重点描述数据元素之间的关系、存储方式和对数据的操作 只是一种概念类型，不能进行编译 抽象数据类型只有实现之后才能被使用 实现过程要设计存储结构、编写实现源程序 是使用者和编程者之间的约定形式ADT形式化说明本课程中编程使用的本课程中编程使用的C+C+技术技术动态存储分配动态存储分配深复制和浅复制深复制和浅复制模板模板STLSTLC C中中malloc()malloc()和和free()free()C+C+中中newnew和和deletedeletenewnew按指定类型自动分配足够的空间按指定类型自动分配足够的空间newnew自动返回指定类型的指针自动返回指定类型的指针newnew和和d

8、eletedelete可以重载可以重载动态存储空间的管理需要注意的问题动态存储空间的管理需要注意的问题C+C+没有垃圾收集机制，不再使用的动态存储没有垃圾收集机制，不再使用的动态存储空间一定要由程序员采用空间一定要由程序员采用deletedelete方式回收方式回收C+C+的动态存储分配的动态存储分配例例1 1：int*int*ip ip=new int;=new int;if(if(ip ip=0)=0)cerrcerr “Memory not allocated”“Memory not allocated”endlendl;例例2 2：point*p=new point 100;point

9、*p=new point 100;delete delete p;p;C+的动态存储分配deletedelete的指针只能是的指针只能是newnew申请到的申请到的如果是数组，必须用如果是数组，必须用delete delete 删除删除深复制和浅复制I内部数据：蕴含在结构之中，例如：内部数据：蕴含在结构之中，例如：class Teacherclass Teacher string*string*firstnamefirstname;string*string*lastnamelastname;int int employeeNumemployeeNum;I外部数据：位于结构之外，通过指针加以访

10、问外部数据：位于结构之外，通过指针加以访问默认复制是复制指针而不是指针指向的数据默认复制是复制指针而不是指针指向的数据n浅复制：指针的复制浅复制：指针的复制n深复制：复制指针所指向的数值深复制：复制指针所指向的数值需要重载复制运算符需要重载复制运算符String*fiirstnameString*lastnameint employeeNum模板（模板（TemplateTemplate）I模板：允许编写对任意类型均有效的函数例程，模板：允许编写对任意类型均有效的函数例程，而无需知道具体的类型而无需知道具体的类型I模板分类：函数模板模板分类：函数模板类模板类模板I模板的使用：模板的使用：在编写与

11、类型无关的算法或所谓的通用算法时在编写与类型无关的算法或所谓的通用算法时采用模板的方式编写程序可以取得更广泛的应采用模板的方式编写程序可以取得更广泛的应用效果用效果函数模板可以用来创建一个通用功能的函数，函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的以支持多种不同形参，进一步简化重载函数的函数体设计。函数体设计。定义形式：定义形式：模板类定义中只有一个函数的定义模板类定义中只有一个函数的定义定义方法：定义方法：template 函数定义函数模板的定义用模板定义用于排序的数据表用模板定义用于排序的数据表(dataListdataList)类类template c

12、lass dataList private:Type*Element;int ArraySize;void Swap(const int m1,const int m2);int MaxKey(const int low,const int high);声明一个模版类public:dataList(int size=10):ArraySize(size),Element(new Type Size)dataList()delete Element;void Sort();friend ostream&operator (ostream&outStream,const datalist&outL

13、ist);friend istream&operator (istream&inStream,const datalist&inList);template void dataList:Sort()/按非递减顺序对ArraySize个关键码/Element0ElementArraySize-1排序。for(int i=ArraySize-1;i 0;i-)int j=MaxKey(0,i);if(j!=i)swap(j,i);使用模板的选择排序算法的主函数使用模板的选择排序算法的主函数#includeinclude“selecttm.h”const intconst intSIZE=10;in

14、tintmain()dataListTestList(SIZE);cincin TestList;coutcout“Testing Selection Sort:n”TestList endlendl;TestList.Sort();coutcout“After sorting:n”TestList endlendl;returnreturn0;标准模板库标准模板库-STL STL 是是C+C+的一个的一个通用库通用库，它提供了许多大部分，它提供了许多大部分程序通用的组件，这些组件灵活有效，提高了编程程序通用的组件，这些组件灵活有效，提高了编程的效率。的效率。STL STL 组件都是模板。组件

15、都是模板。-STLSTL提供了许多基本算法，数据结构，主要包括三提供了许多基本算法，数据结构，主要包括三方面：方面：ContainersContainersIteratorsIteratorsAlgorithmsAlgorithmsSTL(Standard Template Library)ContainersContainersSTLSTL容器的头文件，名字就是容器的类型名称容器的头文件，名字就是容器的类型名称1:#include /strings 1:#include /strings 2:#include /arrays 2:#include /arrays 3:#include /cy

16、clic doubly linked lists3:#include /cyclic doubly linked lists4:#include /hybrid list/array 4:#include /hybrid list/array 5:#include /queue 5:#include /queue 6:#include /stack 6:#include /stack 7:#include 7:#include /bit /bit-vectors vectors 8 8:#include /general sets:#include /general sets 9 9:#inc

17、lude /associative arrays:#include /associative arrays1:1:#include#include /complex numbers/complex numbers 2:2:#include#include /numerical arrays/numerical arrays 3:3:#include#include /numerical algorithms/numerical algorithms 4 4:#include:#include /math functions/math functions 数值计算头文件STLSTL的扩展头文件的

18、扩展头文件1:1:#include#include /hash set 2:2:#include#include /hash map/hash map 3:3:#include#include /singly linked list Listing/singly linked list Listing STLSTL中中iteratorsiterators提供了提供了ContainersContainers和和AlgorithmsAlgorithms之之间的接口，与指针相似。间的接口，与指针相似。例如：例如：itritr+、*itritr运算运算Iterators/Traversing a co

19、ntainer using iterators string A=This is a string;string:iterator it;/create iteratorfor(it=A.begin();it!=A.end();+it)cout *it endl;STLSTL中中的的核心核心是算法。由是算法。由于于容器和算法之间通过容器和算法之间通过迭代迭代器器联联系系起来起来，所以算法可以，所以算法可以脱离脱离容器容器来来写写如排如排序算法序算法template class template void void sortsort(R RandomIteratorandomIterator b

20、eginbegin,R RandomIteratorandomIterator endend)template class template Comparatorvoidvoid sortsort(R RandomIteratorandomIterator beginbegin,R RandomIteratorandomIterator endend,Comparator Comparator lessThanlessThan)算法（算法（AlgorithmsAlgorithms）#include#include#include#include using namespace std;int

21、main(int argc,char*argv)string s=This is a test;cout s endl;/replace spaces with hyphens replace(s.begin(),s.end(),-);cout s endl;/reverse the stringreverse(s.begin(),s.end();cout s endl;return EXIT_SUCCESS;n数据类型是高数据类型是高级语言中级语言中提供的基本数据存储和操提供的基本数据存储和操作的方法作的方法；n抽象数据类型是用抽象数据类型是用户户定定义义的，用的，用于解决于解决实实际问题际问题的的复合复合数据类型和操作方法数据类型和操作方法；n一一般般用数据对象、关系和操作三元组描述抽象数用数据对象、关系和操作三元组描述抽象数据类型据类型；n模板模板等等是需要是需要常常用的编程用的编程技术；技术；nSTLSTL是实是实际际应用应用中中要使用的数据类型。要使用的数据类型。小结