第1章数据结构概念

1、1第一章 数据结构概念2 2第一章第一章 数据结构概念数据结构概念3 3 学学 号号 姓姓 名名 性别性别 籍籍 贯贯 出生年月出生年月 1 98131 刘激扬刘激扬 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 岛岛 1979.07 3 98165 卢声凯卢声凯 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 苏苏 州州 1980.03 7 98297 宫宫 力力 男男 北北 京京 1981.01 8 98310 蔡

2、晓莉蔡晓莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健 男男 杭杭 州州 1979.124 4 课程编号课程编号 课课 程程 名名 学时学时 024002 程序设计基础程序设计基础 64 024010 汇编语言汇编语言 48 024016 计算机原理计算机原理 64 024020 数据结构数据结构 64 024021 微机技术微机技术 64 024024 操作系统操作系统 48 024026 数据库原理数据库原理 485 5学生学生( (学号学号, ,姓名姓名, ,性别性别, ,籍贯籍贯) )课程课程( (课程号课程号, ,课程名课程名, ,学分学分) )选课选课( (学号学

3、号, ,课程号课程号, ,成绩成绩, ,时间时间) )6 6UNIX文件系统的系统结构图文件系统的系统结构图/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp7 7百度地图百度地图8 8数据（数据（datadata）n数据是数据是信息信息的载体，是描述客观事物的数、的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。机程序识别和处理的符号的集合。n数据的分类：数据的分类：u 数值性数据数值性数据u 非数值性数据非数值性数据9 9姓名姓名

4、 所在院系所在院系 性别性别 出生日期出生日期 年年 月月职务职务 业绩业绩数据元素数据元素 (data element)(data element)n数据的基本单位数据的基本单位。在计算机程序中常作为在计算机程序中常作为一个整体进行考虑和处理。一个整体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项 (Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小的最小标识单位。标识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。1010什么是数据结构什么是数据结构殷人昆殷人昆数据结构数据结构 : 由某一数据元素的集合

5、以及该集合由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记中所有数据元素之间的关系组成。记为：为： Data_Structure Data_Structure = D, R= D, R其中其中，D D 是某一数据元素的集合，是某一数据元素的集合，R R 是该集合中所有数据元素之间的关系是该集合中所有数据元素之间的关系的的有限有限集合集合nSartaj Sahni 数据结构、算法与应用数据结构、算法与应用：“数据结构是数据对象，以及存在于该对象数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的

6、函数联系。这些联系可以通过定义相关的函数来给出。来给出。” nClifford A.Shaffer 数据结构与算法分数据结构与算法分析析：“数据结构是数据结构是 ADT（抽象数据类型（抽象数据类型 Abstract Data Type） 的物理实现。的物理实现。” nLobert L.Kruse 数据结构与程序设计数据结构与程序设计：一个数据结构的设计过程分成抽象层、数据一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据运算，数

7、据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及结构的表示和在计算机内的存储细节以及运算的实现。运算的实现。 1414例：例：N N 个网点之间的连通关系个网点之间的连通关系 1561524362431515数据结构是数据的组织形式数据结构是数据的组织形式n包括三个方面：包括三个方面：u数据元素间的逻辑关系，即数据的数据元素间的逻辑关系，即数据的逻辑逻辑结构结构；u数据元素及其关系在计算机存储内的表数据元素及其关系在计算机存储内的表示，即数据的示，即数据的存储表示存储表示；u数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。1616数据的逻辑结构数据的逻辑结

8、构n数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，从逻辑关系上描述数据，与数据的存储无关与数据的存储无关；n数据的逻辑结构数据的逻辑结构可以看作是从具体问题抽可以看作是从具体问题抽象出来的数据模型；象出来的数据模型；n数据的逻辑结构数据的逻辑结构与数据元素本身的形式、与数据元素本身的形式、内容无关；内容无关；n数据的逻辑结构数据的逻辑结构与数据元素的相对存储位与数据元素的相对存储位置无关。置无关。1717数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构u 线性表线性表n非线性结构非线性结构u 树树u 图（或网络）图（或网络）1818线性结构线性结构树形结构树形结构树树 二叉树二叉树

9、二叉搜索树二叉搜索树bindevetclibuser141312112345678910315871011998745662313111919堆结构堆结构1235487111029164101211512369872020图结构图结构 网络结构网络结构125436113318146651619211256342121数据的存储结构数据的存储结构n数据的存储结构数据的存储结构是逻辑结构用计算机语言是逻辑结构用计算机语言的实现；的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表

10、示散列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示 顺序存储n需要一块连续的存储空间，并把逻辑上相需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区关的数据元素依次存储在该连续的存储区中中。 LocLoc（ak）1021022 2k k 地址信息称为链。地址信息称为链。 表示空链。表示空链。 链接存储数据结构的运算数据结构的运算数据结构最常见的运算数据结构最常见的运算 创建运算创建运算: :创建一个数据结构；创建一个数据结构； 清除运算清除运算: :删除数据结构中的全部元素；删除数据结构中的全部元素；插入

11、运算插入运算: :在数据结构的指定位置上插入一个新元在数据结构的指定位置上插入一个新元素；素；删除运算删除运算: :将数据结构中的某个元素删除；将数据结构中的某个元素删除； 2525抽象数据类型及面向对象概念抽象数据类型及面向对象概念n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合, 以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC语言中的数据类型语言中的数据类型字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 2626数据类型数据类型2727n数据类型数据类型由由基本数据类型基本数据类型或或构造数据类型构造数据类型

12、组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是计算机中已实现基本数据类型可以看作是计算机中已实现的数据结构。的数据结构。n数据类型就是数据结构，不过它是从编程数据类型就是数据结构，不过它是从编程者的角度来使用的。者的角度来使用的。n数据类型是模板，必须定义属于某种数据数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。类型的变量，才能参加运算。 2828抽象数据类型抽象数据类型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)n抽象数据类型是由用户定义，用以表示应抽象数

