华师本科生数据结构课件 第1章 绪论

1、主讲人：王京花，华中师范大学计算机学院数据结构专业。数据结构作为国外的一门独立课程，建立于1968年。在此之前，它的一些内容已经在其他课程中进行了阐述，如表格处理语言。1968年，在美国一些大学计算机系的教学计划中，虽然数据结构被定义为一门课程，但课程的范围并没有明确界定。当时，数据结构几乎是图论的同义词，尤其是表和树的理论。随后，数据结构的概念被扩展到包括网络、集合代数、格、关系等，这已成为现在称为离散数学的内容。然而，因为数据结构是在计算机中处理的，所以不仅考虑了数据的数学属性，还考虑了数据的存储结构，这进一步扩展了数据结构的内容。近年来，随着数据库系统的不断发展，文件管理的内容(尤其是大

2、型文件的组织等)也越来越多。)已添加到数据结构课程中。数据结构是高校计算机科学的核心课程，是研究计算机软件应用和发展的必要专业基础。随着计算机的日益普及，它也是“软件资格考试”和“研究生入学考试”的必修科目。同时，数据结构是一门实践性很强的课程，与高级编程语言密切相关。如果你不精通高级编程语言，你就不能很好地理解数据结构中算法的本质。本课程介绍了如何在计算机中组织各种数据并存储、传输和转换它们。内容包括：数组、链表、堆栈和队列、递归、树和森林、图形、搜索、内部排序、外部排序和文件结构。该课程加强了数据结构基础知识和编程基础能力的双基训练。为计算机专业课程的后续学习奠定了坚实的基础。前课程：C语

3、言程序设计，计算机数学(离散数学)，课程的主要内容，数据结构的前课程主要包括程序设计语言，学好这门课程可以加深对程序设计的理解，有助于进一步提高程序设计能力，并为计算机专业的后续课程打下良好的基础，如数据库、操作系统、编译原理、软件工程等。教材：数据结构与应用算法教程严为民，陈文博清华大学出版社，本课程目的，参考书，1。数据结构(C语言版)严为民清华大学出版社2。数据结构黄国玉，叶乃菁清华大学出版社3。数据结构(C语言版)陈风起中国铁路出版社4。数据结构、算法与应用(C语言描述)王世林等译。机械工业出版社5。数据结构算法实现与分析高一凡西安电子科技大学出版社6，数据结构学习指导与培训江中国水利

4、水电出版社7。各种数据结构的研究生入学考试试题集和解答，本课程的教学目标，掌握常用数据的逻辑结构和存储方法，并学会在常用存储方法下编写数据的基本运算算法。学会分析问题，并正确选择合适的数据结构和算法进行编程。了解算法时间和空间开销的分析方法。通过对基本算法的学习和计算机实践，加强了编程基础训练，提高了编程能力，为软件开发打下了良好的基础。内容安排(54堂课，36个实验)，评估形式：常规表现(讨论和回答问题):20%常规作业(基础作业):10%课程设计(实验报告):20%期末考试(闭卷笔试):50%，数据结构，计算机实验。安装c编译器。可以使用Borland C或Visual C。前者系统较小。

5、然而，同一个源程序在这两个编译器上可能有不同的编译信息。本着教与学的精神，我希望能经常反馈教学效果，以便及时改进教学方法。要学好一门课程，教师的指导非常重要，但这主要取决于学生自己的努力。课堂教学可以达到终点，但只有通过不断的实践才能巩固和掌握课程内容。因此，本课程要求学生积极独立地完成指定的练习和实验内容。数据结构，第1章绪论，学习要点，了解数据结构相关概念的含义，尤其是数据的逻辑结构和数据的存储结构之间的关系；熟悉C语言的编写标准，特别注意值调用和引用调用的区别以及错误处理方法；了解计算算法时间复杂度的方法；第一章是绪论，学习内容常用术语集、线性结构、树和图的表达算法评价时间复杂度和空间复

