01.第01节课第1章数据结构引论

罗泽兵 · 发表于 2024-4-15 09:13:04

咳。好同学们，大家好，今天呢，我们来为大家讲解一下我们数据结构的有关知识，那么我们首先。要讲的呢是数据结构的这样一个引论，以及呢，我们线性表它的知识。首先我们来看一下数据结构引论的部分。那么，我们早期的计算机呢？主要用于数值计算，现在呢？计算机主要用于非数值计算，

包括处理字符，表格和图像。等具有一定结构的数据，这些数据内容呢，存在某种联系，只有分清楚数据的内在联系了。合理的组织数据，才能对他们进行有效的处理，设计出高效的算法。那么，我们数据结构主要研究的问题呢？就是如何合理的组织数据，高效的处理数据，那么这个呢？就是我们数据结构呢，

主要研究的问题。那么，我们来看一下。我们呢，首先来看一下数据结构研究的内容。计算机呢，主要用于数值计算的时候呢，一般呢，都要经过几个步骤，比如说。首先，从具体问题抽象出数学模型，然后设计一个解决此数学模型的算法，最后编写程序。然后呢，

进行测试。调试直到了解决问题。在此过程中呢，寻求数学模型的实质呢，是分析问题，从中提取操作的对象。并找出这些操作对象之间的关系，然后用数学语言呢加以描述，那么也就说建立相应的。数学方程。那么就是我们。现实世界解决一个问题的方法。它的过程呢，是抽象一个数学模型，解决数学模型的算法，

最后呢，编制一个程序。我们举一个例子。结构精力分析计算需要用到我们的线性代数方程组。全球天气预报需要用到我们的环流模式方程，球面坐标系。非数值计算的程序设计问题了，比如说求一个一组n个指数中的最大值，它的算法呢，是它的基本操作是比较两个数的大小。模型呢，要取决于整数值的范围。另外呢，还有计算机的对弈，对弈的算法呢，

是我们计算机对于我们对弈的规则和策略的这样一个控制。模型呢，是棋盘和棋盘的格局。再比如说足协的管数据库管理算法呢，是需要管理的项目是什么？如何管理用户界面是什么样的？模型呢，就是我们的各种表格那么概括的说呢，数据结构是一门讨论描述现实世界实体的数学模型。以及呢，其上的操作在计算机中如何表示和实现的学科？那么，我们来看一下我们刚才举的这些例子，有我们的足协，有我们的天气预报，

有我们求我们一组数中的最大值。那么我们呢？在这些过程当中呢？我们提取操作的对象，找出这些操作对象之间的关系。然后用数学语言呢，加以描述，最后呢，得到我们的结果。我们数据结构的作用呢？那么由我们的。数据表示，数据类型，数据关系，系统设计，

存取算法，设计数据，运算编码，理论数据总和，还有我们数学方面以及我们的硬件和软件方面。呢都要应用到我们的数据结构，这样一个知识。那么，我们先来看一下与数据结构相关的概念，我们的基本概念和术语，我们的数据结构以及数据类型。和抽象数据类型。我们首先来看一下什么叫做数据。数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。

是计算机操作的对象的总称，是计算机处理信息的某种特定符号的表示形式。那么，数据元素是什么呢？数据元素。是集合数据集合中的一个个个体，是数据结构讨论的基本单位。我们举一个例子。我们的数据。比如说。数学计算机中的用到的整数和实数。文本编辑中用到的字符串多媒体程序处理的数据，图形图像。声音，动画等通过特殊编码定义后的数据，

那么这些呢，都是我们的数据。数据元素是什么呢？比如说。数据元素用于完整的描述一个对象，比如说。一名学生记录。棋盘中的一个格局，状态以及呢，图中的一个顶点，那么这些呢都是。我们的这样一个数据的元素。那么我们再看一下数据项。数据项是什么呢？数据项是数据结构中。

