《精品课件数据结构概论》由会员分享，可在线阅读，更多相关《精品课件数据结构概论（138页珍藏版）》请在金锄头文库上搜索。
1、李云李云清清 杨庆红杨庆红 揭安全揭安全第1章概论 数据结构讨论的是数据的逻辑结构、存储方式数据结构讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题，为学习后续专业课程以及相关操作的实现等问题，为学习后续专业课程打下基础。本章讲述数据结构的基本概念及相关术打下基础。本章讲述数据结构的基本概念及相关术语，介绍数据结构、数据类型和抽象数据类型之间语，介绍数据结构、数据类型和抽象数据类型之间的联系，介绍了算法的特点及算法的时间与空间复的联系，介绍了算法的特点及算法的时间与空间复杂性。杂性。 1.1数据结构数据结构1.1.1数据结构随着计算机软、硬件的发展，计算机的应用范随着计算机软、硬件的发
2、展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。数据，而更多的是非数值数据。需要处理的数据并不是杂乱无章的，它们一定需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处理。才能使用计算机对大量的数据进行有效的处理。 某电信公司的市话用户信息表格如下图所示：某电信公司的市话用户信息表格如下图所示： 序号用户名
3、电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王 冬5700123瑶湖大道198700004王 三5700567瑶湖大道200800005江 凡8800129学府大道5035这里序号、用户名、电话号码等项称为基本项，它这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项意义的标识
4、单位，每一行称为一个结点，每一个组合项称为一个字段。称为一个字段。使用计算机处理用户信息表中的数据时，必须弄清楚使用计算机处理用户信息表中的数据时，必须弄清楚下面下面3 3个问题：个问题： 1 数据的逻辑结构这些数据之间有什么样的内在联系？这些数据之间有什么样的内在联系？ 除除最最前前和和最最后后两两个个结结点点之之外外，表表中中所所有有其其它它的的结结点点都都有有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之前前的的一一个个结结点点，也也有有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之后后的的一一个个结结点点，这这些些就就是是用户信息表的逻辑结构。用户信息表的逻辑结构。2数据的
5、存储结构 将将用用户户信信息息表表中中的的所所有有结结点点存存入入计计算算机机时时，就就必必须须考考虑虑存存储储结结构构，使使用用C C语语言言进进行行设设计计时时，常常见见的的方方式式是是用用一一个个结结构构数数组组来来存存储储整整个个用用户户信信息息表表，每每一一个个数数组组元元素素是是一一个个结结构构，它它对对应应于于用用户户信信息息表表中中的的一一个个结结点点。数数据在计算机的存储方式称为存储结构。据在计算机的存储方式称为存储结构。3数据的运算集合 数据处理必涉及到相关的运算，在上述用户信息表数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用中
6、，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为作，是删除序号为5 5的用户还是删除用户名为王三的用的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。一个运算（操作）集合。 对待处理的数据，只有分析清楚上面对待处理的数据，只有分析清楚上面3 3个方面的问个方面的问题，才能进行有效的处理！题，才能
7、进行有效的处理！ 数数数数据据据据结结结结构构构构就就是是指指按按一一定定的的逻逻辑辑结结构构组组成成的的一一批批数数据据，使使用用某某种种存存储储结结构构将将这这批批数数据据存存储储于于计计算算机机中中，并并在在这些数据上定义了一个运算集合。这些数据上定义了一个运算集合。1.1.2数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构是是数数据据和和数数据据之之间间所所存存在在的的逻逻辑辑关关系，它可以用一个二元组系，它可以用一个二元组B=B=（K K，R R）来表示，其中来表示，其中K K是数据、即结点的有限集合；是数据、即结点的有限集合；R R是集是集合合K K上关系的有限集合，这里
8、的关系是从集合上关系的有限集合，这里的关系是从集合K K到集到集合合K K的关系，这里一般只涉及到一个关系的逻辑结构。的关系，这里一般只涉及到一个关系的逻辑结构。 例例如如，有有5 5个个人人，分分别别记记为为a,b,c,d a,b,c,d ,e,e,其其中中a a是是b b的的父父亲亲，b b是是c c的的父父亲亲，c c是是d d的的父父亲亲, ,d d是是e e的的父父亲亲，如如果果只只讨讨论论他他们们之之间间所所存存在在的的父父子子关关系系，则则可可以以用用下下面面的的二二元元组组形形式式化地予以表达。化地予以表达。B=B=（K K，R R）其中：其中：K=a,b,c,d,eK=a,b
9、,c,d,e R=r R=rr=,r=, 逻逻辑辑结结构构的的图图形形表表示示方方式式，对对K K中中的的每每个个结结点点k ki i用用一一个个方方框框表表示示，而而结结点点之之间间的的关关系系用用带带箭箭头头的的线线段段表表示示，这这5 5人之间的逻辑结构用图形的方式表达如下图人之间的逻辑结构用图形的方式表达如下图 所示。所示。若若k ki iK K，k kj jR R， r r，则称则称k ki i是是k kj j的相对的相对于关系于关系r r的的前驱结点前驱结点，k kj j是是k ki i的相对于关系的相对于关系r r的的后继结点后继结点，因为一般只讨论具有一种关系的逻辑结构，即因为
10、一般只讨论具有一种关系的逻辑结构，即R=rR=r，所以简称所以简称k ki i是是k kj j前驱，前驱，k kj j是是k ki i的后继。如果某个结点没有的后继。如果某个结点没有前驱结点，称之为前驱结点，称之为开始结点开始结点；如果某个结点没有后继；如果某个结点没有后继结点，称之为结点，称之为终端结点终端结点；既不是开始结点也不是终端；既不是开始结点也不是终端结点的结点称为结点的结点称为内部结点内部结点。 1.1.3数据的存储结构数据的存储结构 数数据据的的逻逻辑辑结结构构是是独独立立于于计计算算机机的的，它它与与数数据据在在计计算算机机中中的的存存储储无无关关，要要对对数数据据进进行行处
11、处理理，就就必必须须将将数数据据存存储储在在计计算算机机中中。如如果果将将数数据据在在计计算算机机中中无无规规律律地地存存储储，那那么么在在处处理理时时是是非非常常糟糟的的，是是没没有有用用的的。试试想想一一下下，如如果果一一本本英英汉汉字字典典中中的的单单词词是是随随意意编编排排的的，这本字典谁会用！这本字典谁会用！ 对对于于一一个个数数据据结结构构B=B=（K K，R R），必必须须建建立立从从结结点点集集合合到到计计算算机机某某个个存存储储区区域域MM的的一一个个映映象象，这这个个映映象象要要直直接接或或间间接接地地表表达达结结点点之之间间的的关关系系R R。数数据据在在计计算算机中的存
12、储方式称为数据的存储结构。机中的存储方式称为数据的存储结构。数据的存储结构主要有数据的存储结构主要有4 4种。种。数据的存储结构主要有数据的存储结构主要有4 4种。种。1 1 顺序存储顺序存储顺序存储通常用于存储具有线性结构的数据。将顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域逻辑上相邻的结点存储在连续存储区域MM的相邻的存的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。储单元中，使得逻辑相邻的结点一定是物理位置相邻。 对于一个数据结构对于一个数据结构B=B=（K K，R R）其中其中K=kK=k1 1,k ,k2 2,k ,k3 3,k ,k4 4,
13、k ,k5 5,k ,k6 6,k ,k7 7,k ,k8 8,k ,k9 9 R=r R=r r=kr=,它的顺序存储方式如图所示它的顺序存储方式如图所示 2 2 链式存储链式存储链式存储方式是给每个结点附加一个指针段，一链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。指针，也可以是一个多个指针。 例，数据的逻辑结构例，数据的逻辑结构B=B=（K K，R R） 其中其中 K=kK=k1 1
14、,k ,k2 2,k ,k3 3,k ,k4 4,k ,k5 5 R=r R=r R= k R=,这是一个线性结构，它的链式存储如图所示。这是一个线性结构，它的链式存储如图所示。 3 3 索引存储索引存储在线性结构中，设开始结点的索引号为在线性结构中，设开始结点的索引号为1 1，其它结，其它结点的索引号等于其前继结点的索引号加点的索引号等于其前继结点的索引号加1 1，则每一个结，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。确定该结点的存储地址。 4 4 散列存储散列存储散列存储的思想是构造一个从集合散列存储的思想是
15、构造一个从集合K K到存储区域到存储区域MM的一个函数的一个函数h h，该函数的定义域为该函数的定义域为K K，值域为值域为MM，K K中的中的每个结点每个结点k ki i在计算机中的存储地址由在计算机中的存储地址由h(h(k ki i) )确定。确定。 1.1.4数据的运算集合数据的运算集合对于一批数据，数据的运算是定义在数据的逻对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存辑结构之上的，而运算的具体实现就依赖于数据的存储结构。储结构。 数数据据的的运运算算集集合合要要视视情情况况而而定定，一一般般而而言言，数数据据的运算包括插入、删除、检索、输出、排
16、序等。的运算包括插入、删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。排序：将一个结构中所有结点按某种顺序重新排列。在程序设计中，数据和运算是两个不可缺少的因在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相素。所有的程序设计活动都是围绕着数据和
17、其上的相关运算而进行的。从机器指令、汇编语言中的数据没关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。次次抽象，数据的抽象经历了三个发展阶段。 1.2数据类型和抽象数据类型数据类型和抽象数据类型从无类型的二进制数到基本数据类型的产生从无类型的二进制数到基本数据类型的产生 从基本数据类型到用户自定义类型的产生从基本数据类型到用户自定义类型的产生 从用户自定义类型到抽象数据类型的
18、出现从用户自定义类型到抽象数据类型的出现 1.2.1数据类型数据类型数据类型（或简称类型）反映了数据的取值范围以数据类型（或简称类型）反映了数据的取值范围以及对这类数据可以施加的运算。及对这类数据可以施加的运算。1.2.2数据结构数据结构 数数据据结结构构是是计计算算机机科科学学中中广广泛泛使使用用的的一一个个术术语语，在在计计算算机机科科学学中中具具有有非非常常重重要要的的作作用用。数数据据结结构构包包括括三三个个方方面面的的内内容容：一一组组数数据据中中各各数数据据之之间间的的逻逻辑辑关关系系；这这组组数数据据在在计计算算机机中中的的存存储储方方式式；对对这这组组数数据据所所能能施施加加的
19、的运运算算的的集集合合。数数据据结结构构是是数数据据存存在在的的形形式式。所所有有的的数数据据都都是是按按照照数数据据结结构构进进行行分分类类的的。简简单单数数据据类类型型对对应应于于简简单单的数据结构；构造数据类型对应于复杂的数据结构。的数据结构；构造数据类型对应于复杂的数据结构。1.2.3抽象数据类型抽象数据类型抽象数据类型是与表示无关的数据类型，是一个数抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符类型进行定义时，必须给出它的名字及各运算的运算符名
20、，即函数名，并且规定这些函数的参数性质。一旦定名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类像使用基本数据类型那样，十分方便地使用抽象数据类型。型。 1.2.4抽象数据类型的描述和实现抽象数据类型的描述和实现抽象数据类型的描述包括给出抽象数据类型的名称、抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具述。抽象数
21、据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。数据类型。 抽象数据类型描述的一般形式如下：抽象数据类型描述的一般形式如下：ADTADT抽象数据类型名称抽象数据类型名称 数据对象：数据对象：数据关系：数据关系：操作集合：操作集合：操作名操作名1 1：操作名操作名n n：ADTADT抽象数据类型名称抽象数据类型名称 1.3 1.3 算法和算法分析算法和算法分析 1.3.1算法算法 为为了了求求解解某某问问题题，必必须须给给出出一一系系列列的的运运算算规规则则，这这一一系系列列的的运运算算规规则则是是有
22、有限限的的，表表达达了了求求解解问问题题方方法和步骤，这就是一个算法。法和步骤，这就是一个算法。 一一个个算算法法可可以以用用自自然然语语言言描描述述，也也可可以以用用高高级级程程序序设设计计语语言言描描述述，也也可可以以用用伪伪代代码码描描述述。本本书书采采用用C C语言对算法进行描述。语言对算法进行描述。算法具有五个基本特征：算法具有五个基本特征：有穷性，算法的执行必须在有限步内结束。有穷性，算法的执行必须在有限步内结束。确确定定性性，算算法法的的每每一一个个步步骤骤必必须须是是确确定定的的无无二二义义性性的。的。输入，输入， 算法可以有算法可以有0 0个或多个输入。个或多个输入。输出，输
23、出， 算法一定有输出结果算法一定有输出结果可行性，算法中的运算都必须是可以实现的。可行性，算法中的运算都必须是可以实现的。算法具有有穷性，程序不需要具备有穷性。一般算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。永远都不会终止的。 1.3.2算法的时间和空间复杂性算法的时间和空间复杂性一个算法的优劣主要从算法的执行时间和所需一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行
24、时间的度要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。执行次数，称为计算量来度量。 算法中基本操作的执行次数一般
25、是与问题规模算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为有关的，对于结点个数为n n的数据处理问题，用的数据处理问题，用T(n)T(n)表示算法基本操作的执行次数。表示算法基本操作的执行次数。 在评价算法的时间复杂性时，不考虑两算法执行在评价算法的时间复杂性时，不考虑两算法执行次数之间的细小区别，而只关心算法的本质差别。为次数之间的细小区别，而只关心算法的本质差别。为此，引入一个所谓的此，引入一个所谓的O()O()记号，则记号，则T1(n)=2n=O(n),T2(n)=n+1=O(n)T1(n)=2n=O(n),T2(n)=n+1=O(n)。一个函数一个函数f(n)f(n)是
26、是O(g(n)O(g(n)的，则一定存在正常数的，则一定存在正常数c c和和mm，使对所有的使对所有的nmnm，都满足都满足f(n)c*g(n)f(n)c*g(n)。下下面面的的表表格格给给出出了了一一些些具具体体函函数数的的O()O()的的表表示示，如如图图所示。所示。f(n)O(g(n)量级量级35O(1)常数阶常数阶2n+7O(n)线性阶线性阶n2+10O(n2)平方阶平方阶2n3+nO(n3)立方阶立方阶算法的时间复杂性不仅和问题的规模大小有关，算法的时间复杂性不仅和问题的规模大小有关，还与问题数据的初始状态有关。还与问题数据的初始状态有关。 这这样样就就有有了了算算法法在在最最好好、
27、最最坏坏以以及及在在平平均均状状态态下下的的时间复杂性的概念。时间复杂性的概念。算算法法在在最最好好情情况况下下的的时时间间复复杂杂性性是是指指算算法法计计算算量量的的最小值。最小值。算算法法在在最最坏坏情情况况下下的的时时间间复复杂杂性性是是指指算算法法计计算算量量的的最大值。最大值。算算法法的的平平均均情情况况下下的的时时间间复复杂杂性性是是指指算算法法在在所所有有可可能的情况下的计算量经过加权计算出的平均值。能的情况下的计算量经过加权计算出的平均值。 本书在对算法进行分析时，会用到如下两个记号：本书在对算法进行分析时，会用到如下两个记号： x x ：表示不大于表示不大于x x的最大整数；
28、的最大整数； x x ：表示不小于表示不小于x x的最小整数。的最小整数。第第2章章 线性表及其顺序存储线性表及其顺序存储 线性表是一种常用的数据结构，本章介绍线性表线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。了详细的设计描述。 2.1线性表线性表线性表是一个线性结构，它是一个含有线性表是一个线性结构，它是一个含有n0n0个结个结点的有限序列，对于其中的结点，有且仅有一个开点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个始结点没有前驱但有一个后继结
29、点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：个线性表可以表示成一个线性序列：k k1 1,k,k2 2,k kn n，其中其中k k1 1是开始结点，是开始结点，k kn n是终端结点。是终端结点。 2.2.1顺序表顺序表 线性表采用顺序存储的方式存储就称之为顺序表。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单
30、元中。地址连续的存储单元中。 如如顺顺序序表表的的每每个个结结点点占占用用lenlen个个内内存存单单元元，用用location location ( (k ki i) )表表示示顺顺序序表表中中第第i i个个结结点点k ki i所所占占内内存存空空间间的的第第1 1个单元的地址。则有如下的关系个单元的地址。则有如下的关系location (location (k ki i+1+1) = location () = location (k ki i) +len) +lenlocation (location (k ki i) = location(k) = location(k1 1) + (
31、i-1)len) + (i-1)len2.2顺序表顺序表顺序表的存储结构如下图所示：顺序表的存储结构如下图所示： 存储结构要体现数据的逻辑结构，顺序表的存储存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。中的逻辑关系。 顺序表类型的描述如下：顺序表类型的描述如下：ADT sequence_listADT sequence_list数据集合数据集合K K：K=kK=k1 1, k, k2 2, k kn n,n,n 0 0，K K中的元素是中的元素是datatypedatatype类型类型数据关系
32、数据关系R R：R=rR=r，r= r= | i=1,2,n-1| i=1,2,n-1操作集合：操作集合：(1) (1) void init_sequence_list(sequence_list *void init_sequence_list(sequence_list *sltslt) ) 顺序表的初始化顺序表的初始化-置空表置空表 (2) (2) void insert_sequence_list(sequence_list *void insert_sequence_list(sequence_list *sltslt, ,datatypedatatype x) x) 后部插入值为后
33、部插入值为x x结点结点(3) (3) void print_sequence_list(sequence_listvoid print_sequence_list(sequence_list slt slt) ) 打印顺序表的各结点值打印顺序表的各结点值(4) (4) intint is_empty_sequence_list(sequence_list is_empty_sequence_list(sequence_list slt slt) ) 判断顺序表是否为空判断顺序表是否为空(5) (5) intint find_num_sequence_list(sequence_list fi
34、nd_num_sequence_list(sequence_list slt slt, ,datatypedatatype x) x) 查找值为查找值为x x结点位置结点位置(6) (6) intint get_data_pos(sequence_list get_data_pos(sequence_list slt slt, ,intint i) i) 取得顺序表中第取得顺序表中第i i个结点的值个结点的值(7) (7) void insert_pos_sequence_list(sequence_list *void insert_pos_sequence_list(sequence_li
35、st *sltslt, ,intint position, position,datatypedatatype x) x)(8) void delete_pos_sequence_list(sequence_list *(8) void delete_pos_sequence_list(sequence_list *sltslt, ,intint position) position) ADT sequence_list ADT sequence_list；2.2.2顺序表的实现顺序表的实现 用用C C语语言言中中的的数数组组存存储储顺顺序序表表。C C语语言言中中数数组组的的下下标标是是从从
36、0 0开开始始的的，即即数数组组中中下下标标为为0 0的的元元素素对对应应的的是是顺顺序序表表中中的的第第1 1个个结结点点，数数组组中中下下标标为为i i的的元元素素对对应应的的是是顺顺序序表表中中的的第第i+1i+1个个结结点点。为为了了方方便便，将将顺顺序序表表中中各各结结点点的的序序号号改改为为和和对对应应数数组组元元素素的的下下标标序序号号一一致致，即即将将顺顺序序表表中中各各结结点点的的序序号号从从0 0开开始始编编号号。这这样样，一一个个长长度度为为n n的顺序表可以表示为的顺序表可以表示为 k k0 0, k, k1 1, k, k2 2, , , , k kn n-1-1 顺
37、序表的存储结构的顺序表的存储结构的C C语言描述如下：语言描述如下：/*/*/*/*顺序表的头文件，文件名顺序表的头文件，文件名sequlistsequlist.h*/.h*/*/*/ #defineMAXSIZE100#defineMAXSIZE100typedefintdatatypetypedefintdatatype; ;typedefstructtypedefstruct datatypedatatypeaMAXSIZE;aMAXSIZE;intintsize;size;sequence_list;sequence_list;顺序表的几个基本操作的具体实现顺序表的几个基本操作的具体实
38、现 ：/*/*/* /* 顺序表的初始化顺序表的初始化-置空表置空表 */ */* /* 文件名文件名seqlinitseqlinit.c, .c, 函数名函数名init_sequence_list() */init_sequence_list() */*/ /*/ voidinit_sequence_list(sequence_list*voidinit_sequence_list(sequence_list*sltslt) ) sltslt-size=0;-size=0; 算法算法2.12.1顺序表的初始化顺序表的初始化-置空表置空表/*/*/ /* /* 在顺序表后部进行插入操作在顺序表
39、后部进行插入操作 */ */* /* 文件名文件名seqlinseseqlinse.c, .c, 函数名函数名insert_sequence_list() */insert_sequence_list() */*/*/ / voidinsert_sequence_list(sequence_list*voidinsert_sequence_list(sequence_list*sltslt, ,datatypedatatypex)x) if(if(sltslt-size=MAXSIZE)-size=MAXSIZE)printfprintf( (顺序表是满的顺序表是满的!);!);exit(1)
40、;exit(1);sltslt-size=-size=sltslt-size+1;-size+1;sltslt-a-asltslt-size=x;-size=x; 算法算法2.22.2在顺序表后部进行插入操作在顺序表后部进行插入操作 /*/*/ /* /* 打印顺序表的各结点值打印顺序表的各结点值 */ */* /* 文件名文件名seqlprinseqlprin.c, .c, 函数名函数名print_sequence_list() */print_sequence_list() */*/ /*/ voidprint_sequence_list(sequence_listvoidprint_se
41、quence_list(sequence_listsltslt) ) intinti;i;if(!if(!sltslt.size).size)printfprintf(n(n顺序表是空的顺序表是空的!);!);elseelsefor(i=0;ifor(i=0;isltslt.size;i+).size;i+)printfprintf(%5d,(%5d,sltslt.ai);.ai); 算法算法2.32.3打印顺序表的各结点值打印顺序表的各结点值/*/*/ /* /* 判断顺序表是否为空判断顺序表是否为空 */ */* /* 文文件件名名seqlemptseqlempt.c, .c, 函函数数名
42、名is_empty_sequence_list() is_empty_sequence_list() */*/*/*/ /intintis_empty_sequence_list(sequence_listis_empty_sequence_list(sequence_listsltslt) ) return(return(sltslt.size=0?0:1);.size=0?0:1); 算法算法2.42.4判断顺序表是否为空判断顺序表是否为空/*/*/ /* /* 查找顺序表中值为查找顺序表中值为x x的结点位置的结点位置 */ */* /* 文文件件名名seqlfindseqlfind.c
43、, .c, 函函数数名名find_num_sequence_list() find_num_sequence_list() */*/*/*/ /intintfind_num_sequence_list(sequence_listfind_num_sequence_list(sequence_listsltslt, ,datatypedatatypex)x) intinti=0;i=0;while(while(sltslt.ai!=x&i.ai!=x&isltslt.size)i+;.size)i+;return(ireturn(isltslt.size?i:-1);.size?i:-1); 算
44、法算法2.52.5查找顺序表中值为查找顺序表中值为x x的结点位置的结点位置/*/*/* /* 取得顺序表中第取得顺序表中第i i个结点的值个结点的值 */ */*/*文文件件名名seqlgetseqlget.c,.c,函函数数名名get_data_pos_sequence_list() get_data_pos_sequence_list() */*/*/*/intintget_data_pos(sequence_listget_data_pos(sequence_listsltslt, ,intinti)i) if(i=if(i=sltslt.size).size)printfprintf
45、(n(n指定位置的结点不存在指定位置的结点不存在!);!);exit(1);exit(1);elseelsereturnreturnsltslt.ai;.ai; 算法算法2.62.6取得顺序表中第取得顺序表中第i i个结点的值个结点的值 顺顺序序表表的的插插入入运运算算是是将将一一个个值值为为x x的的结结点点插插入入到到顺顺序序表表的的第第i i个个位位置置0 0 i i n n，即即将将x x插插入入到到k ki i-1-1和和k ki i之之间间，如如果果i=ni=n，则表示插入到表的最后，一般地可表示为：则表示插入到表的最后，一般地可表示为：插入前：插入前： k k0 0, k, k1
46、 1, , , , k ki i-1-1, , k ki i, , , , k kn n-1-1 插入后：插入后： k k0 0,k,k1 1,kki i-1-1,x,x,kki i,kkn n-1-1 插入过程的图示见下图：插入过程的图示见下图： /*/*/ /* /* 在顺序表的在顺序表的positionposition位置插入值为位置插入值为x x的结点的结点 */ */* /* 文文件件名名seqlinseseqlinse.c, .c, 函函数数名名insert_pos_sequence_list() insert_pos_sequence_list() */*/*/*/voidvoi
47、dinsert_pos_sequence_list(sequence_listinsert_pos_sequence_list(sequence_list* *sltslt, ,intint position,position,datatypedatatypex)x)intinti;i;if(if(sltslt-size=MAXSIZE)-size=MAXSIZE)printfprintf(n(n顺序表是满的顺序表是满的! !没法插入没法插入!);!);exit(1);exit(1);if(positionif(positionsltslt-size)-size)printfprintf(n(
48、n指定的插入位置不存在指定的插入位置不存在!);!);exit(1);exit(1);for(i=for(i=sltslt-size;iposition;i-)-size;iposition;i-)sltslt-ai=-ai=sltslt-ai-1;-ai-1;sltslt-aposition=x;-aposition=x;sltslt-size+;-size+; 算法算法2.72.7在顺序表的在顺序表的positionposition位置插入值为位置插入值为x x的结点的结点 算算法法2.72.7中中，所所花花费费的的时时间间主主要要是是元元素素后后移移操操作作，对对于于在在第第i i个个位
49、位置置上上插插入入一一个个新新的的元元素素，需需要要移移动动（n-in-i）个个元元素素，设设在在第第i i个个位位置置上上插插入入一一个个元元素素的的概概率率为为p pi i，且且在在 任任 意意 一一 个个 位位 置置 上上 插插 入入 元元 素素 的的 概概 率率 相相 等等 ， 即即p p0 0=p=p1 1=p=p2 2= = =p pn n=1/n+1=1/n+1，则则在在一一个个长长度度为为n n的的顺顺序序表表中中插插入一个元素所需的平均移动次数为：入一个元素所需的平均移动次数为：即在长度为即在长度为n n的顺序表中插入一个元素平均需要的顺序表中插入一个元素平均需要移动表中的一
50、半元素。该算法的时间复杂度为移动表中的一半元素。该算法的时间复杂度为OO（n n）。）。 顺顺序序表表的的删删除除操操作作是是指指删删除除顺顺序序表表中中的的第第i i个个结结点点，0 0 i i n-1n-1，一般地可表示为：一般地可表示为：删除前：删除前： k k0 0, k, k1 1, , , , k ki i-1-1, , k ki i, , k ki i+1+1, , , , , k kn n-1-1 删除后：删除后： k k0 0,k,k1 1,kki i-1-1,k ki i+1+1,kkn n-1-1 删除过程的图示见下图删除过程的图示见下图 ：删除操作的具体实现见算法删除操
51、作的具体实现见算法2.82.8/*/*/* /* 删除顺序表中第删除顺序表中第positionposition位置的结点位置的结点 */ */* /* 文文件件名名seqldeleseqldele.c, .c, 函函数数名名delete_pos_sequence_list() delete_pos_sequence_list() */*/*/*/voiddelete_pos_sequence_list(sequence_list*voiddelete_pos_sequence_list(sequence_list*sltslt, ,intintposition)position) intint
52、i;i;if(if(sltslt-size=0)-size=0)printfprintf(n(n顺序表是空的顺序表是空的!);!);exit(1);exit(1);if(position=if(position=sltslt-size)-size)printfprintf(n(n指定的删除位置不存在指定的删除位置不存在!);!);exit(1);exit(1);for(i=position;ifor(i=position;isize-1;i-)-size-1;i-)sltslt-ai=-ai=sltslt-ai+1;-ai+1;sltslt-size-;-size-; 算法算法2.82.8删除
53、顺序表中第删除顺序表中第positionposition位置的结点位置的结点 要要删删除除顺顺序序表表中中的的第第i i个个结结点点，则则需需要要称称动动（n-i-1n-i-1）个个元元素素，设设删删除除表表中中第第i i个个结结点点的的概概率率为为q qi i，且且在在表表中中每每一个位置删除的概率相等，即：一个位置删除的概率相等，即：q q0 0=q=q1 1= = =q qn n-1-1=1/n=1/n则在一个长度为则在一个长度为n n的顺序表中删除一个结点的平均的顺序表中删除一个结点的平均移动次数为：移动次数为： 这表明，在一个长为这表明，在一个长为n n的顺序表中删除一个元素平的顺序
54、表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂均需要移动表中大约一半的元素。该算法的时间复杂度为度为OO（n n）。）。 2.3 栈栈 2.3.1栈栈 栈是一种特殊的线性表，对于这种线性表规定它栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为栈顶，另一端称为栈底。行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。栈的插入操作和删除操作也分别简称进栈和出栈。 如果栈中有如果栈中有n n个结点个结点 k k0 0,k,k1 1,k,
55、k2 2,kkn n- -1 1 ，k k0 0为栈底，为栈底，k kn n-1-1是是栈顶，则栈中结点的栈顶，则栈中结点的进栈顺序为进栈顺序为k k0 0,k,k1 1, ,k k2 2,kkn n-1-1，而出栈而出栈的顺序为的顺序为k kn n-1-1, ,kkn n-2-2, ,k,k1 1,k,k0 0。如图所如图所示。示。 栈具有后栈具有后进先出或进先出或先进后出先进后出（FILO,FFILO,FirstInirstInLastLastOutOut）的的性质性质 栈类型的描述如下：栈类型的描述如下：ADTsequence_stackADTsequence_stack数数据据集集合合
56、K K：K=kK=k1 1, ,k k2 2, k kn n,n0,n0，K K中中的的元元素素是是datatypedatatype类型类型数据关系数据关系R R：R=rR=rr=r=|i=1,2,n-1|i=1,2,n-1操作集合：操作集合：(1)(1)voidvoidinit_sequence_stack(sequence_stackinit_sequence_stack(sequence_stack * *stst) )（顺顺序序存存储）初始化储）初始化(2)(2)intint is_empty_stack(sequence_stackis_empty_stack(sequence_st
57、ack stst) )判判断断栈栈（顺顺序序存存储储）是否为空是否为空(3)(3)voidvoidprint_sequence_stack(sequence_stackprint_sequence_stack(sequence_stack stst) )打打印印栈栈（顺序存储）的结点值（顺序存储）的结点值(4)(4)datatypedatatype get_top(sequence_stackget_top(sequence_stack stst) )取取得得栈栈顶顶（顺顺序序存存储）结点值储）结点值(5)(5)voidvoidpush(sequence_stackpush(sequence_
58、stack* *stst, ,datatypedatatype x)x)栈栈（顺顺序序存存储储）的插入操作的插入操作(6)(6)voidvoidpop(sequence_stackpop(sequence_stack* *stst) )栈栈（顺顺序序存存储储）的的删删除除操操作作 ADTsequence_stackADTsequence_stack2.3.22.3.2顺序栈及其实现顺序栈及其实现顺序栈及其实现顺序栈及其实现 栈的实现方式一般有两种：顺序存储和链式存储。栈的实现方式一般有两种：顺序存储和链式存储。本小节将给出栈的顺序存储实现。本小节将给出栈的顺序存储实现。 栈的顺序存储方式就是在
59、顺序表的基础上对插入栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，一般地，可以设定一个足够大的一维数组存储栈，数组中下标为数组中下标为0 0的元素就是栈底，对于栈顶，可以设一的元素就是栈底，对于栈顶，可以设一个指针个指针toptop指示它。指示它。为了方便，设定为了方便，设定toptop所指的位置是下一个将要插入所指的位置是下一个将要插入的结点的存储位置，这样，当的结点的存储位置，这样，当top=0top
60、=0时就表示是一个空时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针的栈。一个栈的几种状态以及在这些状态下栈顶指针toptop和栈中结点的关系如下图所示。和栈中结点的关系如下图所示。 栈的顺序存储结构的栈的顺序存储结构的C C语言描述如下：语言描述如下：/*/*/*/*栈（顺序存储）的头文件栈（顺序存储）的头文件*/*/*/*文件名文件名seqstackseqstack.h*/.h*/*/*/#defineMAXSIZE100#defineMAXSIZE100typedefintdatatypetypedefintdatatype; ;typedefstructtypedefst
61、ruct datatypedatatypeaMAXSIZE;aMAXSIZE;intinttop;top;sequence_stack;sequence_stack;下面是顺序存储栈的几个基本操作的具体实现下面是顺序存储栈的几个基本操作的具体实现 /*/*/*/*/* 栈栈（顺顺序序存存储储）初初始始化化 */ */*/*文件名文件名seqsinitseqsinit.c,.c,函数名函数名init_sequence_stack()*/init_sequence_stack()*/*/*/*/voidinit_sequence_stack(sequence_stack*voidinit_sequ
62、ence_stack(sequence_stack*stst) ) stst-top=0;-top=0; 算法算法2.92.9栈（顺序存储）初始化栈（顺序存储）初始化 /*/*/*/*判断栈（顺序存储）是否为空判断栈（顺序存储）是否为空*/*/*/*文件名文件名seqsemptseqsempt.c,.c,函数名函数名is_empty_sequence_stack()*/is_empty_sequence_stack()*/*/*/intintis_empty_stack(sequence_stackis_empty_stack(sequence_stackstst) ) return(retu
63、rn(stst.top?0:1);.top?0:1); 算法算法2.102.10判断栈（顺序存储）是否为空判断栈（顺序存储）是否为空 /*/*/*/*取得栈顶（顺序存储）结点值取得栈顶（顺序存储）结点值*/*/*/*文件名文件名seqsfirsseqsfirs.c,.c,函数名函数名get_top()*/get_top()*/*/*/datatypedatatypeget_top(sequence_stackget_top(sequence_stackstst) ) if(empty_stack(if(empty_stack(stst) )printfprintf(n(n栈是空的栈是空的!);
64、!);exit(1);exit(1);elseelsereturnreturnstst.a.astst.top-1;.top-1; 算法算法2.112.11取得栈顶（顺序存储）结点值取得栈顶（顺序存储）结点值/*/*/*/*栈（顺序存储）的插入操作栈（顺序存储）的插入操作*/*/*/*文件名文件名seqspushseqspush.c,.c,函数名函数名push()*/push()*/*/*/voidpush(sequence_stack*voidpush(sequence_stack*stst, ,datatypedatatypex)x) if(if(stst-top=MAXSIZE)-top
65、=MAXSIZE)printfprintf(nThenThesequencestackisfull!);exit(1);sequencestackisfull!);exit(1);stst-a-astst-top=x;-top=x;stst-top+;-top+; 算法算法2.122.12栈（顺序存储）的插入操作栈（顺序存储）的插入操作 /*/*/*/*栈（顺序存储）的删除操作栈（顺序存储）的删除操作*/*/*/*文件名文件名seqspopseqspop.c,.c,函数名函数名pop()*/pop()*/*/*/voidpop(sequence_stack*voidpop(sequence_s
66、tack*stst) ) if(if(stst-top=0)-top=0)printfprintf(nThenThesequencestackisempty!);exit(1);sequencestackisempty!);exit(1);stst-top-;-top-; 算法算法2.132.13栈（顺序存储）的删除操作栈（顺序存储）的删除操作 2.3.3栈的应用之一栈的应用之一-括号匹配括号匹配 设设一一个个表表达达式式中中可可以以包包含含三三种种括括号号：小小括括号号、中中括括号号和和大大括括号号，各各种种括括号号之之间间允允许许任任意意嵌嵌套套，如如小小括括号号内内可以嵌套中括号、大括号
67、，但是不能交叉。举例如下：可以嵌套中括号、大括号，但是不能交叉。举例如下：()()正确的正确的()() 正确的正确的()()正确的正确的()()不正确的不正确的()()不正确的不正确的 如何去检验一个表达式的括号是否匹配呢？大家如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和它对应的闭括号（或称（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。右括号）与之匹配。按照括号正确匹配的规则，在自左向右扫描一个表按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到
68、的开括号比先遇到的开括号更加期待有达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。一个闭括号与之匹配。 可能会连续遇到多个开括号，且它们都期待寻求可能会连续遇到多个开括号，且它们都期待寻求匹对的闭括号，所以必须将遇到的开括号存放好。又匹对的闭括号，所以必须将遇到的开括号存放好。又因为后遇到的开括号的期待程度高于其先前遇到的开因为后遇到的开括号的期待程度高于其先前遇到的开括号的期待程度，所以应该将所遇到的开括号存放于括号的期待程度，所以应该将所遇到的开括号存放于一个栈中。这样，当遇到一个闭括号时，就查看这个一个栈中。这样，当遇到一个闭括号时，就查看这个栈的栈顶结点，如果它们匹
69、配，则删除栈顶结点，如栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的，如果扫果不匹配，则说明表达式中括号是不匹配的，如果扫描它整个表达式后，这个栈是空的，则说明表达式中描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。的括号是匹配的，否则表达式的括号是不匹配的。 判断表达式括号是否匹配的具体实现见算法判断表达式括号是否匹配的具体实现见算法2.142.14。/*/*/* /* 判断表达式括号是否匹配判断表达式括号是否匹配 */ */* /* 文文件件名名seqmatchseqmatch.c .c，函函数数名名match
70、_match_huohaohuohao() () */*/*/*/ intintmatch_match_kuohaokuohao(charc)(charc) intinti=0;i=0;sequence_stacks;sequence_stacks;init_sequence_stack(&s);init_sequence_stack(&s);while(ci!=#)while(ci!=#)switch(ci)switch(ci)case:case:case:case:case(:push(&s,ci);break;case(:push(&s,ci);break;case:if(!is_emp
71、ty_sequence_stack(s)&get_top(s)=case:if(!is_empty_sequence_stack(s)&get_top(s)=pop(&s);break;elsereturn0;pop(&s);break;elsereturn0;case:if(!is_empty_sequence_stack(s)&get_top(s)=case:if(!is_empty_sequence_stack(s)&get_top(s)=pop(&s);break;elsereturn0;pop(&s);break;elsereturn0;case):if(!is_empty_sequ
72、ence_stack(s)&get_top(s)=()case):if(!is_empty_sequence_stack(s)&get_top(s)=()pop(&s);break;elsereturn0;pop(&s);break;elsereturn0;i+;i+; returnreturn(is_empty_sequence_stack(s);(is_empty_sequence_stack(s);/* /*栈栈空空则则匹匹配配，否否则则不不匹匹配配*/ */ 算法算法2.142.14判断表达式括号是否匹配判断表达式括号是否匹配2.3.4栈的应用之二栈的应用之二-算术表达式求值算术表达式
73、求值2.4 队列队列 2.4.1 队列队列队列是一种特殊的线性表，它的特殊性在于队列队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。作和删除操作也分别简称进队和出队。 对于一个队列：对于一个队列： k k0 0, k, k1 1, k, k2 2, , , , k kn n-1-1 如果如果k k0 0那端是队首，那端是队首，k kn n-1-1那端是队尾，则那端是队尾，则k k0 0
74、是这些结点是这些结点中最先插入的结点，若要做删除操作，中最先插入的结点，若要做删除操作，k k0 0将首先被删将首先被删除，所以说，队列是具有除，所以说，队列是具有“ “先进先出先进先出” ”（FIFO,FirstFIFO,FirstInFirstOutInFirstOut）特点的线性结构。特点的线性结构。 队列类型的描述如下：队列类型的描述如下：ADTsequence_queueADTsequence_queue数数据据集集合合K K：K=kK=k1 1, ,k k2 2, k kn n,n0,n0，K K中中的的元元素素是是datatypedatatype类类型型数据关系数据关系R R：R
75、=rR=rr=r=|i=1,2,n-1|i=1,2,n-1操作集合：操作集合：(1)(1) voidvoid init_sequence_queue(sequence_queueinit_sequence_queue(sequence_queue *sq)*sq) 队队列列（顺序存储）初始化（顺序存储）初始化(2)(2)intint is_empty_sequence_queue(sequence_queueis_empty_sequence_queue(sequence_queuesq)sq)判判断断队列（顺序存储）是否为空队列（顺序存储）是否为空(3)(3)voidvoidprint_se
76、quence_queue(sequence_queueprint_sequence_queue(sequence_queuesq)sq)打打印印队队列（顺序存储）的结点值列（顺序存储）的结点值(4)(4)datatypedatatype get_first(sequence_queueget_first(sequence_queuesq)sq)取取得得队队列列（顺顺序序存储）的队首结点值存储）的队首结点值(5)(5) voidvoid insert_sequence_queueinsert_sequence_queue (sequence_queue(sequence_queue*sq,*sq
77、,datatypedatatypex)x)队列（顺序存储）插入操作队列（顺序存储）插入操作(6)(6) voidvoid delete_sequence_queue(sequence_queuedelete_sequence_queue(sequence_queue *sq)*sq) 队队列（顺序存储）的删除操作列（顺序存储）的删除操作 ADTsequence_queue;ADTsequence_queue;2.4.22.4.2顺序队列及其实现顺序队列及其实现 队列的顺序存储在队列的顺序存储在C C语言中可以用一维数组表示，语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针为了标识
78、队首和队尾，需要附设两个指针frontfront和和rearrear，frontfront指示的是队列中最前面，即队首结点在数组中指示的是队列中最前面，即队首结点在数组中元素的下标，元素的下标，rearrear指示的是队尾结点在数组中元素的指示的是队尾结点在数组中元素的下标的下一个位置，也就是说下标的下一个位置，也就是说rearrear指示的是即将插入指示的是即将插入的结点在数组中的下标。的结点在数组中的下标。 队列的几种状态队列的几种状态 ：下标下标下标下标下标下标 下标下标 下标下标队列的顺序存储结构的队列的顺序存储结构的C C语言描述如下：语言描述如下：/*/*/*/*队列（顺序存储）的
79、头文件队列（顺序存储）的头文件*/*/*/*文件名文件名seqqueueseqqueue.h*/.h*/*/*/#defineMAXSIZE100#defineMAXSIZE100typedefintdatatypetypedefintdatatype; ;typedefstructtypedefstruct datatypedatatypeaMAXSIZE;aMAXSIZE;intintfront;front;intintrear;rear;sequence_queue;sequence_queue;顺序存储队列的几个基本操作的具体实现顺序存储队列的几个基本操作的具体实现: :/*/*/*/
80、*队列（顺序存储）初始化队列（顺序存储）初始化*/*/*/*文件名文件名seqqinitseqqinit.c.c， 函数名函数名init_sequence_queue()*/init_sequence_queue()*/*/*/voidinit_sequence_queue(sequence_queue*sq)voidinit_sequence_queue(sequence_queue*sq) sq-front=sq-rear=0;sq-front=sq-rear=0; 算法算法2.202.20队列（顺序存储）初始化队列（顺序存储）初始化 /*/*/*/*判断队列（顺序存储）是否为空判断队列（
81、顺序存储）是否为空*/*/* /*文件名文件名seqqemptseqqempt.c.c， 函数名函数名is_empty_sequence_queue()*/is_empty_sequence_queue()*/*/*/intintis_empty_sequence_queue(sequence_queuesq)is_empty_sequence_queue(sequence_queuesq) return(sq.front=sq.rear?1:0);return(sq.front=sq.rear?1:0); 算法算法2.212.21判断队列（顺序存储）是否为空判断队列（顺序存储）是否为空 /*
82、/*/*/*打印队列（顺序存储）的结点值打印队列（顺序存储）的结点值*/*/*/*文件名文件名seqqprinseqqprin.c,.c,函数名函数名print_sequence_queue()*/print_sequence_queue()*/*/*/voidprint_sequence_queue(sequence_queuesq)voidprint_sequence_queue(sequence_queuesq) intinti;i;if(is_empty_sequence_queue(sq)if(is_empty_sequence_queue(sq)printfprintf(n(n顺序
83、队列是空的顺序队列是空的!);!);elseelsefor(i=sq.front;isq.rear;i+)for(i=sq.front;irear=MAXSIZE)if(sq-rear=MAXSIZE)printfprintf(n(n顺序循环队列是满的顺序循环队列是满的!);!);exit(1);exit(1);sq-asq-rear=x;sq-asq-rear=x;sq-rear=sq-rear+1;sq-rear=sq-rear+1; 算法算法2.242.24队列（顺序存储）的插入操作队列（顺序存储）的插入操作/*/*/*/*队列（顺序存储）的删除操作队列（顺序存储）的删除操作*/*/*/
84、*文件名文件名seqqdeleseqqdele.c,.c,函数名函数名delete_sequence_queue()*/delete_sequence_queue()*/*/*/voiddelete_sequence_queue(sequence_queue*sq)voiddelete_sequence_queue(sequence_queue*sq) if(sq-front=sq-rear)if(sq-front=sq-rear)printfprintf(n(n顺序队列是空的！不能做删除操作！顺序队列是空的！不能做删除操作！););exit(1);exit(1);sq-front+;sq-f
85、ront+; 算法算法2.252.25队列（顺序存储）的删除操作队列（顺序存储）的删除操作 在队列的几种状态在队列的几种状态图的（图的（e e）状态中，队列是一种状态中，队列是一种队满状态，将不能再插入新的结点，而实际上数组的队满状态，将不能再插入新的结点，而实际上数组的前部还有许多空的位置。为了充分地利用空间，可以前部还有许多空的位置。为了充分地利用空间，可以将队列看作一个循环队列，在数组的前部继续作插入将队列看作一个循环队列，在数组的前部继续作插入运算，这就是循环队列。运算，这就是循环队列。 下标下标 下标下标2.4.3顺序循环队列及其实现顺序循环队列及其实现给定一个大小为给定一个大小为M
86、AXSIZEMAXSIZE的数组存储一个队列的数组存储一个队列时，经过若干次插入和删除操作后，当队尾指指时，经过若干次插入和删除操作后，当队尾指指rear=MAXSIZErear=MAXSIZE时，呈现队列满的状态，而事实上数时，呈现队列满的状态，而事实上数组的前部可能还有空闲的位置。为了有效利用空间，组的前部可能还有空闲的位置。为了有效利用空间，将顺序存储的队列想象为一个环状，把数组中的最前将顺序存储的队列想象为一个环状，把数组中的最前和最后两个元素看作是相邻的，这就是循环队列。和最后两个元素看作是相邻的，这就是循环队列。 循环队列的几种状态表示循环队列的几种状态表示 ：在（在（b b）状态
87、中，如果再插入一个新的结点，则数状态中，如果再插入一个新的结点，则数组空间将被全部占用，队列已满，且组空间将被全部占用，队列已满，且rear=frontrear=front，而在而在（c c）状态中，若删除一个结点队列成为空队列，此时状态中，若删除一个结点队列成为空队列，此时也有也有rear=frontrear=front，这就是说循环队列满与空的条件都是这就是说循环队列满与空的条件都是rear=frontrear=front。 解解决决方方法法是是牺牺牲牲一一个个数数组组元元素素的的空空间间，即即若若数数组组的的大大小小是是MAXSIZEMAXSIZE，则则该该数数组组所所表表示示的的循循环
88、环队队列列最最多多允允许许存存储储MAXSIZE-1MAXSIZE-1个结点。这样，循环队列满的条件是个结点。这样，循环队列满的条件是( (rear+1)%MAXSIZE=frontrear+1)%MAXSIZE=front循环队列空的条件是循环队列空的条件是 rear=frontrear=front循环队列的插入与删除操作的实现循环队列的插入与删除操作的实现 ：/*/*/*/*循环队列（顺序存储）的插入操作循环队列（顺序存储）的插入操作*/*/*/*文件名文件名secqinstsecqinst.c,.c,函数名函数名insert_sequence_insert_sequence_cqueue
89、cqueue()*/()*/*/*/ voidvoid insert_sequence_insert_sequence_cqueuecqueue(sequence_queue(sequence_queue *sq,*sq,datatypedatatype x)x) intinti;i;if(sq-rear+1)%MAXSIZE=sq-front)if(sq-rear+1)%MAXSIZE=sq-front) printfprintf(n(n顺顺 序序 循循 环环 队队 列列 是是 满满 的的 ！ 无无 法法 进进 行行 插插 入入 操操 作作 ！););exit(1);exit(1);sq-a
90、sq-rear=x;sq-asq-rear=x;sq-rear=(sq-rear+1)%MAXSIZE;sq-rear=(sq-rear+1)%MAXSIZE; 算法算法2.272.27循环队列（顺序存储）的插入操作循环队列（顺序存储）的插入操作 /*/*/*/*循环队列（顺序存储）的删除操作循环队列（顺序存储）的删除操作*/*/*/*文件名文件名secqdelesecqdele.c,.c,函数名函数名delete_sequence_delete_sequence_cqueuecqueue()*/()*/*/*/voiddelete_sequence_voiddelete_sequence_c
91、queuecqueue(sequence_queue*sq)(sequence_queue*sq) if(sq-front=sq-rear)if(sq-front=sq-rear) printfprintf(“n(“n循循环环队队列列是是空空的的！无无法法进进行行删删除除！);); exit(1);exit(1);sq-front=(sq-front+1)%MAXSIZE;sq-front=(sq-front+1)%MAXSIZE; 算法算法2.282.28循环队列（顺序存储）的删除操作循环队列（顺序存储）的删除操作 第第3章章 线性表的链式存储线性表的链式存储 线性表的存储方式除了常用的顺序
92、存储外，采用线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式。本章将介绍一般链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表点单链表、循环单链表、双链表以及特殊的线性表-栈和队列的链式存储实现。栈和队列的链式存储实现。 3.1链式存储链式存储 数据结构的存储方式必须体现它的逻辑关系数据结构的存储方式必须体现它的逻辑关系 。在链式存储方式下，实现中除存放一个结点的信息外，在链式存储方式下，实现中除存放一个结点的信息外，还需附设指针，用指针体
93、现结点之间的逻辑关系。如还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱，那么可以附设相果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继。点的某个前驱或后继。 线性结构中，每个结点最多只有一个前驱和一个线性结构中，每个结点最多只有一个前驱和一个后继，这里暂且设定更关心它的后继，这样在存储时除后继，这里暂且设定更关心它的后继，这样在存储时除了存放该结点的信息外，只要附设一个指针即可，该指了存放该结点的信息外，只要附设一个指针即可，该指针指向它的后继结点的存放位置
94、。每个结点的存储形式针指向它的后继结点的存放位置。每个结点的存储形式是：是： infonext例，数据的逻辑结构例，数据的逻辑结构B=B=（K K，R R）其中其中 K=kK=k1 1,k ,k2 2,k ,k3 3,k ,k4 4,k ,k5 5 R=r R=r R= k R=,是一个线性结构，它的链式存储如图所是一个线性结构，它的链式存储如图所示示 为为了了清清晰晰，左左图图可可以以更更简简洁洁地地用用下下图表示。图表示。3.2 单链表单链表 单链表是线性表链式存储的一种形式，其中的结点单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个是存放数据信息的一般含有两个域，一个是存
95、放数据信息的infoinfo域，另一域，另一个是指向该结点的后继结点的存放地址的指针域个是指向该结点的后继结点的存放地址的指针域nextnext。一个单链表必须有一个首指针指向单链表中的第一个结一个单链表必须有一个首指针指向单链表中的第一个结点。图点。图3.33.3给出了空的单链表和非空的单链表的图示。给出了空的单链表和非空的单链表的图示。 单链表类型的描述如下：单链表类型的描述如下： ADTlink_listADTlink_list数数据据集集合合K K：K=kK=k1 1, ,k k2 2, k kn n,n0,n0，K K中中的的元元素素是是datatypedatatype类类型型数据关
96、系数据关系R R：R=rR=rr=r=|i=1,2,n-1|i=1,2,n-1操作集合：操作集合：(1)(1)node*init_link_list()node*init_link_list()建立一个空的单链表建立一个空的单链表(2)(2)voidprint_link_list(node*head)voidprint_link_list(node*head)输出单链表中各个结点的值输出单链表中各个结点的值(3)(3)node*insert_in_front_link_list(node*head,node*insert_in_front_link_list(node*head,datatyp
97、edatatypex)x)插入一个值为插入一个值为x x的结点作为单链表的第一个结点的结点作为单链表的第一个结点(4)(4)nodenode*find_num_link_list(node*find_num_link_list(node*head,*head,datatypedatatype x)x)在在单单链链表表中查找一个值为中查找一个值为x x的结点的结点(5)(5)nodenode*find_pos_link_list(node*find_pos_link_list(node*head,*head,intint i)i)在在单单链链表表中中查查找找第第i i个结点个结点(6)(6)no
98、de*insert_x_after_y(node*head,node*insert_x_after_y(node*head,datatypedatatypex,x,datatypedatatypey)y)在单链表中值为在单链表中值为y y的结点后插入一个值为的结点后插入一个值为x x的新结点的新结点(7)(7)node*insert_x_after_i(node*head,node*insert_x_after_i(node*head,datatypedatatypex,x,intinti)i)在单链表中第在单链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点(8)(
99、8)nodenode*delete_num_link_list(node*delete_num_link_list(node*head,*head,datatypedatatype x)x)在在单单链链表中删除一个值为表中删除一个值为x x的结点的结点(9)(9)nodenode*delete_pos_link_list(node*delete_pos_link_list(node*head,*head,intint i)i)在在单单链链表表中中删删除第除第i i个结点个结点 ADTlink_list;ADTlink_list;3.2.2单链表的实现单链表的实现 单链表结构的单链表结构的C C
100、语言描述如下：语言描述如下：/*/*/* /*链表实现的头文件，文件名链表实现的头文件，文件名slnklistslnklist.h*/.h*/*/*/typedefintdatatypetypedefintdatatype; ;typedefstructtypedefstructlink_nodelink_nodedatatypedatatypeinfo;info;structstructlink_node*next;link_node*next;node;node;单链表几个基本操作的具体实现：单链表几个基本操作的具体实现：/*/*/*/*建立一个空的单链表建立一个空的单链表*/*/*/*文
101、件名文件名slnkinitslnkinit.c.c，函数名函数名init_link_list()*/init_link_list()*/*/*/node*init_link_list()/*node*init_link_list()/*建立一个空的单链表建立一个空的单链表*/ */ returnNULL;returnNULL; 算法算法3.13.1建立一个空的单链表建立一个空的单链表 /*/*/*/*输出单链表中各个结点的值输出单链表中各个结点的值*/*/*/*文件名文件名slnkprinslnkprin.c.c，函数名函数名print_link_list()*/print_link_list
102、()*/*/*/voidprint_link_list(node*head)voidprint_link_list(node*head)node*p;node*p;p=head;p=head;if(!p)if(!p)printfprintf(n(n单链表是空的！单链表是空的！););elseelseprintfprintf(n(n单链表各个结点的值为：单链表各个结点的值为： n);n);while(p)while(p)printfprintf(%5d,p-info);p=p-next;(%5d,p-info);p=p-next; 算法算法3.23.2输出单链表中各个结点的值输出单链表中各个结点
103、的值/*/*/*/*在单链表中查找一个值为在单链表中查找一个值为x x的结点的结点*/*/*/*文件名文件名slnkfinxslnkfinx.c.c，函数名函数名find_num_link_list()*/find_num_link_list()*/*/*/node*find_num_link_list(node*head,node*find_num_link_list(node*head,datatypedatatypex)x) node*p;node*p;p=head;p=head;while(p&p-info!=x)p=p-next;while(p&p-info!=x)p=p-next;
104、returnp;returnp; 算法算法3.33.3在单链表中查找一个值为在单链表中查找一个值为x x的结点的结点/*/*/*/*在单链表中查找第在单链表中查找第i i个结点个结点*/*/*/*文件名文件名slnkfinislnkfini.c.c，函数名函数名find_pos_link_list()*/find_pos_link_list()*/*/*/node*find_pos_link_list(node*head,node*find_pos_link_list(node*head,intinti)i) intintj=1;j=1;node*p=head;node*p=head;if(i
105、1)if(inext;j+;while(p&i!=j)p=p-next;j+;returnp;returnp; 算法算法3.43.4在单链表中查找第在单链表中查找第i i个结点个结点 单链表的插入过程见下图所示单链表的插入过程见下图所示 ：/*/*/*/*插入一个值为插入一个值为x x的结点作为单链表的第一个结点的结点作为单链表的第一个结点*/*/*/*文件名文件名slnkinfxslnkinfx.c.c，函数名函数名insert_in_front_link_list()*/insert_in_front_link_list()*/*/*/node*insert_in_front_link_l
106、ist(node*head,node*insert_in_front_link_list(node*head,datatypedatatypex)x) node*p;node*p;p=(node*)p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*分配空间分配空间*/ */p-info=x;/*p-info=x;/*设置新结点的值设置新结点的值*/ */p-next=head;/*p-next=head;/*插入插入(1)*/(1)*/head=p;/*head=p;/*插入插入(2)*/(2)*/returnhead;returnhe
107、ad; 算法算法3.53.5插入一个值为插入一个值为x x的结点作为单链表的第一个结点的结点作为单链表的第一个结点 /*/*/*/*在单链表中第在单链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点*/*/*/*文件名文件名slnkinixslnkinix.c.c，函数名函数名insert_x_after_i()*/insert_x_after_i()*/*/*/node*insert_x_after_i(node*head,node*insert_x_after_i(node*head,datatypedatatypex,x,intinti)i) node*p,*q
108、;node*p,*q;q=find_pos_link_list(head,i);/*q=find_pos_link_list(head,i);/*查找第查找第i i个结点个结点*/ */if(!q)if(!q) printfprintf(n(n找找 不不 到到 第第 %d d个个 结结 点点 ， 不不 能能 进进 行行 插插 入入 ！, ,i,x);exit(1);i,x);exit(1);p=(node*)p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*分配空间分配空间*/ */p-info=x;/*p-info=x;/*设置新结点
109、设置新结点*/ */p-next=q-next;/*p-next=q-next;/*插入插入(1)*/(1)*/q-next=p;/*q-next=p;/*插入插入(2)*/(2)*/returnhead;returnhead; 算法算法3.73.7在单链表中第在单链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点 删除操作见下图所示：删除操作见下图所示： node*delete_num_link_list(node*head,node*delete_num_link_list(node*head,datatypedatatypex)x) node*pre=NULL,
110、*p;node*pre=NULL,*p;if(!head)if(!head)printfprintf( (单链表是空的！单链表是空的！););returnhead;returnhead;p=head;p=head;while(p&p-info!=x)/*while(p&p-info!=x)/*没有找到并且没有找完没有找到并且没有找完*/*/pre=p;p=p-next;/*prepre=p;p=p-next;/*pre指向指向p p的前驱结点的前驱结点*/ */if(!pre&p-info=x)/*if(!pre&p-info=x)/*要删除的是第一个结点要删除的是第一个结点*/ */head
111、=head-next;/*head=head-next;/*删除删除(1)*/(1)*/elseelsepre-next=p-next;pre-next=p-next;free(p);free(p);returnhead;returnhead; 算法算法3.83.8在单链表中删除一个值为在单链表中删除一个值为x x的结点的结点 链式存储的插入和删除链式存储的插入和删除链式存储的插入和删除链式存储的插入和删除操作比顺序存储方便，但不能操作比顺序存储方便，但不能操作比顺序存储方便，但不能操作比顺序存储方便，但不能随机访问某个结点！随机访问某个结点！随机访问某个结点！随机访问某个结点！ 3.3带头结
112、点单链表带头结点单链表 3.3.1带头结点单链表带头结点单链表带头结点单链表见下图所示：带头结点单链表见下图所示： 带头结点单链表类型的描述如下：带头结点单链表类型的描述如下： ADTADThlinkhlink_list_list数数据据集集合合K K：K=kK=k1 1, ,k k2 2, k kn n,n0,n0，K K中中的的元元素素是是datatypedatatype类类型型数据关系数据关系R R：R=rR=rr=r=|i=1,2,n-1|i=1,2,n-1操作集合：操作集合：(1)(1)node*init_node*init_hlinkhlink_list()_list()建立一个空
113、的带头结点的单链表建立一个空的带头结点的单链表(2)(2)voidvoidprint_print_hlinkhlink_list(node_list(node*head)*head)输输出出带带头头结结点点单单链链表表中中各各个结点的值个结点的值(3)(3)node*find_num_node*find_num_hlinkhlink_list(node*head,_list(node*head,datatypedatatypex)x)在带头结点单链表中查找一个值为在带头结点单链表中查找一个值为x x的结点的结点(4)(4)nodenode*find_pos_*find_pos_hlinkhli
114、nk_list(node_list(node*head,*head,intint i)i)在在带带头头结结点点单单链表中查找第链表中查找第i i个结点个结点(5)(5)node*insert_in_front_node*insert_in_front_hlinkhlink_list(node*head,_list(node*head,datatypedatatypex)x)插入一个值为插入一个值为x x的结点作为带头结点单链表的第一个结点的结点作为带头结点单链表的第一个结点(6)(6)node*insert_x_after_y(node*head,node*insert_x_after_y(n
115、ode*head,datatypedatatypex,x,datatypedatatypey)y)在带头结点单链表中值为在带头结点单链表中值为y y的结点后插入一个值为的结点后插入一个值为x x的新结点的新结点(7)(7)node*insert_x_after_i(node*head,node*insert_x_after_i(node*head,datatypedatatypex,x,intinti)i)在带头结点单链表中第在带头结点单链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点(8)(8)node*delete_num_node*delete_num_hli
116、nkhlink_list(node*head,_list(node*head,datatypedatatypex)x)在带头结点单链表中删除一个值为在带头结点单链表中删除一个值为x x的结点的结点(9)(9)node*delete_pos_node*delete_pos_hlinkhlink_list(node*head,_list(node*head,intinti)i)在带头结点单链表中删除第在带头结点单链表中删除第i i个结点个结点 ADTADThlinkhlink_list;_list;3.3.2带头结点单链表的实现带头结点单链表的实现 一般的单链表中，第一个结点由一般的单链表中，第一
117、个结点由headhead指示，而在指示，而在带头结点单链表中，带头结点单链表中，headhead指示的是所谓的头结点，它指示的是所谓的头结点，它不是存储数据结构中的实际结点，第一个实际的结点是不是存储数据结构中的实际结点，第一个实际的结点是head-nexthead-next指示的。在带头结点单链表的操作实现时要指示的。在带头结点单链表的操作实现时要注意这一点。注意这一点。 node*init_node*init_hlinkhlink_list()_list() node*head;node*head;head=(node*)head=(node*)mallocmalloc( (sizeofs
118、izeof(node);(node);head-next=NULL;head-next=NULL;returnhead;returnhead; 算法算法3.103.10建立一个空的带头结点单链表建立一个空的带头结点单链表 voidprint_voidprint_hlinkhlink_list(node*head)_list(node*head) node*p;node*p;p=head-next;/*p=head-next;/*从第一个（实际）结点开始从第一个（实际）结点开始*/ */if(!p)if(!p)printfprintf(n(n带头结点单链表是空的带头结点单链表是空的!);!);e
119、lseelseprintfprintf(n(n带头结点的单链表各个结点的值为：带头结点的单链表各个结点的值为： n);n);while(p)while(p)printfprintf(%5d,p-info);p=p-next;(%5d,p-info);p=p-next; 算法算法3.113.11输出带头结点单链表中各个结点的值输出带头结点单链表中各个结点的值 /*/*/*/*在带头结点单链表中查找一个值为在带头结点单链表中查找一个值为x x的结点的结点*/*/*/*文件名文件名hlnkfinxhlnkfinx.c.c，函数名函数名find_num_find_num_hlinkhlink_list
120、()*/_list()*/*/*/node*find_num_node*find_num_hlinkhlink_list(node*head,_list(node*head,datatypedatatypex)x) node*p;node*p;p=head-next;/*p=head-next;/*从第一个（实际）结点开始从第一个（实际）结点开始*/ */while(p&p-info!=x)p=p-next;while(p&p-info!=x)p=p-next;returnp;returnp; 算法算法3.123.12在带头结点单链表中查找一个值为在带头结点单链表中查找一个值为x x的结点的结
121、点 node*find_pos_node*find_pos_hlinkhlink_list(node*head,_list(node*head,intinti)i) intintj=0;j=0;node*p=head;node*p=head; if(i0)if(inext;j+;/*p=p-next;j+;/*继续向后（左）查找，计数器加继续向后（左）查找，计数器加1*/1*/returnp;/*returnp;/*返回结果，返回结果，i=0i=0时，时，p p指示的是头结点指示的是头结点*/ */ 算法算法3.133.13在带头结点单链表中查找第在带头结点单链表中查找第i i个结点个结点 带
122、头结点单链表的插入过程见图带头结点单链表的插入过程见图3.73.7：带头结点单链表的几个插入操作的具体实现见算法带头结点单链表的几个插入操作的具体实现见算法3.143.14算法算法3.163.16。 node *insert_x_after_y(node *head,node *insert_x_after_y(node *head,datatypedatatype x, x,datatypedatatype y) y) node *p,*q; node *p,*q; q=find_num_ q=find_num_hlinkhlink_list(head,y);/*_list(head,y);
123、/*查找值为查找值为查找值为查找值为y y的结点的结点的结点的结点*/ */ if(!q)/*if(!q)/*没有找到没有找到没有找到没有找到*/ */ printfprintf(n(n没有找到值为没有找到值为没有找到值为没有找到值为%d d的结点，不能插入的结点，不能插入的结点，不能插入的结点，不能插入%d!,y,x);return head;d!,y,x);return head; p=(node*) p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*为准备插入的新结点分配空间为准备插入的新结点分配空间为准备插入的新结点分配空间为准
124、备插入的新结点分配空间*/ */ p-info=x;/*p-info=x;/*为新结点设置值为新结点设置值为新结点设置值为新结点设置值x*/x*/ p-next=q-next;/* p-next=q-next;/*插入插入插入插入(1)*/(1)*/ q-next=p;/*q-next=p;/*插入插入插入插入(2)*/(2)*/ return head;return head; 算法算法算法算法3.153.15在带头结点单链表中值为在带头结点单链表中值为在带头结点单链表中值为在带头结点单链表中值为y y的结点后插入一个值为的结点后插入一个值为的结点后插入一个值为的结点后插入一个值为x x的新
125、结点的新结点的新结点的新结点 带头结点单链表的删除过程见图带头结点单链表的删除过程见图3.83.8。 node*delete_num_node*delete_num_hlinkhlink_list(node*head,_list(node*head,datatypedatatypex)x) node*pre=head,*q;/*node*pre=head,*q;/*首先首先prepre指向头结点指向头结点*/ */ q=head-next;/*qq=head-next;/*q从从带带头头结结点点的的第第一一个个实实际际结结点点开开始始找找值值为为x x的结点的结点*/ */while(q&q-
126、info!=x)/*while(q&q-info!=x)/*没有查找完并且还没有找到没有查找完并且还没有找到*/ */pre=q;q=q-next;/*pre=q;q=q-next;/*继续查找，继续查找，prepre指向指向q q的前驱的前驱*/ */pre-next=q-next;/*pre-next=q-next;/*删除删除*/ */free(q);/*free(q);/*释放空间释放空间*/ */returnhead;returnhead; 算法算法3.173.17在带头结点单链表中删除一个值为在带头结点单链表中删除一个值为x x的结点的结点 3.4 循环单链表循环单链表 3.4.1
127、 循环单链表循环单链表无论是单链表，还是带头结点单链表，从表中的无论是单链表，还是带头结点单链表，从表中的某个结点开始，只能访问到这个结点及其后面的结点，某个结点开始，只能访问到这个结点及其后面的结点，不能访问到它前面的结点，除非再从首指针指示的结不能访问到它前面的结点，除非再从首指针指示的结点开始访问。如果希望从表中的任意一个结点开始，点开始访问。如果希望从表中的任意一个结点开始，都能访问到表中的所有其它结点，可以设置表中最后都能访问到表中的所有其它结点，可以设置表中最后一个结点的指针域指向表中的第一个结点，这种链表一个结点的指针域指向表中的第一个结点，这种链表称为循环单链表。称为循环单链表
128、。 循环单链表类型的描述循环单链表类型的描述 （略）（略）3.4.2循环单链表的实现循环单链表的实现 单单链链表表中中某某个个结结点点p p是是表表中中最最后后一一个个结结点点的的特特征征是是p-next=NULLp-next=NULL。对对于于一一个个循循环环单单链链表表，若若首首指指针针为为headhead，表表中中的的某某个个结结点点p p是是最最后后一一个个结结点点的的特特征征应应该该是是p-next=headp-next=head。循环单链表的头文件和单链表的相同。循环单链表的头文件和单链表的相同。 /*/*/*/*建立一个空的循环单链表建立一个空的循环单链表*/*/*/*文件名文件
129、名clnkinitclnkinit.c.c，函数名函数名init_clink_list()*/init_clink_list()*/*/*/node*init_clink_list()/*node*init_clink_list()/*建立一个空的循环单链表建立一个空的循环单链表*/ */ returnNULL;returnNULL; 算法算法3.193.19建立一个空的循环单链表建立一个空的循环单链表 void print_clink_list(node *head)void print_clink_list(node *head) node *p; node *p; if(!head) i
130、f(!head) printf printf(n(n循环单链表是空的！循环单链表是空的！循环单链表是空的！循环单链表是空的！ n);n); else else printfprintf(n(n循环单链表各个结点的值分别为循环单链表各个结点的值分别为循环单链表各个结点的值分别为循环单链表各个结点的值分别为: :n);n); printf printf(%5d,head-info);/*(%5d,head-info);/*输出非空表中第一个结点的值输出非空表中第一个结点的值输出非空表中第一个结点的值输出非空表中第一个结点的值*/*/ p=head-next;/*pp=head-next;/*p指向
131、第一个结点的下一个结点指向第一个结点的下一个结点指向第一个结点的下一个结点指向第一个结点的下一个结点*/*/ while(p!=head)/*while(p!=head)/*没有回到第一个结点没有回到第一个结点没有回到第一个结点没有回到第一个结点*/*/ printfprintf(%5d,p-info);(%5d,p-info); p=p-next; p=p-next; 算法算法算法算法3.213.21输出循环单链表中各个结点的值输出循环单链表中各个结点的值输出循环单链表中各个结点的值输出循环单链表中各个结点的值 循环单链表的插入过程如图循环单链表的插入过程如图 ：node *insert_x
132、_after_i(node *head,node *insert_x_after_i(node *head,datatypedatatype x, x,intint i) i) node *p,*q; node *p,*q; q=find_pos_clink_list(head,i);/* q=find_pos_clink_list(head,i);/*查找第查找第查找第查找第i i个结点，个结点，个结点，个结点，q q指向第指向第指向第指向第i i个结点个结点个结点个结点*/ */ if(!q)/*if(!q)/*没有找到，则不进行插入没有找到，则不进行插入没有找到，则不进行插入没有找到，则
133、不进行插入*/ */ printfprintf(n(n表中不存在第表中不存在第表中不存在第表中不存在第%d d个结点，无法进行插入个结点，无法进行插入个结点，无法进行插入个结点，无法进行插入! !n,i);n,i); else else /* /*找到了第找到了第找到了第找到了第i i个结点，准备插入个结点，准备插入个结点，准备插入个结点，准备插入x*/x*/ p=(node*) p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*分配空间分配空间分配空间分配空间*/ */ p-info=x;/*p-info=x;/*设置新结点的值设置新
134、结点的值设置新结点的值设置新结点的值*/ */ p-next=q-next;/*p-next=q-next;/*插入，修改指针插入，修改指针插入，修改指针插入，修改指针(1)*/(1)*/ q-next=p;/*q-next=p;/*插入，修改指针插入，修改指针插入，修改指针插入，修改指针(2)*/(2)*/ return head;return head; 算法算法算法算法3.263.26在循环单链表中第在循环单链表中第在循环单链表中第在循环单链表中第i i个结点后插入一个值为个结点后插入一个值为个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点的新结点的新结点 循环单链表的删除
135、过程如图循环单链表的删除过程如图 ：node*delete_num_clink_list(node*head,node*delete_num_clink_list(node*head,datatypedatatypex)x)node*pre=NULL,*q;/*qnode*pre=NULL,*q;/*q用于查找值为用于查找值为x x的结点，的结点，prepre指向指向q q的前驱结点的前驱结点*/ */if(!head)/*if(!head)/*表为空，则无法做删除操作表为空，则无法做删除操作*/ */printfprintf(“n(“n循环单链表为空，循环单链表为空， 无法做删除操作！无法做
136、删除操作！”);”);returnNULL;returnNULL;q=head;/*q=head;/*从第从第1 1个结点开始准备查找个结点开始准备查找*/ */while(q-next!=head&q-info!=x)/*while(q-next!=head&q-info!=x)/*没有找遍整个表并且没有找到没有找遍整个表并且没有找到*/ */pre=q;q=q-next;/*prepre=q;q=q-next;/*pre为为q q的前驱，继续查找的前驱，继续查找*/ */*/*循环结束后，循环结束后，prepre为为q q的前驱的前驱*/ */if(q-info!=x)/*if(q-inf
137、o!=x)/*没找到没找到*/*/printfprintf( (没有找到值为没有找到值为%d d的结点！的结点！, ,x);x);else/*else/*找到了，下面要删除找到了，下面要删除q*/q*/pre-next=q-next;/*pre-next=q-next;/*删除删除q q指向的结点指向的结点*/*/free(q);/*free(q);/*释放空间释放空间*/*/returnhead;returnhead; 算法算法3.273.27在循环单链表中删除一个值为在循环单链表中删除一个值为x x的结点的结点 3.5 双链表双链表 3.5.1 双链表双链表前面的各种链式表中，一个结点的指
138、针域是指向前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点它的后继结点的，如果需要找一个结点p p的前驱结点，的前驱结点，则必须从表首指针开始查找，当某个结点则必须从表首指针开始查找，当某个结点prepre的指针域的指针域指向的是结点指向的是结点p p时，即时，即pre-next=ppre-next=p时，则说明时，则说明prepre是是p p的前驱结点。如果常常需要知道一个结点的前驱和的前驱结点。如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。既然单链表中后继结点，上述的链式表是不适合的。既然单链表中每个结点有一个指针域指向它的后继结点，那自然地
139、每个结点有一个指针域指向它的后继结点，那自然地想到再增设一个指针域指向它的前驱结点，这就构成想到再增设一个指针域指向它的前驱结点，这就构成了双链表。了双链表。 双链表的结点包括三个域，一个是存放数据信息双链表的结点包括三个域，一个是存放数据信息的的infoinfo域，另外两个是指针域，这里用域，另外两个是指针域，这里用llinkllink和和rlinkrlink表示，表示，llinkllink指向它的前驱结点，指向它的前驱结点，rlinkrlink指向它的后继结点。指向它的后继结点。 双链表的一般情形如图所示：双链表的一般情形如图所示： 双链表类型的描述（略！）双链表类型的描述（略！）3.5.
140、2 双链表的实现双链表的实现 双链表结构的双链表结构的C C语言描述如下：语言描述如下：/*/*/*/*双链表的头文件，文件名双链表的头文件，文件名dlnklistdlnklist.h/.h/*/*/typedefintdatatypetypedefintdatatype; ;typedefstructdlinktypedefstructdlink_node_nodedatatypedatatypeinfo;info;structdlinkstructdlink_node*llink,*rlink;_node*llink,*rlink; dnodednode; ;voidprint_voidp
141、rint_dlinkdlink_list(_list(dnodednode*head)*head) dnodednode*p;*p;printfprintf(n);p=head;(n);p=head;if(!p)if(!p)printfprintf(n(n双链表是空的双链表是空的! !n);n);elseelseprintfprintf(n(n双链表中各个结点的值为：双链表中各个结点的值为： n);n);while(p)while(p)printfprintf(%5d,p-info);p=p-rlink;(%5d,p-info);p=p-rlink; 算法算法3.303.30输出双链表中各个结
142、点的值输出双链表中各个结点的值 dnodednode*find_pos_*find_pos_dlinkdlink_list(_list(dnodednode*head,*head,intinti)i) intintj=1;j=1;dnodednode*p=head;*p=head;if(i1)if(irlink;j+;/*p=p-rlink;j+;/*继续沿着右指针向后查找，计数器加继续沿着右指针向后查找，计数器加1*/1*/if(!p)if(!p)printfprintf(n(n第第%d d个结点不存在个结点不存在! !n,i);returnNULL;n,i);returnNULL;retu
143、rnp;returnp; 算法算法3.323.32查找双链表中第查找双链表中第i i个结点个结点 双链表插入过程如下图所示：双链表插入过程如下图所示： /*/*在双链表中第在双链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点*/*/dnodednode*insert_x_after_i(*insert_x_after_i(dnodednode*head,*head,datatypedatatypex,x,intinti)i) dnodednode*p,*q;*p,*q;p=(p=(dnodednode*) *)mallocmalloc( (sizeofsizeof(
144、 (dnodednode);/*);/*分配空间分配空间*/ */p-info=x;/*p-info=x;/*设置新结点的值设置新结点的值*/ */if(i=0)/*if(i=0)/*在最前面插入一个值为在最前面插入一个值为x x的新结点的新结点*/ */p-llink=NULL;/*p-llink=NULL;/*新插入的结点没有前驱新插入的结点没有前驱*/ */p-rlink=head;p-rlink=head;/* /*新插入的结点的后继是原来双链表中的第一个结点新插入的结点的后继是原来双链表中的第一个结点*/ */head=p;/*head=p;/*新结点成为双链表的第一个结点新结点成为
145、双链表的第一个结点*/ */returnhead;returnhead;q=find_pos_q=find_pos_dlinkdlink_list(head,i);/*_list(head,i);/*查找第查找第i i个结点个结点*/ */if(!q)/*if(!q)/*第第i i个结点不存在个结点不存在*/ */ printfprintf( (第第 %d d个个 结结 点点 不不 存存 在在 ， 无无 法法 进进 行行 插插 入入 , ,i);returni);returnhead;head;if(q-rlink=NULL)/*if(q-rlink=NULL)/*在最后一个结点后插入在最后一
146、个结点后插入*/ */ p-rlink=q-rlink;/*p-rlink=q-rlink;/*即即为为NULLNULL，新新插插入入的的结结点点没没有有后后继继。插插入操作入操作(1)*/(1)*/p-llink=q;/*p-llink=q;/*插入操作插入操作(2)*/(2)*/q-rlink=p;/*q-rlink=p;/*插入操作插入操作(4)*/(4)*/*/*注意不能和下面的一般情况一样处理，这里如执行下面的注意不能和下面的一般情况一样处理，这里如执行下面的(3)(3)将出错！将出错！*/*/else/*else/*一般情况下的插入一般情况下的插入*/ */p-rlink=q-rl
147、ink;/*p-rlink=q-rlink;/*插入操作插入操作(1)*/(1)*/p-llink=q;/*p-llink=q;/*插入操作插入操作(2)*/(2)*/q-rlink-llink=p;/*q-rlink-llink=p;/*插入操作插入操作(3)*/(3)*/q-rlink=p;/*q-rlink=p;/*插入操作插入操作(4)*/(4)*/returnhead;returnhead; 算法算法3.353.35在双链表中第在双链表中第i i个结点后插入一个值为个结点后插入一个值为x x的新结点的新结点 双链表删除操作图示双链表删除操作图示 ：/*/*在双链表中删除一个值为在双链
148、表中删除一个值为x x的结点的结点*/*/dnodednode*delete_num_*delete_num_dlinkdlink_list(_list(dnodednode*head,*head,datatypedatatypex)x)dnodednode*q;*q;if(!head)/*if(!head)/*双链表为空，无法进行删除操作双链表为空，无法进行删除操作*/ */printfprintf( (双链表为空，无法进行删除操作双链表为空，无法进行删除操作););returnhead;returnhead;q=head;q=head; while(q&q-info!=x)while(q&
149、q-info!=x)q=q-rlink;/*q=q-rlink;/*循循环环结结束束后后q q指指向向的的是是值值为为x x的结点的结点*/ */if(!q)if(!q)printfprintf(n(n没有找到值为没有找到值为%d d的结点！不做删除操作！的结点！不做删除操作！, ,x);x); if(q=head&head-rlink)/*if(q=head&head-rlink)/*被被删删除除的的结结点点是是第第一一个个结结点点并并且且表表中中不只一个结点不只一个结点*/ */head=head-rlink;head=head-rlink;head-llink=NULL;head-lli
150、nk=NULL;free(q);returnhead;free(q);returnhead; if(q=head&!head-rlink)/*if(q=head&!head-rlink)/*被被删删除除的的结结点点是是第第一一个个结结点点并并且且表表中只有这一个结点中只有这一个结点*/ */free(q);free(q);returnNULL;/*returnNULL;/*双链表置空双链表置空*/ */elseelseif(!q-rlink)/*if(!q-rlink)/*被删除的结点是双链表中的最后一个结点被删除的结点是双链表中的最后一个结点*/ */q-llink-rlink=NULL;f
151、ree(q);returnhead;q-llink-rlink=NULL;free(q);returnhead;elseelse/*q/*q是在一个有是在一个有2 2个以上结点的双链表中的一个非开始、也非终端结点个以上结点的双链表中的一个非开始、也非终端结点*/ */ q-llink-rlink=q-rlink;q-llink-rlink=q-rlink;q-rlink-llink=q-llink;q-rlink-llink=q-llink;free(q);returnhead;free(q);returnhead; 算法算法3.363.36在双链表中删除一个值为在双链表中删除一个值为x x的
152、结点的结点 3.6 链式栈链式栈 3.6.1 链式栈链式栈栈的链式存储称为链式栈。链式栈就是一个特殊栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除规的单链表，对于这特殊的单链表，它的插入和删除规定在单链表的同一端进行。链式栈的栈顶指针一般用定在单链表的同一端进行。链式栈的栈顶指针一般用toptop表示，链式栈如下图所示。表示，链式栈如下图所示。 链式栈类型的描述如下：链式栈类型的描述如下：ADTlink_stackADTlink_stack数据集合数据集合K K：K=kK=k1 1,k,k2 2,kkn n,n0,n0，K K中的元素是中的元素是data
153、typedatatype类型类型数据关系数据关系R R：R=rR=rr=r=|i=1,2,n-1|i=1,2,n-1操作集合：操作集合：(1)(1)node*init_link_stack()node*init_link_stack()建立一个空链式栈建立一个空链式栈(2)(2)intintempty_link_stack(node*top)empty_link_stack(node*top)判断链式栈是否为空判断链式栈是否为空(3)(3)datatypedatatypeget_top(node*top)get_top(node*top)取得链式栈的栈顶结点值取得链式栈的栈顶结点值(4)(4)
154、voidprint_link_stack(node*top)voidprint_link_stack(node*top)输出链式栈中各个结点的值输出链式栈中各个结点的值(5)(5)nodenode*push_link_stack(node*push_link_stack(node*top,*top,datatypedatatype x)x)向向链链式式栈栈中中插插入入一一个个值值为为x x的结点的结点node*pop_link_stack(node*top)node*pop_link_stack(node*top)/*/*删除链式栈的栈顶结点删除链式栈的栈顶结点*/*/ ADTlink_sta
155、ck;ADTlink_stack;3.6.2 链式栈的实现链式栈的实现 datatypedatatypeget_top(node*top)get_top(node*top) if(!top)if(!top)printfprintf(n(n链式栈是空的链式栈是空的!);!);exit(1);exit(1);return(top-info);return(top-info); intintempty_link_stack(node*top)empty_link_stack(node*top) return(top?0:1);return(top?0:1); 算法算法3.403.40取得链式栈的栈顶
156、结点值取得链式栈的栈顶结点值 /*/*输出链式栈中各个结点的值输出链式栈中各个结点的值*/*/*/*文件名文件名lnksprinlnksprin.c.c，函数名函数名print_link_stack()*/print_link_stack()*/*/*/voidprint_link_stack(node*top)voidprint_link_stack(node*top) node*p;node*p;p=top;p=top;printfprintf(n);(n);if(!p)if(!p)printfprintf(n(n链式栈是空的链式栈是空的!);!);while(p)while(p)prin
157、tfprintf(%5d,p-info);p=p-next;(%5d,p-info);p=p-next; 算法算法3.413.41输出链式栈中各个结点的值输出链式栈中各个结点的值 /*/*向链式栈中插入一个值为向链式栈中插入一个值为x x的结点的结点*/*/*/*文件名文件名lnkspushlnkspush.c.c，函数名函数名push_link_stack()*/push_link_stack()*/node*push_link_stack(node*top,node*push_link_stack(node*top,datatypedatatypex)x) node*p;node*p;p=
158、(node*)p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*分配空间分配空间*/ */p-info=x;/*p-info=x;/*设置新结点的值设置新结点的值*/ */p-next=top;/*p-next=top;/*插入插入(1)*/(1)*/top=p;/*top=p;/*插入插入(2)*/(2)*/returntop;returntop; 算法算法3.423.42向链式栈中插入一个值为向链式栈中插入一个值为x x的结点的结点 /*/*删除链式栈的栈顶结点删除链式栈的栈顶结点*/*/*/*文件名文件名lnkspoplnkspo
159、p.c.c，函数名函数名pop_link_stack()*/pop_link_stack()*/node*pop_link_stack(node*top)node*pop_link_stack(node*top) node*q;node*q;if(!top)if(!top)printfprintf(n(n链式栈是空的链式栈是空的!);!);returnNULL;returnNULL;q=top;/*q=top;/*指向被删除的结点指向被删除的结点(1)*/(1)*/top=top-next;/*top=top-next;/*删除栈顶结点删除栈顶结点(2)*/(2)*/free(q);free(
160、q);returntop;returntop; 算法算法3.433.43删除链式栈的栈顶结点删除链式栈的栈顶结点 3.7 链式队列链式队列 3.7.1 链式队列链式队列队列的链式存储称为链式队列。链式队列就是一队列的链式存储称为链式队列。链式队列就是一个特殊的单链表，对于这种特殊的单链表，它的插入个特殊的单链表，对于这种特殊的单链表，它的插入和删除规定在单链表的不同端进行。链式队列的队首和删除规定在单链表的不同端进行。链式队列的队首和队尾指针分别用和队尾指针分别用frontfront和和rearrear表示，链式队列如下图表示，链式队列如下图所示。所示。 链式队列类型的描述如下：链式队列类型的
161、描述如下：链式队列类型的描述如下：链式队列类型的描述如下：ADT link_queueADT link_queue数据集合数据集合数据集合数据集合K K：K=kK=k1 1, k, k2 2, k kn n,n0,n0，K K中的元素是中的元素是中的元素是中的元素是datatypedatatype类型类型类型类型数据关系数据关系数据关系数据关系R R：R=rR=r r= r= | i=1,2,n-1| i=1,2,n-1操作集合：操作集合：操作集合：操作集合：(1) (1) queue *init_link_queue() queue *init_link_queue() 建立一个空的链式队列
162、建立一个空的链式队列建立一个空的链式队列建立一个空的链式队列(2) (2) intint empty_link_queue(queue qu) empty_link_queue(queue qu) 判断链式队列是否为空判断链式队列是否为空判断链式队列是否为空判断链式队列是否为空(3) (3) void print_link_queue(queue *qu) void print_link_queue(queue *qu) 输出链式队列中各个结点的值输出链式队列中各个结点的值输出链式队列中各个结点的值输出链式队列中各个结点的值(4) (4) datatypedatatype get_first(
163、queue qu) get_first(queue qu) 取得链式队列的队首结点值取得链式队列的队首结点值取得链式队列的队首结点值取得链式队列的队首结点值(5) (5) queue queue *insert_link_queue(queue *insert_link_queue(queue *qu,*qu,datatypedatatype x) x) 向向向向链链链链式式式式队队队队列列列列中中中中插插插插入入入入一个值为一个值为一个值为一个值为x x的结点的结点的结点的结点(6) (6) queue *delete_link_queue(queue *qu) queue *delete_
164、link_queue(queue *qu) 删除链式队列中队首结点删除链式队列中队首结点删除链式队列中队首结点删除链式队列中队首结点 ADT link_queue; ADT link_queue; 3.7.2链式队列的实现：链式队列的实现： 链链式式队队列列的的结结点点定定义义和和单单链链表表一一样样。队队列列必必须须有有队队首首和和队队尾尾指指针针，因因此此增增加加定定义义一一个个结结构构类类型型，其其中中的的两个域分别为队首和队尾指针。其定义如下：两个域分别为队首和队尾指针。其定义如下：typedefstructtypedefstruct node*front,*rear;/*node*f
165、ront,*rear;/*定义队首与队尾指针定义队首与队尾指针*/ */ queue;queue;/*/*建立一个空的链式队列建立一个空的链式队列*/*/*/*文件名文件名lnkqinitlnkqinit.c.c，函数名函数名init_link_queue()*/init_link_queue()*/*/*/queue*init_link_queue()/*queue*init_link_queue()/*建立一个空的链式队列建立一个空的链式队列*/ */ queue*qu;queue*qu;qu=(queue*)qu=(queue*)mallocmalloc( (sizeofsizeof(q
166、ueue);/*(queue);/*分配空间分配空间*/ */qu-front=NULL;/*qu-front=NULL;/*队首指针设置为空队首指针设置为空*/ */qu-rear=NULL;/*qu-rear=NULL;/*队尾指针设置为空队尾指针设置为空*/ */returnqu;returnqu; 算法算法3.443.44建立一个空的链式队列建立一个空的链式队列 /*/*/*/*取得链式队列的队首结点值取得链式队列的队首结点值*/*/*/*文件名文件名lnkqgetlnkqget.c.c，函数名函数名get_first()*/get_first()*/*/*/datatypedatat
167、ypeget_first(queuequ)get_first(queuequ) if(!qu.front)if(!qu.front)printfprintf(n(n链式队列是空的链式队列是空的!);!);exit(1);exit(1);return(qu.front-info);return(qu.front-info); 算法算法3.473.47取得链式队列的队首结点值取得链式队列的队首结点值 链式队列的插入过程图示见下图：链式队列的插入过程图示见下图： /*/*向链式队列中插入一个值为向链式队列中插入一个值为x x的结点的结点*/*/queue*insert_link_queue(queu
168、e*qu,queue*insert_link_queue(queue*qu,datatypedatatypex)x)node*p;node*p;p=(node*)p=(node*)mallocmalloc( (sizeofsizeof(node);/*(node);/*分配空间分配空间*/ */p-info=x;/*p-info=x;/*设置新结点的值设置新结点的值*/*/p-next=NULL;p-next=NULL;if(qu-front=NULL)qu-front=qu-rear=p;if(qu-front=NULL)qu-front=qu-rear=p;elseelsequ-rear-
169、next=p;/*qu-rear-next=p;/*队尾插入队尾插入*/ */ qu-rear=p;qu-rear=p;returnqu;returnqu; 算法算法3.483.48向链式队列中插入一个值为向链式队列中插入一个值为x x的结点的结点 链式队列的删除过程图示见下图：链式队列的删除过程图示见下图： /*/*删除链式队列中队首结点删除链式队列中队首结点*/*/queue*delete_link_queue(queue*qu)/*queue*delete_link_queue(queue*qu)/*删除队首结点删除队首结点*/ */node*q;node*q;if(!qu-front)
170、if(!qu-front)printfprintf( (队列为空，无法删除！队列为空，无法删除！););returnqu;returnqu;q=qu-front;/*qq=qu-front;/*q指向队首结点指向队首结点(1)*/(1)*/qu-front=q-next;/*qu-front=q-next;/*队首指针指向下一个结点队首指针指向下一个结点(2)*/(2)*/free(q);/*free(q);/*释放原队首结点空间释放原队首结点空间*/ */ ifif(qu-front=NULL)(qu-front=NULL) qu-rear=NULL;qu-rear=NULL; /* /*队队列列中中的的唯唯一一结结点点被删除后，队列变空被删除后，队列变空(3)*/(3)*/returnqu;returnqu; 算法算法3.493.49删除链式队列中队首结点删除链式队列中队首结点
