数据结构PPT课件

PPT 内容
PPT 图集

1. 课程内容：计算机软件的基础知识——数据结构课时安排：数据结构——80学时理论——60学时上机实验——20学时教材：数据结构（C语言版）严蔚敏吴伟民清华大学出版社
2. 课程安排：讲课60课时，实验20课时，共80课时；实验从第5周开始。完成作业及实验报告，结合考勤作为平时成绩（20%-30%），考试采用闭卷考试方式(70%-80%)。
3. 数据结构学习内容教学内容教学方式讲课(60)实验(20)第一章绪论3第二章线性表6第三章栈和队列5第四章串4第五章数组和广义表42第六章二叉树104第七章树42第八章图84第九章查找84第十章内部排序62综合22
4. 第一章绪论本章目的：是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。
5. 1.1 什么是数据结构1) 数据结构讨论的范畴。Niklaus Wirth：算法 + 数据结构 = 程序程序设计: 算法: 数据结构: 为计算机处理问题编制一组指令集处理问题的策略问题的数学模型
6. 用计算机解决一个具体问题时，大致需要经过下列几个步骤: （1）抽象出一个适当的数学模型（2）设计一个解此问题的算法（3）编出程序进行测试、修改直至得到最终结果。
7. 第一章绪论1.1 什么是数据结构算法+数据结构=程序例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表
8. 例1-2 学生信息检索系统当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。类似的人事管理、物资管理、商品管理等大量问题都可以抽象出类似的线性数据结构。（b）姓名索引表崔文靖 8 何文颖 6 李淑芳 2 刘丽 3，9 石宝国 5 魏永鸣 10 吴承志 1 赵胜利 7 张会有 42000级 6，7，8 2001级 9，10 98级 1，2，3 99级 4，5计算机科学与技术 1，5，6，9 信息与计算科学 2，4，8 数学与应用数学 3，7，10 记录号学号姓名性别专业年级 1 980001 吴承志男计算机科学与技术 98级 2 980002 李淑芳女信息与计算科学 98级 3 990301 刘丽女数学与应用数学 99级 4 990302 张会友男信息与计算科学 99级 5 990303 石宝国男计算机科学与技术 99级 6 000801 何文颖女计算机科学与技术 2000级 7 000802 赵胜利男数学与应用数学 2000级 8 000803 崔文靖男信息与计算科学 2000级 9 010601 刘丽女计算机科学与技术 2001级 10 010602 魏永鸣男数学与应用数学 2001级（a）学生信息表（c）专业索引表（d）年级索引表图 1.1 学生信息查询系统中的数据结构线性表
9. 例2 人机对奕问题树……..……..…...…...…...…... 在此问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。像计算机游戏、组织机构的层次结构等许多实际问题也可以抽象树形数据结构。
10. 例3-1 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图
11. 例3-2 教学计划编排问题图一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。像交通管理控制、课程安排、工程管理等大量问题都可以抽象出图状数据结构。
12. 由以上几个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。
13. 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科
14. 为什么要学习数据结构在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。
15. 例4 建立一个住院病人押金情况表。住院病人押金情况表包括：姓名、性别、年龄、住院押金。 (1)顺序存储结构：即把所有记录依次存储在一个数组中。如数组下标姓名性别年龄住院押金 0 张三 m 40 500．00 1 李四 f 50 100．00 ：：：：：
16. (2)单链存储结构：即把每个记录看作一个结点，让所有结点依次链接。如 L→张三 m40500.00 　→李四f50100.00 　…
17. 一个具体问题的软件设计通常包括三个步骤： (1) 分析和确定该问题的逻辑结构 (2) 设计该问题的具体存储结构 (3) 设计该问题在具体存储结构下的操作实现算法
18. 1.2 基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能被输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(Data Item）:一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构（data structure)—数据元素和数据元素关系的集合
19. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的不同，数据结构可分为四种：线性结构：结构中的数据元素之间存在一对一的关系。如线性表、栈、队列树型结构（层次结构）：结构中的数据元素之间存在一对多的关系。如树图状结构(网状结构)：结构中的数据元素之间存在多对多的关系。如图集合：结构中的数据元素除了同属于一个集合外，别无其它关系。（逻辑结构）
20. 数据结构是一个二元组 Data-Structure=(D,S) 其中，D是数据元素的集合，S是D上关系的集合例如，复数可以被定义为一种数据结构： Complex=(C,R) 其中 C={x|x是实数} 是含两个实数（c1,c2）的集合 R={P} P={<c1,c2>|c1,c2∈C,c1称为实部，c2称为虚部} 一个数据结构有两个要素。一是数据元素的集合, 另一是关系的集合。在形式上, 数据结构通常可以采用一个二元组来表示。
21. 数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系
22. (本页无文本内容)
23. 元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储
24. 1536元素21400元素11346元素3 ∧元素41345h存储地址存储内容指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1346 链式存储 h
25. 数据的逻辑结构数据的存储结构数据的运算：插入、删除、更新、查找、排序等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：
26. 数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型typedef struct { int num; char name[20]; float score; } STUDENT; STUDENT stu1,stu2, *p;
27. 主要基本操作： 1. 插入：在数据结构中的指定位置上增加新的数据元素。 2. 删除：删去数据结构中某个指定的数据元素。 3. 更新：改变数据结构中某个数据元素的值。 4. 查找：在数据结构中寻找满足某个特定要求的数据元素 (的位置和值)。 5. 排序：重新安排数据元素之间的逻辑顺序关系。这主要是在线性结构中要做的，使这些数据元素按值由小到大或由大到小的次序排列。
28. 数据结构课程的内容数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。数据结构的内容包括三个层次的五个“要素” 。
29. 1.3 算法和算法分析算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—ïïïîïïïíì输出一个算法有一个或多个—输出输入一个算法有零个或多个—输入算法是能行的—可行性义性切定义的，不能产生二算法的每一步必须是确确定性限步骤之后结束一个算法必须在执行有有穷性——
30. 1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。例1.5、例1.62．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
31. 3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
32. 5．有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
33. 例1.6 一个不超过100次计数的算法 n=1;s=0; while(n<=100) { s+=n; n++; } 输出n的值；例1.5 一个不是算法的例子 n=1; while(n>0){ n=n+1; } 输出n的值；
34. 算法的描述—采用C语言 (1)预定义常量和类型的说明； (2)数据结构的表示（存储结构）用类型定义(typedef)描述。数据元素类型约定为Elem Type，由用户在使用这个数据类型时自行定义； (3)基本操作的算法所用的函数描述形式； (4)赋值语句； (5)选择语句； (6)循环语句； (7)结束语句； (8)输入和输出语句； (9)注释； (10)基本函数； (11)关于逻辑运算的约定；
35. void 函数名(<参数表>) { <语句组> } 函数类型函数名(<参数表>) { <语句组> }算法的一般形式：
36. main() { int a,b,c; scanf("%d,%d",&a,&b); c=max(a,b); printf("max=%d",c); } int max(int x,int y) { int z; if (x>y) z=x; else z=y; return(z); }
37. 算法的评价—衡量算法优劣的标准正确性(correctness) 可读性(readability) 健壮性(robustness) 高效与低存储量1.4 算法的性能分析与度量 1.4.1 算法的性能标准
38. 1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；
39. c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。 d．程序对于一切合法的输入数据都能得出满足要求的结果；
40. 2. 可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。
41. 3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
42. 4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。
43. 算法效率的衡量方法和准则通常有两种衡量算法效率的方法: 事后统计法事前分析估算法
44. 和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度
45. 如何估算算法的好坏？
46. 1．运行时间，依据算法编制成程序后在计算机中运行时所消耗的时间。 2．所占存储容量，依据算法编制成程序后在计算机中所占存储量的大小。 3．其它性能，算法是否易读、是否容易转换成任何其它可运行的语言编制的程序，以及是否易被测试等等。
47. 1．程序运行时所需输入的数据总量。 2．对源程序进行编译所需时间。 3．计算机执行每条指令所需时间。 4．程序中的指令重复执行的次数。程序在计算机上运行所耗时间取决于：
48. 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
49. 一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
50. for (i=1;i<=n;++i) n+1 for (j=1;j<=n;++j) n(n+1) { c[i][j]=0; n2 for (k=1;k<=n;++k) n2(n+1) c[i][j]+=a[i][k]*b[k][j] n3 } T(n)=2n3+3n2+2n+1，当n→∞时，T(n)/n3→2， T(n)为算法的时间复杂度。算法的时间复杂度T(n)=O(f(n))
51. 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))称T (n) 为算法的(渐近)时间复杂度。例：2n3+1000n2+1=O(n3) 1000n2+n+1000000= O(n2)
52. 如何估算算法的时间复杂度？从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
53. (1) { ++x;s=0;} (2) for (i=1;i<=n;++i) { ++x;s+=x;} (3) for (j=1;j<=n;++j) for (k=1;k<=n;++k) { ++x;s+=x;} (1)的频度就为1，(2)的频度为n，(3)的频度为n2 时间复杂度为O(1) O(n) O(n2) 常数阶线性阶平方阶算法还可能呈现的时间复杂度有：对数阶O(log2n)，指数阶O(2n)等。
54. 例一两个矩阵相乘void mult(int a[], int b[], int& c[] ) { //以二维数组存储矩阵元素，c为a和b的乘积 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i,j] = 0; for (k=1; k<=n; ++k) c[i,j] += a[i,k]*b[k,j]; } //for } //mult基本操作: 乘法操作时间复杂度: O(n3)
55. 例二选择排序时间复杂度: O(n2)基本操作: 比较(数据元素)操作 void select_sort(int& a[], int n) { //将a中整数序列重新排列成自小至大有序的整数序列。 } // select_sortj = i; // 选择第 i 个最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k;for ( i = 0; i< n-1; ++i ) { if ( j != i ) a[j] ←→ a[i] }比较次数=（n-1)+(n-2)+…+1 T(n)=n(n-1)/2
56. 例三起泡排序基本操作: 赋值操作时间复杂度: O(n2)void bubble_sort(int a[ ], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。 for (i=n-1, change=TRUE; i>1 && change; --i) } // bubble_sort{ change = FALSE;//change为元素进行交换标志 for (j=0; j<i; ++j) if (a[j] > a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;} } // 一趟起泡比较次数：最好情况：n-1最坏情况：n(n-1)/2
57. 最坏情况下的时间复杂度平均时间复杂度若不特别说明，以后我们所说的都是最坏情况下的时间复杂度
58. 常见函数的增长率常见函数的时间复杂度按数量递增排列及增长率。常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n）
59. 算法的存储空间需求算法的空间复杂度定义为: 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。S(n) = O(g(n))算法的存储量包括:输入数据所占空间程序本身所占空间辅助变量所占空间
60. 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
61. 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣
62. 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量 2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适
63. 空间复杂度：s(n)=O(f(n))存储空间：指令、常数、变量；输入数据；辅助空间
64. 实际应用中有关程序性能分析与测量的主要方法有： 1)确定一个程序对内存及时间的需求 2)使用操作数和执行步数来分析测量程序的时间需求 3)采用渐进符号描述算法的复杂性 4)利用计时函数实际测量一个程序的实际运行时间
65. S=1+2+……+(k-1)+k×(n-k)=k×(k-1)/2+k×(n-k)=k×n-k×k/2-k/2 算法+数据结构=程序如果n=108，k=5×107那么S>3.7×1015 3.7×108
66. 1. 熟悉各名词、术语的含义，掌握基本概念。2. 理解算法五个要素的确切含义。本章学习要点3. 掌握计算语句频度和估算算法时间复杂度的方法。
67. 参考教材： 1．《Data Structure with C++》 1998/William Ford,William Topp 清华大学出版社 2．《DATA STRUCTURES & PROGRAM DESIGN IN C》 Second Edition Robert Kruse，C.L. Tondo,Bruce P. Leung 清华大学出版社,Prentice Hall International,Inc. 3．《数据结构习题集》（Ｃ语言版）严蔚敏等，清华大学出版社 4.算法与数据结构 —C语言描述张乃考编著，高等教育出版社
68. 5.数据结构耿国华等编，西安电子科技大学 6.数据结构实用教程（C/C++描述）徐孝凯，清华大学出版社 7.数据结构用面向对象方法与C++描述殷人昆等，清华大学出版社 8.数据结构算法实现及解析高一凡编著，西安电子科技大学 2002.10 9.数据结构学习指导与训练蒋盛益等，中国水利水电出版社 10.数据结构刘振鹏张晓莉郝杰，中国铁道出版社
69. 推荐教学网站和相关专业文献网站 http://www.zjtcm.net/wljx/Computer/Data%20Structure/Tsinghua/index.html http://student.zjzk.cn/course_ware/data_structure/web/main.htm http://jpkc.onlinesjtu.com/CourseShare/DataStructure/Index.aspx http://jpkc.hfut.edu.cn/other/sjjg/ http://211.86.56.4:8082/

下载需要 10 香币 [ 香币充值 ]

亲，您也可以通过分享原创文档来获得香币奖励！

服务器/托管费、人工审核、技术维护等都需要很多费用，请您支持香当网的发展

下载PPT

数据结构PPT课件

该用户的其他文档

相关PPT

相关文档