计算机软件基础(孟彩霞)第2章线性数据结构.ppt

《计算机软件基础(孟彩霞)第2章线性数据结构.ppt》由会员分享，可在线阅读，更多相关《计算机软件基础(孟彩霞)第2章线性数据结构.ppt（207页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 线性数据结构线性数据结构 第第2章章 线性数据结构线性数据结构 2.1 基本概念基本概念 2.2 线性表线性表 2.3 栈和队列栈和队列 2.4 串和数组串和数组 习题习题 第第2 2章章 线性数据结构线性数据结构 2.1 基基 本本 概概 念念 2.1.1数据和数据结构现代数字计算机原是作为能快速地进行复杂、耗时计算的工具而发明的。随着计算机的发展，在计算机的绝大多数应用中，能够存取、处理大量信息的能力却被认为是计算机的首要特征，而它的计算能力在许多情况下已经几乎被人们忽略了。有位美国学者曾批评说：“计算机”这个词只告诉我们以前能做的事，却未道出它的潜能。有鉴于此，人们常常把

2、计算机称作数据处理机。第第2 2章章 线性数据结构线性数据结构 什么是数据？数据就是计算机可以保存和处理的信息。可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如文字、表格、图形、图像、声音等也属于数据的范畴。第第2 2章章 线性数据结构线性数据结构 组成数据的基本单位是数据元素。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串，也可以由若干数据项组成。在这种情况下，通常把数据元素称为

3、记录。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。第第2 2章章 线性数据结构线性数据结构 什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说，数据结构就是研究数据及数据元素之间关系的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容：数据的逻辑结构。数据的存储结构。数据的运算。第第2 2章章 线性数据结构线性数据结构

4、 表2-1学生学籍登记表学号姓名性别民族籍贯专业1王安男汉北京计算机通信2李华男回河北软件3张莉女汉山西计算机应用4张平女汉广东软件第第2 2章章 线性数据结构线性数据结构 1.数据的逻辑结构数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为Data?Structure=(D，R)其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。根据数据元素之间关系的不同特性，数据结构又可分为两大类：线性数据结构和非线性数据结构。按照这种划分原则，本书介绍的所有数据结构如图2-1所示。第第2 2章章 线性数据结构线性数据结构 图2-1数据结构分类第第2 2章章 线性

5、数据结构线性数据结构 2数据的存储结构数据的逻辑结构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结构。计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。数据的存储结构要讨论的就是数据结构在计算机存储器上的存储映像方法。第第2 2章章 线性数据结构线性数据结构 实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说，数据在存储器中的存储有四种基本的映像方法。(1)顺序存储结构。这种存储方式主要用于线性数据结构，就是把数据元素按某种

6、顺序放在一块连续的存储单元中。其特点是逻辑上相邻的数据元素存储在物理上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。某些非线性数据结构也可以采用顺序方式存储，例如完全二叉树、多维数组等，具体方法将在后面介绍。第第2 2章章 线性数据结构线性数据结构 (2)链式存储结构。链式存储结构可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。即可用一组任意的存储单元来存储数据元素，这些存储单元可以是连续的，也可以是不连续的。另外对于非线性数据结构，还可以在线性编址的计算机存储器中表示结点之间的非线性关系。链式存储结构的特点就是将存放每个数据元素的结点分为两部分：一部分存放数据元素(称

7、为数据域)：另一部分存放指示存储地址的指针(称为指针域)，借助指针表示数据元素之间的关系。第第2 2章章 线性数据结构线性数据结构 (3)索引存储结构。在线性表中，数据元素可以排成一个序列：R1、R2、R3、Rn，每个数据元素Ri在序列里都有对应的位置数据i，这就是元素的索引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是建立附加的索引表，索引表里第i项的值就是第i个元素的存储地址。第第2 2章章 线性数据结构线性数据结构 (4)散列存储结构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关系F。根据这个映像关系F，已知某数

8、据元素就可以得到它的存储地址。即D=F(E)，这里E是要存放的数据元素，D是该数据元素的存储位置。可见，这种存储结构的关键是设计这个函数F。但函数F不可能解决数据存储中的所有问题，还应有一套意外事件的处理方法，它们共同实现数据的散列存储结构。本书第4章中介绍的哈希表，就是散列存储结构的一个实例。第第2 2章章 线性数据结构线性数据结构 3.数据的运算数据的运算是定义在数据逻辑结构上的操作，每种数据结构都有一个运算的集合。常用的运算有检索、插入、删除、更新、排序等。运算的具体实现要在存储结构上进行。数据的运算是数据结构的一个重要方面。讨论任何一种数据结构时都离不开对该结构上的数据运算及实现算法的

