《数据结构》全套教学课件

数据结构

全套可编辑PPT课件数据结构与算法项目一全套可编辑PPT课件01数据结构概述算法与算法分析02CONTENTS全套可编辑PPT课件PART1.1数据结构概述全套可编辑PPT课件1.1.1数据结构的概念1.数据2.数据元素3.数据项数据(Data)是信息的载体，是能够输入计算机中并能被计算机识别、存储和加工处理的符号集合。在计算机科学中，数据的含义很广泛，既包括整数和实数等数值类型，也包括声音、文字和图像等非数值类型。数据元素(DataElement)是数据的基本单位，在计算机程序中通常作为一个整体进行处理。数据元素也称为结点或记录。一个数据元素可以由一个或多个数据项组成。通常，能独立、完整地描述问题中的一切实体都是数据元素。数据项(DataItem)是数据的最小单位，是对数据元素属性的描述，也称为域或字段。例如，在图书管理系统中，可以把一本图书的有关信息视为一个数据元素，其由书名、作者、书号、出版时间和出版社等数据项组成。全套可编辑PPT课件1.1.1数据结构的概念4.数据对象5.数据类型6.数据结构数据对象(DataObject)是性质相同的数据元素的集合，是数据的子集。例如，整数数据对象是集合N={0，±1，±2，…};图书数据对象是集合A={“数据结构”，“数据库”，“软件工程”}。数据类型(DataType)是一组性质相同的值的集合和定义在该集合上的一组操作的总称。每个数据项均属于某一确定的数据类型。按“值”的特性不同，数据类型可以分为原子类型和结构类型两类。数据结构(DataStructure)是相互之间存在一定关系的数据元素的集合。数据结构包含三方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。数据的逻辑结构分为线性结构和非线性结构两种。1.线性结构线性结构有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。2.非线性结构非线性结构中，一个结点可能有多个直接前驱或多个直接后继。3.常见的基本逻辑结构集合结构：数据元素的有限集合。数据元素之间只有“属于同一个集合”的关系。1.1.2数据的逻辑结构线性结构：数据元素的有序集合。数据元素之间存在一对一的关系。树形结构：树形层次数据结构，树中的数据元素之间存在一对多的关系。图形结构：图中的数据元素之间是多对多的关系。上述基本逻辑结构如图1-1所示。1.1.2数据的逻辑结构关于数据的存储结构主要有以下4种。1.顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构通常借助于程序语言的数组来描述。2.链式存储结构该结构不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针结点来表示，由此得到的存储表示称为链式存储结构。1.1.3数据的存储结构链式存储结构通常借助于程序语言的指针来描述，如图1-2所示。1.1.3数据的存储结构T

extT

ext3.索引存储结构在建立结点信息的同时，还要建立附加的索引表来标识结点的地址。索引表中的每一项称为索引项，索引项由结点的关键字和该结点的存储地址组成，关键字是能唯一标识一个结点的数据项。4.散列存储结构这种结构的基本思想是，根据结点的关键字直接计算出该结点的存储地址。上述4种存储结构既可以单独使用，也可以组合使用，具体使用可根据实际问题具体分析。PART1.2算法与算法分析4.确定性算法中的每条指令都必须有确切的含义，不能有二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入，只能得到相同的输出。5.可行性一个算法必须是可行的，即算法中描述的操作，可通过已经实现的基本运算执行有限次来实现。2.输出一个算法有一个或多个输出，这些输出是与输入有着一定关系的量。3.有穷性一个算法总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。1.2.1算法及其特性1.输入一个算法有零个或多个输入，这些输入取自某个特定对象的集合。1.2.2算法分析1.算法设计的要求(1)正确性正确性的含义是算法对于一切合法的输入数据都能够得出满足规格说明要求的结果。事实上，要验证算法的正确性是极为困难的，因为通常情况下合法的输入数据量太大，用穷举法逐一验证是不现实的。所谓的算法正确性，就是指算法达到了测试要求。(2)可读性可读性是指开发人员对算法阅读理解的难易程度，可读性高的算法便于开发人员之间的交流，有利于算法的调试与修改。1.2.2算法分析1.算法设计的要求(3)健壮性对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。(4)高效率与低存储量需求效率指的是算法的执行时间，对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求是指算法执行过程中所需的最大存储空间。效率与存储量需求都与问题的规模有关，如求100个人的平均薪资与求1000个人的平均薪资显然不同。对于同样问题规模的多个算法，满足高效率和低存储量需求的算法好。2.影响算法运行时间的因素影响算法运行时间的主要因素有计算机硬件、实现算法的语言、编译生成的目标代码的质量和问题的规模。换言之，主要因素即计算机硬件系统、软件系统和问题的规模。在各种因素都不能确定的情况下，很难比较出算法的执行时间，按照执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将与计算机软硬件相关的因素确定下来，这样，一个特定算法的运行时间就只依赖于问题的规模，即算法的运行时间是问题规模n的函数T(n)。1.2.2算法分析3.算法的时间效率分析执行一个算法所耗费的时间，应该是该算法中每条语句执行时间之和，而每条语句的执行时间是该语句执行次数(也称为频度)与该语句执行一次所需时间的乘积。但当算法转换为程序之后，每条语句执行一次所需的时间取决于机器的指令性能、速度及编译所产生的代码质量，这是很难确定的。假设每条语句执行所需的时间均是单位时间，这样，一个算法的时间耗费就是该算法中所有语句执行频度之和。于是，就可以独立于机器的软件、硬件系统来分析算法的时间耗费。计算算法的时间耗费T(n)需要计算算法中每条语句的执行频度之和。1.2.2算法分析

1.2.2算法分析常用算法时间复杂度的比较如表1-1所示。5.影响算法时间复杂度的因素算法的时间复杂度不仅依赖于问题的规模，还与输入实例的初始状态有关。例如，在数组A[0…n-1]中查找给定值K的算法如下：此算法中语句③的执行频度最高，它不仅与问题规模n有关，还与输入实例中数组A中各元素的取值及K的取值有关。若A中没有与K相等的元素，则语句③的执行频度f(n)=n。若A的最后一个元素等于K，则语句③的执行频度f(n)是常数0。6.最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称为最坏时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。7.算法的空间复杂度空间复杂度是对算法在运行过程中临时占用存储空间的大小，记作S(n)=O(f(n))。其中，n为问题规模。【例1-1】求以下5个算法的时间复杂度。i=i

∗2是基本语句，设执行次数为T(n)，则要满足：2T(n)-1≤n，即T(n)≤log2

n+1。则时间复杂度为O(log2

n)。x=x+1是基本语句，执行次数为1，其语句频度与问题规模n无关，则时间复杂度为O(1)。x=x+1是基本语句，执行次数为n，其语句频度与问题规模呈线性关系，并随着问题规模n的增大而增大，则时间复杂度为O(n)。x=x+1是基本语句，执行次数为n2，则时间复杂度为O(n2)。x=x+1是基本语句，执行次数为n3，则时间复杂度为O(n3)。谢谢观看！数据结构