13、据类型是由用户定义，用以表示应用问题的数据模型。用问题的数据模型。n特点是：特点是：信息隐蔽信息隐蔽和和数据封装数据封装，使用与实使用与实现相分离现相分离。n抽象数据类型可用抽象数据类型可用（D, R, P）三元组表示，三元组表示，其中，其中，D 是数据元素的集合（简称数据对是数据元素的集合（简称数据对象），象），R 是是 D上的关系集合，上的关系集合，P 是对是对 D 的的基本操作集合。基本操作集合。 2929抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表3030抽象数据类型的描述抽象数据类型的描述n其中数据对象、数据之间的关系用伪码描其中数据对象、数据之间

14、的关系用伪码描述；基本操作定义格式为述；基本操作定义格式为ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名（参数表）基本操作名（参数表）前置条件：前置条件：先决条件描述先决条件描述后置条件：后置条件：操作结果描述操作结果描述3131n基本操作有两种参数：基本操作有两种参数：赋值参数赋值参数只为操作提只为操作提供输入值；供输入值；引用参数引用参数以以&打头，除可提供输打头，除可提供输入值外，还将返回操作结果。入值

15、外，还将返回操作结果。n “前置条件前置条件”描述了操作执行之前数据结描述了操作执行之前数据结构和参数应满足的先决条件，若不满足，则构和参数应满足的先决条件，若不满足，则操作失败，并返回相应出错信息。操作失败，并返回相应出错信息。n “后置条件后置条件”说明了操作正常完成之后，说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若前数据结构的变化状况和应返回的结果。若前置条件为空，则省略之。置条件为空，则省略之。3232自然数的抽象数据类型定义自然数的抽象数据类型定义ADT NaturalNumber isobjects: 一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,

16、结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function: 对于所有的对于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是等都是可用的服务。可用的服务。 Zero( ) : NaturalNumber /前置条件前置条件：无：无 /后置条件后置条件：返回自然数返回自然数03333IsZero(x) : Boolean /前置条件前置条件：x为为NaturalNumber /后置条件后置条件：if (x = 0) then 返回返回True else 返回返回False Add (x, y) : Nat

