什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义.ppt

《什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义.ppt》由会员分享，可在线阅读，更多相关《什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn 什么是数据结构什么是数据结构n 抽象数据类型及面向对象概念抽象数据类型及面向对象概念n 模板模板n 算法定义算法定义n 算法性能分析与度量算法性能分析与度量Chapter 1 基本概念和算法分析 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES1.1 什么是数据结构什么是数据结构n数据：数据是信息的载体，是描

2、述客观事物的数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。算机程序识别和处理的符号的集合。P.2 数值数据数值数据, 非数值性数据非数值性数据n数据对象：数据的子集。具有相同性质的数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。成员（数据元素）的集合。整数数据对象整数数据对象 N = 0, 1, 2, 学生数据对象学生数据对象 Department of Computer Science & Technology, Nanjing University fallDATA

3、 STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES如：如： 152643152643 复数的数据结构定义如下：复数的数据结构定义如下： Complex=(C，R)C是包含两个实数的集合是包含两个实数的集合C1，C2R=P，P是定义在集合上的一种关系是定义在集合上的一种关系C1，C2。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES数据结构

4、是数据的组织形式n包括三个方面：包括三个方面：u数据元素间的逻辑关系，即数据的数据元素间的逻辑关系，即数据的逻辑结构逻辑结构；u数据元素及其关系在计算机存储内的表示，即数数据元素及其关系在计算机存储内的表示，即数据的据的存储表示存储表示；u数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES相关：相关： 逻辑结构逻辑结构 物理结构物理结构 相关操作相关操作 实现实现 Department of Computer

5、 Science & Technology, Nanjing University fallDATA STRUCTURES数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据，与数据数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；的存储无关；n数据的逻辑结构可以看作是从具体问题抽象出来数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；的数据模型；n数据的逻辑结构与数据元素本身的形式、内容无数据的逻辑结构与数据元素本身的形式、内容无关；关；n数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构与数据元素的相对存储位置无关。 Department of Computer Scienc

6、e & Technology, Nanjing University fallDATA STRUCTURES数据的逻辑结构分类n线性结构线性结构u 线性表线性表n非线性结构非线性结构u 树树u 图（或网络）图（或网络） Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES线性结构bindevetclibuser Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES树形结

7、构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树14131211234567891031587101199874566231311 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES堆结构123548711102916410121151236987 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES图结构图结构 网络结构网络结构125436113318146651

8、61921125634 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES数据的存储结构n数据的存储结构是逻辑结构用计算机语言的数据的存储结构是逻辑结构用计算机语言的实现；实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存 (文文件件) 的存储表示的存储表示 Department

9、of Computer Science & Technology, Nanjing University fallDATA STRUCTURES1.2 抽象数据类型及面向对象概念抽象数据类型及面向对象概念 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例：自然数的抽象数据类型定义例：自然数的抽象数据类型定义 (P.8)一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0, 结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。 Department o

10、f Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES1.3 模板模板 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES(dataList) #ifndef DATALIST_H #define DATALIST_H #inc

11、lude template class dataList private: Type *Element; int ArraySize; void Swap (const int m1, const int m2); int MaxKey (const int low, const int high); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES public: dataList (int size = 10) : ArraySize (size), Element (ne

12、w Type Size) dataList ( ) delete Element; void Sort ( ); friend ostream& operator (ostream& outStream, const datalist& outList); friend istream& operator (istream& inStream, const datalist& inList); ; #endif Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES #ifndef

13、SELECTTM_H #define SELECTTM_H #include “datalist.h” template void dataList : Swap (const int m1, const int m2) Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES template int dataList: MaxKey (const