9、讨论。第第2 2章章 线性数据结构线性数据结构 2.1.2算法的描述和评价算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。有时，把运算的实现称之为算法。运算是定义在逻辑结构上的操作，是独立于计算机的，而运算的具体实现则是在计算机上进行的，因此算法要依赖于数据的存储结构。作为算法应具有下述的五个重要特性：(1)有穷性。一个算法必须在执行有穷步后结束，且每一步都能在有限的时间内完成。第第2 2章章 线性数据结构线性数据结构 (2)确定性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的

10、输入只能得到相同的输出。(3)可行性。一个算法必须是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。(4)输入。一个算法应该有零个或多个输入。(5)输出。一个算法应该有一个或多个输出。第第2 2章章 线性数据结构线性数据结构 1.算法的描述算法需要用一种工具来描述，同时，算法可有各种描述方法以满足不同的需求。常用的描述方法有自然语言描述、伪码描述、流程图描述、类PASCAL语言描述、C语言描述等。本书中使用C语言作为描述算法的工具。第第2 2章章 线性数据结构线性数据结构 2.算法的评价在算法是“正确”的前提下，评价算法主要有两个指标：(1)时间复杂度：依据算法编制成

11、程序后，在计算机上运行时所消耗的时间。(2)空间复杂度：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。第第2 2章章 线性数据结构线性数据结构 要确定实现算法在运行时所花的时间和所占用的存储空间，最直接的方法就是测试，即将依据算法编制的程序在计算机上运行，所得到的结果就是算法运行时所花的时间。这种方法有时也称为事后统计的方法。同一算法在不同档次的计算机上运行所花的时间肯定不同，这取决于计算机系统的速度。另外一种方法就是事前分析估算的方法，这是人们常常采用的一种方法，下面将详细讨论之。第第2 2章章 线性数据结构线性数据结构 (1)时间复杂度。假定知道算法中每一条语句执行一次所花

