计算机软件技术基础及实验指导 作者 席晓慧 袁玲 第4章 数据结构

第四章数据结构在线教务辅导网：http://教材其余课件及动画素材请查阅在线教务辅导网QQ:349134187

或者直接输入下面地址：§4.1数据结构概述§4.1.1数据结构的定义1、数据(data)：数据是一些可以输入到计算机中的描述客观事物的符号,即信息的载体。这些符号可以是数值、字符、图象等。在计算机领域，人们把能够被计算机加工的对象，或者说能够被计算机输入、存储、处理、输出的一切信息都叫做数据。2、数据元素(element)：数据元素是算法可以处理的最小数据单位，是一个数据整体中相对独立的元素。数据元素可以是简单数据，也可以由若干个简单数据（数据项）组成数据元素。数据和数据元素是相对而言的，是整体和个体之间的关系。例如，对一个字符串来说，每个字符都是它的数据元素；对一个数组来说，每个数组元素都是它的数据元素。本书中，经常将数据元素、数据结点、结点、记录这些概念不加区别的使用，它们表示的是同一概念。3、数据项：数据元素由更小的单位——数据项(item)（或成员）所组成，一个记录一般包括一个或若干个数据项。4、数据之间的联系：现实世界中的客观对象在计算机中是用数据来描述的，在现实世界当中，客观对象是有联系的，因此数据之间也是有联系的，数据联系是数据本身所具有的特性。5、数据结构（datastructure）：简单的说，数据结构就是研究数据和数据之间联系的一门学科，它包括三个方面。①数据的逻辑结构②数据的物理结构③数据的运算数据结构通常用二元组表示，其形式如下：Data_struct=(D,R)其中D为数据元素的集合，R为数据元素之间关系的集合。即：D={ai|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥1}ai为第i个数据元素，n为数据元素的个数，特别地，当n=0，D为空集，则无结构可言。rj表示第j个关系，m为关系的个数。§4.1.2数据结构的基本内容数据结构的基本内容包括数据的逻辑结构、数据的存储结构和数据的运算。1、数据的逻辑结构数据元素之间的逻辑关系就是数据的逻辑结构。一般情况下，一组数据元素并不是杂乱无章的，而是具有某种联系形式。这里的联系形式指数据元素与元素间的相互关系。数据之间的联系可以是固有的，也可以是根据数据处理的需要人为定义的。数据元素之间的联系方式可分为一对一、一对多和多对多三种，根据数据元素之间联系的不同特性，数据的逻辑结构通常有以下三种基本结构。线性结构数据结构中数据元素之间的联系方式是一对一的。树形结构数据结构中数据元素之间的联系方式是一对多的。

