数据结构课件

1、数据结构(c语言版本)，1，PPT学习交换，主题，概述，第1章，折线图，第2章，堆栈，队列和数组，第3章，树，第4章，图，第5章，搜索，第6章，4，数据结构课程在PPT学习通信、故障诊断过程中的作用：与模型的关系和算法设计关系、存储结构选择关系和编程之间的关系；5，PPT学习通信，1.1.2学习数据结构的重要性；在计算机科学中，数据结构是除一般编程外，编译器、操作系统、数据库系统和其他系统程序以及大型应用程序的设计和实现的重要基础。目前在我国，数据结构不仅是计算机专业的核心课程之一，也是部分计算机专业以外的主要选修课之一。瑞士计算机科学家沃思(N.Wirth)曾将“算法数据结构程序”作为他的着

2、作之一。可以看出，编程的本质是对实际问题选择好的数据结构，设计好的算法。因此，如果只掌握一些计算机语言和编程方法，缺乏数据结构的知识，就很难应对很多复杂的挑战，也无法有效地利用计算机。返回，6，PPT学习交流，数据结构是研究非数值计算编程问题的计算机运行对象及其关系和运行等的学科。是数学、计算机软件、计算机硬件的核心课程。7，PPT学习交换，1.2基本术语，计数标准，数据元素，字段(域)，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实现，8，PPT学习交换，1.2基本术语，计数标准，计数标准资料有更多的形式，如我们前面讨论的工资清单、学生成绩单、一个家庭关系的表达、一组个体

3、之间关系的图形说明等。9，PPT学习通信，1.2基本术语，计数标准，数据元素，字段(域)，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实施，对数据具有独立意义的各个。例如，工资单上的个人工资信息、成绩单上的学生成绩信息、家庭关系中的个人等。有时也称为元素、记录、节点、顶点等。10，PPT学习通信，1.2基本术语，数据元素、字段、数据结构、数据结构的逻辑结构、数据结构的物理结构、数据结构运算的实现，虽然将具有独立意义的对象显示为元素，但很多情况下需要特定对象的具体信息，因此与元素的字段信息相关。字段是元素的详细说明，元素通常可以包含多个字段。11，PPT学习通信，1.2基本术

4、语，数量标准，数据元素，字段(域)，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实施，数据结构表示构成数据的元素之间的结构关系。线性结构、树状结构和图形结构是数据结构中几种常见类型的数据结构。如果数据的元素之间没有关系，则组织集合。这也是一种结构。12，PPT学习通信，1.2基本术语，数据元素，字段(域)，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实现，我们将线性结构，树结构和图形结构的这种结构称为逻辑结构，其中包括数据元素的表示和关系的表示。这是因为仅考虑元素之间的逻辑关系，而不考虑计算机中这些元素的具体实现。13，PPT学习通信，1.2基本术语，数

5、据元素，字段，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实现，选择相关数据结构的存储格式，并将其存储在计算机上，以获取内存中数据结构的物理结构(也称为存储结构)。逻辑结构可以有多个存储结构。例如，可以使用顺序存储或连接形式的存储。每个存储结构实施的计算性能可能会有所差异。14，PPT学习通信，1.2基本术语，数据元素、字段(域)、数据结构、数据结构的逻辑结构、数据结构的物理结构、数据结构运算的实现，数据的逻辑结构与存储结构密切相关。一种算法的设计取决于所选择的逻辑结构，而算法的实现取决于所采用的存储结构。选择数据结构的存储结构后，可以执行给定的运算。15，PPT学习通信，

6、1.2小节点，数据元素，字段(域)，数据结构，数据结构的逻辑结构，数据结构的物理结构，数据结构运算的实施可能会对算法的时间性能、空间性能等产生重大影响，因此同一存储结构也可能具有不同的算法实现，需要解决的问题是什么？哪个算法更有效？为此，需要分析算法，算法分析部分将在本章后面进行讨论。分析表明了实现的算法的性能，以及选定的存储结构是否符合要求。返回、16、PPT学习交换、1.3算法描述和分析、1.3.1算法描述语言概述、说明：算法可以用多种描述语言(例如自然语言、计算机语言或某些伪语言)描述。各种说明语言对问题的说明能力略有不同。自然语言更灵活，但不够严格。计算机语言虽然严格，但由于语法限制，

7、灵活性不足。因此，许多教材都使用特定种类的语言，例如PASCAL、c语言，这种语言可以根据计算机语言适当地添加特定功能或放宽特定限制，从而使计算机语言的严格和灵活性更容易实现。定义：是特定故障排除步骤的说明，其中每个命令表示一个或多个操作的受限命令序列。特征：具有较差的确定性可行性输入输出，17，PPT学习交换，算法设计要求：正确性：算法是否正确，是否满足特定问题的要求。可读性：人机交换，有助于机器运行。坚固性：能够适当地应对或处理错误。效率和低存储要求。18，PPT学习通信，1.3算法描述和分析，1.3.2算法分析，测量算法的主要性能指标包括时间性能和空间性能。其中，时间性能表示运行算法所需

8、的时间量，空间性能表示运行算法所需的辅助空间量。测量运行时间的方法：事后统计、预分析估计(通常是后者)。19，PPT学习交流，时间的复杂性意味着简单的操作在算法中重复执行的次数和语句重复的次数是该语句的频率。例如：T(n)=O(f(n)，其中f(n)是问题大小n的函数，通常是算法中最频繁的语句频率。例如s 3360=0；for(k=1；k=n；k)for(j=0；j=n；j)s 3360=s 2；语句的频率为n * (n 1)，如果存在*循环嵌套语句，则算法的时间复杂性由嵌套中最深的语句频率确定。评价算法时间性能的主要标准是时间复杂度的级数。，此程序段的时间复杂性为：T(n)=O(n2 n)=O(n2)，所谓的数量层次定义如下：如果变量n的函数f(n)和g(n)满足，则f(n)和g(n)具有相同的比例，并以f(n)