17、uralNumber /前置条件前置条件：x, y为为NaturalNumber且且x+yMaxInt /后置条件后置条件：返回返回 x+y Subtract (x, y) : NaturalNumber /前置条件前置条件： x, y为为NaturalNumber且且xy /后置条件后置条件：返回返回 x- - y3434Equal (x, y) : Boolean /前置条件前置条件： x, y为为NaturalNumber /后置条件后置条件： if (x = y) 返回返回True else 返回返回 False Successor (x) : NaturalNumber /前置条件前

18、置条件： x为为NaturalNumber /后置条件后置条件： if (x = MaxInt) 返回返回 x else 返回返回 x+1end NaturalNumber3535面向对象的概念面向对象的概念n面向对象面向对象 = = 对象类继承通信对象类继承通信n对象对象u在应用问题中出现的各种在应用问题中出现的各种实体实体、事件事件、规格说明规格说明等。等。u由一组由一组属性值属性值和在这组值上的一组和在这组值上的一组服务服务（或称操作）构成。（或称操作）构成。u与与C中构造数据类型不同在于：中构造数据类型不同在于：C中的构中的构造数据类型的变量仅涉及属性值，与操造数据类型的变量仅涉及属性

19、值，与操作分离，而作分离，而C+中的对象则不然。中的对象则不然。3636n类类 (class)，实例，实例 (instance)u具有相同属性和服务的对象归于同一类，具有相同属性和服务的对象归于同一类，形成类。形成类。u类中的对象为该类的实例。类中的对象为该类的实例。u同一类的实例同一类的实例 共享类的属性和类的操作；共享类的属性和类的操作； 通过继承共享其父类的公共的和保护通过继承共享其父类的公共的和保护性的属性和操作；性的属性和操作； 同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。3737四边形类及其对象四边形类及其对象属性aPoint1 aPoint2aPoint3 a

20、Point4服务服务Draw( )move(x, y)contains(aPoint)属性值属性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服务服务服务服务quadrilateral3838n继承继承u派生类（子类）：派生类（子类）：四边形，三角形，四边形，三角形，u基类（父类）：基类（父类）：多边形多边形派生类派生

21、类继承的特性继承的特性+特有的特性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形3939n通信通信u消息传递消息传递uC+中消息传递的方式：中消息传递的方式：操作含于类中操作含于类中 定义：定义：Point p; void move(int x, inty); 使用：使用：p.move(x, y);uC中则不同，需使用函数调用方式：中则不同，需使用函数调用方式： 定义：定义：Point p; void move(Point q, int x, inty); 使用：使用：move(p, x, y);4040Draw( )move(x, y)contains(aPoint)Po

22、lygonreferencePointVerticesPolygon 类类referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral4141算法定义算法定义n定义：定义： 笼统笼统的说，算法是求解一类问题的任意一的说，算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述，它是指令的特定问题的求解步骤的一种描述，它是指令的有限有限序列。序列。4242算法定义算法定义n特性：特性：u输

23、入输入 有有0个或多个输入个或多个输入u输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)u确定性确定性 每步定义都是确切无歧义的每步定义都是确切无歧义的u有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束u有效性有效性 每一条运算应足够基本每一条运算应足够基本程序程序 = 数据结构数据结构+算法算法43434444n事例学习：事例学习：选择排序问题选择排序问题n明确问题：明确问题：递增排序递增排序n解决方案：解决方案：逐个选择最小数据逐个选择最小数据n算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 从从ai检查到检查到an-1

24、; 若最小整数在若最小整数在ak, 交换交换ai与与ak; 算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 4545细化程序：细化程序：程序程序 SelectSort void selectSort ( int a , const int n ) /对n个整数a0,a1,an-1按递增顺序排序 for (int i = 0; i n-1; i+) int k = i; /从ai查到an-1, 找最小整数, 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; /记录最小的值if(k!=i) int temp = ai; ai = ak; ak