12、的平均时间，则有：算法运行所花的时间=语句执行一次所花的时间语句执行次数其中语句执行一次所花的平均时间取决于计算机系统中硬件、软件等环境因素，而一个算法中语句的执行次数一般来说是确定的。因此，对于事前分析估算方法，我们讨论的目标集中在确定语句的执行频度上，即把算法的语句执行频度作为衡量一个算法时间复杂度的依据。第第2 2章章 线性数据结构线性数据结构 在实际分析中，关注的是频度的数量级，即按重复执行次数最多的语句确定算法的时间复杂度。引入符号“O”来表示这种数量级，算法的时间复杂度记作：T(n)=O(f(n)它表示随问题规模n的增大，算法执行时间的增长率和函数f(n)的增长率相同，称作算法的渐

13、近时间复杂度，简称时间复杂度。按数量级递增次序排列，常见的几种时间复杂度有：O(1)，O(logn)，O(n)，O(nlogn)，O(n2)，O(n3)，O(2n)，这里，n表示问题的规模。第第2 2章章 线性数据结构线性数据结构 例如，在下列三个程序段中：(1)+x；s=0；(2)for(i=1；i=n；+i)+x；s+=x；(3)for(j=1；j=n；+j)for(k=1；k=n；+k)+x；s+=x；含基本操作“x增1”的语句的频度分别为1，n和n2，则这三个程序段的时间复杂度分别为O(1)，O(n)和O(n2)，它们分别称为常量阶、线性阶和平方阶。第第2 2章章 线性数据结构线性数据

14、结构 需要指出的是，有些算法的基本操作的频度不仅仅依赖于问题的规模，还取决于它所处理的输入数据集的状态。对于这一类算法，一般按每种情况发生的概率求出其数学期望值作为算法的平均时间复杂度，或者按最坏情况下基本操作的执行频度得出算法最坏情况下的时间复杂度，以此作为该算法的时间复杂度。第第2 2章章 线性数据结构线性数据结构 (2)空间复杂度。一个算法的实现所占用的存储空间大致有这样三个方面：其一是指令、常数、变量所占用的存储空间；其二是输入数据所占用的存储空间；其三是算法执行时必需的辅助空间。前两种空间是计算机运行时所必须的。因此，把算法在执行时所需的辅助空间的大小作为分析算法空间复杂度的依据。第

15、第2 2章章 线性数据结构线性数据结构 与算法时间复杂度的表示一致，也用辅助空间大小的数量级来表示算法的空间复杂度，仍然记为：O(x)。常见的几种空间复杂度有：O(1)，O(n)，O(n2)，O(n3)等。事实上，一个问题的算法实现，时间复杂度和空间复杂度往往是相互矛盾的，要降低算法的执行时间就要以使用更多的空间为代价，要节省空间就可能要以增加算法的执行时间作为代价，两者很难兼顾。因此，只能根据具体情况有所侧重。第第2 2章章 线性数据结构线性数据结构 2.2 线线 性性 表表 2.2.1线性表的定义及操作定义2-1线性表(Linear-list)是n(n0)个数据元素的有限序列。记为：(a1

16、，a2,.,an)其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。第第2 2章章 线性数据结构线性数据结构 线性表的结构仅涉及诸元素的线性相对位置，即第i个元素ai处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。第第2 2章章 线性数据结构线性数据结构 若线性表是非空表，则第一个元素a1无前趋，最后一个元素

17、an无后继，其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。下面给出几个线性表的例子：例2-126个大写的英文字母表：(A，B，C，.，Z)例2-2某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出：(200，220，250，300，400，700，1200)第第2 2章章 线性数据结构线性数据结构 例2-3某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名、性别、职称、工龄、政治面貌六个数据项组成。在表2-2中，一个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。

18、第第2 2章章 线性数据结构线性数据结构 表2-2职工政治面貌登记表职工号姓名性别职称工龄政治面貌000100020003张忠王平李林男女男工程师助工助工1222党员团员团员第第2 2章章 线性数据结构线性数据结构 线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线性表的基本操作有以下几种：(1)INITIATE(L)。初始化操作，设定一个空的线性表L。(2)LENGTH(L)。求表长，求出线性表L中数据元素个数。(3)GET(L，i)。取元素函数，若1iLENGTH(L)，则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。第第2 2章章 线性数据结构

19、线性数据结构 (4)PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。(5)NEXT(L，elm)。求后继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。(6)LOCATE(L，x)。定位函数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。(7)INSERT(L，i，x)。插入操作，在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。第第2 2章章 线性数据结构线性数据结构 (8)DELETE(L，i)。删除操作，若1iLENGTH(L)，删除

20、给定线性表L中的第i个数据元素，使得线性表的长度减1。(9)EMPTY(L)。判空表函数，若L为空表，则返回布尔值“true”，否则返回布尔值“false”。对线性表还有一些更为复杂的操作，如将两个线性表合并成一个线性表；把一个线性表拆成两个或两个以上的线性表；重新复制一个线性表；对线性表中的元素按值的大小重新排列等。这些运算都可以通过上述基本运算来实现。第第2 2章章 线性数据结构线性数据结构 2.2.2线性表的顺序存储结构在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。第第2 2章章 线性数据结构线性数据结构 图2-2线性表

21、顺序存储结构示意图第第2 2章章 线性数据结构线性数据结构 线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。设有线性表(a1，a2，.，an)，若一个数据元素只占一个存储单元，则这种分配方式如图2-2所示。若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为：Loc(ai)=Loc(a1)+(I-1)其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。第第2 2章章 线性数据结构线性数据结构 若一个数据元素占l个存储单元，则有Loc(ai)=Loc(a1)+(I-1)*lLoc(ai+1)=Loc(ai)+

22、l可见，线性表中每个元素的存储地址是该元素在表中序号的线性函数。只要确定了线性表的起始地址，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。第第2 2章章 线性数据结构线性数据结构 顺序存储结构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关系。也就是说，在顺序存储结构中，线性表的逻辑关系的存储是隐含的。线性表的顺序存储结构通常称为向量(Vector)。可用字母V来表示，用Vi表示向量V的第i个分量，设向量下界为1，上界为线性表的长度n，则可以用此向量来表示长度为n的线性表。向量的第i个分量Vi是线性表的第i个数据元素ai在计算机内

23、存中的映像。在C语言中，向量即一维数组，所以可用一维数组来描述顺序存储结构。第第2 2章章 线性数据结构线性数据结构#definemaxlen100structsqlisttpintelemmaxlen;intlast;第第2 2章章 线性数据结构线性数据结构 其中，maxlen是大于线性表长度的一个整数，它可以根据实际需要而修改。这里假设线性表的数据元素是整数，当然也可以根据需要取其它类型。数据域elem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，an依次存放在一维数组elem的各个分量elem1，elem2，elemn中。数据域last指示最后一个数据元素在数组中的位

24、置。在这种存储结构中，线性表的某些操作很容易实现。如线性表的长度即为last域的值等。下面着重讨论线性表的插入和删除两种操作。第第2 2章章 线性数据结构线性数据结构 算法2-1线性表的插入算法。已知线性表的当前状态是(a1，a2，ai-1，ai，an)，要在第i个位置插入一个元素x，线性表变为(a1，a2，ai-1，x，ai，an)。其实施步骤为：(1)将第n至第i个元素后移一个存储位置；(2)将x插入到第i个位置；(3)线性表的长度加1。第第2 2章章 线性数据结构线性数据结构#definemaxlen100structsqlisttpintelemmaxlen;intlast;sqlis

25、ttpv;voidinsert(sqlisttpv,inti,intx)intk;if(iv.last+1)第第2 2章章 线性数据结构线性数据结构 printf(插入位置不合适！n);elseif(v.last=maxlen?1)printf(线性表已满！n);elsefor(k=v.last;k=i;k?)v.elemk+1=v.elemk;v.elemi=x;v.last+;第第2 2章章 线性数据结构线性数据结构 算法2-2线性表的删除算法。已知线性表的当前状态是(a1，a2，ai-1，ai，ai+1，an)，若要删除第i个元素ai，则线性表成为(a1，a2，ai-1，ai+1，an)

26、。具体实施步骤为：(1)若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位；(2)将线性表的长度减1。第第2 2章章 线性数据结构线性数据结构#definemaxlen100structsqlisttpintelemmaxlen;intlast;sqlisttpv;voiddelete(sqlisttpv,inti)intk;if(iv.last)第第2 2章章 线性数据结构线性数据结构 printf(删除位置不合适！n);elsefor(k=i+1;knext;while(p!=NULL)&(counternext;counter+;第第2 2章章 线性数据结构线性数据结构

27、 if(p!=NULL)&(counter=i)returnp;elsereturnNULL;第第2 2章章 线性数据结构线性数据结构 2)单链表的插入设有线性表(a1，a2，.，ai-1，ai，.，an)，用带头结点的单链表存储，头指针为head，要求在线性表中第i个元素ai之前插入一个值为x的元素。插入前单链表的逻辑状态如图2-6所示。第第2 2章章 线性数据结构线性数据结构 图2-6带头结点的单链表第第2 2章章 线性数据结构线性数据结构 为插入数据元素x，首先要生成一个数据域为x的新结点s；然后确定插入位置，即找到ai之前的元素ai-1，并使指针p指向之；最后改变链接，将x插在ai-1