图形结构或网状结构数据结构中数据元素之间的联系方式是多对多一的。通常我们也把数据的逻辑结构分为线性结构和非线性结构，树形结构和图形结构统称为非线性结构。研究数据结构的目的是为了在计算机上实现对它的操作，因此还需研究如何在计算机中表示数据结构。2、数据的物理结构数据结构（包括数据及其数据之间的关系）在计算机存储器上的存储表示称为数据的物理结构或存储结构。数据结构研究的是数据及其数据之间联系的学科，因此在研究数据的存储结构时，要求数据的存储方式既能表示数据又能表示数据之间的联系。常用数据的存储结构有：顺序存储链式存储索引存储哈希存储顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的关系；链式存储结构是借助指示元素存储位置的指针表示数据元素之间的关系；索引存储结构是为存储的数据建立一个索引表，访问数据时先在索引表中查找，再根据索引表的相关信息访问数据；哈希存储是建立数据的关键字和存储地址之间的对应关系（哈希函数），这样访问一个数据时，可根据哈希函数直接获得该数据在计算机中的存储地址，到该地址访问数据。由于数据的存储结构有多种，所以一种数据的逻辑结构可以根据需要表示成一种或多种存储结构，只要存储结构既能表示数据，也能表示数据之间的联系或者存储结构能满足用户对数据的某种操纵要求即可。在后面的章节中，读者可根据具体的存储实例了解到一种数据的逻辑结构可以采用不同的存储方式进行存储。数据的逻辑结构和物理结构是数据结构两个密切相关的方面，以后读者可看到，一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采取的存储结构。算法的设计取决于数据的逻辑结构，算法的实现依赖于采用的存储结构，在不产生误解的情况下我们也将数据的逻辑结构称为数据结构如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存储器中的存储方式，但由于本书是在高级语言的层次上讨论数据结构的操作，因此可以借助高级语言中提供的“数据类型”来描述它。例如可以用C语言中提供的“数组类型”来描述顺序存储结构，用“指针”来构造链式存储结构。检索（查找）：在给定的数据结构中，找出满足一定条件的结点来，这个条件往往是一个或几个数据项的值。排序：根据给定的条件，将数据结构中所有结点重新排列顺序插入：在给定的数据结构中，根据某些条件，将一个结点插入到一个合适的位置。删除：在给定的数据结构中，根据某些条件，将一个结点删除。修改：修改数据结构中某些结点的值。运算的种类很多，同一种运算也存在各种各样的算法。在一种数据结构中要进行那一种或那几种运算，往往取决于要解决的实际问题。完成一种指定的运算，当然要选一种最好的算法。但对一种具体的数据结构来说，完成一种运算的效率较高，完成另外一种则可能较低，对另一种数据结构来说，情况可能正好相反。因此，要解决一个实际问题，数据结构的设计和算法的选择要结合起来考虑，对各种情况要反复比较，最终选择一个较好的数据结构和高效率的算法。3、数据的运算研究数据结构，除了研究数据结构本身以外，还要研究与数据结构相关联的运算。这里的运算是指对数据结构中的数据元素进行的操作处理，而这些操作与数据的逻辑结构和物理结构有直接的关系，结构不同，则实现方法也不同。运算的种类很多，但常用的有以下几种：§4.2线性表§4.2.1线性表的逻辑结构线性表（linearlist）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫线性表的长度，用n表示，n≥0。当n=0时，线性表是一个空表，即表中不包含任何元素。当n≠0时，设序列中的第i个元素为ai(1≤i≤n)，则线性表的一般表示为：（a1，a2，……，ai，……，an）其中，a1为第一个元素，又称为表头元素，an为最后一个元素，又称为表尾元素。每一个元素在表中的位置用其下标来表示。线性表具有如下特点：1）线性表的数据元素ai具有相同特性，在不同的情况下含义不同。可以为一个数、一个字符或更复杂的信息；在一个表中，ai类型必须相同。2）表非空的情况下，除第一个元素以外，每个元素都有且仅有一个直接前驱；除最后一个元素以外，每个元素都有且仅有一个直接后继。线性表中的元素在逻辑上是有序的，即第i个元素处在第i-1和第i+1个元素的中间，这种逻辑上的有序性就是一种线性关系，所以线性表的逻辑结构是线性结构。用二元组表示为：Linear_list=(D,R)D={ai|1≤i≤n,n≥0,ai∈elemtype}/*elemtype为任何数据类型*/R={r|r=<ai,ai+1>1≤i≤n-1}下面给出几个线性表的例子：（‘0’，‘1’，‘2’，‘3’，‘4’，‘5’，‘5’，‘6’，‘7’，‘8’，‘9’，‘-’，‘=’）（12，34，56，78，89，54，76，32，98）（“basic”,“fortran”,“pascal”,“cobol”）”其中，第一个线性表数据元素为字符型，第二个线性表数据元素为数值型，第三个线性表数据元素为字符串。§4.2.2线性表的存储结构线性表的存储结构有两种，即顺序存储结构和链式存储结构。具有顺序存储结构的线性表称为顺序表，具有链式存储结构的线性表称为线性链表。根据不同的需要对线性表可以进行多种操作，其基本运算有：清表清除表中的结点使其成为空表。排序根据给定的条件，将表中结点重新排列顺序。插入根据条件在表中插入一个结点。删除根据某些条件，将一个结点删除。修改修改表中给定结点的值。检索（查找）查找表中某一特征的结点。求长求线性表的长度。对线性表所采取的存储结构不同，其实现方法也不一样。下面分别介绍。1、线性表的顺序存储结构及其算法线性表的顺序存储结构是线性表的一种最简单的存储结构，其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于等于线性表的长度（假定每个存储单元存储线性表中的一个元素）。因为一个数组在内存中占据一段连续的存储单元，所以可以借助数组来为线性表的顺序存储开辟空间，如图4.1所示。其中L为每个元素占据的字节数，Loc(a1)为线性表的起始地址。存储地址Loc(a1)Loc(a1)+L…Loc(a1)+L*(i-1)…Loc(a1)+L*(n-1)数据元素序号12…i…na1a2…ai…an图4.1线性表的顺序存储结构示意图内存状态另外为了存储线性表的长度，还要定义一个整型变量。若将线性表的顺序存储结构定义为一个数组与一个整型变量，则可将它们放在一个结构体中，C语言定义形式为：#defineN1000/*N为线性表的最大元素个数*/typedefstructlist{elemtypev[N];intlen;}LIST;其中，N为线性表开辟的存储单元数，可以根据需要改变其大下。elemtype为线性表中元素的类型。在线性表的顺序存储结构中，借助存储单元的顺序性表示数据元素逻辑上的顺序性，可以看到逻辑上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任一元素，它的存贮位置可以用一个直观、简单的公式来表示(参看§4.3特殊线性表)，我们称顺序存储随机访问。下面是顺序存储的线性表的几个常用的算法。线性表顺序存储结构的几个常用算法①插入运算根据给定的条件不同，插入算法也不一样，如果要在线性表L的第i(0≤i≤L.len)个位置上插入一个元素x，那么只需要将第i个元素及其以后的所有元素后移一位，第i个位置上存入x，线性表的长度加1，如图4.2所示。LISTinslist(LISTL,inti,elemtypex){if(L.len==N)printf(“OVERFLOW\n”);elseif(i<0)||(i>L.len)printf(“positionERROR\n”);else{for(j=L.len-1;j>=i;j--)L.v[j+1]=L.v[j];L.v[i]=x;L.len++;}returnL}从算法中可见，当i的位置不合适时，插入无法进行。当表中有L.len个元素时，插入位置可以是从0到L.len。当插入位置在最后一个元素的后边（即下标L.len）时，不需要移动元素。如果插入条件是：在线性表中的某一元素之前（或之后）插入一元素，则应先查找该元素的位置，然后利用上述方法实现即可。从图4.2读者可以看到在数据x插入前后，线性表的有效元素都是从下表0到下标L.len-1。读者可自行编写该算法。②删除运算将线性表中的第i个元素删除的情况，可以用图4.3所示的方法实现。只要将从第i+1个元素到最后一个元素向前各移动一个元素，表的长度减一即可。相应的算法为：LISTdellist(LISTL,inti)/*删除线性表L中的第i个元素*/{if(i<0)||(i>=L.len)printf(“positionERROR\n”);else{for(j=i+1;j<=L.len-1;j++)L.v[j-1]=L.v[j];L.len--;}returnL}从算法中可见，当i的位置不合适时，删除无法进行。从图4.3读者同样可以看到，在第i个元素删除前后，线性表的有效元素都是从下表0到下标L.len-1。如果删除条件是：删除线性表中某一特定元素x，则应先查找该元素x的位置，然后利用上述方法实现即可。读者可自行编写该算法。③检索（查找）在线性表中检索值为x的元素，检索的方法很多，有顺序检索、折半检索、分块检索、散列检索等。下面仅介绍顺序检索，方法是，从线性表的第一个元素起，依次使每一个元素与值为x的元素进行比较，直到某个元素与x相等（既查找成功）或查完所有元素都找不到值为x的元素（查找失败）为止。算法为：intsearchlist(LISTL,elemtypex){for(i=0;i<L.len-1&&L.v[i]!=x;i++);if(i==L.len){printf(“notfound\n”);return–1;}elsereturni;}2、线性表的链式存储结构及其算法所谓链式存储结构是用户在编写程序时，利用高级语言提供的功能自己构建的存储结构。用户根据自己存储数据的需要，向计算机系统申请随机的存储单元，再将这些存储单元利用指针联系起来，构成链表。利用链式存储结构存储线性表，把线性表的第一个元素存储在链表的第一个结点，线性表的第二个元素存储在链表的第二个结点，…，线性表的最后一个元素存储在链表最后一个结点。结点示意结点地址Hd1d2d3dn结点序号头结点第一个结点第二个结点第三个结点第n个结点d1…a1d3a1d2a2d4annull这样逻辑在前的元素，在链表中的位置也在前（注意：不是地址单元在前，实际上d1,d2,…,dn为随机值，di与di+1的值之间没有谁大谁小的关系），利用指针访问链表中的结点时，通常是通过头指针获得逻辑上的第一个结点的地址，通过第一个结点获得第二个结点的地址，…，因次对链式存储的线性表访问时，逻辑在在前的元素访问也在前。我们称随机存储顺序访问。链式存储结构不要求逻辑上相邻的元素物理位置（存储地址）也相邻。它的存储特点是，用随机的存储单元存储线性表中的元素，其存储空间可连续、也可以不连续。因为存储空间不要求连续性，所以在存储完每一个数据元素的内容以后，还应指出下一元素的存储位置，将这两部分信息共同称为一个结点。，因此我们说，在线性表的链式存储结构中利用指针表示了元素之间逻辑上的顺序关系。一个链接表由n（n≥0）个结点组成，当n=0时称为空表。每一个结点中的指针域可以有一个，也可以有两个。有一个指针域的链表称为单链表，其中的指针域存储数据元素的后继结点的位置。有两个指针域的链表称为双链表，其中一个指针域存储数据元素的后继结点的位置，另一个指针域存储数据元素的前驱结点的位置。下面我们介绍单链表几个常见的算法。单链表的定义如下：typedefstructnode{elemtypedata;structnode*next;}NODE;NODE*H;设单链表H中有n个元素，分别为(a1,a2,……an),可以用图4.4描述单链表的结构。a1a2anNULLH…图4.4单链表示意图其中H为单链表中第一个结点的地址，称为头指针。最后一个元素an所在的结点不存在后继，因此其指针域的值为空(NULL)，从上面的结构中可以看到，链表在存储空间上的要求比线性表要付出更大的代价，因为它除了存储数据元素外，还要存储每个元素的后继元素的位置。判断一个链表为空的条件为：H==NULL。为了便于计算机算法编写，在单链表的第一个元素所在的结点之前附设一个结点——头结点。头结点的指针域存放第一个元素所在结点的存储位置，数据域不存储任何信息，因此单链表的头指针指向头结点，如图4.5（a）为带头结点的单链表的一般形式。如图4.5（b）为带头结点的单链表为空时的形式。(a)带头结点的单链表(b)带头结点的空单链表图4.5带头结点的单链表示意图a1anNULL…a2