讨论的最小单位。数据元素呢，可以是数据项的集合。比如说描述一个运动员的数据元素呢，可以用他的姓名，他所在的俱乐部名称，他的出生日期，参加的日期，他的职务业绩。那么，这些呢？来进行描述，那么这是它的数据元素。另外呢？我们的。

这个数据元素当中的编号，姓名，俱乐部名称，参加日期。职务业绩这些呢，都是数据项，也就是说数据项是组成数据元素的。有独立含义的，不可分割的最小单位，比如说我们这些这些部分呢，这些数据项呢，都是不可再分的数据项。那么我们再来看一下数据结构。数据结构呢，是带有结构的数据元素的集合。

那么，我们来看一下数据结构的这样一个部分。数据结构，它是相互之间存在一种或多种特定关系的数据元素的集合。比如说换句话说呢，数据结构呢，它就是带有结构的数据元素的集合。结构呢，就是数据元素之间存在的关系。数据结构。我们通常呢，要从几个方面来探讨它的这样一个结构部分，比如说。它的逻辑结构。另外呢，

以它的存储结构。数据的逻辑结构呢，是从逻辑上描述数据。它与数据的存储无关，是独立于计算机的，因此呢，数据的逻辑结构呢，可以看作是从具体问题抽象出的数据模型。而数据的存储结构呢？数据对象在计算机中的表示。存储。称为数据的存储结构，也称为物理结构。把数据对象呢存储到计算机时。通常要求，

既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系。数据元素在计算机内呢，用一个节点来表示。数据元素在计算机中有两种基本的存储结构，一种呢，是顺序存储结构。另外一种呢，是我们的链式存储结构，这里呢，我们之后呢，会讲这样一个内容好，我们来看一下这个例子。假设用三个四位的十进制数表示，一个含12位数的十进制数，

比如说。这样一个三个四位的十进制数，那么表示一个12位数的十进制数，那么这在数据元素a1。a2a3那么a1代表第一个三位的四进四三三，第一个四位的二进制数。a2表示，第二个四位的时间之数。a3表示，第三个。四位的十进制数，那么则在数据元素a1a2a3之间存在着次序关系，比如说a1要和再过了是a2。然后呢？a2过了是a3，

那么这是我们的要存在它的一个顺顺序的关系。另外呢，再看一个例子，在二行三列的二维数组a1a2a3a4a5a6当中。存在六个元素之间的关系。行的次数关系呢，是a1a2a2a3a4a5a5a6。列的次序关系呢，是a1a4a2a5a3a6，甚至是它们之间的这样一个次序关系。也就是说，我们的数据结构呢，是相互之间存在一种或多种特定关系的数据元素的集合，也就是说，数据元素呢？

是带结构的。数据元素的集合。那我们再来看一下这样一个例子，在一维数组a1a2a3a4a5a6的数组数据元素之间。存在的这样一个关系AI。后在前AI+1在后对吧？就是a1a2a2a3a3a4a4a5a5a6。那么，不同的关系呢？构成不同的机格，那么刚才我们讲过数据结构就是相互之间存在着某种逻辑关系的数据元素的集合。我们的数据结构呢？它的数据逻辑结构呢？可以分为四类。第一种呢，

是线性结构。线性结构呢？也就是说数据之间。存在一对一的关系。学生信息按入学的报到先后顺序进行行排列，构成一个线性结构，这是我们这样一个例子。第二个呢，是我们的树形结构。树形结构呢，就是数据元素之间存在着一对多的这样一个关系。比如说在班里的管理体系中，班长呢？管理多名组长。每位组长管理多名组员，

从而呢，形成树形结构。第三种图状结构。那么，图状结构呢？也就是说，数据元素之间存在着多对多的关系，比如说。多位同学之间的朋友关系，任何两位同学呢，都可以是朋友，从而构成图状结构。第四个集合结构。集合结构呢？数据元素之间，

