2024新粤教版（2019）《高中信息技术》选择性必修第一册单元教学PPT课件（全册打包）.rar

2.1数据存储的顺序结构与链式结构2.1.1 数据存储的顺序结构数据元素之间有一种常见的逻辑结构线性结构，其数据元素中除第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。就如生活中的一个队伍一样，队伍中的每个人可以看作一个数据元素，除了第一个人和最后一个人之外，其他人都是跟在某一个人之后，且其后面又跟着另外一个人。如某数据结构中，数据元素的集合K和K上二元关系的集合R如下：K a1，a2，ai-1，ai，an-1，an R=，其中，i为整数且1in。我们说ai-1是ai的前驱，ai是ai-1的后继。这种数据元素之间的线性关系指的是逻辑结构上的，而在物理存储上则不一定。2.2数据的顺序存储与组织数据在计算机中能够以顺序结构进行存储。用计算机程序来实现对数据元素的顺序存储与组织，可以使用数组这种数据结构。1一维数组在计算机程序设计中，可以通过数组（Array）这种数据结构来实现对具有相同数据类型且按一定逻辑顺序排列的数据元素的存储与组织，定义了一个数组就是定义了一块可使用的连续存储空间，数组的基本类型就是数据元素的类型，数组的长度就是数组元素的最大个数。在C+语言中，数组的一般定义方式为：类型说明符类型说明符 数组名数组名 数组长度数组长度;其中，“类型说明符”是任一种数据类型，“数组名”是用户定义的数组标识符，“数组长度”必须为常量表达式。例如：int a6;一维数组 int a6a0a1a2a3a4a5123456定义数组为整型，数组名为a，数组长度为6的一个数组。a=1,2,3,4,5,62二维数组数组的下标可以是一个，也可以是多个。当数组有两个下标时，就称为二维数组。二维数组可以看成一维数组的嵌套，即首先把它看作一个一维数组，这个数组的每个元素又是一个一维数组。如一个二维数组b，可看成为某个一维数组共有n个元素，分别是b0，b1，bn-1，其中每个元素bi（0in）又是一个有m个元素的一维数组，分别是bi0，bi1，bim-1。从逻辑结构上，我们也可以把这个二维数组看成一个n行m列的矩阵，并把第一个下标称为行下标，第二个下标称为列下标。int b43;int b4虽然二维数组在逻辑结构上具有行与列两个方向，但它作为一种顺序结构，所有元素在计算机内存空间中的物理存储地址仍是连续的。如在n行m列的二维数组b中，每个数据元素占用d个字节，假设b的第一个数据元素的计算机存储地址为Loc(b00)，那么b的存储结构如图2-5所示。2.2.2 数组的基本操作对于一维数组，通常有遍历（用于数组元素的赋值或查找）、插入元素、删除元素这几种操作。通过对数组的操作，我们可以实现以数组为数据结构的数据的各种管理功能。2.1.2 数据存储的链式结构数据的链式结构与顺序结构不同，它的特点是存储各个数据元素的计算机存储单元的地址不一定是连续的。因此，为了表示每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对于数据元素ai来说，除了存储其本身的信息，还需要存储其后继数据元素的存储位置信息。比如，人们到银行、医院办理业务时，一般都是在叫号系统取号之后就在大厅中静坐等候。此时的人们看似无序，但叫号系统为每个人分配的号码无形中把等候的人们串成了一条链子。当以链式结构存储数据时，一种最简单也最常用的方法是分别用两个域存储数据元素的两部分信息：数据域存储数据元素自身信息，指针域存储后继数据元素的存储位置。链式结构存储学生信息表指针不指向任何一个存储单元，这种指针称为空指针，最后一位同学由于没有后记数据，所以指针域没有指向任何一个存储单元，用符号表示指针域为空指针赋值为null。2.3.1 指针与指针变量采用链式结构存储数据的特点是：每个数据元素除了要存储数据本身的信息外，还需要存储一个指示其后继数据元素的信息（即后继数据元素的存储位置）。在C+语言中，通常使用指针（Pointer）来实现这种存储位置的指示。所谓指针，就是指某个内存单元的地址。在C+语言中，指针也是一种数据类型。与普通数据类型不同的是，定义指针变量（Pointer Variable）没有专门的关键字，而是利用“*”（星号）来进行定义。C+语言中定义指针变量的一般形式为：类型说明符*变量名;/指针变量的定义形式：类型说明符*变量名；int*pi;/定义一个整型指针float*pf;/定义一个浮点型指针string*ps;/定义一个字符串指针struct WareInfo*pware;/定义一个结构类型指针定义一个变量，其实就代表分配计算机内存中的一个存储单元用于存储数据，变量名通常就代表所存储的数据。但是，如果我们在变量名前面使用“&”运算符（取地址运算符），则表示获取变量对应存储空间的地址。例如：int a=42;int*pi=&a;在计算机程序中，我们通过链表（Linked Lists）这种数据结构来实现链式结构的数据存储与组织，链表由一系列结点组成，结点可以动态生成。每个结点包括两个部分：一个是存储数据的数据域，另一个是存储下一个结点物理地址的指针域。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表有多种不同的类型，如单向链表、单向循环链表、双向链表、双向循环链表等，本节我们学习的是单向链表。因为链表是由若干个结点链接而成的，每个结点都具有相同的结构，因此我们定义链表的结构时只需要定义链表结点的结构即可。以下是链表结点的类型定义：typedef 类型声明 类型别名;因为链表就像铁链一样，一环扣一环，只要记住第一环，那整个链表就被记住了。所以，只需要定义一个LinkList类型的变量L（即LinkNode的指针变量），就可以记录和使用整个链表，L就称为链表的头指针，其定义如下：LinkList L=NULL;/定义链表头指针在定义链表头指针L时，可将其初始值设为NULL。这是因为，对于指针变量，如果没有指向任何存储单元，我们通常会把它赋值为NULL，NULL是一个常量值，表示指针不指向任何一个存储单元。这样的指针称为空指针。插入结点删除结点认识数据和数据结构1.1 数据及其价值1数字数字（Number）是一种用来表示数的书写符号。数字在不同的记数系统中表示的形式各不相同，阿拉伯数字是最普遍的一种。（二进制）2数值量是事物在同一种属性上的差别，通常用数字和单位来表示。一个量用数字表示时，这个数字叫作这个量的数值（Numerical Value）。例如，对于“质量”这种属性，一个大苹果质量约150克，一个小苹果质量约100克；对于“长度”这种属性，一张A4纸的两条边长分别为29.7厘米、21厘米3数据数据（Data）是指对现实世界客观事物进行记录并可以鉴别的符号。数据是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的原始素材数据是信息的载体，是计算机程序加工的“原材料”。可用于表示这个苹果“相片中、画中描述的、近似球形的、红色的、香甜的、质量为150克的物品”。当然，数据越详细越准确，对于“苹果”这个事物的表示就越准确。1.下列描述正确的是()。A.“200”和“两百”是相同的数值在不同的记数系统中的写法B.人体的正常体温是37.9C,“37.9C 是数据C.小明的英语考试成绩是90分，“90”是数字D.信息是数据的载体，是有意义的数据1.2 对实际问题的数据抽象计算机越来越多地用于控制、管理及数据处理等非数值计算的工作，这些工作的操作对象及其关系是一些具有一定结构的数据，无法用数学方程进行描述。因此，我们必须对实际问题进行数据抽象，分析待处理对象的特性以及各处理对象之间存在的关系，建立问题的数据模型。1.2 对实际问题的数据抽象2.收集资料，进行分析，探究问题的解。研究表明，对超市经营有影响的各种因素中，人的因素起重要作用。“人”的属性众多，“超市客户”的属性则需要筛选，可以从超市客户管理需要的角度进行筛选。1.2 对实际问题的数据抽象1.2 对实际问题的数据抽象1.2.2 分析数据之间的关系1.2.2 分析数据之间的关系1.2.2 分析数据之间的关系在图1-11中，数据间的联系是多对多的：每个数据既有多个前驱，也有多个后继。这种数据间的多对多联系称为网状关系。例如，学校教育教学活动中涉及的人员之间的关系就是网状关系：一个教师同时教多个学生，一个学生也同时有多个教师授课。综合以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是用诸如表、树、图之类的数据模型进行描述。数据模型是客观事物及其关系的数据描述，是对客观事物进行数据抽象的结果。1.2.3 建立数据模型线性关系是计算机中最常见的数据关系，表是计算机中最常见的数据模型。在本教科书的后续章节中将要学习到的链表、队列、栈、字符串，其数据模型都是表。具有层次关系的数据，其数据模型是树如家族成员树（如图1-10所示）、班级成员树、学校机构树等。具有网状关系的数据，其数据模型是图如城市交通图（如图1-11所示）、学校人员图、（师生）教学图等。数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，-1，2，-2，3，-3，1.3认识数据结构假设超市商品数据是随机排列的查找的方法最简单：从头开始逐个比较，顺序查对，直到找到目标为止。查找操作必须对所有数据进行，所以虽然方法简单却效率低下。假设超市商品数据是有组织的可按照商品所属类别进行分类，同类商品数据放在一起，则商品查找效率将大大提高：先找到商品所属类别，再从该类别下的首个数据开始进行逐个比较查对即可，无须对所有数据进行查找。（1）对于商品数据，除了图中所列组织方式，还有其他方式吗？（2）对应图中数据的不同的组织方式，如果增加新的商品数据，其操作效率如何？删除商品呢？通过以上探究活动可知，当数据组织的方式、数据之间的关系不同时，实现同一功能的数据处理的过程就不同，数据处理的效率也不同。也就是说，在用计算机程序解决问题时，数据之间的关系会影响解决问题的步骤设计和程序执行效率。为了描述和处理越来越复杂的数据关系，人们需要研究数据结构。在计算机世界中，把数据元素以及数据元素之间的关系构成的集合称为数据结构（Data Structure）数据元素之间的关系包括：（1）数据元素之间的逻辑关系，即数据的逻辑结构（Logical Structure）。（2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构（Storage Structure），也称为数据的物理结构。2数据的逻辑结构根据数据元素之间逻辑关系的不同，数据结构有以下四种基本结构，如图1-14所示。（1）集合结构：数据元素除同属于一个集合之外，没有其他关系。（2）线性结构：数据元素之间存在前后有序的一对一的关系。（3）树形结构：数据元素之间存在一对多的关系。（4）图形结构：数据元素之间存在多对多的关系。3数据的存储结构数据结构在计算机存储器中的存储方式称为数据的存储结构，又称物理结构。它包括数据元素的存储和数据元素之间关系的存储。二进制的一位是计算机存储器的最小单位，数据在计算机中的存储形式都是二进制位串。可以把这些位串看成数据元素在计算机中的存储形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储和非顺序存储。因此，可以得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构是把逻辑上相邻的数据元素存储在物理位置也相邻的单元中，这是最基本的存储方法。链式存储结构对逻辑上相邻的元素不要求其在物理位置上也相邻。这种存储结构就像链条一样一环扣一环，存入每一数据元素的同时，也存入其下一元素的存储地址。图1-13（b）中的数据表的顺序存储结构和链式存储结构如图1-15所示。数据的存储结构不同，对数据进行同一操作的实现方法也不同1.在顺序存储结构中：（1）查找到“洗发水”的位置。（2）“洗发水”后的数据逐个后移，空出一个位置。（3）“沐浴露”存放进空出的位置中。2.在链式存储结构中：（1）找到空间存放“沐浴露”数据，记住这个位置的地址。（2）“沐浴露”数据的下一地址指向原“洗发水”的下一地址，即指向“牙刷”数据。（3）查找到数据“洗发水”，并使其下一地址指向“沐浴露”数据。毛巾洗发水牙刷1.3.2 数据类型计算机通过执行程序进行数据处理。对于不同的数据，能执行的操作不尽相同。对于大多数编写程序的人来说，只需要关心数据的取值范围、数据元素间的关系、施加在数据上的操作规则。至于某种操作在计算机中如何实现，对程序员来说并不重要。例如，对于求和操作，程序员注重的仅仅是其“数学上求和”的抽象特性，而不是其在计算机硬件上究竟如何实现。于是，封装了数据操作的数据类型就被引入程序设计语言中。与数据结构相比，数据类型增加了对施加在数据元素上的操作的定义，即对数据的运算规则的定义。常用的运算有检索、插入、删除、更新、排序等，这些运算实质上是在抽象的数据上所施加的一系列的抽象的操作。例如，整型变量之间的除法运算，结果也只能是整数。因此，整型变量的除法运算实际上是整除运算。如果整型变量的取值范围为-3276732767，则两个整型变量的值分别为300和500，做加法运算，结果为800，在整型变量的取值范围内，正确；但是，如果是30 000和30 000做加法，则会发生错误结果60 000超出了整型变量的取值范围，发生溢出错误。不同的程序设计语言和不同的计算机系统对于数据类型的定义和实现可能稍有不同。2数据类型的分类按数据类型“值”的不同特性，高级程序设计语言中的数据类型可分为两类：简单类型和结构类型。简单类型中的每个数据都是不可再分割的整体。例如C+语言中的基本类型（整型、实型、字符型和枚举型）、指针类型和空类型。结构类型是由简单类型按照一定的规则构造的。而且，结构类型内部还可以再包含结构类型。所以，每一种结构类型的值都是可以再分解为若干个简单类型或结构类型的值。1.3.3 数据结构的重要作用用计算机解决此问题，首先要对数据进行组织，设计数据结构。最简单的方法就是将生活中的通信录直接转化存储，构造一张号码表，表中每个数据元素包含两个数据项：姓名和号码。将表中的数据元素顺序存储在计算机中，查找时从头开始依次查对姓名，直到找到目标或找完整张表为止。当数据量大的时候，这种方法就不实用了。要提高查找速度，就要改进数据表的结构和存储方式1.3.3 数据结构的重要作用要提高查找速度，就要改进数据表的结构和存储方式。可通过以下方法改进数据结构的设计：（1）号码表中的数据元素按姓氏排列。（2）设计一张姓氏索引表，采用如图1-19所示的存储结构。程序员通过定义数据结构来描述数据以及数据之间的关系。算法的设计取决于选定的数据结构（逻辑结构），而算法的实现依赖于采用的存储结构。选择什么样的逻辑结构决定了处理数据的步骤和方法，选择何种存储结构则决定了如何编写程序语句。如果数据结构选择不好，除影响程序开发速度之外，更重要的是影响设计出来的程序的运行效率。所以，学好数据结构是学好程序设计的基础。1单选题（1）对数字、数值、数据，以下描述正确的是（）。A.“一个苹果重150克”“150克”是数值B.“观察一幅画获得了美的感受”“美的感受”是数据C.“100读作一百”同一个数在不同记数系统中的写法不同D.“计算机擅长计算”计算机只能处理数值数据（2）关于大数据的描述，下列说法错误的是（）。A.当今社会注重隐私，只要人们不愿意，人们在社会生活中生成的数据就不会被收集B.大数据计算可以给人们的社会活动提供参考C.大数据计算的结果，能够调节、影响人们的活动D.自然界中的事物也能提供数据（3）数据结构在解决问题的过程中有重要作用。下列对数据结构的描述中正确的是（）。A.对同一事物，只能构造出一种数据结构B.选择的数据结构不同，解决问题的步骤也不同C.数据逻辑结构中相邻的数据，其存储位置也一定相邻D.对同一操作如插入、删除等，不同数据存储结构的实现方法相同线性数据的组织和存储线性表（Linear List）是最简单且最常用的一种数据结构，是由若干个具有相同属性的数据元素组成的有限序列。比如，英文字母表（A，B，C，Z）就是一个长度为26的线性表，表中的每一个英文字母为一个数据元素。线性表具有如下的结构特点：1均匀性虽然不同数据表的数据元素可以是各种各样的，但同一线性表的各数据元素必定具有相同的数据类型和长度。2有序性各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个，其他元素前面均只有一个数据元素（直接前趋），后面也只有一个数据元素（直接后继）。对于线性表，常见的基本运算有：（1）置空表setnull(L)，这是一个过程，其结果是将线性表L置为空表。（2）求长度length(L)，这是一个函数，返回值为线性表L的长度。（3）取得表中第i个元素get(L,i)，这是一个函数，当1ilength(L)时，返回第i个数据元素。（4）取直接前趋prior(L,ai)，这是一个函数，当2ilength(L)时，返回ai的直接前趋ai-1。（5）取直接后继next(L,ai)，这是一个函数，当1ilength(L)-1时，返回ai的直接后继ai+1。（6）根据特定值查找线性表locate(L,x)，这是一个函数，若线性表中存在值为x的数据元素ai时，则返回i值，即ai在线性表中的序号；若存在多个值为x的数据元素ai时，则i为其序号最小的值；若不存在值为x的数据元素，则返回值零。（7）插入数据元素insert(L,x,i)，这是一个过程，是将新数据元素x插入到数据元素ai之前，因此当1ilength(L)+1时有意义，运算的结果使长度为n的线性表变为长度为n+1的线性表。（8）删除操作delete(L,i)，这是一个过程，当1ilength(L)时，将线性表L中第i个数据元素删除，使长度为n的线性表变为长度为n-1的线性表。3.2用字符串存储数据3.2.1 字符串及其存储字符串（String）一般简称为串，可以将它看作一种特殊的线性表，它的每个数据元素仅由一个字符组成。与一般线性表相比，字符串有以下特点：（1）字符串的数据元素的类型限定为字符型。（2）字符串操作的对象，多数情况下是字符串整体或其中一部分，当然也可以是单个的数据元素。随着计算机技术的发展，字符串成为非数值计算问题中的主要操作对象，如信息检索、文本编辑、问答系统、音乐分析程序等。1字符串的描述字符串是由零个或有限个字符构成的有序序列。一般记作：s=c0c1c2cn-1(n0)其中：s为串名，用双引号引起来的字符序列称为串值；ci（0in-1）可以是字母、数字或其他字符。下标i表示字符ci在串中的位置。双引号是串值的定界符，不是串的一部分。字符串中字符的个数n称为串的长度。长度为0的字符串称为空串，此时串中没有任何字符。注意：空格在字符串中也算一个字符；长度为1的字符串与单个字符的意义及可执行的操作是不同的。例如，字符串“20180105”，长度为8，其中字符“8”的位置是3。为了支持字符串的处理，在高级语言中引入了串的数据类型。并且，字符串变量与其他变量（如整型、实型等）一样，可以进行各种运算，字符串运算的基本函数和过程也可以同时建立。在C+语言中，字符串被定义为结构数据类型，可以直接用string来定义字符串变量：string s;一个字符串中任意个连续的字符组成的子序列称为该串的子串，包含这个子串的字符串就称为主串。一个子串在主串中的位置是用这个子串的第一个字符在主串中的位置来表示的。例如，s1=20180105，s2=01，则称s2是s1的子串，子串s2在s1中的位置是1。2字符串的存储结构字符串是一种特殊的线性表。因此，字符串的存储结构也有两种：静态的顺序存储结构，动态的链式存储结构或堆存储结构。（1）串的顺序存储结构。串的顺序存储结构与一维数组的类似，用一组地址连续的存储单元存储串值的符序列，如图3-6所示。字符串的字符依次存放在这些存储单元中。因此，串可以用数组表示。此外，存储串的连续的存储单元一般要求先定义好最大长度，这也使得串的操作受限。两个字符串连接的结果，很可能超出这个最大长度。（2）串的动态存储结构用顺序存储结构来存储字符串，因为其规模在定义的时候就已定下，容易造成存储空间的浪费；同时，线性表的插入和删除操作效率很低。因此，有些时候也采用动态存储方式。动态存储方式包括链式存储结构和堆存储结构。3.2.2 字符串的基本操作字符串的基本操作有赋值、连接、求串长、求子串、插入子串、删除子串、查找子串、判断两个串是否相等。目前，字符串在很多程序设计语言中被定义为结构数据类型，有关字符串的操作也被设计成系统函数，可以直接引用。以C+语言为例，通常有以下几种基本操作：（1）字符串赋值：直接赋值s=20180105。（2）字符串连接s1.append(s2)：把字符串s2接在s1的后面，返回连接后的新串。（3）求字符串长度s.length()：返回字符串s中当前所含字符个数。（4）求子串操作s1.substr(pos1,len1)：从字符串s1中复制指定位置pos1开始、指定长度len1的子串。（5）插入操作s1.insert(pos,s2)：将一个子串s2插入到s1的指定位置pos，返回这个新的主串。（6）删除操作s.erase(pos,len)：删除位置pos开始的长度为len的一个子串。3.2.2 字符串的基本操作字符串的基本操作有赋值、连接、求串长、求子串、插入子串、删除子串、查找子串、判断两个串是否相等。目前，字符串在很多程序设计语言中被定义为结构数据类型，有关字符串的操作也被设计成系统函数，可以直接引用。（7）查找子串操作s1.find(s2)：找出主串s1中是否包含子串s2，包含则返回该子串位置，不包含则返回空值。（8）判断两个字符串是否相等pare(s2)：比较s1、s2两个字符串是否相等，相等返回true，否则返回false。字符串相等，是指两个字符串长度相等且对应位置的元素一一相等。例如，字符串s1=693450213，s2=693450213，s3=693550213，其中串s2与s1相等，s3与s1不等。顾客若要求查询编号为“693450213”的商品销量，则需将此字符串与销售记录中的商品编号逐一比较，找到该字符串第一次出现的记录。3.3用队列组织先进先出数据（先进先出）队列（Queue）是一种特殊的线性表，它只允许在表的一端进行插入，在表的另一端进行删除。在队列中，可以插入的一端称为队尾，可以删除的一端称为队头。把一个数据元素插入队列中的操作叫作进队，从队列中删除一个数据元素的操作叫作出队。队列中没有元素时，称为空队列。在日常生活中，售票窗外或服务台前，顾客按到达的先后次序排成一队。排在队头的首先得到服务，然后离队。所有顾客一律平等，严格遵守秩序，不允许插队现象。也就是说，队列中总是排在最前面的对象首先离队。因此，队列符合这个规律：先放入队列中的数据元素首先取出。故队列又被称为先进先出（FIFO：First In First Out）线性表。3.3.2 队列的基本操作3.3.3 队列的实现1顺序队列在队列的程序定义中，可以利用数组这种具有一定容量的顺序存储结构来存储队列元素，并用队头标志front指示即将出队的元素的位置，用队尾标志rear指示即将入队的元素的位置，它们的初始值在队列初始化时均为0。同时我们约定：当入队或出队时，队尾标志rear或队头标志front只能往后移动一位，且其最大值为队列的最大长度maxsize（数组的量），我们把这种队列称为顺序队列。假设已定义队列q，队头front，队尾rear，数组容量为6，其顺序队列存储方式如图3-12所示。基于以上约定，在编程实现队列操作时，队头标志和队尾标志会有几种不同的变化，还可以利用队头标志和队尾标志来求得队列的当前长度：（1）初始化队列：front=rear=0（2）入队操作：rear=rear+1（3）出队操作：front=front+1（4）队空判断：front=rear（5）队满判断：rear=maxsize（6）求队列长度：rear-front2循环队列当我们对顺序队列不断执行入队操作时，队列就有可能出现溢出现象。如已定义顺序队列q，队头front，队尾rear，数组容量为6，当有元素入队时，有下面两种情况：（1）真溢出。当队列中的实际元素个数达到队列最大长度maxsize时，队列满，这时做入队操作将产生空间溢出的现象，如图3-13所示。真溢出是一种出错状态，应设法避免。循环队列为充分利用队列的存储空间，克服“假溢出”现象，可以将数组存储区想象为一个首尾相接的圆环，并称存储在其中的队列为循环队列。同时，为了区别队满和队空，我们约定：当数组中只剩下一个元素为空时，即若队尾标志继续后移一位将与队头标志重叠，就判为队满，此时不能再做入队操作。循环队列为充分利用队列的存储空间，克服“假溢出”现象，可以将数组存储区想象为一个首尾相接的圆环，并称存储在其中的队列为循环队列。同时，为了区别队满和队空，我们约定：当数组中只剩下一个元素为空时，即若队尾标志继续后移一位将与队头标志重叠，就判为队满，此时不能再做入队操作。不难发现，循环队列中的元素被删除后，其原来的空间仍然可以使用，因而循环队列能实现对空间更大限度的利用。3.4用栈组织后进先出数据（后进先出）队列对应了生活中的排队现象，但还有另一种现象，如对一叠碗的取放：每次把洗净的碗放好时总是放在这叠碗的最上面，而每次取用的时候也总是取最上面的。在这种现象中，事物的进出顺序都有共同的特征，那就是后进先出。栈（Stack）是限制只能在一端进行插入和删除的特殊线性表。栈中能进行插入和删除的一端称为栈顶（Top），而另一固定端称为栈底（Bottom）。把一个数据元素放入栈中的操作叫作进栈或压栈（Push），从栈中取出一个数据元素的操作称为出栈或弹出Pop）。栈中没有元素时，称为空栈。3.4.3 顺序栈的实现栈的存储也可采用顺序存储结构的方法来实现，采用顺序存储结构的栈称为顺序栈，是指利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置指针top来动态地指示栈顶元素的当前位置。3.4.2 栈的基本操作栈的常用基本操作有以下几种：（1）初始化栈：构造一个空栈，初始化栈顶标志。（2）元素入栈：若栈非满，栈顶标志上移一位，插入一个元素到栈顶标志指向的位置，该元素成为新的栈顶元素。（3）元素出栈：删除栈顶标志指向的栈顶元素，栈顶标志下移一位，若此时栈非空，则栈顶标志指向的元素成为新的栈顶元素。（4）栈空判断：判断栈是否为空。（5）栈满判断：判断栈是否为满。（6）栈的长度：求栈的元素个数。由于栈是一个动态结构，而数组是一个静态结构，所以在顺序栈的操作过程中会有“溢出”情况的出现。当栈满时，如果再有元素入栈，将会产生“上溢（Overflow）”；当栈空时，如果再执行出栈操作，将会产生“下溢（Underflow）”。为了避免发生栈溢出情况，在进行入栈和出栈操作前应先检测栈是否已满或已空。顺序栈的程序定义如下：其中，maxsize为栈中允许存放元素个数的最大值，top是栈顶标志，指示存放数组的下标，不是真正的指针，当top=-1时表示空栈，当top=maxsize-1时表示满栈。栈来存储数学运算表达式日常生活中，我们所遇见的数学表达式都是类似于a+b-xy这样的中缀表达式。但在计算机中，是如何翻译这个表达式并对其求值呢？例如，x+y*(a-b)-d/e所对应的后缀表达式是xyab-*+de/。计算机运用该方法进行计算的原理在于，从左向右扫描时，当遇到操作数，则将操作数进栈；当遇到操作符时，弹出两个操作数，进行运算后，将新的结果压入栈中。循环如此，直到栈内不含操作符，弹出结果。该算法的特点在于，操作数与操作符使用同一个栈，但是要将算术表达式先转换为后缀表达式。实践：一个是存放操作数的data栈，一个是存放操作符op栈。利用事先定义好的运算符优先级，将操作符压栈或退栈。1.操作符站初始化，将#压入op栈内，从表达式中读取字符ch。2.若ch是操作数，则直接压入data栈内。3.若ch是操作符，则判断instack(op)与outstack(ch)的优先级。汽车轮渡口假设数组q的最大下标为10，恰好是每次载渡的最大量。假设客车的队列是q1，货车的队列为q2。若q1充足，则每取4个q1元素后再取一个q2元素，直到q的长度为10。若q1不充足，则直接用q2补齐。数据结构的应用查找和排序，与我们的学习、生活息息相关。如从字典 中查找汉字，从电话号码本中查找电话，在图书馆中查找图 书，高考查询成绩等；教师按身高来安排学生的座位，大学 按照高考成绩高低顺序录取新生，网上商城按照销量高低排 序来推荐商品等。在信息时代，数据的增长速度越来越快，导致信息量呈几何级的增长。在庞大的数据里进行人工查找和排序是非常困难的，甚至是无法办到的，所以必须依靠计 算机才能快速、准确地对数据进行查找和排序。5.1迭代与递归在利用计算机解决实际问题中，迭代和递归都是非常实用的算法，很多难的问题都是通过迭代或递归算法解出来的。1迭代法迭代法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令（或一定步骤），在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。int n,sum=0;/sum初始化为0 for(int i=1;i=3)算法分析：设f(n)表示第n个月的兔子对数，先看前几个月的情况：第一个月有一对 刚出生的兔子，即f(1)=1；第二个月，这对兔子长成成年兔，兔子对数还是只有1对，即f(2)=1；第三个月，这对成年兔生出一对小兔，共有两对兔子，即f(3)=2；第四个月，成年兔又生出一对小兔，第三个月出生的兔子长成成年兔，共有三对兔子，即f(4)=3；第五个月，原成年兔又生出一对小兔，新成年兔也生出一对小兔，共有五对兔子，即 f(5)=5以此类推，每个月兔子数为1，1，2，3，5，8，13，21，转化为数学模型，设f(n)为第n个月的兔子对数，则有：下面是实现求一年后繁殖的兔子总数的核心代码，其中f1、f2、fn这三个迭代变量分别代表前两个月、前一个月、当前月的兔子数，用迭代关系式“fn=f1+f2;”计算当月的兔子数，再用“f1=f2;f2=fn;”为下一个月的迭代计算做好准备。int f1=1,f2=1,fn=0;/迭代变量 for(int i=3;i=12;i+)/用i的值来控制迭代的次数 fn=f1+f2;/计算当月数量 f1=f2;/f1、f2迭代计算，为下个月迭代赋初值 f2=fn;每个月的兔子对数组成数列：1，1，2，3，5，8，13，21，34，55，89，144，此数列也称为斐波那契数列。5.1.2递归1递归的基本概念若一个对象用自己来定义自己或部分地包含自己，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归过程。在程序设计中，函数直接调用函数本身，称为直接递归调用直接递归调用；在函数中调用其他函数，其他函数又调用原函数，构成了函数自身的间接调用，则称为间接递归调用间接递归调用。2递归在数学中的应用:在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列，即通过初值及与前面临近几项之间的关系来描述。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，二是数列间各项一是最前面几项的数值，二是数列间各项的关系。的关系。这是递归函数的最简单形式，从中可以明显看出递归函数一般的写法特点：先处理一 些特殊情况（递归终结条件），再处理递归关系。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作 为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。3递归算法的思想与应用（1）递归算法的思想。为求解一个不能或不好直接求解的“大问题”，设法将它分解成规模较小但解法相同的“小问题”，并且这些“小问题”也能采用同样的分解方法再分解成规模更小的“小问题”，当规模最小的一个或几个值能直接得出解时，再利用这些“小问题”的解构造出“大问题”的解。（2）递归算法解决问题的特点。递归算法有四个特性：必须有明确的递归终结条件，否则程序将陷入无穷循环而造成栈溢出。子问题在规模上比原问题小，或更接近终止条件。子问题可通过再次递归调用求解或因满足终止条件而直接求解。子问题的解应能组合为整个问题的解。（3）递归算法一般用于解决的三类问题。数据的定义是按递归定义的。如数学上常用的阶乘数列、斐波那契数列、幂函数等，它们的定义都是递归的。问题方便用递归算法实现。有些问题用递归方法实现更方便，如求阶乘函数的值。数据的结构形式是按递归定义的。如链表、树的遍历、图的搜索等。5.2查找在日常生活和学习中，我们经常要进行查找工作，例如从字典中查找汉字、单词，从电话号码本中查找电话，在图书馆中查找图书，高考查询成绩等。其实，“电话号码本”“字典”等都可以看作一张表，查找则是在一个含有众多数据元素（或记录）的表中找出某个特定的数据元素（或记录）。在信息时代，由于信息量巨大，人工查找是非常困难的，甚至是无法办到的，所以必须依靠计算机才能快速、准确地查找信息。5.2.1 顺序查找顺序表是指采用顺序存储的方式存储的集合或线性表。在本章，我们主要探讨一维数 组这种顺序表的顺序查找和二分查找方法。顺序查找也称为线性查找，它的基本思想是：从顺序表的一端开始，将每个元素的关 键字与给定值k进行比较，如果相同，则表明查找成功，返回该元素的下标；如果在所有 元素都进行了比较后，仍找不到关键字为k的元素，则表明查找失败，返回特定值-1。在超市中，要实现查询某商品在哪个货架，我们可以用数组存储商品的编号、存放的 货架等信息。程序运行时，输入需查询商品的编号，然后在数组中依次查找编号，就可查找出该商品的信息，方便顾客查找商品。下面是顺序查找算法的核心代码：5.2.2 二分查找顺序查找虽然能帮助顾客查找到所需信息，但由于超市销售的商品种类繁多，数据量比较大，而顺序查找每次都要从头到尾去查找，需要花费不少时间，很多顾客没有耐心长时间等待查询结果。所以查找的速度必须要快，可以考虑用查找速度更快的二分查找来实现。二分查找又称折半查找，是针对顺序存储的有序表（有序表是指各元素按关键字的值以升序或降序存放的表）进行的查找，它是一种较常用的查找方法。在按升序存储的顺序表a中查找k，其二分查找算法流程如下：（1）选取查找范围a0an-1。（2）选定查找范围的中点元素amid，与k值比较。（3）若相等，则查找成功，返回该元素的下标。（4）若k amid，则将范围缩小到右子表amid+1an-1。（6）迭代以上过程，直到找到k或当前查找区间为空（即查找失败）。对比解决同一个问题，我们可以用不同的算法编写程序，不同的算法对数据结构的要求可 能是不同的。对比顺序查找与二分查找算法，当数据量较大时，二分查找会比顺序查找快 很多，这是它的主要优点，但它要求查找表是有序的，所以在进行二分查找之前，必须先 对查找表进行排序。另外，二分查找要求表是顺序存储顺序存储的，为保持表的有序性，在进行插 入、删除操作时，都必须移动大量记录。因此，二分查找的高查找效率是以排序为代价 的，所以它特别适合一经建立就很少移动而且经常需要查找的线性表。了解不同算法的特点，可以帮助我们在解决实际问题时，从不同的算法中选择出较为 合适的一种，或对现有算法进行改进或创新，从而设计出更好的算法5.3排序排序与我们的日常生活息息相关。例如，教师按身高来安排学生的座位，试卷和答题 卡按从小号到大号的顺序来整理，各类比赛按成绩的高低来排名，查询火车票时会按照出 发的先后来显示，到网上购物会参考销量高低来排序购买等。排序是数据处理和分析中最 常用的运算之一，它往往可以提高数据处理的效率；排序也是最基本的算法之一，其他很 多算法都是以排序算法为基础，所以研究和掌握排序算法是非常重要的。在信息时代，面 对庞大的信息量，想要靠人工进行排序，会耗费大量时间和精力，甚