NULLH

H判断一个链表是否为空的条件是：H->next==NULL链表加上头结点以后将空表和非空表的处理统一起来，因而简化了单链表的实现算法。下面介绍在这种存储结构上链表的几个主要操作。①带头结点单链表的查找设H为一带头结点的单链表的头指针，在线性表中查找第i（i>0）个元素所在的结点。要查找单链表中的某一结点，必须从头指针出发，沿结点的指针域往后找直到找到所要结点为止。算法如下：NODE*get(NODE*H,inti){NODE*p;intj=1;p=H->next;while((p!=NULL)&&(j<i)){p=p->next;j++;}if(p!=NULL)returnp;/*返回指向待查找结点的指针*/elsereturnNULL;/*查找的位置不合适*/}查找元素的时间复杂度为O(n)。②带头结点单链表的插入设H为一带头结点的单链表的头指针，在线性表的两个元素a和c之间插入一个元素b，设p为存储数据元素a结点地址的指针变量，设q为存储数据元素b结点地址的的指针变量，如图4.6(a)所示…pq…pacb…q(a)插入前(b)插入后图4.6单链表的插入示意图acb…在一个以链式存储的线性表的某个位置上插入一个结点，只需要改变其链接关系就可以。从图中可以看出插入结点b时，需要修改两个指针，将a结点的指针域的值由指向结点c改为指向结点b，再使结点b的指针域的值指向结点c，从而实现改变a，b和c之间的链接关系，插入后各元素的关系如图4.6(b)所示。修改指针关系的语句为：

q->next=p->next;p->next=q;下面的算法是在链表H中第i个位置上插入一元素为x的结点：voidinsnode(NODE*H,inti,intx){NODE*p,*q;if(i==1)p=H;elsep=get(H,i-1);/*查找插入元素的位置*/if(p!=NULL){q=(NODE*)malloc(sizeof(NODE));q->date=x;q->next=p->next;p->next=q;/*实现插入*/}elseprintf(“i<1或者i>表长，插入位置错误\n”);}与顺序表的插入比较，链表的插入更容易实现，不需要移动元素，只须修改两个指针，时间复杂度为O(1)。但是为了找到插入位置，需花费的时间复杂度为O(n)。③带头结点单链表的删除删除操作和插入基本相同，应先找到待删结点的前驱结点的位置后再完成删除。如图4.7（a）所示，设b为待删除的元素，p为指向待删元素的前一结点的指针，删除结束后元素a的后继由b改为c，操作中将b所在结点的地址记为q，以便处理和回收结点，如图4.7（b）所示。…p…pacb…q(a)删除前(b)删除后图4.7单链表的删除示意图pacb…q删除语句为：