线性表项目二01线性表的定义及基本操作线性表的顺序存储结构线性表的链式存储结构020304CONTENTS顺序表与链表的比较案例实现——通信录管理0405PART2.1线性表的定义及基本操作2.1.1线性表的定义线性表(LinearList)是由n个性质相同的数据元素构成的有限序列。其中，表中数据元素的个数n定义为线性表的长度，当n=0时，称为空表，此时表中没有任何数据元素。以n>0时的线性表L=(a1

，a2

，…，ai，…，an

)为例，其中ai(1≤i≤n)称为表中的第i个数据元素，下标i表示该元素在线性表中的位置。任意一对相邻的数据元素ai-1和ai(2≤i≤n)均存在线性关系(ai-1，ai)，且ai-1称为ai的直接前驱，ai

称为ai-1的直接后继。线性表的逻辑结构如图2-1所示。(1)存在唯一的数据元素a1

，或称首结点，它没有直接前驱，只有一个直接后继。(2)存在唯一的数据元素an，或称尾结点，它没有直接后继，只有一个直接前驱。(3)除第一个结点(首结点)外，集合中的每个数据元素均只有一个直接前驱。(4)除最后一个结点(尾结点)外，集合中的每个数据元素均只有一个直接后继。2.1.2线性表的基本操作(1)InitList(&L)。初始化线性表L。(2)ListEmpty(L)。判断线性表L是否为空表，如果L为空表，则返回true(1)；否则返回false(0)。(3)ListLength(L)。求线性表L的长度。(4)LocateNode(L，x)。查找线性表L中值为x的结点的位置。(5)GetNode(L，i)。取线性表L中的第i个结点，要求1≤i≤ListLength(L)。(6)InsertList(&L，x，i)。在线性表L中的第i个结点之前插入值为x的新结点。(7)DeleteList(&L，i)。删除线性表L中的第i个结点。在实际运用中，线性表往往还有其他操作，如将两个或两个以上的线性表合并成一个线性表；把一个线性表拆分成两个或两个以上的线性表，并完成多种条件的合并、拆分、复制和排序等运算。这一过程通常可以借助上述基本操作的组合来实现。PART2.2线性表的顺序存储结构2.2.1顺序表的定义顺序表(SequentialList)是线性表的顺序存储表示的简称，指的是用一组地址连续的存储单元依次存储线性表中的元素，即以存储位置的相邻表示相继的两个元素之间的前驱和后继关系(逻辑关系)，并以表中第一个元素的存储位置作为顺序表的起始地址，称为顺序表的基地址。顺序表存储结构如图2-2所示。若每个数据元素需占用c个存储单元，并将第一个存储单元所占的地址作为该数据元素的存储位置，设表的最大长度为MaxSize，顺序表逻辑结构如图2-3所示，则表中任一元素ai的存储地址为：顺序表为相邻的元素ai

和ai+1赋予相邻的存储位置LOC(ai)和LOC(ai+1)，即在线性表中逻辑关系相邻的数据元素在内存中的物理位置也是相邻的。对于这种存储方式，只要确定表头结点的首地址，线性表中任一数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。2.2.2顺序表的基本操作在C语言中，可以使用结构体类型来定义顺序表类型，顺序表的类型定义为：注意：①该方法是在前述方法的基础上，使用结构体将结点和表长封装在一起。②SeqList是新定义的结构体类型标识符，用来定义顺序表，可使用语句“SeqListL；”定义一个顺序表L，这样表长可表示为L.length，顺序表中的各个结点可依次表示为L.data[0]、L.data[1]、...、L.data[L.length-1]。③也可使用语句“SeqList∗L；”定义一个指向顺序表的指针L，为叙述方便就把L称为顺序表，这样，顺序表的表长和结点都可用L表示为L->length和L->data[0]、L->data[1]、…、L->data[L->length-1]。下面将使用结构体来描述顺序表，并通过此方法来定义顺序表。但要注意，这样定义的顺序表L在使用前必须要确定L的指向。有了顺序表的描述方法之后，就可以实现对顺序表的操作。该算法的问题规模是表的长度n，基本语句是for循环中执行元素赋值的语句，因此时间复杂度为O(n)。1.建表操作输入给定的数组元素作为线性表的数据元素，将其输入顺序表中，并将输入的元素个数作为顺序表的长度来建立顺序表。具体算法如右：2.插入操作将值为t的新结点插入到当前表L中第i个结点的位置上，如果插入成功，则返回1；否则返回0。可将顺序表、新结点的值t和插入位置i作为参数。算法步骤：①判断插入位置是否正确，如果不正确，则给出提示，返回0；否则转向②。②判断当前表是否已满，如果已满，则给出提示，返回0；否则转向③。③从最后一个结点开始依次后移，直到第i个结点，转向④。④将t插到第i个结点位置上，并将表长加1，返回1。在C语言中，数组中元素的下标是从0开始的，顺序表插入过程如图2-4所示。具体算法如下：显然程序中结点后移的语句执行的频度最高，而对不同的位置该语句执行的频度也不相同，因此需要求该语句的平均执行频度。设顺序表的表长为n，即L->length=n，当i的值为1、2、…、n+1时，该语句的执行频度分别为n、n-1、…、1、0，所以平均频度为[n(n+1)/2]/(n+1)=n/2，因此，该算法的时间复杂度为T(n)=O(n)。3.删除操作删除当前表L中第i个结点，如果删除成功，则返回1；否则返回0。可将顺序表和待删结点的位置i作为参数。算法步骤：①判断删除位置是否正确，如果不正确，则给出提示，返回0；否则转向②。②判断当前表是否为空，如果为空，则给出提示，返回0；否则转向③。③从第i+1个结点开始依次前移，直到最后一个结点，转向④。④将表长减1，返回1。顺序表删除过程如图2-5所示。具体算法如下：与插入操作的算法分析相同，在顺序表上实现删除操作，等概率情况下，平均要移动表中大约一半的数据元素，最终可得该算法的时间复杂度为T(n)=(n-1)/2=O(n)。4.查找操作查找操作分为按值查找和按位查找。(1)按值查找在顺序表中实现按值查找操作，需要与顺序表中的数据元素按照顺序依次加以比较，若查找成功，则返回对应元素的序号；否则返回0。注意：此处序号非元素下标。具体算法如下：该算法的问题规模是表长n，基本语句为while循环中元素比较的语句。如果顺序表的最后一个元素为要找的t，则需要从第一个元素开始，比较n个元素，这是最坏的情况，时间复杂度为O(n)；如果顺序表的第一个元素就是t，则算法只要比较一次即可，这是最好的情况，时间复杂度为O(1)。等概率情况下，平均要比较n/2个元素，该算法的平均时间复杂度为O(n)。该算法按顺序表从前向后进行查找，也可以修改算法实现从后向前查找。当实际项目中数据量比较大，经常使用的数据在表的后半部分时，则适合采取从后向前查找的算法。(2)按位查找根据顺序表的随机查找的特性，按位查找只需返回相应位置的数据元素即可。具体算法如下：显然，按位查找算法的时间复杂度为O(1)。PART2.3线性表的链式存储结构2.3.1链表的定义1.结点(Node)的组成线性表中的数据元素及元素之间的逻辑关系可由结点来表示。结点由两部分组成：一部分用来存储数据元素信息的数据域；另一部分用来存储元素直接后继存储位置的指针域。结点结构如图2-6所示。2.单链表(LingleLinkedList)用链式存储结构表示的线性表称为链表，即用一组任意(可以连续也可以不连续)的存储单元来存放线性表的结点。把每个结点中只包含一个指针域的链表称为单链表。3.开始结点、尾结点、头结点和头指针在链表中存储第一个数据元素(a1)的结点称为开始结点；存储最后一个数据元素(an)的结点称为尾结点，由于尾结点没有直接后继，所以尾结点指针域的值为NULL，NULL在表示链表的示意图中经常用“∧”来代替；在开始结点之前附加的一个结点称为头结点；指向链表中第一个结点(头结点或开始结点)的指针称为头指针。4.单链表示意图不带头结点的单链表如图2-7(a)所示，带头结点的单链表如图2-7(b)所示。在C语言中，单链表的类型定义为：注意：①LinkList和ListNode∗是不同名字的同一个指针类型，各有特定的用途以示区别。②LinkList用来定义指向单链表的头指针。③ListNode∗用来定义指向某一结点的指针，如有定义“ListNode∗p；”并使p指向某结点，则p指向结点的数据域可表示为p->data，p指向结点的指针域可表示为p->next。2.3.2单链表的基本操作1.建表操作链表的建立有头插法建立链表和尾插法建立链表两种方式。(1)头插法建立链表头插法建立链表是将新生成的结点插入现有链表的首结点之前。不带头结点和带头结点的单链表头插法算法如下：以带头结点的单链表头插法建立链表为例，具体操作过程如图2-8所示。(2)尾插法建立链表尾插法建立链表是将新生成的结点插入现有链表的尾结点之后。不带头结点的单链表和带头结点的单链表的尾插法具体算法如下：以带头结点的单链表尾插法建立链表为例，具体操作过程如图2-9所示。以上四种建表算法中，问题规模都取决于表长n，基本语句为while循环中新结点插入的语句。因此，算法的平均时间复杂度均为O(n)。2.插入操作将值为x的新结点插入到当前链表第i个结点的位置上，如果插入成功，则返回1；否则返回0。可将链表头指针、插入结点的值和插入位置i作为参数。算法思路：从开始结点出发，按顺序查找到第i-1个结点，将待插入结点插入到第i-1个结点的后面。单链表的插入如图2-10所示。具体算法如下：