25、 = temp; 4646算法简单性能分析与度量算法简单性能分析与度量4747算法的性能标准算法的性能标准(Correctness ) 算法应满足具体问题算法应满足具体问题的需求。的需求。(Readability) 算法应该容易阅读。算法应该容易阅读。以有利于阅读者对程序的理解。以有利于阅读者对程序的理解。效率指的是算法执行的时间和空间利效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。用率。通常这两者与问题的规模有关。(Robustness) 算法应具有容错处理算法应具有容错处理的功能。当输入非法数据时，算法应对其作的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名

26、其妙的输出结果。出反应，而不应产生莫名其妙的输出结果。4848算法的后期测试算法的后期测试n对一个算法要作出全面的分析可分成两个阶对一个算法要作出全面的分析可分成两个阶段进行，即段进行，即事前分析事前分析和和事后测试事后测试n事前分析事前分析要求事前求出该算法的一个时间界要求事前求出该算法的一个时间界限函数。限函数。n事后测试事后测试则要求在算法执行后通过算法执行则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。的时间和实际占用空间的统计资料来分析。n事后分析要求在算法中的某些部位插装时间事后分析要求在算法中的某些部位插装时间函数函数 time ( )，4949例如，给出顺序

27、搜索例如，给出顺序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索与给定值 x 相等的元/素，函数返回其位置，失败返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;5050 插装插装 time( ) 的计时程序的计时程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double r

28、unTime = stop - start; cout n runTime endl;事实上，算法运行时间要受事实上，算法运行时间要受输入规模、利用输入规模、利用编译程序生成的目标代码的质量、计算机编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。程序指令系统的品质和速度等制约。5151程序在计算机上运行所消耗的时间与下列因程序在计算机上运行所消耗的时间与下列因素有关：素有关：（1 1）书写算法的程序设计语言；）书写算法的程序设计语言；（2 2）代码书写的质量；）代码书写的质量；（3 3）编译产生的机器语言代码质量；）编译产生的机器语言代码质量；（4 4）机器执行指令的速度；

29、）机器执行指令的速度；（5 5）问题的规模，即算法的时间效率与算法）问题的规模，即算法的时间效率与算法处理的数据个数处理的数据个数n n的关系。的关系。5252算法的事前估计算法的事前估计n算法的事前估计主要包括时间复杂性和空算法的事前估计主要包括时间复杂性和空间复杂性的分析：间复杂性的分析：u问题的规模：问题的规模：如：矩阵的阶数、图的结如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。点个数、被分类序列的正整数个数等。u时间复杂性时间复杂性：算法所需时间和问题规模：算法所需时间和问题规模的函数，记为的函数，记为 T(n)。当当 n 时的时间时的时间复杂性，称为复杂性，称为渐进时间复杂

30、性渐进时间复杂性。u空间复杂性空间复杂性：算法所需空间和问题规模：算法所需空间和问题规模的函数。记为的函数。记为 S(n)。当当 n 时的时间时的时间复杂性，称为复杂性，称为渐进空间复杂性渐进空间复杂性。5353空间复杂度度量空间复杂度度量5454时间复杂度度量时间复杂度度量5555n程序步确定方法程序步确定方法u插入计数全局变量插入计数全局变量countu建表，建表，列出个语句的程序步列出个语句的程序步例例 以迭代方式求累加和的函数以迭代方式求累加和的函数 float sum (float a , int n) float s = 0.0; for (int i = 0; i n; i+)

31、s = s + ai; return s; 5656在求累加和程序中加入在求累加和程序中加入 count 语句语句 float sum (float a , int n) float s = 0.0; count+; /count 统计执行语句条数 for (int i = 0; i n; i+) count +; /针对 for 语句 count +; s += ai;count+; /针对赋值语句 count +; count +; /针对 for 的最后一次 count+; /针对 return 语句 return s; 执行结束得执行结束得 程序步数程序步数 count = 3*n+4

