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

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

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

2、算机发展的初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如文字、表格、图形、图像、声音等也属于数据的范畴。,组成数据的基本单位是数据元素。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串，也可以由若干数据项组成。在这种情况下，通常把数据元素称为记录。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。,什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，

3、它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说，数据结构就是研究数据及数据元素之间关系的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容： 数据的逻辑结构。 数据的存储结构。 数据的运算。,表2-1 学生学籍登记表,1. 数据的逻辑结构 数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为 Data?Structure =(D，R) 其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。 根据数据元素之间关系的不同特性，数据结构又可分为两

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

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

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

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

8、指令的有限序列，其中每一条指令表示一个或多个操作。有时，把运算的实现称之为算法。运算是定义在逻辑结构上的操作，是独立于计算机的，而运算的具体实现则是在计算机上进行的，因此算法要依赖于数据的存储结构。 作为算法应具有下述的五个重要特性： (1) 有穷性。一个算法必须在执行有穷步后结束，且每一步都能在有限的时间内完成。,(2) 确定性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得到相同的输出。 (3) 可行性。一个算法必须是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 (4) 输入。

9、一个算法应该有零个或多个输入。 (5) 输出。一个算法应该有一个或多个输出。,1. 算法的描述 算法需要用一种工具来描述，同时，算法可有各种描述方法以满足不同的需求。常用的描述方法有自然语言描述、伪码描述、流程图描述、类PASCAL语言描述、C语言描述等。本书中使用C语言作为描述算法的工具。,2. 算法的评价 在算法是“正确”的前提下，评价算法主要有两个指标： (1) 时间复杂度：依据算法编制成程序后，在计算机上运行时所消耗的时间。 (2) 空间复杂度：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。,要确定实现算法在运行时所花的时间和所占用的存储空间，最直接的方法就是测试，即将

10、依据算法编制的程序在计算机上运行，所得到的结果就是算法运行时所花的时间。这种方法有时也称为事后统计的方法。同一算法在不同档次的计算机上运行所花的时间肯定不同，这取决于计算机系统的速度。 另外一种方法就是事前分析估算的方法，这是人们常常采用的一种方法，下面将详细讨论之。,(1) 时间复杂度。假定知道算法中每一条语句执行一次所花的平均时间，则有： 算法运行所花的时间 = 语句执行一次所花的时间语句执行次数 其中语句执行一次所花的平均时间取决于计算机系统中硬件、软件等环境因素，而一个算法中语句的执行次数一般来说是确定的。因此，对于事前分析估算方法，我们讨论的目标集中在确定语句的执行频度上，即把算法的

11、语句执行频度作为衡量一个算法时间复杂度的依据。,在实际分析中，关注的是频度的数量级，即按重复执行次数最多的语句确定算法的时间复杂度。引入符号“O”来表示这种数量级，算法的时间复杂度记作： T (n) = O (f ( n ) ) 它表示随问题规模n的增大，算法执行时间的增长率和函数f (n) 的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 按数量级递增次序排列，常见的几种时间复杂度有：O(1)，O(logn)，O(n)，O(nlogn)，O(n2)，O(n3)，O(2n)，这里，n表示问题的规模。,例如，在下列三个程序段中： (1) +x；s = 0； (2) for ( i = 1

12、；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) 空间复

13、杂度。一个算法的实现所占用的存储空间大致有这样三个方面：其一是指令、常数、变量所占用的存储空间；其二是输入数据所占用的存储空间；其三是算法执行时必需的辅助空间。前两种空间是计算机运行时所必须的。因此，把算法在执行时所需的辅助空间的大小作为分析算法空间复杂度的依据。,与算法时间复杂度的表示一致，也用辅助空间大小的数量级来表示算法的空间复杂度，仍然记为：O(x)。常见的几种空间复杂度有：O(1)，O(n)，O(n2)，O(n3)等。 事实上，一个问题的算法实现，时间复杂度和空间复杂度往往是相互矛盾的，要降低算法的执行时间就要以使用更多的空间为代价，要节省空间就可能要以增加算法的执行时间作为代价，两