q=p->next;p->next=q->next;free(q);下面的算法是在头指针为H的带头结点的单链表中删除第i个结点：voiddelnode(NODE*H,inti){NODE*p,*q;if(i==1)p=H;elsep=get(H,i-1);/*查找删除元素的位置*/if((p==NULL)||(p->next==NULL))printf(“表中无此结点\n”);else{q=p->next;p->next=q->next;free(q);}}与顺序表的删除比较，链表的删除也更容易实现，不需要移动元素，只须修改几个指针，时间复杂度为O(1)。同样为了找到删除位置，需花费的时间复杂度为O(n)。§4.2.3算法评价及改进算法的各种策略在前面两节我们讲解了线性表的两中存储方式，在这两种存储方式中我们采用了不同的方式将线性表表示到计算机中。用这两种存储方式存储线性表时，既表示了数据，也表示了数据之间的联系，同时我们看到，在实现线性表的相关运算（查找、插入、删除）时，两种存储结构采用的算法完全不同，正如我们在§4.1.1.中所讲：算法的设计取决于数据的逻辑结构，算法的实现依赖于采用的存储结构。下面我们分析线性表的顺序存储和链式存储在完成线性表的插入和删除算法的时间复杂度和空间复杂度。1、算法评价①时间复杂度前面在§2.2.3节中,我们讲到算法的时间复杂度的估算通常有两中方法：平均运算量和最坏的情况，对于具有n个元素的线性表的插入算法，在线性表第1,2,…,i,i+1,…n+1个位置任意一个位置进行插入在实际运行时都有可能，一个算法在实际使用的过程中，运行的次数很大，因此在任意一个位置的插入运算可以看做是一个随机量，在进行平均运算量的估算时，按在每个位置插入的概率是均等的。下面我们估算线性表的顺序存储结构和链式存储结构的时间复杂度。顺序存储结构：顺序存储的线性表在第i个位置进行插入时,应将i到n个位置上的元素依次向后移动，将要插入的元素存储到第i个存储单元，实现在线性表的第i个位置插入元素的运算。插入的位置数据移动的次数n+10n1n-12n-23……in-i+1……1n链式存储结构：在链式存储的线性表的第i个位置插入元素，只要能够获得一个指向第i-1个元素的指针，插入运算只需要进行下列面的两个基本运算：q->next=p->next;p->next=q;

换句话说，线性表的链式存储结构的插入运算的基本运算量，和插入的位置无关，在线性表的任意位置插入元素的基本运算量均为2，基本运算量不随数据规模的增长而变化，其时间复杂度为：O（1）②空间复杂度假设线性表的每个元素存储到计算机中，向系统申请的字节数为k，线性表长度为n。用顺序存储结构存储线性表，则相应的算法运行时，向系统申请的临时空间字节数为：

k*n用链式存储结构存储线性表，每个结点的指针域向系统申请的字节数为2，则相应的算法在运行时向系统申请的临时空间字节数为：（k+2）*n用线性表两种不同的存储方式设计算法时，从向系统申请的总的字节数来说，链式存储结构由于每个结点除存储线性表的元素外，还需开辟存储下一个结点地址的指针，因此链式存储结构向系统申请的总字节数比顺序存储结构多（（k+2）*n>k*n），但是，顺序存储的线性表向系统申请的是连续的存储单元（地址号连续的k*n个字节），而链式存储的线性表向系统申请的是随机的存储单元（n个随机的（k+2）字节单元），从这一点上说，顺序存储的线性表比链式存储的线性表对系统存储空间的要求高，链式存储的线性表的空间复杂度比顺序存储的线性表的空间复杂度小，即从空间复杂度上讲，链式存储的线性表优于顺序存储的线性表。比较线性表的链式存储结构和顺序存储结构编写的线性表的插入算法，我们可以看到，链式存储的线性表的算法的编写对编程者有更高的要求。综上所述，线性表的链式存储和顺序存储各有自己的特点，程序设计者在实际编程中可根据实际情况选择相应的存储方式存储线性表、操纵线性表。查找算法的复杂度读者可自行分析。2、算法的策略①不带头结点的单链表和带头结点的单链表通过前面的研究我们知道，链接存储结构是线性表的一种存储方式。在构造链式存储时我们采用的是将线性表的第1个元素存放放在单链表的第2个结点，线性表的第2个元素存放放在单链表的第3个结点，…，线性表的第i个元素存放放在单链表的第i+1个结点,…,这样构造的单链表我们称为带头结点的单链表，当然在构造单链表时我们也可以将线性表的第1个元素存放在单链表的第1个结点，线性表的第2个元素存放放在单链表的第2个结点，…，线性表的第i个元素存放放在单链表的第i个结点，…，这样构造的单链表我们称为不带头结点的单链表，因此我们说在构造线性表的链式存储结构时，是否带头结点是一种构造存储的策略，在§4.2.2线性表的插入、删除、查找运算中，链式存储的线性表采用的是带头结点的单链表，下面我们给出用不带头结点的单链表存储线性表插入运算的算法。用此算法和上面带头结点的单链表中删除第i个元素的算法进行比较，读者可发现两种方法的不同之处。在不带头结点的单链表中进行操作时，要区分第一个结点和表中结点，因为第一个结点的地址值发生变化后，表示链表的头指针H的值也会发生变化（参考图4.4），比如删除操作，若删除的元素为a1，则删除后H的值为a2的地址，若是在带头结点的单链表中进行操作则不同（参考图4.5（a）），此时即使删除的元素为a1，删除后H的值也不会发生变化。

voiddel(NODE*H,inti)/*将H为头指针的链表中第i个结点删除*/{NODE*p,*q;intm=1;if(H!=NULL){q=H;if(i==1){H=H->next;/*删除表头结点*/free(q);}else{while(q!=NULL&&m<i)/*查找待删结点q,q为第i个结点的前一结点*/{ p=q;q=q->next;m++;}if(q==NULL) printf("%dnotbeenfound\n",i);/*没找到待删结点*/else{p->next=q->next;/*删除结点q*/ free(q);}}}elseprintf("thelistempty\n");/*表空*/}通过带头结点和不带头结点两种不同的存储线性表的策略，我们明显地看到，在线性表的插入、删除运算中，带头结点的单链表比不带头结点的单链表算法思路简洁、结构简单。②循环单链表和双向链表采用链式存储的线性表在算法设计中，对线性表的操作我们总是利用头指针找到被访问的结点，对该结点进行访问，而且这种访问是单方向的（如果我们需要访问该结点的前一个结点，又必须从头结点开始），这种情况下采用单链表的存储方式，运算的效率低。如果我们构建循环单链表和双向链表来存储线性表，这样对上述情况将会有所改观。循环单链表如果有一个单链表其表尾元素的指针域的值不为NULL，而让它指向头结点，这样的链表叫循环单链表或环形链表。图4.8为带头结点的循环链表示意图：

Ha1an…(a)循环单链表a2空的表循环单链表图4.8循环单链表示意图H

Ha1an…(a)循环单链表a2空的表循环单链表图4.8循环单链表示意图