32、5757计算累加和程序计算累加和程序程序步数计算工作表格程序步数计算工作表格5858注意注意： 一个语句本身的程序步数可能不等于该语一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。句一次执行所具有的程序步数。 例如：例如：赋值语句赋值语句x = sum (R, n) 本身程序步数为本身程序步数为 1；一次执行对函数一次执行对函数 sum (R, n) 的调用需要的程的调用需要的程序步数为序步数为 3*n+4；一次执行的程序步数为一次执行的程序步数为 1+3*n+4 = 3*n+55959程序程序步练习步练习习题：求两个习题：求两个n阶方阵的乘积阶方阵的乘积C = A Bvoid

33、 MatrixMultiply (int Ann, int Bnn,int Cnn) for (int i = 0; i n; i+) for (int j = 0; j n; j+) Cij = 0; for (int k = 0; k n; k+) Cij = Cij + Aik * Bkj; 6060时间复杂度的渐进表示法时间复杂度的渐进表示法n算法中所有语句的频度之和是算法中所有语句的频度之和是n的函数的函数 T(n) = 3n3 + 5n2 + 4n +2n一般地，称一般地，称 n 是问题的规模。则时间复杂是问题的规模。则时间复杂度度 T(n) 是问题规模是问题规模 n 的函数。的函

34、数。n当当n趋于无穷大时，把时间复杂度的趋于无穷大时，把时间复杂度的数量级数量级（阶）称为算法的渐进时间复杂度（阶）称为算法的渐进时间复杂度 T(n) = O(n3) 大大O表示法表示法6161n加法规则加法规则 针对并列程序段针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)n各种函数的增长趋势各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n!6262T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n;

35、 i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;6363n乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n两个并列循环的例子两个并列循环的例子6464 void exam (float *x, int m, int n) float *sum = new float m; for (int i = 0; i m; i+)

36、 /x中各行 sumi = 0.0; /数据累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行数据和 cout i “ : ” sum i endl; delete sum; O(max (m*n, m)6565 void main () float *x; int m=5,n=6; x= new float *m; for(int j=0;jm;j+) xj= new float n; int j=0; for(int i=0;im;i+) for(int k=0;kn;k+) xik=j+; exam(x,

37、m,n); 6666起泡排序起泡排序 void bubbleSort (int a , int n ) /对表 a 逐趟比较, n 是表当前长度 for (int i = 1; i = i; j-) /n-i次比较 if (aj-1 aj) int tmp = aj-1; aj-1 = aj;aj = tmp; /一趟比较 6767 O(f (n)*g (n) = O(n2) 1121ccni)n(ni)(nBubblrSort 外层循环外层循环 n-1 趟趟内层循环内层循环 n-i 次比较次比较6868n渐进的空间复杂度渐进的空间复杂度 S (n) = O(f (n)for (i=1;i=n

38、;i=2*i)couti; /基本语句基本语句的执行次数f(n)，则2f(n)=n,因此f(n)=lb n T(n)= O(lb n)6969for (i=1; i=n;i+)for (j=1;j=i;j+)coutj;基本语句执行次数 nT(n)= O(n2)7070niniijnninf1112) 1(1)(for (i=1; i=n;i+)for (j=1;j=i;j+)for (k=1;k=j;k+) cout= 0 & Ai != k) i-; return i;n算法的语句算法的语句 i- 的频度不仅与的频度不仅与 n 有关，还与有关，还与 A 中各元素的取值中各元素的取值以及以及

39、 k 的取值的取值有关。有关。本章重点本章重点：n1数据结构的概念n2抽象数据类型n3算法和算法性能分析73737474模板模板 (template)(template)定义定义 适合适合多种数据类型多种数据类型的的类定义类定义或或算法算法，在特，在特定环境下通过简单地代换，变成定环境下通过简单地代换，变成针对具体某针对具体某种数据类型种数据类型的的类定义类定义或或算法。算法。7575用模板定义用于排序的数据表类用模板定义用于排序的数据表类#ifndef DATALIST_H#define DATALIST_H#include template / /E是表项类型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);7676 public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); frien