14、者很难兼顾。因此，只能根据具体情况有所侧重。,2.2 线 性 表,2.2.1 线性表的定义及操作 定义2-1 线性表(Linear-list)是n(n0)个数据元素的有限序列。记为： (a1，a2, ., an) 其中，数据元素个数n称为表的长度，n = 0时，称此线性表为空表。,线性表的结构仅涉及诸元素的线性相对位置，即第i个元素ai处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。 线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在同

15、一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。,若线性表是非空表，则第一个元素a1无前趋，最后一个元素an无后继，其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。 下面给出几个线性表的例子： 例2-1 26个大写的英文字母表：(A，B，C，.，Z) 例2-2 某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出： (200，220，250，300，400，700，1200),例2-3 某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名、性别、职称、工龄、政治面貌六个数据项组成。 在表2-2中，一

16、个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。,表2-2 职工政治面貌登记表,线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线性表的基本操作有以下几种： (1) INITIATE(L)。初始化操作，设定一个空的线性表L。 (2) LENGTH(L)。求表长，求出线性表L中数据元素个数。 (3) GET(L，i)。取元素函数，若1iLENGTH(L)，则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。,(4) PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空

17、元素。 (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。,(8) DELETE(L，i)。删除操作，若1iLENGTH(L)，删除给定线性表L中的第i个数据元素，使得线性表的长度减1。 (9) EMPTY(L)。判空表函数，若L为空表，则返回布尔值“true”，否则返

18、回布尔值“false”。 对线性表还有一些更为复杂的操作，如将两个线性表合并成一个线性表；把一个线性表拆成两个或两个以上的线性表；重新复制一个线性表；对线性表中的元素按值的大小重新排列等。这些运算都可以通过上述基本运算来实现。,2.2.2 线性表的顺序存储结构 在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。,图2-2 线性表顺序存储结构示意图,线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。 设有线性表(a1，a2，.，an)，若一个数据元素只占一个存储单元，则这种分配方式如图2-2所示。

19、 若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为： Loc(ai)= Loc(a1)+(I-1) 其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。,若一个数据元素占l个存储单元，则有 Loc(ai)= Loc(a1)+(I-1)*l Loc(ai+1)= Loc(ai)+ l 可见，线性表中每个元素的存储地址是该元素在表中序号的线性函数。只要确定了线性表的起始地址，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,顺序存储结构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关

20、系。也就是说，在顺序存储结构中，线性表的逻辑关系的存储是隐含的。 线性表的顺序存储结构通常称为向量(Vector)。可用字母V来表示，用Vi表示向量V的第i个分量，设向量下界为1，上界为线性表的长度n，则可以用此向量来表示长度为n的线性表。向量的第i个分量Vi是线性表的第i个数据元素ai在计算机内存中的映像。 在C语言中，向量即一维数组，所以可用一维数组来描述顺序存储结构。,#define maxlen 100 struct sqlisttp int elemmaxlen; int last; ;,其中，maxlen是大于线性表长度的一个整数，它可以根据实际需要而修改。这里假设线性表的数据元素

21、是整数，当然也可以根据需要取其它类型。数据域elem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，an依次存放在一维数组elem的各个分量elem1，elem2，elemn中。数据域last指示最后一个数据元素在数组中的位置。 在这种存储结构中，线性表的某些操作很容易实现。如线性表的长度即为last域的值等。 下面着重讨论线性表的插入和删除两种操作。,算法2-1 线性表的插入算法。 已知线性表的当前状态是(a1，a2，ai-1，ai，an)，要在第i个位置插入一个元素x，线性表变为(a1，a2，ai-1，x，ai，an)。其实施步骤为： (1) 将第n至第i个元素后移一个存

22、储位置； (2) 将x插入到第i个位置； (3) 线性表的长度加1。,#define maxlen 100 struct sqlisttp int elemmaxlen; int last; ; sqlisttp v; void insert(sqlisttp v, int i, int x) int k; if (iv.last+1),printf( 插入位置不合适！n ); else if (v.last=maxlen?1) printf( 线性表已满！n ); else for( k = v.last; k = i; k? ) v.elemk+1 = v.elemk; v.elemi =

23、 x; v.last+; ,算法2-2 线性表的删除算法。 已知线性表的当前状态是(a1，a2，ai-1，ai，ai+1，an)，若要删除第i个元素ai，则线性表成为(a1，a2，ai-1，ai+1，an)。具体实施步骤为： (1) 若i值合法，则将第i+1至第n个位置上的元素依次向前移动一个存储单位； (2) 将线性表的长度减1。,#define maxlen 100 struct sqlisttp int elemmaxlen; int last; ; sqlisttp v; void delete(sqlisttp v, int i) int k; if (iv.last),printf

24、( 删除位置不合适！n ); else for( k = i+1; k = v.last; k+ ) v.elemk-1 = v.elemk; v.last?; ,从上述算法中不难看出，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。假设在第i个元素之前插入一个新元素的概率为1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，则插入操作中元素的平均移动次数为： T =,对于删除操作，假定对长度为n的线性表，在表的任何位置上删除元素的概率是相等的，即等于1/n，则删除操作中元素的平均移动次

25、数为： T = 从以上分析可以看出，在顺序存储的线性表中进行插入或删除操作，平均要移动一半的元素，当线性表的元素很多，且每个元素的数据项较多时，花费在移动元素上的时间会很长。一般情况下，线性表的顺序存储结构适合于表中元素变动较少的线性表。,2.2.3 线性表的链式存储结构 上节介绍的线性表的顺序存储结构，它的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的。因此，可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，这种存储结构有三个缺点：第一，在作插入或删除操作时，需移动大量元素；第二，在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充

26、分利用；第三，表的容量难以扩充。为克服线性表顺序存储结构的缺点，引进了另一种存储结构链式存储结构。,1线性链表 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能正确反映元素的逻辑顺序，就必须在存储每个元素ai的同时，存储其直接后继元素的存储位置。这时，存放数据元素的结点至少包括两个域，一个域存放该元素的数据，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指针域或链域(next)。这种链式分配的存储结构称为链表。数据元素的结点结构如下：,此结构的C语言

27、描述为 struct node int data; struct node *next; ; typedef struct node NODE;,图2-3 线性链表的物理状态示意图,一般情况下，链表中每个结点可以包含若干个数据域和指针域。若每个结点中只有一个指针域，则称此链表为线性链表或单链表，否则被称为多链表。 例2-4 设有线性表由动物名组成：(cat, horse, monkey, elephant, pig, panda)，其物理状态如图2-3所示。 当链表采用图2-3来表示时，逻辑上的顺序不易观察，所以经常把链表用图2-4所示的逻辑状态来表示。,图2-4 线性链表的逻辑状态示意图,在

28、图2-4中，指针域的值用箭头代替了，线性链表结点的相邻关系用箭头来指示，逻辑结构的表示非常形象、清晰。在此单链表中，head是指向单链表中第一个结点的指针，我们称之为头指针；最后一个元素panda所在结点不存在后继，因而其指针域为“空”(用NIL或 表示)。,可以看出，用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，因此，这种存储结构为非顺序映像或链式映像。在使用中，我们只关心数据元素的逻辑次序而不必关心它的真正存储地址。 通常，我们在单链表第一个元素所在的结点之前附设一个结点头结点。头结点的指针域存储第一个元素所在结点

29、的存储位置；数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。若线性表为空表，则头结点的指针域为“空”，如图2-5所示。,图2-5 带头结点的单链表 (a) 非空表；(b) 空表,2线性链表的运算 线性链表是线性表的链式存储表示，所以对线性链表的运算与前面所介绍的对线性表的运算相同，只是相应的算法与顺序存储的线性表有所不同。 设head为单链表的表头指针。下面主要介绍对单链表的查找、插入、删除等常用操作的算法。,对链表操作时，最基本的操作为插入、删除运算。在讨论插入、删除操作之前，首先要解决插入时的新结点从何处取出，删除后的结点又往何处送的问题。在采用链接分配时，总存在一个可利用的

30、内存空间称为可利用空间表，至于可利用空间表是怎样生成的，可以有不同的方法，这里不再介绍。假设可利用空间表总是可以满足存储要求的。这样，每当要调用新结点时就到这个可利用空间表里去取，删除时就把结点归还给这个可利用空间表。,在编程实现时，申请与释放一结点对应于C语言中两个标准函数malloc(sizeof(NODE)和free(p)。malloc 是从可利用空间表中调用一新结点，并返回该结点的地址。free(p)将p指向的结点归还给可利用空间表。为方便起见，以后把指针型变量p所指向的结点称为p结点。,1) 单链表的查找 由于链表存储结构不是一种随机存取结构，要查找单链表中的一个结点，必须从头指针出

31、发，沿结点的指针域逐个往后查找，直到找到要查找的结点为止。 算法2-3 在带头结点的单链表中找出第i个元素所在的结点。,NODE *get(NODE *head, int i) NODE *p; int counter = 1; p = head - next; while ( p!=NULL) , if ( p!= NULL) ,2) 单链表的插入 设有线性表(a1，a2，.，ai-1，ai，.，an)，用带头结点的单链表存储，头指针为head，要求在线性表中第i个元素ai之前插入一个值为x的元素。插入前单链表的逻辑状态如图2-6所示。,图2-6 带头结点的单链表,为插入数据元素x，首先要生