除了属于同一集合的关系外，并无其他关系。比如说我们要确定一名学生呢，是否为班级成员，只需要将班级看作一个集合结构。那么，在我们这四种结构当中。集合结构。树结构。图结构。都属于非线性结构。那么，只有我们的线性结构呢？包括我们的线性表在队列字符串数组广义表。呃，

包括我们只有我们这些线性结构呢，它才是我们的线性结构。其他的，比如说集合结构，树结构，图结构都是非线性结构，这里大家要注意。图结构。树结构，集合结构都是非线性结构，那么这里大家要注意。好，我们接下来再看一下。数据结构呢，是一个二元组data structures ds，

其中呢d是数据元素的有限集。s呢，是低上关系的有限集。数据的存储结构呢，是逻辑结构在存储器中的印象。哈哈哈。数据元素的印象方法呢，是用二进制位比特，它的二进制位。比特的位串表示数据元素。比如说我们三二一，这是三百二十一十进制的321=8进制的五零一=2进制的一零一。零零零一。那么a呢？等于八进制的一零一=2进制的零零一零零零一，

那么这样一些部分。关系的印象方法呢，就是表示xy的方法。有我们的顺序印象，就是以相对的存储位置啊，表示后继关系，比如说。令y和的存储位置和x的存储位置之间差一个常量c，而c是一个隐含值整个存储结构中呢？只含有纯数据元素本身的信息，那么。这是我们的顺序印象。另外呢？还有我们的。面试印象。

以附加信息指针表示，后继关系需要用一个和x在一起的附加信息。只是y的存储位置，比如说在x这样一个。部分当中呢，它需要添加一个附加信息，也就说我们的指针来指向下一个y的。存储位置。在不同的编程环境中呢？存储结构呢？可以有不同的描述方法，当当用高级程序设计语言呢？进行编程时。通常可用高级编程语言中提供的数据类型，那么进行描述。

比如说我们看一下。当用三个带有次序关系的整数呢？表示一个常整数时可利用C语言中提供的整数数组类型，比如说我们定义常整数呢？help define.int long int.三那么这定义我们的长整数。数据类型和抽象数据类型我们来看一下数据类型呢，在用高级程序语言编写的程序中呢。必须对程序中出现的每个变量，常量或表达式明确的说出它们所属的这样一个数据类型。比如说我们C语言中呢，提供的这些数据类型呢，基本的呢，有我们的整形浮点型。

双精度型字符型。浮点型呢和双精度型呢，又称之为我们的实型，还有我们的逻辑型布偶型。也是我们的这样一个基本的数据类型。不同类型值的变量呢？其所能取的值的范围不同，所能进行的操作不同。数据类型是一个值的集合和定义，在此集合上的一组操作的总称。我们来看一下抽象数据类型abstract data type简称adt，是指一个数学模型。以及定义在此数学模型上的一组操作。比如说我们来看一下抽象数据类型，复数的定义adt complex，

complex。数据对象是我们的第一。一一一二一一一二呢？属于我们的实数集。数据的关系呢？r1等于一一一二一一呢？是实数负数的实数部分。一二呢，是复实数的虚数部分。那么，基本的操作呢？我们看一下assign complex。取z的地址v1v2操作的结果呢？是构造复数z其实实部和虚部呢？分别被赋予参数v1和v2的值destroy company s。

取z的地址操作结果呢，是实数负数z呢，被销毁get real z。这个符号real part。它的初始条件呢，是复数已存在操作结果呢，是real part返回十复数z的十不值。另外呢，还有我们的get image。还有我们的add那么这样一些部分。比如说我们的adt complex。那么就是用我们的抽象数据类型。指一个数学模型以及呢，定义在此数据模型上的一种操作。adt呢？

有两个重要特征，一个呢？是我们的。数据抽象。一个呢，是我们的。数据封装，那么这是它的两个重要特征。数据抽象呢，是用adt描述程序处理的，实体时强调的是其本质的特征，其所能完成的功能以及它和外部用户的接口。比如说外部用户呢，使用他的方法数据封装呢，是指将实体外部特性和其内部实现的细节分离，