该算法的问题规模是表长n，基本语句为while循环中用于寻找第i-1个结点的语句，因此算法的平均时间复杂度为O(n)。3.删除操作删除当前单链表的第i个结点，如果删除成功，则返回1；否则返回0。可将链表头指针和删除位置i作为参数。算法思路：从开始结点出发，按顺序查找到第i-1个结点，将第i个结点删除。例如，如果要删除单链表中的数据元素ai，则需要找到指向待删除元素的指针p及指向其直接前驱结点的指针r，再将r的next指针指向p的后继结点，最后释放结点p。单链表的删除如图2-11所示。具体算法如下：

该算法的问题规模是表长n，基本语句为while循环中用于查找值等于x的结点的语句。算法的平均时间复杂度为O(n)。4.查找操作单链表上的查找操作同样包括按值查找和按位查找两种，但与顺序表查找不同的是，单链表的查找并不能实现随机查找，因此只能从表头开始查找，属于顺序查找。(1)按值查找返回当前链表中值等于给定值结点的地址，可将链表头指针和给定值作为参数。算法思路：从开始结点出发，按顺序扫描链表的结点，比较当前结点数据域的值与给定值是否相等，若相等，则移动指针指向的结点就是要找的结点。算法步骤：①定义一个移动指针p指向开始结点，转向②。②判断p指向的结点是否存在，并且当前结点数据域的值与给定值是否不相等，若是，则转向③；否则返回p。③使p指向下一个结点，转向②。具体算法如下：(2)按位查找返回当前链表中第i个结点的地址，可将链表头指针和查找位置i作为参数。算法思路：从开始结点出发，按顺序扫描链表的结点，并将计数器加1，当计数器的值为i时，移动指针指向的结点就是第i个结点。算法步骤：①定义一个移动指针p指向开始结点，设置一个计数器j并置初值为1，转向②。②判断p指向的结点是否存在，并且j是否小于i，若是，则转向③；否则转向④。③使p指向下一个结点，并将计数器加1，转向②。④如果j==i，则返回p；否则返回NULL。具体算法如下：上述两种查找均需从表头结点依次向后比较，因此该算法问题规模均为表长n，时间复杂度均为O(n)。2.3.3循环链表概述将单链表中最后一个结点的指针指向链表中的第一个结点，使整个链表构成一个环形，这种链表称为单循环链表，简称循环链表(CircularLinkedList)。从循环链表中的任意一个结点出发都可以找到表中的其他结点。为了统一处理空表与非空表，通常循环链表也附设一个头结点，如图2-12所示。有时，在循环链表中只设指向尾结点的尾指针rear而不设头指针，这样便于对链表的头结点和尾结点进行操作。循环链表的操作过程与单链表类似，差别在于当需要从头到尾遍历整个链表时，判断是否达到表尾的条件不同。在单链表中找表尾结点要判断某结点链域值是否为“空”；在循环链表中找表尾结点则要判断某结点的链域值是否等于头指针。在循环链表中，从表中任一结点p出发，均可以找到其前驱结点。具体算法如下：显然，该算法的时间复杂度为O(n)。2.3.4双向链表概述在单链表中，从一个已知结点出发，只能访问到该结点及其后继结点，无法找到该结点之前的其他结点。而在循环链表中，虽然从任一结点出发都可访问到表中的所有结点，但访问该结点的直接前驱结点的时间复杂度为O(n)；另外，在单链表中，若已知某结点p的存储位置，则将一新结点s插入p之后比插入p之前更方便，因为使用前插法必须知晓p直接前驱结点的位置。同理，删除p的直接后继结点比删除p本身更方便。1.双向链表(DoublyLinkedList)在单链表的每个结点里再增加一个指向其直接前驱结点的指针域prior，这样形成的链表中有两条方向不同的链，因此称为双向链表。在双向链表中增加一个头结点，得到带头结点的双向链表。带头结点的双向链表能使某些操作变得方便。将双向链表头结点和尾结点连接起来构成的循环链表，称为双向循环链表。双向(循环)链表示意图如图2-13所示。在C语言中，双向链表的类型定义为：2.插入操作(前插)在带头结点的双向链表中，将值为x的新结点s插入结点p之前，设p!=NULL。可将指向结点的指针p和插入结点的值x作为参数。在结点p之前插入结点s，需要完成以下4个操作，双向链表前插操作如图2-14所示。注意：操作③必须在操作①和操作②之后进行，只要能够保证这一点，4个操作的顺序可以任意，都能实现前插操作。具体算法如下：3.删除操作在带头结点的双向链表中，删除当前结点p，设p!=NULL。可将指向结点的指针p作为参数。关于此处的结点p，有以下两种情况需要考虑。(1)p不是尾结点，即p->next!=NULL此时需要完成以下两个操作，双向链表删除当前结点操作如图2-15所示。(2)p是尾结点，即p->next==NULL此时只需完成操作p->prior->next=NULL或p->prior->next=p->next即可。注意：无论上述哪种情况，完成后均需做一个释放结点p的存储空间的操作，即free(p)。PART2.4顺序表与链表的比较1.基于时间的考虑顺序表可实现元素的随机存取，对表中任意结点都可以在O(1)时间内直接存取；而链表中的结点则需要从头指针起，按顺序扫描结点才能存取。因此，若线性表的操作主要是进行查找操作，很少进行插入和删除操作，则应采用顺序表作为存储结构。对于频繁进行插入和删除操作的线性表,应采用链表作为存储结构。2.基于空间的考虑顺序表的存储空间是静态分配的，在程序执行之前，必须明确规定它的存储规模，即对MaxSize要有合适的设定。因此，当线性表的长度变化较大而难以估计其存储规模时，不宜采用顺序表。链表无须事先估计存储规模，但链表的存储密度较低。存储密度是指结点数据本身所占的存储单元数和整个结点所占的存储单元数之比。显然，存储密度越大，存储空间的利用率就越高。3.基于语言的考虑各种高级语言都提供数组，但不一定提供指针，由于链表是基于指针的，所以链表的使用有时会受到高级语言的限制。PART2.5案例实现——通信录管理2.5.1案例分析现有一份通信录如表2-1所示，在该表中，单个数据元素是联系人所对应的一行信息，包括姓名、性别、手机号码、住宅电话和电子邮箱五个数据项，通信录中的记录按顺序排列。其中，“性别”字段用0和1表示，0表示女性，1表示男性。记录之间是一对一的关系，除第一条记录和最后一条记录外，每条记录都只有一个直接前驱和一个直接后继。因此，系统中的数据元素是线性结构，可以采用顺序表和链表两种方式实现。表2-1通信录2.5.2案例1——基于顺序表的通信录管理在基于顺序表的通信录管理实现过程中，设计了如下操作：(1)输入数组中存放的数据以建立顺序表，并输出检验。本步骤使用了顺序表的建立算法。(2)输入新记录的插入位置和各项值，从而实现新记录的插入，并输出检验。本步骤使用了顺序表的指定位置插入算法。(3)删除查找到的记录。输入要查找的记录的“姓名”，若找到，则删除该记录的信息；否则输出“删除位置非法”。本步骤使用了顺序表的查找算法和删除算法。程序运行结果如图2-16所示。2.5.3案例2——基于链表的通信录管理在基于链表的通信录管理实现过程中，出于对系统灵活性和可操作性的考虑，要求系统运行采用菜单式呈现。针对案例的具体要求，设计以下操作：(1)设计菜单显示效果，可供用户通过选择菜单项执行不同的功能。(2)用单链表存储数据。因为在通信录的使用过程中，新添加的记录使用频率相对较高，所以本步骤采用了不带头结点的单链表头插法建立链表。(3)输入新记录的各项值，在原有链表的首结点之前插入新结点。本步骤采用单链表的头插法建立链表。(4)输入要查找记录的姓名，若找到，则输出该记录的信息；否则输出“该记录不存在”。本步骤采用单链表的查找算法。(5)输入要删除记录的姓名，若找到，则删除该记录；否则提示“没有查到要删除的通讯者”。本步骤采用单链表的删除算法。程序运行后，按照提示进行选择，如选择“1”，然后输入“张婉0166000000016000001zhang_x0002_wan@163.com”和“郑涂1166000000026000002zhengtu@126.com”两条记录，如图2-17(a)所示。之后选择“2”插入新结点“李丽”的相关信息，选择“5”输出链表后如图2-17(b)所示。谢谢观看！数据结构