32、成一个数据域为x的新结点s；然后确定插入位置，即找到ai之前的元素ai-1，并使指针p指向之；最后改变链接，将x插在ai-1与ai之间，修改结点p和结点s的指针域。即s-next = p-next；p-next = s。 插入结点s后单链表的逻辑状态如图2-7所示。,图2-7 在单链表中插入结点S,算法2-4 void insert(NODE *head, int i, int x) NODE *p, *s; int j=0; p = head; while ( p!=NULL) ,if (p = NULL) | (j i-1) printf( i值不合法 n); else s = (NODE

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

34、e(NODE *head, int i) NODE *p, *s; int j=0; p = head; while ( p-next != NULL) , if (p-next = NULL) | (j i-1) printf(i值不合法 n); else s = p - next; p - next = s - next; free(s); ,4) 动态建立单链表的算法 要对单链表进行操作，首先要掌握怎样建立单链表。链表是一种动态存储结构，所需的存储空间只有在程序执行malloc之后，才可能申请到一个可用结点空间；free(p)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用

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

36、E *creatlink1( ) NODE *head, *s; int i; head = (NODE *)malloc(sizeof(NODE); head - next = NULL; for(i=N?1; i=0; i-?), s = (NODE *)malloc(sizeof(NODE); s - data = Ai; s - next = head - next; head - next = s; return head; 单链表建立方法二：正向建立单链表。,思想：依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。,算法2-7 NODE *creatlink

37、2( ) NODE *head, *p, *s; int num; head = (NODE *)malloc(sizeof(NODE); scanf(%d, while (num!=0), s = (NODE *)malloc(sizeof(NODE); s - data = num; p - next = s; p = s; scanf(%d, ,3. 线性链表算法示例 例2-5 求不带头结点的头指针为head的单链表中的结点数目。 解： int length(NODE *head) NODE *p; int j; p = head; j = 0;,while ( p != NULL )

38、p = p - next; j+; return j; ,例2-6 设计算法：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序。,解： void disA(NODE *A, NODE *B) NODE *r, *p, *q; B = (NODE *)malloc(sizeof(NODE); /*建立单链表B的头结点*/ r = B; p = A-next; while (p!=NULL) p-next = q-next; r-next = q; r = q; p = p-next; r-next

39、= NULL; p-next = NULL; ,例2-7 已知两个不带头结点的单链表A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。,解： void intersectionset(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) else if (p-data q-data) q = q-next; else if (

40、p-data = q-data) s = (NODE *)malloc(sizeof(NODE); s-data = p-data;,r-next = s; r = s; p = p-next; q = q-next; r-next = NULL; ,2.2.4 循环链表和双向链表 1. 循环链表 如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。,图2-10 循环单链表 (a) 非空表；(b) 空表,循环链表一般设表头结点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。

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

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

43、-15 非空双向循环链表,在图2-15中，设p是指向链表中任一结点的指针，则有 p-next-prior = p-prior-next = p 这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。 双向链表的运算如LENGTH(Head)，GET(Head, i)，LOCATE(Head, x)等操作，仅涉及一个方向的指针，操作类似单链表。但插入、删除时要同时修改两个方向的指针。,(1) 插入。在链表中第i个结点前插入元素x。 步骤：首先搜索插入位置，找到第i个结点用指P指示，然后申请新结点并改变链接。插入结点时指针

44、变化状况如图2-16所示。,图2-16 在双向链表中插入结点,插入时相关操作序列为 s-prior = p-prior; (p-prior)-next = s; s-next = p; p-prior = s。,(2) 删除。在链表中删除第i个结点。 步骤：首先找到删除位置P，然后改变链接，最后释放被删结点P。删除结点时指针变化状况如图2-17所示。 删除时相关操作序列为 (p-prior)-next = p-next; (p-next)-prior = p-prior;,图2-17 在双向链表中删除结点,例2-8 设计算法：判断带头结点的循环双向链表head按元素值是否对称(所谓对称，就是在

45、线性表中a1=an，a2=an-1，.)。 int symmetry(DNODE *head) DNODE *p, *q; p = head-next; q = head-prior; while (p-data = q-data) if (p = q) | (p-next = q),return 1; else p = p-next; q = q-prior; return 0; ,2.3 栈 和 队 列,栈(stack)和队列(queue)是经常遇到的两种数据结构，它们都是特殊情况下的线性表。前面介绍的线性表的向量及链表存储，进行插入、删除时是比较麻烦的。向量导致数据元素的大量移动，而链表

46、中则要顺链寻找指定位置。如果能够把插入、删除操作都限制在线性表的端部进行，则运算效率可以大大提高。本节要讨论的就是这种限制存取位置的线性表栈和队列。,2.3.1 栈 1栈的定义 栈是限定只能在表的同一端进行插入和删除操作的线性表。其中允许进行插入和删除操作的一端称为栈顶(top)，而表中固定的一端称为栈底(bottom)。栈中元素个数为零时称为空栈。 由于栈中元素的插入和删除只能在栈顶进行，所以总是后进栈的元素先出来，即栈具有后进先出(Last In First Out，缩写为LIFO)的特性，故栈又称为“后进先出表”(LIFO表)。,在日常生活中，有不少类似栈的例子。例如食堂中盘子的叠放，如

47、果限定一次叠放一只，那么每次都是叠放到原来一叠盘子的顶上，这相当于入栈操作；而当取用一只盘子时，也是从这一叠盘子的顶上取用，这相当于出栈操作。 栈的五种基本运算： (1) Inistack(S)。初始化栈S为空栈。 (2) Empty(S)。判定S是否为空栈。若S是空栈则返回值为真(Ture)，否则返回值为假(False)。,图 2-18,(3) Push(S，x)。进栈操作。在栈S的栈顶插入数据元素x。 (4) Pop(S)。出栈操作。若栈S不是空栈，则删除栈顶元素。 (5) Gettop(S)。取栈顶元素。它只读取栈顶元素，不改变栈中的内容。 例2-9 有三个元素的进栈序列是1，2，3，举

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

49、将产生“数组越界”的错误，称为栈的“上溢”(overflow)；反之，top= -1意为栈空，若此时再作退栈操作，则发生“下溢”(underflow)。图2-19展示了顺序栈中数据元素和栈顶指针之间的对应关系，设MAXSIZE =m。,图2-19 栈顶指针和栈中元素之间的关系,顺序栈的C语言描述如下： #define MAXSIZE m /* m为栈中数据元素个数的最大可能值*/ int stackMAXSIZE; int top=-1; 通常对栈进行的运算是进栈和出栈，这些运算都比较简单，下面给出进栈和出栈操作的实现算法。,算法2-8 进栈算法。 步骤： step1. 判断栈是否已满，若满则

50、输出栈溢出信息，并停止执行；否则，执行step2。 step2. 栈顶指针top后移。 step3. 在栈顶指针所指当前位置插入元素x。 #define MAXSIZE m /* m为栈中数据元素个数的最大可能值*/ int stackMAXSIZE; /* 假设数据元素的类型为整型*/ int top=-1;,void push(int x) if (top = MAXSIZE-1) printf(栈满溢出 n); exit(1); else top+; stacktop=x; ,算法2-9 出栈算法。 步骤： step1. 判断栈是否为空栈，若为空则输出栈下溢信息，并停止执行；否则，执行

51、step2。 step2. 弹出(删除)栈顶元素。 step3. 栈顶指针top下移。 #define MAXSIZE m /* m为栈中数据元素个数的最大可能值*/ int stackMAXSIZE;,int top; int pop( ) int x; if (top = -1) printf(栈空溢出 n); exit(1); ,else x=stacktop; top-; return x; ,栈的使用非常广泛，常常会出现在一个程序中需要同时使用多个栈的情形，为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为各个栈实际所用空间很难估计。考虑到在实际进程

52、中，当一个栈发生上溢时，其它栈可能还留有很多空间，所以可设法动态地加以调整，以达到多个栈共享内存时，只要有一个栈未满，其它任何栈的入栈操作均不会发生上溢。现在以两个栈为例，讨论其共享内存时的顺序分配方法。,图2-20 两个栈共享空间示意图,当有两个栈共享大小为m的内存空间时，可以把两个栈的栈底分别设在给定内存空间的两端。然后，各自向中间伸展，仅当两个栈顶相遇时才发生溢出。这种分配方式，在每个栈的动态变化过程中，使每个栈可利用的最大空间均有可能超过m/2。这种分配方法如图2-20所示。 2) 栈的链式存储结构链栈 采用顺序存储结构，对于一个栈、两个栈可以清楚自然地表达，但当遇到多个栈共享空间的问

53、题或栈的最大容量事先不能估计时，采用链式存储结构是有效的方法。,图2-21 链栈示意图,类似于单链表，链栈的C语言描述如下： struct snode int data; struct snode *link; ; typedef struct snode SNODE; 栈顶指针仍是top，其类型为SNODE *，相当于单链表的头指针，可惟一确定一个链栈。当top=NULL，表示一个空链栈。链栈的逻辑示意图如图2-21所示。,对于链栈，不会产生单个栈满而其余栈空的情形，只有当整个可用空间都被占满，malloc函数无法实现时才会发生上溢。因此多个链栈共享空间也就是自然的事了。 链栈的出入栈操作类

54、似于单链表，下面给出相应的算法。 算法2-10 进栈操作push(stack,x)。,步骤： step1. 申请一链栈结点，若无可用内存空间，则表示栈满，否则执行step2；step2. 在top所指结点之前插入新结点，并将top指向新申请的结点。 void push(SNODE *top, int x) SNODE *p; p = (SNODE *)malloc(sizeof(SNODE); if (p = NULL), printf( 内存中无可用空间，栈溢出! n); exit(1); else p-data = x; p-link = top; top = p; ,算法2-11 出栈操

55、作pop(stack)。 步骤： step1. 若链栈为空，则输出栈溢出信息；否则执行step2； step2. 删除top所指结点，并使top指向被删结点的后继结点。 void pop(SNODE *top) int x; SNODE *p; if (top = NULL) ,printf(栈空溢出(下溢) n); exit(1); else p = top; top = top-link; x = p-data; free(p); ,2.3.2 队列 队列(Queue)是一种先进先出(FIFO，First In First Out)的线性表。它只允许在表的一端进行插入元素操作，而在另一端进

56、行删除元素操作。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾(rear)，允许删除的一端则称为队头(front)。如图2-22所示。,图2-22 队列的示意图,队列的五种基本运算： (1) Iniqueue(Queue)。初始化队列Queue，即置Queue为空队列。 (2) Empty(Queue)。判定队列Queue是否为空。若Queue是空队列则返回值为真(True)，否则返回值为假(False)。 (3) Addqueue(Queue，x)。入队操作。若队列未满，则在Queue的队尾插入元素x。 (4) Delqueue(Queue)。出队

57、操作。若队列非空，则将Queue的队头元素删除。 (5) Getheadqueue(Queue)。读取队列Queue的队头元素，不改变队列中的内容。,1队列的顺序存储结构 用一组地址连续的空间存放队列中的元素。即用一个能容纳最大容量元素的向量，另外还需要两个指针(front和rear)分别指示队头元素和队尾元素的存储位置。 顺序队列的C语言描述如下： #define MAXSIZE m /* m为队列中数据元素个数的最大可能值*/ int queueMAXSIZE； /* 假设数据元素的类型为整型*/ int front, rear；,约定：队头指针front指向队列中队头元素的前一个位置，队

58、尾指针rear指向队尾元素在队列中的当前位置。若不作上述约定，会出现： 在实现出队列的操作时，第一个元素和其它元素的处理方法不一致，如 front+； 读第一个元素： x = queuefront； front+； 读其它元素：,x = queuefront； front+；, 队列空的判别条件复杂化。 图2-23展示了顺序结构队列中头、尾指针的变化情况。 rear+；/* 修改尾指针*/ queuerear = x；/* x入队列*/ 出队时需修改头指针： front+；,在顺序结构队列中，值得考虑的是队列满(即上溢)的判定条件是什么？假设当前队列处在图2-23中(d)的状态，即MAXSIZ

59、E=6，rear=5，front=3，显然不能作入队列操作，因为rear+1 MAXSIZE-1，出现上溢，但队列中还有空间，我们称这种现象为“假溢出”。,图2-23 顺序队列中头、尾指针变化,解决“假溢出”的办法有两种： (1) 将全部元素向前移动直至队头指针为-1，使队列的第一个元素重新位于queue0。这种方案是比较费时的。 (2) 设想queue0接在queueMAXSIZE-1之后，使一维数组成为一个首尾相接的环，即如果rear+1=maxsize，则令rear=0，这就是循环队列的概念。循环队列如图2-24所示。 在循环队列中，需要解决两类问题，即队头指针及队尾指针的后移和如何判定

60、队列的空与满。,图2-24 循环队列示意图, 队头指针和队尾指针的后移实际上就是如何从队列的第maxsize-1个位置移到第0个位置。这很容易地通过“求模”运算实现。 对于队头指针front： if (front + 1 = maxsize) front = 0 else front = front + 1 或者 front = (front + 1)% maxsize,对于队尾指针rear： if (rear + 1 = maxsize) rear = 0 else rear = rear + 1 或者： rear =(rear + 1)% maxsize, 在循环队列中，习惯上我们采用保留

61、一个空闲位置来区别空和满。 队空时，采用rear=front作为判定条件。 队满时，以队尾指针加1等于队头指针作为判定条件，即front = (rear+1)% maxsize。,当队列满时，队列中实际上只有maxsize-1个元素。假若想利用全部循环队列中的maxsize个存储位置，此时队列满时front=rear与队列空时的关系相同，因而需要另外设一标志tag来区别队列的空和满。初始时front=rear，说明队列空，tag置队列空标志，若随着元素的入队再次满足条件front=rear，说明队列满，tag置队列满标志。 标志所需的时间，通常不采用此法。而前一种方法虽留有一个空额损失了一个空

62、间，但避免了由于判别另设标志造成的时间损失，加快了算法的执行速度。下面是循环队列的出、入队算法。,算法2-12 循环队列的入队列操作Addqueue(Queue，x)。 步骤： step1. 判定循环队列是否已满，若满，则给出队列溢出出错信息； step2. 队尾指针后移，将入队元素放入队尾指针所指的存储位置。 #define MAXSIZE m /* m为队列中数据元素个数的最大可能值*/ int queueMAXSIZE；/* 假设数据元素的类型为整型*/ int front=-1, rear=-1；,void addqueue(int x) if (front = (rear+1)% M

63、AXSIZE) printf(循环队列已满，上溢! n); exit(1); else rear = (rear+1)% MAXSIZE; queuerear = x; ,算法2-13 循环队列的出队列操作Delqueue(Queue)。 步骤： step1. 判定循环队列是否为空，若空，则给出队列溢出(下溢)信息； step2. 队头指针后移一个位置。 #define MAXSIZE m int queueMAXSIZE； int front=-1, rear=-1；,int delqueue( ) int x; if (front = rear), printf(循环队列已空，下溢！ n)

64、; x =-1; else front = (front+1)% MAXSIZE; x = queuefront; return x; ,2. 队列的链式存储结构 利用带头结点的单链表作为队列的链式存储结构。由前所述，一个队列需要两个分别指向队头和队尾的指针才能惟一确定。在链队列里，将队头指针指向单链表的头结点，而将队尾指针指向单链表的最后一个结点。 链队列的C语言描述为：,struct qnode int data; struct qnode *next; ; typedef struct qnode QNODE; QNODE *front, *rear; 链队列的逻辑状态如图2-25所示。,图2-25 链队列示意图,图2-26 链队列,类似于链栈，链队列满的条件是仅当内存中无可利用内存；链队列空的条件是： front = rear 链队列运算指针变化状况如图2-27所示。 算法2-14 链队列