H循环单链表与单链表的大部分操作相同，如插入、删除、查找等。与单链表比较有以下不同点。判断链表结束的条件不同。设p为链表中任意一结点的指针，在单链表中当某一结点p的next域指向NULL时，则说明链表操作结束（p->next==NULL）。而在循环单链表中没有指向NULL的指针，链表操作结束的条件应为：某一结点p的next域指向表头结点（p->next==H）。b)从单链表的某一结点出发只能访问到其后继结点，所需的时间复杂度为O(1)，而循环单链表除了能访问结点p的后继结点外，也能访问其前驱结点，其方法是从此结点出发，找到满足条件（q->next==p）的结点q，则q为p的前驱结点，时间复杂度为O(n)。c)采用单链表的形式存储一个线性表，从一个结点出发只能够访问到该结点的后继结点，而采用循环单链表的形式存储一个线表，从一个结点出发既可以访问到该结点的后继结点，也可以访问到该结点的前驱结点，也就是说，从循环单链表的任意一个结点出发，可以访问该链表的任意一个结点。如果一个链表为循环链表，则许多操作可只对链表设一个尾指针，而没有头指针，因为这样更利于链表的操作，如链表的合并等。上面我们我们对循环单链表存储线性表进行了分析，我们看到采用循环单链表的形式存储线性表，从一个结点出发，可以访问到线性表的任意一个结点，但如果从一个结点出发访问该结点的前一个结点，则算法的运算量最大（需要将线性表中的所有结点均扫描一遍），如果我们采用双向链表的形式存储线表，这种情况可以得到改观。双向链表如果在每个结点上再增加一个指向线性表中每个元素的前驱结点的指针prior，就可以很方便的找到前驱结点（p->prior）或后继结点（p->next），这样组织的链表可以使得我们从一个结点出发，既可以向后访问该结点的后继结点，也可以向前访问该结点的前驱结点，因此我们称这样的链表为双向链表。有时为了满足需要，也为了操作的方便，用双向链表对线性表进行定义和操作。双向链表的定义如下。

typedefstructdnode{elemtypenum;structnode*prior,*next;}DNODE其中prior为指向前趋结点的指针，next为指向后继结点的指针。图4.9(a)为双向链表的示意图，图4.9(b)为空的双向链表的示意图，a1anNULL…(a)

双向链表a2H空表图4.9双向链表示意图NULLNULLHNULL与循环单链表相同，也可以定义循环双链表。如图4.10(a)为循环双链表，图4.10(b)为空的循环双链表。(a)循环双链表(b)空表图4.10循环双链表示意图HHa1an…a2在双向链表中凡涉及一个方向的操作与单链表一样。只是在做插入和删除时的操作不同。1)定位删除设p为待删结点的指针，如图4.11所示，p（b）删除后（a）删除前

xyzxyz图4.11双向链表中结点删除情况删除语句为：

p->prior->next=p->next;p->next->prior=p->prev;free(p);2)定位插入设p为待插入结点的位置，待插结点指针为q,在p结点之前或之后插入均可。如图4.12为在p结点之前插入q结点的示意图。在p结点之前插入的语句可描述为：

q->prior=p->prior;p->prior->next=q;p->prior=q;q->next=p;p（b）插入后（a）插入前

xyzxyz图4.12双向链表中结点删除情况

sq

sqp同样的，也可以在p结点之后插入q结点，插入语句可描述为：

q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;3、算法举例：例1写出在带有头结点的循环链表L中查找第i个元素的算法。#include<stdio.h>typedefstructnode{intdata;structnode*next;}NODE;NODE*search(NODE*H,inti)/*在带头结点的循环单链表中查找第i个元素*/{NODE*p=H->next;intj=1;while(j<i&&p->next!=H){p=p->next;j++;}if(i==j)returnp;elsereturnNULL;}NODEcreat(intn)/*创建带头结点的循环单链表*/{intnum;NODE*head,*s,*p;head=(NODE*)malloc(sizeof(NODE));head->next=head;p=head;while(n>0){printf("Pleaseinputthedatas:");scanf("%d",&num);s=(NODE*)malloc(sizeof(NODE));s->data=num;s->next=p->next;p->next=s;p=s;n=n-1;}returnhead;}

main()/*主函数*/{NODE*p,*q;inti,n;chart='y';printf("PleaeinputthelengthoftheList:");scanf("%d",&n);p=creat(n);while(t=='y'){printf("\nPleaseinputi=");scanf("%d",&i);while(i>n||i<1){printf("ERROR!Pleaeinputiagain:\n");scanf("%d",&i);}q=search(p,i);printf("\nDatais:%d\n",q->data);

printf("\nContinueOrNot?(y/n)");scanf("\n%c",&t);

}}例2写出一个将链表进行逆转的算法。#include<stdio.h>typedefstructnode{intdata;structnode*next;}NODE;NODEturn(NODEH)/*逆转函数*/{NODE*p=H,*q=H,*head;head=(NODE*)malloc(sizeof(NODE));while(p->next!=NULL)p=p->next;head->next=p;while(p->next!=H){while(q->next!=p) q=q->next;p->next=q;p=p->next;q=H;}p->next=NULL;returnhead;free(H);}NODEcreat(intn)/*创建带头结点的单链表*/{intnum;NODE*head,*s,*p;head=(NODE*)malloc(sizeof(NODE));head->next=NULL;p=head->next;while(n>0){printf("Pleaseinputthedatas:");scanf("%d",&num);s=(NODE*)malloc(sizeof(NODE));s->data=num;s->next=p->next;p->next=s;p=s;n=n-1;}returnhead;}

main(){NODE*p,*q,*t;intn,s;printf("PleaeinputthelengthoftheList:");

scanf("%d",&n);

t=creat(n);p=t;

printf("Thelist'sdatais:\n");while(p->next!=NULL){p=p->next;printf("%d\t",p->data);}

q=turn(t);printf("\nTheturnedlistis:\n");while(q->next!=NULL){q=q->next;printf("%d\t",q->data);}printf("\nPressanykeytoquit...");getch();printf("\n\n");}§4.3特殊线性表§4.3.1栈栈又称堆栈（Stack），是在程序设计中广泛应用的一种数据结构，就其逻辑结构而言，是一种特殊的线性表，其特殊性主要体现在做插入和删除时受限制。1、栈的定义栈是允许在一端进行插入和删除操作的特殊线性表，其中，允许进行插入和删除的一端叫栈顶，另一端叫栈底。向栈顶插入元素叫入栈、进栈或压栈，从栈顶删除元素叫出栈或退栈。由于栈的插入和删除仅在栈顶一端进行，后进栈的元素必先删除，所以栈又叫后进先出（LastInFirstOut简称LIFO）表。设有三个元素，入栈序列为a、b、c，则可能的出栈序列有以下五种，如图4.13所示，其中s代表入栈，p代表出栈。不可能得到的出栈序列为cab。出栈序列操作序列abcacbbacbcacbaspspspspssppssppspsspsppsssppp对于栈常进行的运算有以下几种。①初始化初始化栈为空。②判空判断栈是否为空，若为空，则返回真，否则返回假。③入栈向栈顶插入一个元素。④出栈删除栈顶元素。读栈取出栈顶元素。图4.132、栈的存储结构