栈和队列项目三01栈队列案例实现——汉诺塔问题和键盘缓冲区0203CONTENTSPART3.1栈3.1.1栈的定义及基本操作1.栈的定义栈(Stack)是只允许在一端完成插入和删除操作的线性表，向栈中插入元素称为进(入)栈，从栈中删除元素称为退(出)栈。通常允许插入、删除的这一端称为栈顶(StackTop)，由于元素的入栈和出栈，栈顶的位置经常是变动的，因此需要用一个整型量top指示栈顶的位置，通常称top为栈顶指针，另一端称为栈底。当表中没有元素时称为空栈，即top=-1。栈为后进先出(LastInFirstOut，LIFO)的线性表，简称为LIFO表。由于栈的修改是按后进先出的原则进行的，因此每次删除的总是当前栈中“最新”的元素，即最后插入的元素，而最先插入的元素则被放在栈的底部，直到最后才能被删除。如图3-1所示就是栈的基本结构。(4)入栈Push(S，x)。若S非满栈，则将元素x插入栈顶。(6)取栈顶元素GetTop(S，x)。若S非空栈，则将栈顶元素存放到x中，栈的状态不变。(1)置栈空InitStack(S)。构造一个空栈S。(3)判栈满StackFull(S)。若S为满栈，则返回1；否则返回0。(5)出栈Pop(S，x)。若S非空栈，则将栈顶元素存放到x中并返回，变更栈的状态。(2)判栈空StackEmpty(S)。若S为空栈，则返回1；否则返回0。2.栈的基本操作栈可以理解为操作受限的线性表，因此我们可以结合线性表的存储结构来理解栈的存储结构，所以栈的存储结构同样也包括顺序存储和链式存储两种。1.顺序栈的定义栈的顺序存储结构即为顺序栈(SequenceStack)。顺序栈可以进行如下定义：3.1.2顺序栈设S是SeqStack类型的指针变量，则栈顶指针可表示为S->top，栈顶元素可表示为S->stack[S->top]。注意：①条件S->top==StackSize-1表示栈满，条件S->top==-1表示栈空。②当有元素x入栈时，需要先将S->top加1，然后再将元素入栈，即依次完成下列操作：S->top++，S->stack[S->top]=x，可将其合并为一个操作：S->stack[++S->top]=x。③当栈顶元素做出栈操作时，需要先将栈顶元素出栈，即x=S->stack[S->top]，再将栈顶指针减1，即S->top--，可将其合并为一个操作：x=S->stack[S->top--]。栈顶指针与栈中元素的关系如图3-2所示。④当栈满时，做入栈操作所产生的空间溢出现象称为上溢；当栈空时，做出栈操作所产生的溢出现象称为下溢，其中，上溢属于出错状态，应设法避免。2.顺序栈的基本操作(1)栈的初始化(2)判栈空(3)入栈操作(4)出栈操作(5)取栈顶元素3.1.3链栈1.链栈的定义栈的链式存储结构称为链栈(LinkedStack)，其插入和删除操作只允许在表头位置上进行，链表的头指针就是栈顶指针。链栈可以进行如下定义：2.链栈的基本操作(1)栈的初始化(2)判栈空(3)入栈操作(4)出栈操作(5)取栈顶元素注意：由于链栈中的结点是动态分配的，因此可以不考虑上溢，故无须定义StackFull操作。3.1.4顺序栈和链栈的比较1.时间性能因为栈的所有操作都在栈顶进行，所以顺序栈和链栈基本操作的算法都只需要常数阶的时间。2.空间性能顺序栈初始化时需要设定一个固定的长度，当数据元素过多时可能出现上溢现象，数据元素较少时又存在空间浪费现象。链栈只有在内存空间不足时才会出现栈满的问题，但因为每个元素结点都需要指针域，从而产生了结构性开销。因此，栈的使用过程中如果元素个数变化较大，则宜选用链栈；反之则选用顺序栈。3.1.5栈的应用栈的一个重要应用就是在程序设计中实现递归。递归，即子程序(或函数)直接或间接调用自身的算法，可以理解为，递归函数的调用是函数在执行过程中进行多次自我嵌套调用，而栈恰恰是嵌套调用机制的实现基础。递归通常用于解决结构自相似的问题。例如，台阶问题、汉诺塔问题及图的遍历等。它本质上是将一个大问题转换为一个或多个小问题，再将小问题继续分解为更小的问题，直到小问题可以解决为止。因此，递归有两个组成部分：一是递归终止条件；二是递归模式。递归调用的执行步骤为：①记录调用过程结束时的返回地址及前一次调用过程中的数据信息。②无条件转移到被调用过程的入口地址开始执行程序。③传递返回的数据信息。④取出返回地址，且无条件地转移到该地址，即返回到调用过程中去执行程序。【例3-1】递归———阶乘问题的操作。要求：用递归调用编写计算阶乘n!的函数f(n)。设计思路：上述函数中，n=0是终止递归的条件，以3的阶乘为例，递归中栈的变化过程如图3-3所示。(1)开始时，栈为空，如图3-3(a)所示。(2)在栈中保存3乘2!，如图3-3(b)所示。(3)调用2!，在栈中保存2乘1!，如图3-3(c)所示。(4)调用1!，在栈中保存1乘0!，如图3-3(d)所示。(5)调用0!。因为n=0达到了递归终止的条件，0!值为1，所以返回1。1乘1退栈，此时得到1!的值为1，如图3-3(e)所示。(6)2乘1退栈，此时得到2!的值为2，如图3-3(f)所示。(7)3乘2退栈，此时得到3!的值为6。这时栈已空，算法结束。最后结果为6，如图3-3(g)所示。由此分析可知，递归算法因为需要反复入栈、出栈，时间和空间开销比较大，因此执行效率比较低。具体算法如下：程序运行结果如图3-4所示。PART3.2队

