计算机考研基础讲义数据结构基础.ppt

计算机考研小组计算机考研小组计算机考研小组计算机考研小组(100)(100)(100)(100)201020102010201020102010年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义第一章第一章 绪论绪论n n什么是数据结构直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一门学科。门学科。门学科。门学科。数据结构是指数据之间的关系数据结构是指数据之间的关系数据结构是指数据之间的关系数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这就是数据结构。就是数据结构。就是数据结构。就是数据结构。学习数据结构的重要性学习数据结构的重要性1.1.“数据结构数据结构数据结构数据结构”在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专业基础课业基础课业基础课业基础课,在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。2.2.数据结构是介于数学、计算机硬件和计算机软数据结构是介于数学、计算机硬件和计算机软数据结构是介于数学、计算机硬件和计算机软数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。件三者之间的一门核心课程。件三者之间的一门核心课程。件三者之间的一门核心课程。3.3.数数数数据据据据结结结结构构构构这这这这一一一一门门门门课课课课的的的的内内内内容容容容不不不不仅仅仅仅是是是是一一一一般般般般程程程程序序序序设设设设计计计计（特特特特别别别别是是是是非非非非数数数数值值值值性性性性程程程程序序序序设设设设计计计计）的的的的基基基基础础础础，而而而而且且且且是是是是设设设设计计计计和和和和实实实实现现现现编编编编译译译译程程程程序序序序、操操操操作作作作系系系系统统统统、数数数数据据据据库库库库系系系系统统统统及其他系统程序的重要基础。及其他系统程序的重要基础。及其他系统程序的重要基础。及其他系统程序的重要基础。1.2数据结构的概念数据结构的概念一、基本概念一、基本概念n n数据：数据：数据：数据：能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对象。象。象。象。n n数据元素：数据元素：数据元素：数据元素：对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。n n数据项：数据项：数据项：数据项：具有独立意义的最小数据单位。具有独立意义的最小数据单位。具有独立意义的最小数据单位。具有独立意义的最小数据单位。n n数据类型：数据类型：数据类型：数据类型：每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类型。型。型。型。基础基础基础基础 1.3数据的逻辑结构数据的逻辑结构一、基本概念一、基本概念n n数据对象：数据对象：数据对象：数据对象：具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。n n关系：关系：关系：关系：在数据对象中各数据元素之间存在着在数据对象中各数据元素之间存在着在数据对象中各数据元素之间存在着在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。系简单的用前驱和后继关系描述。系简单的用前驱和后继关系描述。系简单的用前驱和后继关系描述。1.3数据的逻辑结构数据的逻辑结构二、数据的逻辑结构二、数据的逻辑结构n n设设设设DD表示数据元素的集合，表示数据元素的集合，表示数据元素的集合，表示数据元素的集合，R R表示表示表示表示DD上的关系的集合，上的关系的集合，上的关系的集合，上的关系的集合，则一个数据结构则一个数据结构则一个数据结构则一个数据结构B B可表示为：可表示为：可表示为：可表示为：n nB=B=（D D，R R）n n由此可见数据结构由两部分构成由此可见数据结构由两部分构成由此可见数据结构由两部分构成由此可见数据结构由两部分构成n n（1 1）表示各元素的信息）表示各元素的信息）表示各元素的信息）表示各元素的信息 DDn n（2 2）表示数据之间关系的信息）表示数据之间关系的信息）表示数据之间关系的信息）表示数据之间关系的信息R Rn n一般用二元组表示一般用二元组表示一般用二元组表示一般用二元组表示DD中各数据元素之间的前驱、中各数据元素之间的前驱、中各数据元素之间的前驱、中各数据元素之间的前驱、后继关系。假设后继关系。假设后继关系。假设后继关系。假设a,ba,b是是是是DD中的两个元素，则二元组中的两个元素，则二元组中的两个元素，则二元组中的两个元素，则二元组表示表示表示表示a a是是是是b b的前驱，的前驱，的前驱，的前驱，b b是是是是a a的后继。的后继。的后继。的后继。1.3 数据的逻辑结构数据的逻辑结构三、数据结构的分类三、数据结构的分类三、数据结构的分类三、数据结构的分类n n线性结构：线性结构：线性结构：线性结构：除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。有唯一的后继。有唯一的后继。有唯一的后继。n n树状结构：树状结构：树状结构：树状结构：除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。n n网状结构：网状结构：网状结构：网状结构：各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。1.4 数据的存储结构数据的存储结构n n数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。n n数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。方式体现出结点之间的关系。方式体现出结点之间的关系。方式体现出结点之间的关系。n n四种基本的存储方式：四种基本的存储方式：四种基本的存储方式：四种基本的存储方式：n n1 1、顺序方式、顺序方式、顺序方式、顺序方式n n顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。1.4 数据的存储结构数据的存储结构n n2 2、链接方式、链接方式、链接方式、链接方式n n链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。存储其后继结点的地址。存储其后继结点的地址。存储其后继结点的地址。n n3 3、索引方式、索引方式、索引方式、索引方式n n在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系排成一个序列（排成一个序列（排成一个序列（排成一个序列（a a1 1,a,a2 2,a,a3 3,a an n)。每个结点。每个结点。每个结点。每个结点a ai i在在在在序列中都对应一个序号序列中都对应一个序号序列中都对应一个序号序列中都对应一个序号i i序号序号序号序号i i也称为结点也称为结点也称为结点也称为结点a ai i的索的索的索的索引号。索引存储就是通过建立一个附加的索引引号。索引存储就是通过建立一个附加的索引引号。索引存储就是通过建立一个附加的索引引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结表，然后利用索引表中的索引项的值来确定结表，然后利用索引表中的索引项的值来确定结表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。点的实际存储单元的地址。点的实际存储单元的地址。点的实际存储单元的地址。1.4 数据的存储结构数据的存储结构n n4 4、散列方式、散列方式、散列方式、散列方式n n利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。1.5 数据运算和算法数据运算和算法1 1、数据运算、数据运算、数据运算、数据运算n n按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。有效地处理数据，提高数据的运算效率。有效地处理数据，提高数据的运算效率。有效地处理数据，提高数据的运算效率。n n1 1）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。n n2 2）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。n n3 3）更新：改变指定结点的值或者改变某些结点的关）更新：改变指定结点的值或者改变某些结点的关）更新：改变指定结点的值或者改变某些结点的关）更新：改变指定结点的值或者改变某些结点的关系称为更新。系称为更新。系称为更新。系称为更新。n n4 4）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。n n5 5）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破小到大或从大到小的重新排列。排序运算实际上是破小到大或从大到小的重新排列。排序运算实际上是破小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。1.5 数据运算和算法数据运算和算法2 2、算法、算法、算法、算法n n算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。n n算法应具有的几个特征：算法应具有的几个特征：算法应具有的几个特征：算法应具有的几个特征：n n1 1）有穷性：算法应在计算机存储资源容许的条件下，）有穷性：算法应在计算机存储资源容许的条件下，）有穷性：算法应在计算机存储资源容许的条件下，）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。在一定时间内执行完毕。在一定时间内执行完毕。在一定时间内执行完毕。n n2 2）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。n n3 3）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。的数据后，应得到正确的结果。的数据后，应得到正确的结果。的数据后，应得到正确的结果。1.5 数据运算和算法数据运算和算法3 3、算法的评价、算法的评价、算法的评价、算法的评价n n对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标n n空间复杂度空间复杂度空间复杂度空间复杂度n n空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间大小。大小。大小。大小。n n时间复杂度时间复杂度时间复杂度时间复杂度n n时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。第二章第二章 线性表线性表n n线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。n n线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结构和链接存储结构。构和链接存储结构。构和链接存储结构。构和链接存储结构。2.1 线性表的定义及基本运算线性表的定义及基本运算n n一、线性表的定义一、线性表的定义一、线性表的定义一、线性表的定义n n线性表是由线性表是由线性表是由线性表是由n(n0)n(n0)个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素a a1 1,a,a2 2,a,a3 3,a an n组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为(a(a1 1,a,a2 2,a,a3 3,a an n)。n n二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算n n（1 1）置线性表为空表；）置线性表为空表；）置线性表为空表；）置线性表为空表；n n（2 2）求线性表的长度；）求线性表的长度；）求线性表的长度；）求线性表的长度；n n（3 3）读取线性表中的第）读取线性表中的第）读取线性表中的第）读取线性表中的第i i个元素；个元素；个元素；个元素；n n（4 4）修改线性表中的第）修改线性表中的第）修改线性表中的第）修改线性表中的第i i个元素；个元素；个元素；个元素；n n（5 5）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；2.1 线性表的定义及基本运算线性表的定义及基本运算n n二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算n n（6 6）在线性表的第）在线性表的第）在线性表的第）在线性表的第i i个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个新的数据元素；个新的数据元素；个新的数据元素；个新的数据元素；n n（7 7）删除线性表中第）删除线性表中第）删除线性表中第）删除线性表中第i i个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件的第一个数据元素；的第一个数据元素；的第一个数据元素；的第一个数据元素；n n（8 8）对线性表中的所有元素按照给定的关键字大）对线性表中的所有元素按照给定的关键字大）对线性表中的所有元素按照给定的关键字大）对线性表中的所有元素按照给定的关键字大小进行排序。小进行排序。小进行排序。小进行排序。2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、一、一、一、线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性顺序依次存放在内存中一组连续的存储单元中，即把线性顺序依次存放在内存中一组连续的存储单元中，即把线性顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。线性表在线性表在线性表在线性表在c c语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。c c语言的描述语言的描述语言的描述语言的描述 Typedef int ET;Typedef int ET;#define maxlen 1000#define maxlen 1000 ET smaxlen;ET smaxlen;2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、一、一、一、线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表线性表线性表线性表C C语言描述的说明：语言描述的说明：语言描述的说明：语言描述的说明：在在在在C C语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从0 0开始的，数开始的，数开始的，数开始的，数据结构中的结点的序号是从一开始的。因此据结构中的结点的序号是从一开始的。因此据结构中的结点的序号是从一开始的。因此据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指在线性表中的第一个元素是指在线性表中的第一个元素是指在线性表中的第一个元素是指S0S0。两个相邻结点两个相邻结点两个相邻结点两个相邻结点a ai i和和和和a a i+1i+1的存储位置记为的存储位置记为的存储位置记为的存储位置记为 LOCLOC（a ai i ）和）和）和）和LOCLOC（a a i+1i+1 ），则结点满足），则结点满足），则结点满足），则结点满足以下关系以下关系以下关系以下关系 LOCLOC（a a i+1i+1 ）=LOC=LOC（a ai i ）+1+12.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算1 1、插入运算的算法描述：、插入运算的算法描述：、插入运算的算法描述：、插入运算的算法描述：int insertqlist(int i,ET x,ET s,int*np)int insertqlist(int i,ET x,ET s,int*np)int j,n;int j,n;n=*np;n=*np;if(in+1)if(in+1)return(0);return(0);else else for(j=n;j=i;j-)for(j=n;j=i;j-)sj=sj-1;sj=sj-1;sj=x;sj=x;*np=+n;*np=+n;return(1);return(1);2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算2 2、删除运算的算法描述：、删除运算的算法描述：、删除运算的算法描述：、删除运算的算法描述：int delqlist(int i,ET s,int*np)int delqlist(int i,ET s,int*np)int j,n;int j,n;n=*np;n=*np;if(in)if(in)return(0);return(0);else else for(j=i;jn;j+)for(j=i;jn;j+)sj-1=sj;sj-1=sj;*np=-n;*np=-n;return(1);return(1);2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算3 3、查找运算的算法描述：、查找运算的算法描述：、查找运算的算法描述：、查找运算的算法描述：int fincl(ET x,ET s,int n)int fincl(ET x,ET s,int n)int j;int j;for(i=0;in;i+)for(i=0;idata=0;p-link=NULL;head=p;p-data=0;p-link=NULL;head=p;for(i=1;i=n;i+)for(i=1;idata);scanf(%d,&q-data);q-link=NULL;p-link=q;p=p-link;q-link=NULL;p-link=q;p=p-link;return(head);return(head);2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算2 2、查找链表中的、查找链表中的、查找链表中的、查找链表中的 X X 查找链表中是否存在结点查找链表中是否存在结点查找链表中是否存在结点查找链表中是否存在结点X X，算法的基本思想为：，算法的基本思想为：，算法的基本思想为：，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值点的数据域和给定值点的数据域和给定值点的数据域和给定值X X 进行比较，直到某个结点的进行比较，直到某个结点的进行比较，直到某个结点的进行比较，直到某个结点的数据域的值等于给定值数据域的值等于给定值数据域的值等于给定值数据域的值等于给定值X X（既查找成功），则返回（既查找成功），则返回（既查找成功），则返回（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找该结点的地址；如果查找到表尾仍未找到（既查找该结点的地址；如果查找到表尾仍未找到（既查找该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回失败），则返回失败），则返回失败），则返回NULLNULL。查找单链表中结点X的算法描述：NODE*found(NODE*head,ET x)NODE*p;p=head-link;while(p!=NULL)&(p-data!=x)p=p-link;return(p);2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算3 3、在单链表中插入新结点、在单链表中插入新结点、在单链表中插入新结点、在单链表中插入新结点X X 在链表中的某一结点在链表中的某一结点在链表中的某一结点在链表中的某一结点p p 之后插入一个数据为之后插入一个数据为之后插入一个数据为之后插入一个数据为X X 的新结的新结的新结的新结点。过程如下：点。过程如下：点。过程如下：点。过程如下：（1 1）生成一个新结点）生成一个新结点）生成一个新结点）生成一个新结点q q，将，将，将，将X X 赋给赋给赋给赋给q-data;q-data;（2 2）修改有关结点的指针域：将原）修改有关结点的指针域：将原）修改有关结点的指针域：将原）修改有关结点的指针域：将原p p 结点的后继作为结点的后继作为结点的后继作为结点的后继作为q q 结点的后继，结点的后继，结点的后继，结点的后继，q q 结点作为结点作为结点作为结点作为p p 结点的后继。结点的后继。结点的后继。结点的后继。在单链表中插入新结点在单链表中插入新结点X X的算法描述：的算法描述：void insert(NODE*head,NODE*p,ET x)void insert(NODE*head,NODE*p,ET x)NODE*q;NODE*q;q=(NODE*)malloc(sizeof(NODE);q=(NODE*)malloc(sizeof(NODE);q-data=x;q-data=x;if(head-link=NULL)if(head-link=NULL)head-link=q;q-link=NULL;head-link=q;q-link=NULL;else else q-link=p-link;p-link=q;q-link=p-link;p-link=q;2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算4 4、删除单链表中的结点、删除单链表中的结点、删除单链表中的结点、删除单链表中的结点X X 删除单链表中的结点删除单链表中的结点删除单链表中的结点删除单链表中的结点X X，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空间。过程如下：间。过程如下：间。过程如下：间。过程如下：（1 1）设定两指针）设定两指针）设定两指针）设定两指针p p 和和和和q q，p p 指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；q q 为为为为跟踪结点，指向被删除结点的前驱结点跟踪结点，指向被删除结点的前驱结点跟踪结点，指向被删除结点的前驱结点跟踪结点，指向被删除结点的前驱结点;（2 2）p p 从表头指针从表头指针从表头指针从表头指针headhead指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依次进行搜索。当次进行搜索。当次进行搜索。当次进行搜索。当p-datap-data等于等于等于等于X X 时，被删除结点找到。时，被删除结点找到。时，被删除结点找到。时，被删除结点找到。（3 3）修改）修改）修改）修改p p 的前驱结点的前驱结点的前驱结点的前驱结点q q 的指针域：使被删除结点的后的指针域：使被删除结点的后的指针域：使被删除结点的后的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既继结点成为其前驱结点的后继结点，既继结点成为其前驱结点的后继结点，既继结点成为其前驱结点的后继结点，既q-link=p-linkq-link=p-link，p p结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。在单链表中删除结点在单链表中删除结点X X的算法描述：的算法描述：void delete(NODE*head,ET x)void delete(NODE*head,ET x)NODE*p,*q;NODE*p,*q;p=head;q=p;p=head;q=p;p=p-link;p=p-link;while(p!=NULL)&(p-data!=x)while(p!=NULL)&(p-data!=x)q=p;p=p-link;q=p;p=p-link;if(p=NULL)if(p=NULL)printf(Not found!n);printf(Not found!n);else else q-link=p-link;free(p);q-link=p-link;free(p);2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表三、循环链表三、循环链表 链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循环链表。环链表。环链表。环链表。循环链表是线性链表的一种变形。其优点是循环链表是线性链表的一种变形。其优点是循环链表是线性链表的一种变形。其优点是循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中的所有结点。的所有结点。的所有结点。的所有结点。在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。可以附加一个表头结点。可以附加一个表头结点。可以附加一个表头结点。2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表非空表（非空表（a)a)headheadheadhead空表（空表（b)b)(1)(1)在头指针为在头指针为headhead的循环链表查找值为的循环链表查找值为x x的前驱的前驱结点。结点。NODE*looknode(head,x)NODE*looknode(head,x)ET x;NODE*head;ET x;NODE*head;NODE*p;NODE*p;p=head;p=head;while(p-link!=head)&while(p-link!=head)&(p-link)-data)!=x)(p-link)-data)!=x)p=-link;p=-link;return(p);return(p);(2)(2)在头指针为在头指针为headhead的循环链表在值为的循环链表在值为x x的结点之的结点之前插入一个值为前插入一个值为b b的新结点。的新结点。NODE insnode(head,x,b)NODE insnode(head,x,b)ET x,b;NODE*head;ET x,b;NODE*head;NODE*p,*q;NODE*p,*q;p=(NODE*)malloc(sizeof(NODE);p=(NODE*)malloc(sizeof(NODE);p-data=b;p-data=b;q=looknode(head,x);q=looknode(head,x);p-link=q-link;p-link=q-link;q-link=p;q-link=p;return;return;(3)(3)在头指针为在头指针为headhead的循环链表中，删除值为的循环链表中，删除值为x x的的结点。结点。Void delnode(head,x)Void delnode(head,x)ET x;NODE*head;ET x;NODE*head;NODE*p,*q;NODE*p,*q;q=looknode(head,x);q=looknode(head,x);if(q-link=head)if(q-link=head)printf(printf(“No this node the list!nNo this node the list!n”)return;return;p=q-link;q-link=p-link;free(p);p=q-link;q-link=p-link;free(p);return;return;2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算四、循环链表四、循环链表四、循环链表四、循环链表 一个链表的每一个结点含有两个指一个链表的每一个结点含有两个指一个链表的每一个结点含有两个指一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称为双向链表。为双向链表。为双向链表。为双向链表。五、双向链表五、双向链表headhead llinkllinkrlinkrlinkdatadata带头结点的双向链表带头结点的双向链表带头结点的双向链表带头结点的双向链表双向链表的结点结构双向链表的结点结构双向链表的结点结构双向链表的结点结构2.4 数组数组一、数组的定义一、数组的定义 数组是由一组类型相同的数据元素构造数组是由一组类型相同的数据元素构造而成。而成。若数组元素只含有一个下标，这样的数若数组元素只含有一个下标，这样的数组称为一维数组。组称为一维数组。当一个数组的每一个数组元素都含有两当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。个下标时，该数组称为两维数组。2.4 数组数组二、数组的存储结构二、数组的存储结构二、数组的存储结构二、数组的存储结构 数组是一种顺序存储结构。也就是将数组元素顺序数组是一种顺序存储结构。也就是将数组元素顺序数组是一种顺序存储结构。也就是将数组元素顺序数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。三、规则矩阵的压缩存储三、规则矩阵的压缩存储三、规则矩阵的压缩存储三、规则矩阵的压缩存储 有时矩阵中包含大量的零元素（或某一确定值的元有时矩阵中包含大量的零元素（或某一确定值的元有时矩阵中包含大量的零元素（或某一确定值的元有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用压缩素