栈是一种特殊的线性表，其特殊性体现在操作受限，前面我们讨论了线性表，我们看到线性表有顺序存储和链式存储两种存储方式，那么栈也有顺序和链式两种存储方式。①栈的顺序存储结构及顺序栈的运算栈的顺序存储结构栈的顺序存储结构是利用一组地址连续的存储单元依次存储栈中元素，顺序存储的栈我们称为顺序栈。利用C语言中的结构体和数组对栈定义如下：#defineN1000/*设N为栈的最大元素个数*/typedefstructstack{elemtypev[N];/*为栈申请的存储单元的个数，栈的最大容量*/inttop；/*栈顶指针，标注栈顶的位置*/}其中top中存储栈顶元素的编号，又称栈顶指针。elemtype为栈中元素的类型。v数组用来存储栈的实际元素。图4.14展示了顺序栈中元素与栈顶指针之间的关系。顺序栈的运算1）初始化栈空初始化栈时只须将栈顶指针设为-1即可。voidinistack(STACK*s){s->top=-1;}2）入栈在栈中插入元素时，若top已指向下标为N-1的分量，则栈满，不可入栈。算法如下：voidpush(STACK*s,elemtypex)/*将值为x的元素入栈*/{if(s->top==N-1){printf(“栈满,overflow\n”);exit(1);}else{s->top=s->top+1;s->v[s->top]=x;}}算法的时间复杂度为O(1)。3）出栈当在栈顶删除元素时，首先要判断栈是否为空，若为空，则不能删除，否则将栈顶指针减1，原栈顶元素返回即可，算法如下：