列3.2.1队列的定义及基本操作与栈类似，队列也是一种操作受限的线性表，但与栈的限制不同。1.队列的定义队列(Queue)是只允许在一端进行插入，而在另一端进行删除的操作受限的线性表。向队列中插入元素称为入队，从队列中删除元素称为出队。允许删除的一端称为队头(Front)，允许插入的一端称为队尾(Rear)，当队列中没有元素时称为空队列。队列是先进先出(FirstInFirstOut，FIFO)的线性表，简称为FIFO表。队列的修改是依照先进先出的原则进行的，新来的成员总是加入队尾(即不允许插队)，每次离开的成员总是队头上的成员(不允许中途离队)，即当前“最老”的成员离队。例如，设队列Q=(a1，a2

，a3

，…，an

)，其中a1

就是队首元素，an

就是队尾元素，若入队时按照自a1

至an

的顺序进入，则出队时也按照同样的顺序退出，队列的先进先出如图3-5所示。2.队列的基本操作(1)置队空：InitQueue(&Q)。构造一个空队列Q。(2)判队空：QueueEmpty(Q)。若队列Q为空，则返回1；否则返回0。(3)判队满：QueueFull(Q)。若队列Q为满，则返回1；否则返回0。(4)入队：EnQueue(&Q，x)。若队列Q非满，则将元素x插入Q的队尾。(5)出队：DelQueue(&Q，&x)。若队列Q非空，则将Q的队头元素赋值给x中并返回，改变队列的状态。(6)取队头元素：GetHead(Q，&x)。若队列Q非空，则将Q的队头元素赋值给x中并返回，不改变队列的状态。3.2.2顺序队列1.顺序队列的定义队列的顺序存储结构称为顺序队列(SequentialQueue)。顺序队列与顺序表类似，采用一个一维数组存放数据元素。由于队列的队首和队尾位置要随着出队、入队操作不断变化，所以应设置两个指针front和rear分别用来指向当前队首和队尾。顺序队列的类型定义如下：队首指针front和队尾指针rear的初值在队列初始化时置为-1。非空队列中，队首指针始终指向当前队首元素的前一个位置，队尾指针指向当前的队尾元素。当新元素入队时，rear指针先加1，再赋值；当队首元素出队时，front指针也先加1，再取走元素。2.顺序队列的基本操作设有一个顺序队列为q=(a，b，c，d，e)，对应的存储结构如图3-6(a)所示，此时front==-1，rear==4。若元素f、g和h相继入队，如图3-6(b)所示，则此时front==-1，rear==7，rear==QueueMaxSize-1，队列已满。元素a和b出队，如图3-6(c)所示，此时front==1，rear==7。若所有元素都出队，如图3-6(d)所示，则此时front==rear==7，队列变为空队列。从图3-6可以看出，在顺序队列中，当rear==QueueMaxSize-1时，队列满；当front==rear时，队列空。在如图3-6(d)所示的情况下，队列实际已经为空，但如果此时存在元素要入队，由于rear指针已达到数组下界，则将会造成“溢出”。顺序队列中，这种不是由于存储空间不够，而是由于经过多次插入和删除操作引起的溢出，称为“假溢出”。当出现假溢出时，如果把所有的元素向低位移动，使空位从低位区移向高位区，则会浪费时间。因此，可以把队列向量空间的元素位置0至QueueMaxSize-1看成一个首尾相接的环形，当入队的队尾指针等于最大容量，即rear==QueueMaxSize时，rear=0。3.2.3循环队列1.循环队列的定义3.2.2节中提到了避免“假溢出”现象的方法，而循环队列可以理解为向量空间的元素位置首尾相接的顺序队列，在循环队列中，可以通过数学运算中的取余运算实现队列的首尾相连。由图3-7可以看出，循环队列队空和队满的条件都是front==rear，这就使两者难以区分，为了解决这一问题，可采用以下三种方式。(1)设置标志位tag。将tag初始化为0，当入队操作成功时，设置tag=1；当出队操作成功时，设置tag=0，则队满的条件为front==rear&&tag==1，队空的条件为front==rear&&tag==0。(2)设置一个计数器num。将num初始化为0，当入队操作成功时，num加1；当出队操作成功时，num减1，则队满的条件为num==QueueMaxSize，队空的条件为num==0。(3)牺牲一个存储空间。在非空循环队列中，队首指针始终指向当前队首元素的前一个位置，队尾指针指向当前的队尾元素。队列为空时，队首指针和队尾指针相等，即front==rear；队满时，队尾指针加1后等于队首指针，即front==(rear+1)%QueueMaxSize。循环队列队满如图3-8所示。该方式用来区别循环队列的队空和队满状态。2.循环队列的基本操作(1)队列的初始化(2)队列判空(3)入队操作(4)出队操作