6、杂度。理解数据结构的逻辑结构、存储结构和数据操作的概念及其相互关系的难点。掌握算法复杂度的分析方法：用C语言描述该方法，用C语言编写程序，首先初步了解数据结构，然后(1)分析处理过程(2)将处理后的对象存储在计算机中。(3)数据操作。电话号码查询系统有一个电话簿，上面有N个人的姓名和电话号码。假设它以下列形式排列：(a1，b1)(a2，b2)(an，bn)，其中ai，bi (i=1，2，n)分别代表某人的姓名和相应的电话号码。需要设计一个程序来根据人的名字找到号码。如果它不存在，它会给出不存在的信息。1.什么是数据结构研究？算法的设计取决于计算机如何存储人们的姓名和相应的电话号码，或者取决于姓

7、名和电话号码的结构。上述问题是一个数据结构问题。姓名和相应的电话号码可以设计成二维数组、表格结构和向量。假设姓名及其电话号码在逻辑上是以N向量的形式排列的，其中每个元素都是一个数字对(AI，BI)，1-in数据的结构直接影响算法的选择和效率。数据结构还提供了基于每种结构类型定义的各种操作的算法实现。在数据结构中研究什么，在数据结构中研究什么，自动书目检索系统，书目文献，人机游戏问题，例如，田径项目的时间安排，1。任何参赛选手所选的项目都应该是双向的；2.由边连接的任意两个顶点的颜色(时间)不能相同。还有许多数据结构问题需要解决，如酒店管理系统中的房间分配、城市燃气管网铺设、班级调度、旅行推销员

8、问题、数据结构的产生和发展等，1968年，德库特发表了计算机编程的艺术，IEEE 68教程，1983 IEEE 83教程，1991 IEEE 91教程，2000 IEEE 2000教程，该教程在中国开放了78年，相应地有93个教程。目前，数据结构已经成为计算机科学与技术、信息管理、机械科学、管理工程等许多学科的必修课。数据结构是研究数据的逻辑结构和物理结构及其关系，为这种结构定义相应的操作，并保证这些操作后获得的新结构仍然是原来的结构类型。什么是数据结构研究？1.数据结构讨论的范围，数学、计算机硬件和计算机软件之间的一门核心课程，关系、对象关系运算、对象关系运算、算法数据结构=编程尼古拉斯沃斯

9、计算机科学与技术的两大支柱1。数据结构2。算法编程的本质是为计算机处理问题编译一组指令集。解决两个问题：提出问题的数学模型，设计相应的算法，输入未处理的数据，输出处理后的数据。数据结构的定义：数据结构是一门研究数据组织、存储和操作的一般方法的学科。整数(1，2)，实数(1.1，1.2)，字符串(北京)，图形，声音。图书馆里有各种各样的卡片：有些是根据标题排列的，有些是根据作者排列的，有些是根据分类排列的。不仅要考虑短查询时间，还要考虑节省空间。最简单的方法之一是建立一个表，每本书的信息在表中占据一行，比如书名、作者的分类号、出版日期、数据元素在计算机中的表示，以及如何存储0、1、2。对于不同的

10、目的，最好的存储方法是不同的。从大到小排列：9，8，7，6，5，4，3，2，1，0输出偶数：0，2，4，6，8，1，3，5，7，9，操作和处理数据结构中的节点(插入，删除，修改，搜索，排序)，数据结构它不仅需要一个算法来解决问题，而且还需要很高的时间和空间效率，良好的算法结构和可读性，易于验证等。第二，与数据结构相关的概念，数据是信息的符号表示。计算机能够输入、存储、处理和输出的所有信息都是数据的基本单位，通常在计算机程序中作为一个整体来考虑和处理。它是整个数据的一个相对独立的单元，也称为节点或记录数据项。一个数据元素可以由几个数据项组成。数据项是不可分割的最小数据单元，也称为字段。数据对象是