并且对外部用户呢，隐藏其内部实现细节。数据抽象数据的形式描述呢？我们可以呢，用DSP 3元组表示d呢是数据对象s呢，是d上的关系集。p呢是对d的基本操作级。adt抽象数据类型名呢？那么可以用数据对象数据关系。数据操作。来进行这样一个使用。那么，其中定义基本操作类型的格式呢？为我们的基本操作名参数表，初始条件操作结果。

复制参数。初始条件那么操作结果那么这样一些部分。我们来看一下抽象类型的表述和实现抽象数据类型呢，需要通过固有数据类型。来实现，比如说对以上定义的复数，那么这样一些部分。type defy struct float real part float image part complex，这是基本操作的函数原型。还有void set complex取z的地址float revolt。float image volt构造复数z是实部和虚部呢，分别不赋予参数rail volt or rail image volt的值。还有我们的float get row，float get image，float add那么这样一些操作。

接下来我们看一下算法的部分。算法。那么是什么呢？数据结构和我们的算法呢？存在着本质，联系在某一类型数据结构上，总要涉及其上施加的运算。而只有通过对所定义运算的研究，才能清楚的理解数据结构的定义和作用。在设计运算时，总要联系到该算法处理对象和结果的数据。在数据结构中呢，遇到大量的算法问题，因为算法。联系的数据呢？

在计算中的组织方式，为了描述实现某种操作，常常需要设计算法。因而呢，算法是研究数据结构的重要途径。那么，什么是算法呢？算法是为了解决某一问题而规定的一个有限长的操作序列。一个算法呢，必须满足五个条件，有重性确定性。可行性输入输出那么是什么呢？有穷性是什么呢？一个算法呢？必须总在执行，

有穷过后结束，而每一步呢？都必须在有穷时间内完成，这是它的有穷。性确定性是什么呢？对于某种情况下所应执行的操作算法中呢？都有明确的规定，不会产生二一性。使算法的执行者或阅读者都能明白其含义，以及呢，如何进行操作。可行性是什么呢？算法中的所有操作都可以通过已经实现的基本操作了来进行运算执行，有限次来实现。那么，

输入输出是什么呢？一个算法有零个或多个输入在用算法的时候呢？输入往往是通过形参表示的，在他们被调用的时候呢，从主调函数或者输入值，那么输出是什么呢？一个算法呢？有一个或多个输出，他们是算法进行信息加工后得到的结果。无处数的算法呢，一般呢，没有什么这样一个使用的，这样一个类型，当用常数描述算法的时候呢，输出了多用返回值或用引用类型的形参表示。

那么，具有上述刚才我们讲过的这些特上述特征的计算描述呢？只是具有了算法的基本属性。通常呢，在设计算法的时候呢，还应该考虑算法的这样一个正确性，可读性。健壮性以及高效性。正确性呢，是指在合理的数据输入下，能够在有限的时间内得到正确的结果。可读性呢，是一个好的算法，首先应该便于人们理解和相互交流，其次才是机器可执行性。

可读性的算法呢，有助于人们对算法的理解，而难懂的算法呢，易于隐藏错误且难于调试和修改。健壮性呢，是当输入的数据非法时，好的算法呢，能适当的做出正确的反应和进行相应的处理，而不会产生一些莫名其妙的这样一些输出其他的输出结果。高效性呢，包括时间和空间两个方面，时间高效呢，是指算法设计合理，执行效率高。可以用时间复杂度来衡量空间高效，

是指算法占用的这样一个存储容量合理，可以用分空间复杂度来衡量。时间复杂度和空间复杂度呢，是衡量算法的，它的这样一个两个主要的指标。效率呢和存储量呢都与问题的规模有关，通常效率指的是算法执行的时间，存储量指的是算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。

		自动登录	找回密码
密码			立即注册