(5)取队首元素3.2.4链队列1.链队列的定义队列的链式存储结构称为链队列(LinkedQueue)。链队列是只允许在表头插入和表尾删除的单链表，因此需要设置指向队头的指针front和指向队尾的指针rear。为了使空链队列与非空链队列的处理一致，链队列也要加上头结点，带头结点的链队列如图3-9所示。当链队列为空时，front==rear，其头指针和尾指针均指向头结点。2.链队列的基本操作链队列的类型定义如下：(1)队列的初始化(2)队列判空(3)入队操作(4)出队操作

(5)取队首元素3.2.5循环队列和链队列的比较关于循环队列和链队列之间的差别，可以从其时间性能和空间性能两个角度进行分析。1.时间性能受限于队列的操作，插入操作只能在队尾进行，删除操作只能在队头进行，因此循环队列和链队列基本操作的算法时间复杂度都为O(1)。2.空间性能循环队列虽然可以避免普通顺序队列的“假溢出”现象，但作为顺序存储结构依然存在事先确定队列空间的问题。所以，循环队列存在存储元素个数的限制和空间浪费的问题。链队列在内存拥有空闲空间时没有队列满的问题，但因结构问题，存储密度小于1，故产生了结构性开销。因此，当队列使用过程中元素个数变化较大时，更适合选用链队列；反之，则应选用循环队列。3.2.6队列的应用下面以一个例题来介绍循环队列的操作。【例3-2】循环队列的操作。要求：对于循环队列，将自然数按顺序入队、出队。具体的操作是：当队列未满时，入队、出队，输出出队元素的值；当队满时，执行连续出队操作，输出出队元素的值(应与队列未满时输出的标识不同)，直至队列为空。当队列采用顺序存储结构时，涉及的操作有队列的初始化、判断队列是否为空、入队、判断队列是否为满、出队。设计思路：(1)若将MaxSize定义为20，则预期的输出结果是：1∗2∗3∗4∗5∗6∗7∗8∗9∗10∗11∗12∗13∗14∗15∗16∗17∗18∗19#20#21#22#23#24#25#26#27#28#29#30#31#32#33#34#35#36#37#。(2)当队列未满时，出队元素的值后跟一个星号(∗)，具体是从1到18(队列中元素的值从19到37，共19个元素)；队列满后，执行连续出队操作，出队元素的值后跟一个井号(#)，具体是从19到37。(3)初始化队列，当队列未满时，自然数按顺序入队、出队，并输出出队元素的值，后跟一个星号；当队列满时，连续出队，并输出出队元素的值，后跟井号，直到队列为空。具体算法如下：程序运行结果如图3-10所示。PART3.3案例实现——汉诺塔问题和键盘缓冲区3.3.1案例1———汉诺塔问题汉诺塔圆盘之间的移动过程很复杂、烦琐，但规律性却很强。分析圆盘的移动顺序。若n=1，则将圆盘从a杆直接移动到c杆。若n=2，则将a杆上的n-1(等于1)个圆盘移到b杆上，再将a杆上的一个圆盘移到c杆上，最后将b杆上的n-1(等于1)个圆盘移到c杆上。若n=3，则：(1)将a杆上的n-1(等于2，令其为n′)个圆盘移到b杆上(借助于c杆)，即①将a杆上的n′-1(等于1)个圆盘移到c杆上。②将a杆上的一个圆盘移到b杆上。③将c杆上的n′-1(等于1)个圆盘移到b杆上。(2)将a杆上的一个圆盘移到c杆上。(3)将b杆上的n-1(等于2，令其为n′)个圆盘移到c杆上(借助a杆)，即①将b杆上的n′-1(等于1)个圆盘移到a杆上。②将b杆上的一个圆盘移到c杆上。③将a杆上的n′-1(等于1)个圆盘移到c杆上。至此，完成了三个圆盘的移动过程。分析该移动过程可知，可以使用递归调用来解决这个移动过程。当n≥2时，移动的过程可分解为三个步骤：①以c杆为临时杆，从a杆将1至n-1号盘移至b杆。②将a杆中剩下的第n号盘移至c杆。③以a杆为临时杆，从b杆将1至n-1号盘移至c杆。可以看到，步骤②只需移动一次即可完成；步骤①与③的操作则完全相同，唯一区别在于各杆的作用有所不同。这样，原问题被转换为相同性质的、规模较小的新问题，即Hanoi(n，a，b，c)可转化为Hanoi(n-1，a，c，b)与Hanoi(n-1，b，a，c)。其中，Hanoi中的参数分别表示为需移动的盘数、起始杆、临时杆与终止杆。采用递归算法实现，汉诺塔问题流程如图3-11所示。程序运行结果如图3-12所示。3.3.2案例2———键盘缓冲区为了充分利用缓冲区的空间，往往将缓冲区设计成循环队列的结构，并为其设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中，就将尾指针后移，进入缓冲区的循环队列中；每输出一个字符，就将队头指针前移，将其从缓冲区队列中删除。程序运行后显示“序号HelloWorld!”，此时可以通过键盘输入字符，但屏幕不显示。例如，输入“havefun，”，由键盘输入“，”时，屏幕显示刚才键盘输入的字符；按Enter键时，继续显示“序号HelloWorld!”；在字符后输入“；”时，系统退出。程序运行结果如图3-13所示。谢谢观看！数据结构

串和数组项目四01串数组案例实现——单词检索计数和稀疏矩阵的运算0203CONTENTSPART4.1串串的逻辑结构与线性表十分相似，区别在于串的数据对象约束为字符集。1.串的定义串(String)是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符。所以也可以这样定义串：串是由零个或多个字符组成的有限序列。串一般记作s="a1a2…an"(n≥0)其中，s是串的名称，用双引号("")括起来的字符序列是串的值；双引号本身不是串的值，它们是串的标记，以便将串与标识符(如变量名)加以区别，称为定界符；ai(1≤i≤n)可以是字母、数字或其他字符；串中字符的数目n被称作串的长度(或串长)。当n=0时，串中没有任何字符，串的长度为0，称为空串，用Ø表示。4.1.1串的逻辑结构而空格串是由一个或者多个空格组成的串，串的长度为所含空格的个数。例如：s1

=""s2

="

"s1

中没有字符，是一个空串；s2