11、具有相同属性的数据元素的集合。是数据的子集。数据记录组织数据的基本单位数据结构是具有相同特征的数据元素的集合。如果数据元素之间有一个或多个特定的关系，它就称为数据结构。逻辑结构数据之间的相互关系通常分为四种基本结构：集合结构：中的数据元素除了属于同一类型之外，没有其他关系。线性结构：中的数据元素之间存在一对一的关系。树结构：中的数据元素之间存在一对多的关系。在图(或网格)结构3360中的数据元素之间存在多对多的关系。存储结构/物理结构数据结构存储在内存中。序列、链接、索引和散列。首先，数据结构()，首先，基本概念和术语。首先，用二进制组描述数据结构。B=(S，R) B是一种数据结构。s是一组数

12、据元素。r是S上的二元关系，它是一个偶集。R=P，P是C1，C2在集合上定义的关系。1.集合结构，数据结构：set=(s，r) s=01，02，03，04，05，06，07，08，09，10r=，数据结构3360l=(d，r) linear=(d，r) 1。线性结构，2。线性结构，数据结构线性=(s，r) s=01，02，03，04，05，06，07，08，09，10r=，数据元素之间的连接：1:1，3 08，09，10 r=，数据元素之间的连接：1:N，4，图表结构，R=，图表=(d，R)图表=(s，r) s=01s是d上的关系集，由节点间的有序对集表示；p是D上的一组基本运算.数据：操作：

13、结束基本操作的定义格式是：基本操作名称(参数表)初始条件：初始条件描述操作结果：操作结果描述，3。算法及其描述和分析。理解算法：介绍算法，算法：算法是一组有限的规则，其中的规则规定了解决特定问题的操作顺序。欧几里德算法：如果a和b是正整数，ab。然后abq r，0n；那么m和n之间的最大公约数可以计算如下：算法：算法是一组有限的规则，其中的规则指定了解决特定问题的操作序列。程序框图：输入m，n，R=mod(m，n)，R=0？m=n；N=R，输出n、输入，求余数，更新被除数和除数，求m和n的最大公约数。不确定性：在执行有限的步骤后完成。2.确定性：每一步都有明确的含义。3.可行性：原则上，可以精

14、确地进行，并且可以用纸和笔完成有限的次数。4.输入：5。产出：3。理解算法：GCD问题，方法1:(欧几里德算法)步骤1:如果n=0，返回M的值作为结果，算法结束；否则，进入第二步；第二步：用n除m，并将余数赋给r；步骤3:将n的值赋给m，将r的值赋给n，然后返回步骤1。方法2:(逐步启发式)在第一步中，最小、n和n的值被分配给t；第二步：用t除m，如果余数为0，进入第三步；否则，进入第四部分；第三步：用t除n，如果余数为0，返回t作为结果；否则，进入第四部分；步骤4:将t的值减少1，然后返回步骤2。方法3:(用筛选法寻找素数)第一步是找出：中M的所有素因子；第二步：找出N的所有素因子；第三步：

15、找出前两步得到的素因子分解公式中的所有公共因子minp1和p2；第四步：将第三步中找到的主要因素相乘，结果就是你想要的。3.理解算法：GCD问题的求解方法，它是用来解决某个问题的一组规则。1.有限步骤的执行肯定可以完成，算法中的每一步都可以在有限的时间内完成；2.确定性在每种情况下，算法中都有要执行的操作的精确规则，因此算法的实现者或读者可以知道它们的含义以及如何执行它们。在任何情况下，算法都只有一条执行路径；3.可行性所有的操作必须足够基本，这可以通过已经实现的有限数量的基本操作来实现；4.以输入为算法处理对象的值通常在算法中反映为一组变量。5.输出是一组与“输入”有确定关系的值，它是算法处理信息的结果。这种明确的关系是算法的功能。第三，理解算法：算法的定义，多种算法可以设