14、int low, const int high) int max = low; for (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return max; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES template ostream&operator (ostream& OutStream, const dataList OutList) OutStream “Array Conten

15、ts : n”; for (int i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “Array Current Size : ” OutList.ArraySize endl; return OutStream; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES template istream& operator (istream& InStream,

16、 dataList InList) cout InList.ArraySize; cout “Enter array elements : n”; for (int i = 0; i InList.ArraySize; i+) cout “Elememt” i InList.Elementi; return InStream; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES template void dataList:Sort ( ) for ( int i = Array

17、Size -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) swap (j, i); #endif Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES #include “selecttm.h” const int SIZE = 10; int main ( ) dataList TestList (SIZE); cin TestList; cout “Testing Selection Sort : n” TestList e

18、ndl; TestList.Sort ( ); cout “After sorting : n” TestList endl; return 0; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES定义定义： 是对特定问题求解步骤的一种描述，是对特定问题求解步骤的一种描述，算法是算法是指令指令的的有限有限序列，其中每一条指令表示序列，其中每一条指令表示一个或多个操作。一个或多个操作。l特性特性：u输入输入u输出输出u确定性确定性u有穷性有穷性 u有效性有效性1.4 算法定义算法定

19、义 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例：选择排序问题例：选择排序问题n 算法框架：算法框架：初始值初始值ak for ( int i = 0; i n-1; i+ ) /n-1趟趟 从从ai检查到检查到an-1;若最小的整数在若最小的整数在ai, 交换交换ai与与ak; 细化程序：程序细化程序：程序 SelectSort Department of Computer Science & Technology, Nanjing University fallDAT

20、A STRUCTURES 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; /k指示当前找到的最小整数指示当前找到的最小整数 int temp = ai; ai = ak; ak = temp; /交换交换ai与与ak Department

21、of Computer Science & Technology, Nanjing University fallDATA STRUCTURES四个层次：四个层次：程序不含语法错误程序不含语法错误;程序对于几组输入数据能够得出满足规格程序对于几组输入数据能够得出满足规格说明要求的结果说明要求的结果;程序对于精心选择的典型、苛刻而带有刁程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说难性的几组输入数据能够得出满足规格说明要求的结果明要求的结果;程序对于一切合法的输入数据都能产生满程序对于一切合法的输入数据都能产生满足规格说明要求的结果。足规格说明要求的结果。1.5 算法性

22、能分析与度量算法性能分析与度量l 正确性正确性 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES 可使用性可使用性 可读性可读性 健壮性健壮性(鲁棒性鲁棒性) 效率效率 时间代价时间代价空间代价空间代价 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing Un

23、iversity fallDATA STRUCTURES后期测试后期测试事前估计事前估计 空间复杂性度量空间复杂性度量 时间复杂性度量时间复杂性度量算法效率的度量：算法效率的度量： Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES一般算法在执行期间所需要的存储量一般算法在执行期间所需要的存储量应该包括以下应该包括以下3个部分：个部分：（1）输入数据所占用的空间）输入数据所占用的空间（2）程序代码所占用的空间）程序代码所占用的空间（3）辅助变量所占用的空间）辅助变量所占用的空间算

24、法空间复杂度度量算法空间复杂度度量 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例例1：求表达式：求表达式a+b+b*c+(a+b-c)/(a+b)+4.0float abc (float a, float b, float c ) return a+b+b*c+(a+b-c)/(a+b)+4.0例例2: 以迭代方式求累加和以迭代方式求累加和 float sum ( float a , const int n ) float s = 0.0; for ( int i = 0

25、; i n; i+ ) s += ai; return s; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例例3.3.递归实现累加和递归实现累加和float rsum(float a ,const int n) if (n=0) return 0; else return rsum(a,n-1)+an-1)空间复杂度是指当问题的规模以某种空间复杂度是指当问题的规模以某种单位从单位从1增加到增加到n时，解决这个问题的时，解决这个问题的算法在执行时所占用的存储空间也以算法在执行

26、时所占用的存储空间也以某种单位由某种单位由1增加到增加到S（n）-P.27 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn运行时间运行时间u程序步程序步语法上或语义上有意义的一段指令序列语法上或语义上有意义的一段指令序列执行时间与实例特性无关执行时间与实例特性无关例如：例如： 注释：程序步数为注释：程序步数为0 声明语句：程序步数为声明语句：程序步数为0 表达式：程序步数为表达式：程序步数为1， return a+b+b*c算法的时间复杂度度量算法的时间复杂度度量 Depa

27、rtment of Computer Science & Technology, Nanjing University fallDATA STRUCTURES 赋值语句赋值语句 = 循环语句（循环控制部分，执行语句）循环语句（循环控制部分，执行语句）for(;)while dodo while switch 语句语句 if then函数执行语句：函数执行语句：动态存储管理：动态存储管理：new delete sizeof( )转移语句：转移语句：continue,break,goto,return Department of Computer Science & Technology, Nan

28、jing University fallDATA STRUCTURES float sum ( float a , const int n ) 1 2 float s = 0.0; 3 for ( int i = 0; i n; i+ ) 4 s += ai; 5 return s; 6 程序步确定方法程序步确定方法 插入计数全局变量插入计数全局变量countcount Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESfloat sum ( float a , const in

29、t n ) float s = 0.0; count+; /count统计执行语句条数统计执行语句条数 for ( int i = 0; i = n0 时，时，T(n)=cf(n), 则记为则记为T(n)=O(f(n) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer

30、 Science & Technology, Nanjing University fallDATA STRUCTURES例例: (线性函数线性函数)考察考察f(n)=3n+2例例: 平方平方函数函数考察考察f(n)=10n2+4n+2 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn例：设有两个算法在同一机器上运行，其执例：设有两个算法在同一机器上运行，其执行时间分别为行时间分别为 100n2 和和 2n，问：要使前者快，问：要使前者快于后者，于后者，n 至少要取多大？至少

31、要取多大？ 解答：解答： 问题是找出满足问题是找出满足 100n2 2n = 8192 n = 14时，时，100n2 = 19600 2n = 16384 n = 15时，时，100n2 = 22500 2n = 32764 取取 n = 15 满足要求。满足要求。启示启示 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESc log2n n nlog2n n2 n3 2n 3n n!大大O表示法下表示法下: Department of Computer Science & T

32、echnology, Nanjing University fallDATA STRUCTURES使用大（使用大（O）表示法：）表示法： 对于多项式，我们只保留最高次幂的项，对于多项式，我们只保留最高次幂的项，常数系数和低阶项可以不要。常数系数和低阶项可以不要。加法规则加法规则 : :针对并列程序段针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) c log2n n nlog2n n2 n3 2n 3n n! Department of Computer Science & Technology, Nanjing Universit

33、y fallDATA STRUCTURES 乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)特例：特例： 若若T1 (n)=O(c), c与与n无关的任意常无关的任意常数，数， T2 (n)=O(f(n), 则则T (n)=O(f(n)任何非任何非0正常数都属于同一数量级，记为正常数都属于同一数量级，记为O(1) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例例1 1：P.33P.33voi

34、d example (float x , int m, int n, int k) float sum ; for ( int i = 0; i m; i+ ) sumi = 0.0; for ( int j=0; jn; j+ ) sumi += xij; for ( i = 0; i m; i+ ) cout “Line ” i “ : ” sum i endl; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES例例2： P.33-34 template void data

35、List:bubbleSort ( ) int i = 1; int exchange = 1; /当当exchange为为0则停止排序则停止排序 while ( i ArraySize & exchange ) BubbleExchange ( i, exchange ); i+; /一趟比较一趟比较 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate void dataList:BubbleExchange(const int i, int & exchang

36、e ) exchange = 0; /假定元素未交换假定元素未交换 for ( int j = ArraySize-1; j=i; j-) if ( Elementj-1 Elementj ) Swap ( j -1, j ); /发生逆序发生逆序/交换交换Elementj-1与与Elementj exchange = 1;/做做“发生了交换发生了交换”标志标志 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESBubbleSort n- -1趟趟BubbleExchange ( ) n- -i次比较次比较1121ni)n(ni)(n O(f (n)*g (n) = O(n2) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESS (n) = O(f (n)