中有两个空格字符，故其长度等于2，是一个空格串。串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地又称为该子串的主串。通常称字符在串中的序号为该字符在串中的位置。当一个字符在串中多次出现时，以该字符第一次在串中出现的位置为该字符在串中的位置。子串在主串中的位置则以子串在主串中第一次出现的第一个字符的位置来表示。当且仅当两个串的长度相等且各个对应位置上的字符都相同时，两个串相等。2.串的基本操作(1)StrAssign(&s1，s2)。将串s1赋值为s2。(2)StrLength(s)。返回串的长度。(3)StrConcat(s1，s2，&s)或StrConcat(&sl，s2)。用s返回由串s2和串s1连接而成的新串。(4)SubStr(s，pos，len)。返回串s中从第pos个字符开始长度为len的子串。(5)StrCompare(sl，s2)。比较串s1和串s2的大小。若s1>s2，则返回正整数；若s1=s2，则返回0；若s1<s2，则返回负整数。(6)StrIndex(s，t，pos)。返回串t在串s的第pos个字符之后首次出现的位置，若t不是s的子串，则返回0。(7)StrInsert(&s，pos，t)。在串s的第pos个字符之前插入串t。(8)StrDelete(&s，pos，len)。删除串s中第pos个字符开始长度为len的子串。(9)StrReplace(&s，t，r)。用串r替换串s中出现的所有与串t相等的不重叠子串。(10)StrEqual(s，t)。判断串s与串t是否相等。以上是串的几个基本操作，其中前五个操作是最为基本的，不能用其他的操作来实现，因此通常将这五个基本操作称为最小操作子集。而其他的操作均可在最小操作子集上实现。4.1.2串的存储结构由于串是一种特殊的线性表，其存储结构与线性表的存储结构类似。但由于串是由若干单个字符组成，所以存储时有一些特殊技巧。串的存储方式取决于对串所进行的操作，串在计算机中有三种表示方法。(1)定长顺序存储结构。这种表示方法是将串定义成字符数组，是最简单的处理方法。此时，数组名即为串名，从而可以根据串名直接访问串值。使用这种方法时，串的大小不能更改。(2)堆分配存储结构。这种表示方法的特点是用一组地址连续的存储单元依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。(3)串的链式存储结构。在链式存储结构中，每个结点设定一个字符域char，存放字符；设定一个指针域next，存放所指向的下一个结点的地址。1.串的定长顺序存储结构串的定长顺序存储结构是采用与其逻辑结构相对应的存储结构，将串中的各个字符按顺序依次存放在一组地址连续的存储单元里，逻辑上相邻的字符在内存中也相邻。这是一种静态存储结构，串值的存储分配是在编译时完成的。因此，需要预先定义串的存储空间大小。在串的定长顺序存储结构中，串的类型定义如下：以下给出串的定长顺序存储结构中，串的判断相等、连接和求子串等基本操作的实现。(1)判断相等(2)连接操作(3)求子串串的定长顺序存储结构适用于求串长和求子串等操作。但这种存储结构存在以下两个缺点：一是需要预先定义一个串允许的最大长度，若定义空间过大，则会造成浪费；二是由于限定了串的最大长度，因而会限制串的部分操作，如连接和置换操作等。2.串的堆分配存储结构堆分配存储结构的实现方法是，提供一个足够大的连续存储空间作为串的可利用空间，用来存储各串的串值。每当建立一个新串时，系统就从这个可利用空间中划分出一个大小与新串长度相等的空间给新串，若分配成功，则返回一个指向起始地址的指针。为操作方便，将每个串的长度信息也作为存储结构的一部分。可使用C语言中动态分配函数库中的malloc(

)函数和free(

)函数来管理可利用空间。串的堆分配存储结构可进行如下定义，串的堆分配存储结构示例如图4-1所示。以下是基于该存储结构实现的一些算法。(1)串的赋值(2)串的连接堆分配存储结构的串既有顺序存储结构的特点(简单、便捷)，又因为在实际操作中对串长没有任何限制，足够灵活，所以经常被用于串处理的过程中。3.串的链式存储结构采用链表的方式存储串值，称为串的链式存储结构，简称链串。在链表方式中，每个结点设定一个字符域char，用来存放字符；设定一个指针域next，用来存放所指向的下一个结点的地址。通常将每个结点所存储的字符个数称为结点的大小。如果每个结点的字符域只存放一个字符，虽然串的运算容易进行，运算速度快，但每个字符都要设置一个指针域，则会导致存储空间利用率降低。为了提高存储空间的利用率，设置结点的字符域存放多个字符时，称为大结点结构。这种链表方式虽然起到了提高存储空间利用率的作用，但运算速度比单字符结点的链表方式要慢。如图4-2和图4-3所示为串“TEACHERSTUDENT”的结点大小分别为1和4的链式存储结构。

在链式存储结构中，串的类型定义如下：串值的链式存储结构对串的某些操作(如连接操作等)有一定不便之处，总体上不如另外两种存储结构灵活，其占用存储量大且操作复杂。4.1.3串的模式匹配串的模式匹配又称子串的定位操作，是在主串s中定位子串t的操作。首先，判断主串s中是否存在子串t，如果存在，则模式匹配成功，并输出子串t在主串s中首次出现的位置；如果不存在，则模式匹配失败。串定位操作StrIndex(s，t，pos)的功能就是模式匹配。在串匹配中，一般将主串称为目标串，子串称为模式串。串的模式匹配应用非常广泛。例如，在文本编辑程序中，经常要查找某一特定单词在文本中出现的位置。显然，解决此问题的有效算法能极大提高文本编辑程序的响应性能。朴素模式匹配算法的基本思想是：从目标串s="s0s1s2..sn-1"的第i个字符起与模式串t="t0t1t2…tm-1"进行比较。即从j=0起比较s[i+j]与t[j]，若相等，则在主串s中存在以i为起始位置匹配成功的可能性，继续向后比较，直至与串t中最后一个字符相等为止；否则改从串s中第i个字符的下一个字符起重新开始下一轮的“匹配”，即将串t向右移动一位(i增1，j退回至0)，重新开始新一轮的匹配，直至串t中的每个字符依次和串s中的一个连续的字符序列相等，则称模式匹配成功，此时串t的第1个字符在串s中的位置就是t在s中的位置；否则模式匹配失败。(1)假设s="edcedcedbedde"，t="edcedb"，则模式匹配过程如下：第1趟匹配，从串s的第1个字符“e”与串t的第1个字符“e”开始比较(假设下标从0开始)，判断s[0]和t[0]是否相等，由于两个字符相等，于是继续逐个比较后续字符s[1]和t[1]是否相等……当比较到第6个字符时，s[5]和t[5]对应的字符不相等，第1趟匹配过程结束，第1趟匹配如图4-4所示。第2趟匹配，将串t向右移动一位，从串s的第2个字符“d”开始，重新与串t的第1个字符进行比较，第1次比较时，s和t的对应字符不相等，第2趟匹配过程结束，第2趟匹配如图4-5所示。第3趟匹配，将串t向右移动一位，从串s的第3个字符“c”开始，重新与串t的第1个字符进行比较，第1次比较时，s和t的对应字符不相等，第3趟匹配过程结束，第3趟匹配如图4-6所示。第4趟匹配，继续将串t向右移动一位，从串s的第4个字符“e”开始，重新与串t的第1个字符进行比较，在串s中找到一个连续的字符序列与串t相等，模式匹配成功，第4趟匹配如图4-7所示。(2)假设s="abcabcaabca"，t="abbb"，则模式匹配过程如下：第1趟匹配，从串s的第1个字符“a”与串t的第1个字符“a”开始比较，由于两个字符相等，于是继续逐个比较后续字符，当比较到第3个字符时，s和t的对应字符不相等，第1趟匹配过程结束。第2趟匹配，将串t向右移动一位，从串s的第2个字符“b”开始，重新与串t的第1个字符进行比较，第1次比较时，s和t的对应字符不相等，第2趟匹配过程结束。按照上述两趟比较的方法，在接下来的比较过程中均没有匹配成功，即在s中没有找到与t相等的连续字符序列。最后一趟匹配，从串s的第8个字符“a”开始，重新与串t的第1个字符进行比较，在串s中仍没有找到一个与串t相等的连续字符序列，模式匹配失败。朴素模式匹配算法具体如下：一般情况下，上述算法的实际执行效率与字符t.str[0]在串s中是否频繁出现有密切关系。例如，s是一般的英文文稿，t="hello"，假设s中有5%的字母是“h”，则在上述算法执行过程中，对于95%的情况可以只进行一次对应位的比较就将t向右移一位，时间复杂度下降为O(s.curlen)，这时算法接近最好情况。然而，在有些情况下，该算法效率却很低。例如，当s="aaaaaaaaaaaaaaaaaaaaaaaab"，t="aaaaab"时，由于模式串t的前六个字符均为“a”，而目标串s的前32个字符均为“a”，每次匹配都在模式串的最后一个位置上发生字符不相等，整个过程需要匹配的次数为(s.curlen-t.curlen)次，总比较次数为t.curlen×(s.curlen-t.curlen)。由于通常有t.curlen<<s.curlen，因此最坏情况的时间复杂度为O(s.curlen×t.curlen)。PART4.2数