28、与ai之间，修改结点p和结点s的指针域。即s-next=p-next；p-next=s。插入结点s后单链表的逻辑状态如图2-7所示。第第2 2章章 线性数据结构线性数据结构 图2-7在单链表中插入结点S第第2 2章章 线性数据结构线性数据结构 算法2-4voidinsert(NODE*head,inti,intx)NODE*p,*s;intj=0;p=head;while(p!=NULL)&(jnext;j+;第第2 2章章 线性数据结构线性数据结构 if(p=NULL)|(ji-1)printf(i值不合法n);elses=(NODE*)malloc(sizeof(NODE);s-data=

29、x;s-next=p-next;p-next=s;第第2 2章章 线性数据结构线性数据结构 3)单链表的删除删除操作和插入操作一样，首先要搜索单链表以找到指定删除结点的前趋结点(假设为p)；然后改变链接，即只要将待删除结点的指针域内容赋予p结点的指针域即可。设有线性表(a1，a2，.，ai-1，ai，ai+1，.，an)，用带头结点的单链表存储，删除前的逻辑状态如图2-8所示。删除元素ai所在的结点之后，单链表的逻辑状态如图2-9所示。第第2 2章章 线性数据结构线性数据结构 图2-8带头结点的单链表第第2 2章章 线性数据结构线性数据结构 图2-9在单链表中删除一个结点第第2 2章章 线性数

30、据结构线性数据结构 算法2-5voiddelete(NODE*head,inti)NODE*p,*s;intj=0;p=head;while(p-next!=NULL)&(jnext;j+;第第2 2章章 线性数据结构线性数据结构 if(p-next=NULL)|(ji-1)printf(i值不合法n);elses=p-next;p-next=s-next;free(s);第第2 2章章 线性数据结构线性数据结构 4)动态建立单链表的算法要对单链表进行操作，首先要掌握怎样建立单链表。链表是一种动态存储结构，所需的存储空间只有在程序执行malloc之后，才可能申请到一个可用结点空间；free(p

31、)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。第第2 2章章 线性数据结构线性数据结构 动态建立线性表的链式存储结构有两种基本方法，分别适用于不同的场合。可根据所建链表结点的顺序要求选择采用一种方法。单链表建立方法一：反向建立链表。思想：若线性表的元素已顺序存放在一维数组AN中，建表方法是从线性表的最后一个元素开始，从后向前依次插入到当前链表的第一个结

32、点之前。第第2 2章章 线性数据结构线性数据结构 算法2-6#defineNm/*m为链表中数据元素的个数*/intAN;NODE*creatlink1()NODE*head,*s;inti;head=(NODE*)malloc(sizeof(NODE);head-next=NULL;for(i=N?1;i=0;i-?)第第2 2章章 线性数据结构线性数据结构 s=(NODE*)malloc(sizeof(NODE);s-data=Ai;s-next=head-next;head-next=s;returnhead;单链表建立方法二：正向建立单链表。第第2 2章章 线性数据结构线性数据结构 思

33、想：依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。第第2 2章章 线性数据结构线性数据结构 算法2-7NODE*creatlink2()NODE*head,*p,*s;intnum;head=(NODE*)malloc(sizeof(NODE);scanf(%d,&num);p=head;while(num!=0)第第2 2章章 线性数据结构线性数据结构 s=(NODE*)malloc(sizeof(NODE);s-data=num;p-next=s;p=s;scanf(%d,&num);p-next=NULL;returnhead;第第2 2章章 线性数据结构线性

34、数据结构 3.线性链表算法示例例2-5求不带头结点的头指针为head的单链表中的结点数目。解：intlength(NODE*head)NODE*p;intj;p=head;j=0;第第2 2章章 线性数据结构线性数据结构 while(p!=NULL)p=p-next;j+;returnj;第第2 2章章 线性数据结构线性数据结构 例2-6设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。第第2 2章章 线性数据结构线性数据结构 解：voiddisA(NODE*A,NODE*B)NODE*

35、r,*p,*q;B=(NODE*)malloc(sizeof(NODE);/*建立单链表B的头结点*/r=B;p=A-next;while(p!=NULL)&(p-next!=NULL)第第2 2章章 线性数据结构线性数据结构 q=p-next;p-next=q-next;r-next=q;r=q;p=p-next;r-next=NULL;p-next=NULL;第第2 2章章 线性数据结构线性数据结构 例2-7已知两个不带头结点的单链表A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。第第2 2章章 线

36、性数据结构线性数据结构 解：voidintersectionset(NODE*A,NODE*B,NODE*C)NODE*r,*p,*q,*s;C=(NODE*)malloc(sizeof(NODE);r=C;p=A;q=B;while(p!=NULL)&(q!=NULL)if(p-datadata)第第2 2章章 线性数据结构线性数据结构 p=p-next;elseif(p-dataq-data)q=q-next;elseif(p-data=q-data)s=(NODE*)malloc(sizeof(NODE);s-data=p-data;第第2 2章章 线性数据结构线性数据结构 r-next

37、=s;r=s;p=p-next;q=q-next;r-next=NULL;第第2 2章章 线性数据结构线性数据结构 2.2.4循环链表和双向链表1.循环链表如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。第第2 2章章 线性数据结构线性数据结构 图2-10循环单链表(a)非空表；(b)空表第第2 2章章 线性数据结构线性数据结构 循环链表一般设表头结点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是P或P-

38、next是否为空，而是它们是否等于头指针。与单链表比较，循环链表有以下特点：(1)在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。(2)循环单链表的空表判定条件是head-next=head。第第2 2章章 线性数据结构线性数据结构 2双向链表前面讨论的链式存储结构中只有一个指示直接后继的指针域，所以从某结点出发只能顺指针往后查找其它结点。若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q-next=p，那么q是p的前趋结点。为克服链表这种单向性的缺点，为

39、有更大的灵活性来操作线性链表，可采用双向链表存储结构。第第2 2章章 线性数据结构线性数据结构 图2-11双向链表结点结构第第2 2章章 线性数据结构线性数据结构 在每个结点上增加一个指向线性表中每个元素的前趋结点的指针域prior，就得到双向链表。其结点的结构如图2-11所示。其中，prior是指向前趋结点的指针域；data是数据域；next是指向后继结点的指针域。和循环单链表类似，也可将双向链表的头结点和尾结点链接起来组成双向循环链表。双向链表的几种不同状态如图2-12，图2-13，图2-14和图2-15所示。第第2 2章章 线性数据结构线性数据结构 图2-12带头结点的空双向链表第第2

40、2章章 线性数据结构线性数据结构 图2-13带头结点的非空双向链表第第2 2章章 线性数据结构线性数据结构 图2-14空的双向循环链表第第2 2章章 线性数据结构线性数据结构 图2-15非空双向循环链表第第2 2章章 线性数据结构线性数据结构 在图2-15中，设p是指向链表中任一结点的指针，则有p-next-prior=p-prior-next=p这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。双向链表的运算如LENGTH(Head)，GET(Head,i)，LOCATE(Head,x)等操作，仅涉及一个方向的指

41、针，操作类似单链表。但插入、删除时要同时修改两个方向的指针。第第2 2章章 线性数据结构线性数据结构 (1)插入。在链表中第i个结点前插入元素x。步骤：首先搜索插入位置，找到第i个结点用指P指示，然后申请新结点并改变链接。插入结点时指针变化状况如图2-16所示。第第2 2章章 线性数据结构线性数据结构 图2-16在双向链表中插入结点第第2 2章章 线性数据结构线性数据结构 插入时相关操作序列为s-prior=p-prior;(p-prior)-next=s;s-next=p;p-prior=s。第第2 2章章 线性数据结构线性数据结构 (2)删除。在链表中删除第i个结点。步骤：首先找到删除位置

42、P，然后改变链接，最后释放被删结点P。删除结点时指针变化状况如图2-17所示。删除时相关操作序列为(p-prior)-next=p-next;(p-next)-prior=p-prior;第第2 2章章 线性数据结构线性数据结构 图2-17在双向链表中删除结点第第2 2章章 线性数据结构线性数据结构 例2-8设计算法：判断带头结点的循环双向链表head按元素值是否对称(所谓对称，就是在线性表中a1=an，a2=an-1，.)。intsymmetry(DNODE*head)DNODE*p,*q;p=head-next;q=head-prior;while(p-data=q-data)if(p=q

43、)|(p-next=q)第第2 2章章 线性数据结构线性数据结构 return1;elsep=p-next;q=q-prior;return0;第第2 2章章 线性数据结构线性数据结构 2.3 栈栈 和和 队队 列列栈(stack)和队列(queue)是经常遇到的两种数据结构，它们都是特殊情况下的线性表。前面介绍的线性表的向量及链表存储，进行插入、删除时是比较麻烦的。向量导致数据元素的大量移动，而链表中则要顺链寻找指定位置。如果能够把插入、删除操作都限制在线性表的端部进行，则运算效率可以大大提高。本节要讨论的就是这种限制存取位置的线性表栈和队列。第第2 2章章 线性数据结构线性数据结构 2.3

44、.1栈1栈的定义栈是限定只能在表的同一端进行插入和删除操作的线性表。其中允许进行插入和删除操作的一端称为栈顶(top)，而表中固定的一端称为栈底(bottom)。栈中元素个数为零时称为空栈。由于栈中元素的插入和删除只能在栈顶进行，所以总是后进栈的元素先出来，即栈具有后进先出(LastInFirstOut，缩写为LIFO)的特性，故栈又称为“后进先出表”(LIFO表)。第第2 2章章 线性数据结构线性数据结构 在日常生活中，有不少类似栈的例子。例如食堂中盘子的叠放，如果限定一次叠放一只，那么每次都是叠放到原来一叠盘子的顶上，这相当于入栈操作；而当取用一只盘子时，也是从这一叠盘子的顶上取用，这相当

45、于出栈操作。栈的五种基本运算：(1)Inistack(S)。初始化栈S为空栈。(2)Empty(S)。判定S是否为空栈。若S是空栈则返回值为真(Ture)，否则返回值为假(False)。第第2 2章章 线性数据结构线性数据结构 图2-18第第2 2章章 线性数据结构线性数据结构 (3)Push(S，x)。进栈操作。在栈S的栈顶插入数据元素x。(4)Pop(S)。出栈操作。若栈S不是空栈，则删除栈顶元素。(5)Gettop(S)。取栈顶元素。它只读取栈顶元素，不改变栈中的内容。例2-9有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列如图2-18所示(

46、假设以I和O表示进栈和出栈操作)。第第2 2章章 线性数据结构线性数据结构 2栈的表示和实现因为栈是线性表的一种特例，所以线性表的存储结构对它都适用。一般称采用顺序存储结构的栈为顺序栈；采用链式存储结构的栈为链栈。1)栈的顺序存储结构顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。空栈的栈顶指针值为-1。设用数组StackMAXSIZE表示栈，则对非空栈，Stack0为最早进入栈的元素，Stacktop为最迟进入栈的元素，即栈顶元素。第第2 2章章 线性数据结构线性数据结构 当top=MAXSIZE-1时意为栈满，此时若有元素入栈则将 产

47、 生“数 组 越 界”的 错 误，称 为 栈 的“上 溢”(overflow)；反之，top=-1意为栈空，若此时再作退栈操作，则发生“下溢”(underflow)。图2-19展示了顺序栈中数据元素和栈顶指针之间的对应关系，设MAXSIZE=m。第第2 2章章 线性数据结构线性数据结构 图2-19栈顶指针和栈中元素之间的关系第第2 2章章 线性数据结构线性数据结构 顺序栈的C语言描述如下：#defineMAXSIZEm/*m为栈中数据元素个数的最大可能值*/intstackMAXSIZE;inttop=-1;通常对栈进行的运算是进栈和出栈，这些运算都比较简单，下面给出进栈和出栈操作的实现算法。

48、第第2 2章章 线性数据结构线性数据结构 算法2-8进栈算法。步骤：step1.判断栈是否已满，若满则输出栈溢出信息，并停止执行；否则，执行step2。step2.栈顶指针top后移。step3.在栈顶指针所指当前位置插入元素x。#defineMAXSIZEm/*m为栈中数据元素个数的最大可能值*/intstackMAXSIZE;/*假设数据元素的类型为整型*/inttop=-1;第第2 2章章 线性数据结构线性数据结构 voidpush(intx)if(top=MAXSIZE-1)printf(栈满溢出n);exit(1);elsetop+;stacktop=x;第第2 2章章 线性数据结构

49、线性数据结构 算法2-9出栈算法。步骤：step1.判断栈是否为空栈，若为空则输出栈下溢信息，并停止执行；否则，执行step2。step2.弹出(删除)栈顶元素。step3.栈顶指针top下移。#defineMAXSIZEm/*m为栈中数据元素个数的最大可能值*/intstackMAXSIZE;第第2 2章章 线性数据结构线性数据结构 inttop;intpop()intx;if(top=-1)printf(栈空溢出n);exit(1);第第2 2章章 线性数据结构线性数据结构 elsex=stacktop;top-;returnx;第第2 2章章 线性数据结构线性数据结构 栈的使用非常广泛，

50、常常会出现在一个程序中需要同时使用多个栈的情形，为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为各个栈实际所用空间很难估计。考虑到在实际进程中，当一个栈发生上溢时，其它栈可能还留有很多空间，所以可设法动态地加以调整，以达到多个栈共享内存时，只要有一个栈未满，其它任何栈的入栈操作均不会发生上溢。现在以两个栈为例，讨论其共享内存时的顺序分配方法。第第2 2章章 线性数据结构线性数据结构 图2-20两个栈共享空间示意图第第2 2章章 线性数据结构线性数据结构 当有两个栈共享大小为m的内存空间时，可以把两个栈的栈底分别设在给定内存空间的两端。然后，各自向中间伸展，仅