elemtypepop(STACK*s){if(s->top==-1){printf(“栈空,downflow\n”);exit(1);}else{s->top=s->top-1;returns->v[s->top+1];}}算法的时间复杂度为O(1)。4）栈的操作策略——双栈操作当在一个程序中需要同时使用具有相同类型的两个栈时，一种最直接的方法是为两个栈开辟一段存储空间，此时如果栈顶位置设置不当，会出现当一个栈满时，另一个栈还有许多空间的情况。较好的方法是将两个栈的栈顶的初始位置设在空间的两端，两个栈的入栈操作各自向中间延伸，当两个栈的栈顶相遇时栈满，如图4.15所示下面是两个栈共享空间时的定义和出入栈算法。#defineN1000/*设N为两个栈总的最大元素个数*/typedefstructstack{elemtypev[N];inttop1，top2;}LSTACK;入栈算法：voidpush(LSTACK*s,inti,elemtypex)/*将值为x的元素入栈*/{if(s->top1+1==s->top2){printf(“栈满,overflow\n”);exit(1);}else{switch(i)1:s->top1=s->top1+1;s->v[s->top1]=x;break;2:s->top2=s->top2-1;s->v[s->top2]=x;break;default:printf(“i不合法\n”);}}出栈算法：elemtypepop(LSTACK*s,inti){elemtypex;switch(i){1:if(s->top1==-1){printf(“栈空,downflow\n”);exit(1);}else{x=s->v[s->top1];s->top1--;}break;2:if(s->top2==N-1){printf(“栈空,downflow\n”);exit(1);}else{x=s->v[s->top2];s->top2++;}break;default:printf(“i不合法\n”);}returnx;}②栈的链式存储结构及链栈的运算由于栈的实际容量是动态变化的，使用顺序栈时，当一个程序中同时使用多个栈时，为了防止栈满溢出，需要为每个栈分配较大的空间，此时往往会出现这样的情况，当一个栈已溢出，其它的栈还有很多的存储空间。这时就要讨论多个栈共享存储空间的问题。因为栈的容量不好事先估计，使用顺序栈时会有存储空间的浪费，如果把一个链表做栈用，可以避免事先估计栈的容量，在使用过程中根据需要向系统申请存储单元，存储栈中的元素。链式存储结构的栈也叫链栈。链栈是只允许在表头进行插入和删除的单链表，表头指针可以作为栈顶指针。图4.16为链栈的存储结构示意图。top为栈顶指针。topa1a2anNULL…图4.16链栈示意图链栈的定义如下：typedefstructnode/*定义链表的结点，与入栈元素的类型一致*/{elemtypedata;structnode*next;}SNODE;SNODEtop;/*栈顶指针，指向栈顶的位置*/栈空的条件为top==NULL.。使用链栈时，程序设计者可以使用不带头结点的单链表、带头结点的单链表、不带头结点的循环单链表、带头结点的循环单链表等做为栈，只是在进行栈的操作时，要本着怎样组织、怎样操作的原则。下面给出使用不带头结点和带头结点的单链表栈，进行入栈和出栈操作的算法，使读者对程序设计中栈的使用有一个更深的理解。1）不带头结点的单链表栈的入栈操作首先申请一结点new，若申请成功才可入栈，否则结束操作。入栈时将new结点插入栈顶指针之前即可。算法如下：voidpush(SNODE*top,elemtypex){SNODE*new;new=(SNODE*)malloc(sizeof(SNODE));/*生成结点*/if(new!=NULL){new->data=x;new->next=top;top=new;}/*入栈*/else{printf(“申请空间失败\n”);exit(1);}}2）不带头结点的单链表栈的出栈操作若链栈头指针为空，则栈空，否则删除栈顶结点并将栈顶指针后移。算法如下。elemtypepop(SNODE*top){SNODE*new;elemtypex;if(top!=NULL){new=top;top=top->next;x=new->data;free(new);/*出栈*/returnx;}else{printf(“栈空删除失败\n”);exit(1);}}3）带头结点的单链表栈的入栈操作与不带头结点的单链表相同，入栈的操作是在栈顶的位置进行，对于链栈来说程序设计者需要设计一个栈顶指针，使在任何时候都指向栈顶的位置，入栈的操作就是把要入栈的元素插入到栈顶的位置。如下图：图4.17链栈入栈示意图topa1anNULL…topxa1anNULL…（a）元素x入栈前（b）元素x入栈后newx其算法如下：voidpush(SNODE*top,elemtypex){SNODE*new;new=(SNODE*)malloc(sizeof(SNODE));/*生成结点*/if(new!=NULL){new->data=x;new->next=top->next;top->next=new;}/*入栈*/else{printf(“申请空间失败\n”);exit(1);}}4）带头结点的单链表栈的出栈操作与不带头结点的单链表相同，带头结点的链栈出栈的操作是在栈顶的位置进行，对于链栈来说程序设计者需要设计一个栈顶指针，使在任何时候都指向栈顶的位置，出栈的操作就是把栈顶元素从栈中删除。如图4-18示topa1anNULL…topxa1anNULL…newx（a）出栈操作前图4.18链栈出栈示意图（b）出栈操作后其算法如下：elemtypepop(SNODE*top){SNODE*new;elemtypex;if(top->next!=NULL)/*出栈*/{new=top->next;top->next=new->next;x=new->data;free(new);returnx;}else{printf(“栈空,删除失败\n”);exit(1);}}有两点需要引起读者的注意，其一，我们必须认识到栈其实是程序设计者在进行算法设计时为达到一定的操作要求（先进后出、后进先出）而采用的算法策略，因此栈不是计算机的固有属性，我们说栈是逻辑结构而非物理结构。然而在实际应用当中，只有编写相对复杂的算法（树和图的遍历算法等）尤其是系统程序时常采用栈这样的算法策略，容易让读者误以为栈是计算机的固有属性，因此提醒读者注意。其二，栈中的数据是动态变化的，它不同于我们以各种方式（数组、链表等）存储在计算机中的数据，随着入栈、出栈操作的进行，栈顶的指针不断的移动，我们知道栈中的元素是栈顶到栈底之间的元素，栈中的元素与我们给栈开辟的存储空间的大小没有直接的关系，为栈开辟的存储空间的大小决定栈的容量。§4.3.2队列同栈一样，队列也是一种操作受限的线性表。1、队列的定义：队列是特殊的线性表，规定只允许在线性表的一端进行插入而在另一端进行删除操作，其中，允许进行插入的一端叫队尾，允许进行删除的一端叫队头。当队列中没有元素时叫空队列。由于队列的插入和删除各在一端进行，所以最先进队的元素必先删除，即队列具有先进先出的特性，所以队列又叫先进先出（FirstInFirstOut简称FIFO）表。对队列可以进行的运算有以下几种：①初始化初始化队列为空。②判空判断队列是否为空，若为空，则返回真，否则返回假。③入队若队列未满，向队尾插入一个元素。④出队若队列未空，删除队头元素。⑤读取队头元素若队列未空，读取队头元素。日常生活中队列的例子比比皆是。如购物排队、等车排队等；在计算机操作系统中，队列的应用也非常广泛，如操作系统中的作业排队、进程排队等。根据操作的需要，队列的存储也可分为顺序存储和链式存储。2、队列的存储结构①队列的顺序存储结构及顺序队列的运算队列的顺序存储结构是利用一组地址连续的存储单元依次存储队列中的元素，但是因为队列分队头和队尾，所以对队列的定义除了一组地址连续的存储单元外还需要两个量分别存储队头和队尾指针。利用C语言中的结构体和数组对队列定义如下：#defineN1000/*设N为队列的最大元素个数*/typedefstructqueue{elemtypev[N];/*elemtype为队中元素的类型*/intfront;/*队头指针*/intrear;/*队尾指针*/}QUEUE;QUEUEQ;在进行操作时，约定队列的队头元素始终指向队头元素的前一位置，队尾元素指向队尾元素的实际位置。此时队列的出、入队变化图如图4.19所示。从下图可以看出，入队列的命令可叙述如下：{Q.rear++;Q.v[Q.rear]=x;}类似的，出队列的命令可叙述如下：{Q.front++;}在上述前提下，空队列时头、尾指针的关系如下：Q.front==Q.rear如图4.19中的(a)和(c)。值得考虑的是队列满的判断条件是什么？假设当前队列处于图4.19的（d）状态，此时Q.rear=N-1，显然不能作入队操作，（因为Q.rear+1=N，超过了队列的最大容量）但是队列里还有剩余空间，这种现象称为假溢出。解决“假溢出”的办法有两个。其一：将队列中的所有元素向前移动，使队列中的第一个元素位于第0分量中，且置队头指针为-1。这种方法较费时。其二：将队列设想为一个循环队列，即第0分量连在第N-1分量之后，使向量v成为一个首尾相接的环，即如果Q.rear+1等于N,则Q.rear=0;如图4.20所示：N-101

Q.rear

Q.front

图4.20

循环队列示意图…此时，入队操作可叙述为：{Q.rear=(Q.rear+1)%N;Q.v[Q.rear]=x;}相应的出队操作可叙述为：{Q.front=(Q.front+1)%N;}然而，此时队列又出现一个新问题，即如何判断队空和队满？假设当前循环队列的状态如图4.21(a)所示。Q.rearQ.rearQ.front(a)队列未满时(b)队列满时（c）队列空时

图4.21

循环队列的头尾指针变化情况示意图Q.frontacbQ.frontQ.rearacbdef现有三个元素相继入队，则队列满如图4.21(b)，此时Q.front=Q.rear。又设在图4.21(a)状态下，有三个元素相继出队，则队列空如图4.21(c)。从图中可以看到这两种情况都存在等式Q.front=Q.rear，由此可见不能只凭该等式去判断队空还是队满。可以有两种方法处理此问题，其一是另设一标志表示队满或队空；其二是少用一个存储空间，以尾指针加1等于头指针作为队满的条件。此时队满和队空分别如图4.22所示。(b)队列满时（c）队列空时

图4.22