组4.2.1数组的定义数组是由n(n>0)个相同类型的元素a1

，a2

，…，an

构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。由此可见，数组的定义就是顺序存储结构的线性表。数组具有如下性质：(1)定义数组就是指明数组中包含元素的个数，即指明数组的长度。换句话说，数组具有固定长度。(2)数组中的元素具有相同的数据类型。(3)数组中的每个元素都和唯一的一组下标值相关联，即可以通过一组下标值唯一确定数组中的一个元素。(4)数组是一种随机存储结构，即可随机存取数组中的任意元素，时间复杂度为O(1)。1.一维数组长度为n的一维数组可用元素序列a0，a1，a2

，…，an-2，an-1来描述。数组在内存中占据连续的内存空间，假设a0

在内存中的地址是LOC(a0

)，且每个元素占用c个单元，那么任意元素ai

的地址为：LOC(ai)=LOC(a0

)+i×c(0≤i≤n-1)2.二维数组长度为m×n的二维数组可用以下元素序列来描述：数组Am×n可以看成是由m个(行)元素a0′，a1′，a2′，…，am-2′，am-1′构成的一维数组：或者是由n个(列)元素a0″，a1″，a2″，…，an-2″，an-1″构成的一维数组：二维数组在内存中有两种存放顺序：按行存储和按列存储。所谓按行存储，就是指先存放第0行元素，接着是第1行元素，依此类推；按列存储是指先存放第0列元素，接着是第1列元素，直至最后一列。这两种存放顺序在高级程序设计语言中都适用。假设a0，0在内存中的地址是LOC(a0，0)，且每个元素占用c个单元，那么任意元素ai，j的地址按行存储时为：LOC(ai，j)=LOC(a0，0)+(i×n+j)×c(0≤i≤m-1，0≤j≤n-1)按列存储时为：LOC(ai

，j)=LOC(a0，0)+(j×m+i)×c

(0≤i≤m-1，0≤j≤n-1)

从理论上讲，数组可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入和删除元素的操作，所以使用顺序存储结构较为适宜。数组一般不使用链式存储结构。组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的。因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。对于一维数组，按下标顺序分配即可。对多维数组分配时，要把其元素映象存储在一维存储器中。一般有两种存储方式：一种是以行为主序(先行后列)的顺序存放，即一行分配完了接着分配下一行；另一种是以列为主序(先列后行)的顺序存放，即一列一列地分配。以行为主序的分配规律是：先排最右的下标，从右向左排，最后排最左的下标。以列为主序分配的规律恰好相反：先排最左的下标，从左向右排，最后排最右的下标。4.2.2数组的存储结构与寻址以二维数组为例，设有m×n的二维数组Am×n，两种顺序下的分配结果如图4-8所示。对于任意元素，可以按元素的下标求其地址。以“以行为主序”的分配为例，设数组的基址为LOC(a0，0)，每个数组元素占据c个地址单元，由于数组元素ai，j的前面有i行，每一行的元素个数为n，因此在第i行中它的前面还有j个数组元素。在C语言中，数组中每一维的下界定义为0，那么ai，j的物理地址可用以下公式计算：同理，对于三维数组Am×n×p，即m×n×p数组，其数组元素ai，j，k物理地址的计算公式为：多科学与工程领域中常用的数据结构，利用矩阵的元素进行各种运算是我们感兴趣的问题。在使用高级语言编制程序时，矩阵通常用二维数组来表示。有些情况下，会有一些特殊矩阵，如三角矩阵、对称矩阵、对角矩阵和稀疏矩阵等，此类矩阵阶数很高但相同值或零元素很多。为了节约存储空间，可以对这类矩阵进行压缩存储。压缩存储是指为多个值相同的元素只分配一个存储空间。下面介绍几种特殊矩阵的压缩存储。1.特殊矩阵的压缩存储(1)对称矩阵对称矩阵是指在一个n阶方阵中，有ai，j=aj，i，其中0≤i<n，0≤j<n。对称矩阵关于主对角线对称，为了节省空间，只需存储上三角或下三角部分即可。例如，只存储下三角的值，对角线上方的值通过对称关系映射过去即可。这样，原来需要n2个存储单元，现在只需要n(n+1)/2个存储单元，节省了大约一半的存储空间。4.2.3矩阵的存储压缩

(2)三角矩阵三角矩阵是指n阶矩阵中的下三角(或上三角)的元素都是0或常数的矩阵，可以分为上三角矩阵和下三角矩阵。以下两个矩阵中，c为某个常数，矩阵A1

为下三角矩阵，主对角线以上均为同一个常数；矩阵A2

为上三角矩阵，主对角线以下均为同一个常数。注意：三角矩阵的特点与对称矩阵相似。下三角矩阵除了存储下三角中的元素，还要存储对角线上方的常数。因为该常数值相等，所以只存一个