循环队列的头尾指针变化情况示意图Q.rearQ.frontQ.rearQ.frontacbde下面是循环队列的入队和出队算法。1)入队操作voidaddqueue(QUEUEQ,elemtypex)/*入队*/{if(Q.front==(Q.rear+1)%N){print(“队满，上溢\n”);exit(1);}else{Q.rear=(Q.rear+1)%N;Q.v[Q.rear]=x;}}2）出队操作elemtypedelqueue(QUEUEQ)/*出队*/{elemtypex;if(Q.front==Q.rear){print(“队空，下溢\n”);exit(1);}else{Q.front=(Q.front+1)%N;x=Q.v[Q.front];returnx;}}与栈相同，队列也是程序设计者在进行算法设计时为达到一定的操作要求（先进先出、后进后出）而采用的算法策略，因此队列不是计算机的固有属性，我们说队列是逻辑结构而非物理结构；队列中的数据是动态变化的，它不同于我们以各种方式（数组、链表等）存储在计算机中的数据，随着入队、出队操作的进行，队头、队尾的指针不断的移动，我们必须清楚队列中的元素是队头到队尾之间的元素，队列中的元素与我们给队列开辟的存储空间的大小没有直接的关系。下面是循环顺序队列中，队列中实际元素的示意图,图中阴影部分为队列中元素所占居的空间。Q.v[n-1]Q.v[0]为队列开辟的存储单元rearQ.v[Q.rear]frontQ.v[Q.front]………Q.v[n-1]Q.v[0]为队列开辟的存储单元frontQ.v[Q.front]rearQ.v[Q.rear]………a队头指针在前、队尾指针在后b队头指针在后队尾指针在前图4-23动态变化过程中队列中元素位置可能出现的两种情况②队列的链式存储结构及链队列的运算利用带头结点的单链表来存储队列，称为队列的链式存储结构。因为一个队列需要队头和队尾两个指针才能更方便其操作，所以在链队列里，设两个指针，其一指向带头结点的单链表的头结点，称为队头指针。其二指向单链表的表尾结点，称为队尾指针，其定义如下：typedefstructnode{elemtypedata;structnode*next;}QNODE;QNODE*front,*rear;链队列如图4.24所示

NULLQ.frontQ.rear图4.24.(b)空队a1anNULL…图4.21(a)链队列a2

Q.frontQ.rear与线性表比较，链队列的操作更方便，入队只需要在表尾添加结点，出队在表头删除结点即可。链队列的出入队算法如下：1)入队操作首先申请一结点new，若申请成功才可入队，否则结束操作。入队时将new结点插入链队列最后即可。算法如下：voidinsqueue(QNODE*front,QNODE*rear,elemtypex){QNODE*new;new=(QNODE*)malloc(sizeof(QNODE));if(new!=NULL){new->next=NULL;new->data=x;rear->next=new;rear=new;}else{printf(“申请空间失败\n”);exit(1);}}2)出队操作若链队列的结点个数大于1时，只须修改队头指针的next域的值，若链队列的结点个数等于1时，出队列操作除修改队头指针的next域的值外，还应该修改尾指针。如图4.25所示。图4.25（a）结点个数大于1时，出队示意图（b）结点个数等于1时，删除前（c）结点个数等于1时，删除后

NULLQ.frontQ.rear图4.25.(c)

Q.frontQ.rear图4.25.(b)a1NULLa1anNULL…图4.25(a)a2

Q.frontQ.rear算法如下：elemtypepop(QNODE*front,QNODE*rear){QNODE*new;elemtypex;if(front==rear){printf(“链队列空，删除失败\n”);exit(1);}else{new=front->next;front->next=new->next;if(new->next==NULL)rear=front;x=new->data;free(new);returnx;}}§4.3.3串串是每个数据元素仅由一个字符组成的特殊线性表。1、串的定义串是字符的一个有限序列，表示为：String=’a1a2a3…an’其中，单引号为字符串的起始界限符，不属于字符串本身的字符，ai(1≤i≤n,n≥0),表示非空字符串中的第i个字符，n为串中字符的个数，称为串的长度；当n=0时，表示空串，即串中不含任何字符。由一个或多个空格字符组成的串称为空格串。串中任意个连续的字符组成的子序列称为该串的子串。相应的包含子串的串称为主串。称某一个字符在主串中的序号为该字符在串中的位置。用子串的第一个字符在主串中的位置作为子串在主串中的位置。当两个串的长度相等，并且每个对应位置上的字符均相等时，称两个串是相等串。例如：s1=‘’s2=‘’s3=‘datastructure’s4=‘Thisisapen’s5=‘is’上面的串长分别为0、3、14、13、2，其中s1为空串，s2为空格串，串s5是s4的子串，串s4是串s5的主串，串s5在串s4中的位置是3。值得注意的是：空串是任意串的子串，任意串又是自己的子串。2、串的存储结构①串的顺序存储结构串的存储也分为链式存储结构和顺序存储结构。串的顺序存储结构是利用一块地址连续的存储单元存储串中的字符序列。用c语言描述时除了描述串本身之外，还应指出串的实际长度。描述如下：#defineN1000/*N为串中实际字符的最大可能值*/charstring[N];C语言中，串的实际长度为串结束符‘\0’之前的所有字符。当计算机的存储结构采用字编址时（1字=4字节），数组的一个分量至少占一个字的存储单元，此时串的存储结构有两种存储格式：紧缩存储格式和非紧缩存储格式。所谓非紧缩存储格式是一个字的存储单元存放1个字符，所谓紧缩存储格式是一个字的存储单元存放4个字符，设串为‘clanguage’则紧缩存储格式和非紧缩存储格式示意图如图4.26所示。从上图中可以看出，与非紧缩存储格式相比，紧缩存储格式比较节约存储单元，但对串的访问要相对慢一些，因为要花费时间去分离同一字中的单个字符，非紧缩存储格式操作方便，却浪费3/4的存储空间。两种存储格式在作插入和删除时都要移动字符。当计算机采用字节编址时，串的顺序存储结构中各种操作的实现都很方便。②串的链式存储结构串是一种特殊的线性表，也可以采用链式存储方式。其链式存储结构描述如下：

typedefstructgnode{chardata;structgnode*next;}GNODE;与线性表的链式存储结构比较，串的定义中数据类型为char，而线性表为elemtype，即任意类型。由于串结构的特殊性，则用链式结构存储串时，存在一个“结点大小”的问题，每个结点可以存储一个字符，也可