数据结构与算法 课件全套 机械自考版 第1-8章 绪论、线性表-查找

全国高等教育自学考试指定教材

计算机应用专业（本科段）数据结构与算法第一章绪论学习目标了解数据结构在计算机应用领域中的作用掌握数据结构中的基本概念和术语，了解4类基本的数据结构，理解逻辑结构与物理结构的含义及相互关系，了解数据结构的4种基本存储方法掌握抽象数据类型的表示与描述，能够用抽象数据类型表示实际问题掌握算法的基本概念及重要特性，能够使用类C语言描述算法掌握算法评估和复杂性度量的基本概念，能够对简单算法进行复杂性评估理解算法的基本设计策略的特点，使用基本的算法策略实现简单程序本章主要内容基本概念和术语12算法和算法分析3算法设计策略简介数据结构数据结构与算法是计算机专业的必修课程之一，在课程体系中占据非常重要的地位，起着承上启下的作用，是学习其他计算机专业课程的基础本章将介绍数据结构的基本概念，还将介绍算法及其特性，介绍时间、空间复杂度的概念，在此基础上，介绍对算法进行复杂度评估的基本方法第一节

基本概念和术语需求推动技术的发展，程序设计语言内置的数据类型越来越多样，提供的处理手段也越来越方便快捷当需要方便地处理众多同类型的数据时，出现了数组，“结构”的雏形显现了数组——例如，可以表示多个同类型的数据二元组——例如，可以表示复数记录——例如，可以表示学生信息经典著作数据结构作为独立的一门课程已经有很多年了世界著名的计算机科学家DonaldE.Knuth教授的巨著《计算机程序设计艺术》著名的计算机科学家N.Wirth编写的《算法+数据结构=程序》

基本概念和术语

20世纪80年代以后出现了抽象数据类型概念数据对数据进行操作的定义但不涉及操作的具体实现数据是指所有能输入计算机并被计算机程序处理的符号的集合数据是各种各样的复杂的数据往往由简单的数据构成构成数据的基本单位称为数据元素数据元素还可以细分为数据项

学生信息示例——“线性”的关系某班30名同学的基本信息学号姓名性别出生日期籍贯M2022103001王义平男2004.11.22山东M2022103002陆东男2004.02.05河南M2022103003李晓敏女2005.01.15江苏┇┇┇┇┇M2022103030杨志强男2004.10.30陕西章节目录示例——“上下级”的关系“结构”是什么数据元素之间的相互关系构成结构，带有结构特性的数据元素集合构成数据结构逻辑结构：指数据元素之间的逻辑关系物理结构。指数据结构在计算机中的表示及存储方式数据的逻辑结构从逻辑上描述数据，表明数据元素之间的关系是什么样的，这与数据的存储方式无关，既独立于计算机，也独立于程序设计语言数据的最小不可分割的单位是数据项逻辑上相关的、具有物理意义的若干数据项构成一个数据元素数据元素作为一个完整的对象（整体）是构成数据的基本单位

基本的数据结构基本的数据结构包括4类集合线性结构树结构图结构基本数据结构示意图

集合线性结构树结构图结构常用的存储方法

顺序存储方法链式存储方法索引存储方法散列存储方法例1-3下列关于顺序存储结构与链式存储结构的叙述中，正确的是（A）。A．顺序存储结构的存储空间是连续的，链式存储结构的存储空间不一定连续B．顺序存储结构只用于线性结构，链式存储结构只用于非线性结构C．顺序存储结构一定比链式存储结构节省存储空间D．链式存储结构一定比顺序存储结构节省存储空间抽象数据类型除了程序设计语言中提供的基本类型外，还可以定义抽象意义下的类型，并为该类型定义一组相关的操作。这样定义的数据类型称为抽象数据类型（AbstractDataType，ADT）抽象数据类型的定义包括类型的名字及对各个操作的刻画，也就是要明确“做什么”对于每个操作，要规定操作的名字、操作执行的前提条件、输入和输出分别是什么等等。每个操作通常表示为一个函数或是方法定义抽象数据类型Triangle

第二节

算法和算法分析算法的概念在计算机科学与技术领域几乎无处不在算法的设计与实现往往处于核心地位算法的思想是计算机程序的灵魂算法规定的流程决定着程序的执行步骤算法的基本概念算法（Algorithm）概念的出现与计算机及程序设计无关使用辗转相除法求两个正整数最大公因子的欧几里得（Euclid）算法，早在2300多年前就提出了，这是目前已知的最古老的算法算法定义定义1-1算法是一个由若干确定的（无二义性的）、可执行的步骤组成的肯定能够终止的有序步骤集合算法是描述一个问题的求解过程，它由一系列解决问题的清晰指令构成可以使用自然语言表示可以使用计算机程序设计语言表示可以混合使用自然语言与计算机程序设计语言温度转换将摄氏温标值C转换为华氏温标值F已知计算公式为：F=(9/5)C+32转换的过程可以这样描述输入一个摄氏温标值CC乘以常数9/5（或1.8）前一步的乘积与常数32相加，得到F输出结果F，即转换后的华氏温标值温度转换算法的程序算法特性算法必须满足如下的5个重要特性输入：有0或多个输入值输出：有1或多个输出值有穷性：一个算法必须在执行有穷步骤之后结束确定性：算法的每一个步骤必须是有确切含义的可行性：算法中要做的运算都是相当基本的、能够精确进行的算法的评估和复杂性度量算法必须要正确，所以算法的正确性成为评判算法的首要指标还要评判算法的其他方面，包括它的执行效率时间复杂度空间复杂度时间复杂度

计算机中最重要的资源之一是CPU，显然，花费的时间与处理的数据个数有很大的关系，这个数据个数称为问题规模，也称问题大小。执行算法花费的时间表示为问题规模的一个函数统计一个程序执行期间需要执行的语句总数，并且约定，程序设计语言中一条基本语句的执行时间为1个单位时长时间复杂度一个算法的时间效率可以用问题规模及关键的处理步骤的多少来定义将算法的运行效率表示为问题规模n的一个解析式，对于规模为n的问题，解析式计算的值，应该是算法处理的步骤数将关于n的这个解析式称为增长函数，表示为T(n)对于一个具体的算法，其增长函数是一个近似的表达式查找给定数组中的最大值

当数组中元素个数为10n时，执行的语句个数最多为10n+1，即问题规模扩大10倍，所花费的时间也增大约10倍程序段sum=0; //赋初值for(i=0;i<n;i++) //对每个n for(j=0;j<n;j++) //对每个n sum++; //累加returnsum;主体是一个二重循环，外层循环每执行一次，内层循环都执行n次，所以sum++的总执行次数为n2，语句执行的总数是n2+2，即增长函数T(n)=n2+2当问题规模扩大10倍时，所花的时间需要增加约100倍渐近时间复杂度考查增长函数时，只关心增长函数表达式中的主项，并且不再考虑主项的系数表达式的主项使用记号O来表示例1.4中增长函数表示为O(n)例1.5中增长函数表示为O(n2)这称为渐近时间复杂度，也称为算法的阶定义定义1-2称（复杂度）函数T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)≤cf(n)T1(n)=(n+1)/2=O(n2)T2(n)=3n2+4n+5=O(n3)当然T1(n)=O(n2)，T2(n)=O(n3)也是对的，但一般取最低阶表示T(n)=O(f(n))说明T(n)的阶不大于f(n)的阶定义定义1-3称（复杂度）函数T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常数c>0与n0，当n>n0时有T(n)≥cf(n)T1(n)=(n+1)/2=Ω(n)T2(n)=3n2+4n+5=Ω(n2)当然T1(n)=Ω(1)，T2(n)=Ω(n)，T2(n)=Ω(nlogn)也都是对的，同样地，取它们之中的最高阶T(n)=Ω(f(n))说明T(n)的阶不小于f(n)的阶大O表示法和大Ω表示法使我们能够描述某一算法的上限（如果能找到某一类输入下开销最大的函数）和下限（如果能找到某一类输入下开销最小的函数）当上、下限相等时，可用Θ表示法。如果一种算法既是O(f(n))，又是Ω(f(n))，则称其是Θ(f(n))的若增长函数不随算法问题规模变化，则增长函数称为O(1)阶，或称常数复杂度与问题规模成正比的问题求解算法称为线性操作许多算法具有log2n对数复杂度其他的算法有n的某次幂的多项式复杂度，如O(n2)或O(n3)更坏的算法是指数复杂度，n是指数，如O(2n)一些增长函数的渐近时间复杂增长函数阶时间复杂度T(n)=17O(1)常数T(n)=20n-4O(n)线性T(n)=12nlogn+100nO(nlogn)线性对数T(n)=3n2+5n-2O(n2)多项式（平方）T(n)=2n+18n2+3nO(2n)指数示例

上述程序的时间复杂度是（

）A．O(log2n) B．O(n)C．O(nlog2n) D．O(n2)解：答案是B程序段intx=m;while(x>1){ x=x/2;}其中m>1，则时间复杂度为（

）A．O(logm) B．O(m2)C．O(m1/2)

D．O(m1/3)解：答案是A

若处理器速度增长10倍

算法时间复杂度提升前最大问题规模提升后最大问题规模A1O(n)s110s1A2O(n2)s23.16s2A3O(n3)s32.15s3A4O(2n)s4s4+3.3除了要评判算法的时间复杂度外，算法在运行过程中临时占用的空间大小也要考虑，这称为空间复杂度。一般地，空间复杂度也表示为问题规模的一个函数。考虑空间存储量时，算法代码占用的空间、算法中初始数据占用的存储空间，都不包含在内第三节

算法设计策略简介算法可以分为多种不同的类型，每种类型都有特定的应用场景和解决问题的方法设计算法时，可以配合采用一些设计策略，使得算法的实现更方便设计策略有时也可以称为设计方法，是指在解决特定问题时所采用的一类方法算法分为递推法、迭代法、递归法、贪心法、分治法、动态规划法等递推法递推法是一种直接求解的算法设计策略，利用问题本身所具有的一种递推关系进行求解。找到问题本身的递推关系是问题求解的前提递推法的思想是，根据递推关系，能从已求得的问题规模为1,2,…,i-1的一系列解，构造出问题规模为i的解。求解规模为i的解时，有时可能仅需规模为1,2,…,i-1的系列解中的一部分，而不是全部示例

由递推公式可计算出数列的第三项，为2再由第二项和第三项，得到第四项的值3再由第三项和第四项，得到第五项的值5以此类推得到数列的前10项为：1,1,2,3,5,8,13,21,34,55程序迭代法是一种直接求解的方法，往往需要建立迭代关系式即根据前一个值推出下一个值的公式初始时设定初始值（原值），然后根据迭代关系式和原值，求出新值，并用新值替代原值迭代过程不能无限进行下去或者设定一个迭代次数，当达到这个次数时迭代过程停止或者设定一个结束条件，当满足这个条件时，迭代过程停止程序递归法

贪心法贪心算法也称贪婪算法，这是一种通过每一步选择局部最优解来达到整体最优解的算法，适用于求某些最优解问题求解过程中，一步一步地进行，根据当前的情况选择最优的可能实际上，这个最优是在当前条件下的最优，称为局部最优第四章构造哈夫曼树的过程采用了贪心法策略，第六章求最小生成树的两个算法也采用了贪心法求解分治法当求解一个输入规模为n并且n的取值又很大的问题时，可以把这个大规模的问题分解为若干个规模更小且可以独立求解的问题，然后把各个小问题的解进行合并，得到原问题的解。这就是分治法的思想一般来说，分治法的求解过程分为三个阶段即划分、求解小问题及小问题解的合并第七章介绍的快速排序和归并排序都采用了分治法求解它们是将大问题分解为2个小问题动态规划法动态规划算法是求多阶段决策过程最优化的一种方法，它将问题的整体按时间或空间的特征分成若干个前后衔接的阶段，把多阶段决策问题表示为前后有关的一系列单阶段决策问题，然后逐个求解，从而求出整个问题的最优决策动态规划法强调了时间和空间的连续性求解最大子序列和问题就是采用动态规划法求解的典型示例。给定一个整数数组A，找到一个具有最大和的连续子数组（至少含有一个元素），返回该最大和例如，A={-2,1,-3,4,-1,2,1,-5,4}得到的最大和是6相应的子数组是{4,-1,2,1}，从A[3]到A[6]程序ThankYou!全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第二章线性表学习目标理解线性表的相关概念，了解其逻辑定义及基本操作，理解线性表数据元素之间的逻辑关系掌握线性表的顺序存储方式和链式存储方式，了解各自的特点掌握顺序表及链表基本操作的实现，并能进行复杂度分析掌握静态链表基本操作的实现，并能进行复杂度分析能够设计与线性表相关的数据结构，灵活运用线性表的基本操作，设计算法解决与线性表相关的实际问题本章主要内容线性表的定义和基本操作12线性表的链式存储及实现3线性表的顺序存储及实现进一步讨论两种基本实现方式4单链表的应用5第一节

线性表的定义和基本操作线性表是一种线性结构。在这种结构中，存在着唯一的“第一个”元素、唯一的“第二个”元素，依此类推线性表中各个元素依次排列例1-1中给出的某班30名同学的基本信息（表1-1），就可以组成一个线性表，可以按照学号排列名单

定义定义2-1一个线性表（linearlist）是由同类型数据元素构成的有限序列由n(n≥0)个元素组成的线性表L，可以表示为L=(a0,a1,…,an-1)这里，ai(0≤i≤n-1)即是线性表中的数据元素，也称为表项线性表中所有数据元素都必须是相同类型的数据元素的次序就是它们在表中的排列次序第一个元素是a0，称为表头或开始元素第n个也即最后一个元素是an-1，称为表尾或终端元素元素的个数n称为表长n=0时称为空表，记为()

示例

例2-1将例1-1的学生基本信息表表示为线性表StudentStudent=

((M2022103001王义平男2004.11.22山东),

(M2022103002陆东男2004.02.05河南),…,

(M2022103030杨志强男2004.10.30陕西))

线性表中常使用非负整数表示各元素的位置表头a0的位置为0a1的位置为1ai(0≤i≤n-1)的位置为i对于元素ai(1≤i≤n-1)，元素aj(0≤j<i)称为ai的前驱，其中元素ai-1称为ai的直接前驱对于元素ai(0≤i≤n-2)，元素aj(i<j≤n-1)称为ai的后继，其中元素ai+1称为ai的直接后继

在不引起歧义的情况下，直接前驱可以简称为前驱，直接后继可以简称为后继“线性”的含义和特点除表头a0外，每个元素有且仅有一个直接前驱除表尾an-1外，每个元素有且仅有一个直接后继线性表中各元素的次序是固有的，即元素ai(1≤i≤n-2)排在ai-1之后，且排在元素ai+1之前

如果线性表中各元素的值可以进行比较，并且表中元素的值按位置顺序递增或递减排列，即按值的“大小”有序排列，则线性表称为有序表表中元素的值不满足按位置顺序递增或递减关系的线性表称为无序表

线性表有3个特点，分别是各元素属于同一个类型元素个数是有限的各元素之间不一定有大小关系，但一定有次序关系

例2-2写出10以内（不含10）的非负偶数组成的线性表10以内（不含10）的非负偶数共有5个，可以写出如下的不同形式L1=(0,2,4,6,8) //递增有序表L2=(8,6,4,2,0) //递减有序表L3=(2,6,4,0,8) //无序表线性表的基本操作线性表中有几个基本操作会涉及到位置position

LinearList中定义的函数都有返回值LinearList中定义的操作都有返回值，有些返回值代表操作的执行结果，另外一些仅表示操作是否已正确执行。例如length返回的是线性表的当前长度，即线性表所含元素的个数find返回的是要查找的元素x在表中第一次出现的位置。如果表中不包含x，则返回-1当表为空时，isEmpty返回1，否则返回0。当表已满时，isFull返回1，否则返回0操作的几个示例序号操作操作结果解释1initList(&s)()创建空线性表s2for(i=0;i<6;i++)insertList(&s,i,2*i)(0,2,4,6,8,10)在空表s的表尾处依次插入6个值3removeList(&s,3,&x)(0,2,4,8,10)删除位置3的值并由x返回该值4setValue(&s,3,-10)(0,2,4,-10,10)给位置3的元素赋值-105find(&s,10)返回值是4在s中查找10，10在位置46find(&s,9)返回值是-1在s中查找9，查找失败第二节

线性表的顺序存储及实现操作的具体实现需要依赖于线性表的存储结构。可以使用顺序存储方式和链式存储方式保存线性表，从而得到线性表的顺序存储结构和链式存储结构顺序存储结构使用数组保存线性表中的各元素，相应的线性表称为顺序表链式存储结构使用链表保存线性表中的各元素，相应的线性表称为链表顺序表顺序存储的基本思想是使用一组连续的存储单元依次存储各个元素，将线性表中的各数据元素，按照其逻辑次序，依次保存在数组的各个单元中线性表中逻辑上相邻的两个元素，保存在数组相邻的两个单元中

分配一个多大的数组是个挑战顺序表的显著特点

分配了数组空间后，将线性表中的n个元素依次保存在数组中，从表头至表尾的各个元素分别对应下标0到下标n-1的位置数组是内存中一片连续的空间，相邻的两个单元在内存中的实际地址也是相邻的，这表明，线性表中逻辑上相邻的两个元素，其存储地址也是相邻的存储示意图假设线性表L=(a0,a1,a2,a3,a4,a5)，每个元素需要占用2个字节，分配一个含8个元素的数组A保存LA在内存中的示意图数组下标与线性表元素的位置相对应线性表元素依次存放的特性，决定着表中元素i（i≥0）存储在数组的下标i处表头元素保存在位置0处，这个位置也称为数组的首地址只要给定数组下标，就能立即计算出相应元素的存储地址，并据此访问该元素地址计算

设LOC(ai)表示元素ai的存储首地址，每个元素需占用d个存储单元，则有 LOC(ai)=LOC(ai-1)+d进一步地有 LOC(ai)=LOC(a0)+i

dLOC(a0)即是数组的首地址例2-4

设顺序表的每个元素占8个存储单元。第1个元素的存储首地址为100，则第6个元素占用的最后一个存储单元的地址是（）A．132 B．139 C．140 D．147解：答案是Dd=8，LOC(a0)=100，第6个元素是a5LOC(a5)=LOC(a0)+5

8=100+40=140即第6个元素占用从140开始的8个存储单元，那么最后一个存储单元是147插入和删除设给定一个顺序表，初始时含有5个元素。在位置2插入元素27，然后删除位置3的元素初始顺序表在位置2插入元素27删除位置3的元素

11523196

…

1152723196

…

11527196

…

程序中使用的常量#defineTRUE1#defineFALSE0#defineERROR-1#ifndefmaxSize#definemaxSize100#endif顺序表基本运算的实现顺序表的定义构造空表及清空表判表空、判表满、求表长插入新元素插入操作中移动元素的平均次数为n/2删除操作删除操作中移动元素的平均次数为(n-1)/2赋值、取值操作查找测试例2-5设有顺序表L，表长为n，保存在数组A中。实现算法将L逆置，即 L=(a0,a1,…,an-2,an-1)变为 L=(an-1,an-2,…,a1,a0)将A[0]与A[n-1]进行交换，然后将A[1]与A[n-2]进行交换，依此类推，当交换到L中间元素时，算法结束算法实现第三节

线性表的链式存储及实现线性表还可以使用链式存储方式保存，即线性表中的各个元素保存在各自的存储空间中，形成一个个的结点这些结点在内存中的地址不要求是相邻的，它们之间通过指针连接起来以这种方式保存的线性表称为链表每个结点中包含元素值和指向其他结点的指针，指针的个数可以是一个，也可能是两个，从而形成不同形式的链表链式存储结构是一种动态灵活的存储方式，它不要求预先分配一块连续的存储空间，而是按需分配，随时需要随时分配同时不要求分配的空间必须是相邻的，而是由系统决定分配的具体位置，既可以相邻也可以不相邻所以在执行插入及删除操作时，不再需要移动元素以保证存储空间的相邻性单链表单链表是由一组动态分配的结点形成的链表，每个结点保存线性表中的一个元素及一个指针，指针指向保存其后继元素的结点保存L的单链表示意图结点定义单链表中结点及链表的定义示例要在上图所示的单链表L的位置2处插入元素E。当前指针为p，指向位置2操作步骤是创建一个新结点，新结点中保存值E让新结点的next指针指向指针p指向的结点，这个结点是当前结点让当前结点的前驱结点的next指针指向新结点另一种定义方式

带头结点的单链表插入在带头结点的单链表中实现插入操作删除在带头结点的单链表L中进行删除例2-6在单链表L中，已知q所指结点是p所指结点的前驱结点，next是结点的指针域，若在q和p之间插入s所指结点，则执行的操作是（）。A．s->next=p->next;p->next=s;B．p->next=s->next;s->next=p;C．p->next=s;s->next=q;D．q->next=s;s->next=p;答案是D。例2-7在带头结点的单链表中，若删除指针p所指结点的后继结点，则执行的操作是（）。A．p->next=p->next->next;B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;答案为A。例2-8线性表若采用链式存储结构保存，则要求内存中可用存储单元的地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案为D。单链表基本操作的实现带头结点的单链表中，始终会有一个头结点，这个结点在初始化时创建清空单链表判空单链表需要判空，通常不需要判满求长度的两种实现位置值与指针的转换插入新元素删除元素赋值、取值查找例2-9返回指针curr指向结点的位置效率分析如果给定了当前指针，则插入操作和删除操作的时间复杂度均为O(1)判定链表是否为空的时间复杂度也为O(1)清空表操作的时间复杂度是O(n)求表长，两种实现分别是O(1)和O(n)查找操作的时间复杂度是根据查找目标在链表中的位置而定的最优情况下为O(1)最坏的情况下为O(n)平均来看是O(n)查找失败是O(n)循环链表修改单链表的定义，将表尾结点的指针指回头结点，从而形成一类新链表这样的链表中，从任何一个结点出发沿着指针域的指示可以再回到这个结点，好象转了一个圈一样，形象地称这样的链表为循环链表双向链表双向链表中，表结点及链表的定义typedefintELEMType;typedefstructnode{ //双向链表结点

ELEMTypedata; structnode*next; //指向后继结点 structnode*prev; //指向前驱结点}DouLinkNode;typedefDouLinkNode*DouLinkList; //双向链表typedefintPosition;双向链表双向链表的初始化辅助函数setCurr插入新元素删除元素双向循环链表例2-11在双向循环链表中，在指针p所指向的结点（非尾结点）之后插入指针s指向的结点，下列选项中，正确的修改指针的语句序列是（）。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案是D。第四节进一步讨论两种基本实现方式线性表有两种基本的实现方式，分别是顺序实现和链式实现简单地说，这两种实现方式各有优势。在不同的情况下，对应于不同的操作，某一种方式可能会优于另外一种。但是哪种方式都不能适用于所有情况示例将下列特性对应到顺序表和链表中，对号入座A．逻辑上相邻的元素，在内存中的存储位置也相邻B．不必事先估计存储空间C．所需空间与元素个数成正比D．插入、删除时不需要移动元素E．支持随机存取F．支持顺序存取顺序表具有的特性有：A、E和F链表具有的特性有：B、C、D和F对比存储每个数据元素时空间比较紧凑，并且是占用连续的空间数组的每个单元中只需要保存数据本身，没有额外的开销链表在每个结点上除存储数据元素外，还要留出空间存放指针。单链表中每个结点包含一个指针，双向链表中每个结点包含两个指针。这些指针占用的空间称为结构性开销为顺序表分配的数组，通常要宽松一些。通常数组中会有空闲的空间，此时并没能充分利用数组的全部空间链表中占用的空间大小与链表中的元素个数成正比，分配的结点是全部使用的当线性表的元素个数相对较少时，链表的实现比顺序表的实现更节省空间当线性表中的元素个数接近分配的最大个数，数组的空间存储效率很高设n表示线性表中当前元素的个数，D表示最多可以在数组中存储的元素个数，也就是数组的大小，P表示指针的存储单元大小，E表示数据元素的存储单元大小顺序表的空间需求为D

E单链表的空间需求为n

(P+E)n的临界值n=D

E/(P+E)双向链表比单链表中每个结点的指针数多1个。所以双向链表的结构性开销是单链表的2倍例2-12设保存线性表L的每个元素需要的空间为10个字节，指针占2个字节。若采用单链表或含30个元素的数组保存L。试分析采用哪种方式空间存储效率更高，仅需要考虑L中元素根据题意，采用单链表保存L时，每个结点占用的空间为12个字节例2-12如果采用数组保存，则需要的空间是30

10=300个字节。使用这些空间保存单链表中的结点的话，可以保存300/12=25在不考虑表头结点占用的空间的前提下，如果L中元素个数少于25个，则采用单链表更省空间如果多于25个元素，则采用数组更省空间如果正好是25个元素，则单链表和数组占用的空间是一样大的如何选择当线性表元素个数变化较大或者未知时，最好使用链表实现如果用户事先知道线性表的大致长度，则使用顺序表的空间效率会更高些还要考虑到，顺序表占用的空间是连续的，而链表占用的空间可能是零散的，并且还需要程序员来管理空间的分配及释放操作的时间复杂度也要考虑在顺序表中是直接定位的，可以实现随机访问，操作的时间复杂度是O(1)单链表不能随机访问指定的元素，平均时间复杂度和最差时间复杂度均为O(n)在给出指向链表的当前指针后，在单链表内进行插入和删除操作的时间复杂度也可以达到O(1)顺序表的插入和删除操作，平均和最差时间复杂度均为O(n)空闲单元链表链表中，当需要在链表中插入一个结点时，需要调用malloc函数分配相应的空间当在链表中删除一个结点时，需要调用delete函数释放空间。如果在链表中频繁进行插入、删除结点的操作，则频繁调用这些函数的时间开销会是非常可观的可以针对实际应用的每类链表，定义一个“伙伴链表”，表结点的结构与所使用的链表结构一致伙伴链表用来管理暂时不用的结点，可以将伙伴链表称为空闲单元链表假设，保存数据的单链表为L当从链表L中删除一个结点时，将这个结点插入到freelist中当需要申请新的结点空间时，先查看链表freelist。如果freelist不空，则从freelist中获取一个结点，结点中保存相应的值，并将该结点插入到L的相应位置，否则调用malloc函数分配新的空间，并完成后续的插入操作插入操作的实现删除操作的实现清空表的操作静态链表静态链表的特点保存在数组中兼具顺序表和链表特性，空间不零碎，插入删除不需要移动元素链表及静态链表在前一个静态链表中插入元素E后的静态链表删除元素D后的静态链表类型定义初始化静态链表清空静态链表判空、判满、求表长的实现插入操作的实现删除操作的实现例2-14设双向静态有序链表L保存在含8个元素的数组A中，表头结点在A[0]中。依次执行下列操作，画出每个操作后得到的数组A（1）初始化L（2）将序列618,205,103,501,781,910依次插入到L中，建立双向静态有序链表（3）从L中依次删除元素501、103（4）将元素301插入到L中（1）初始化L（2）插入数据序列后（3）删除两个元素后（4）再插入一个元素后第五节

单链表的应用创建单链表从键盘读入值创建单链表从数组读入值创建单链表查找单链表倒数第k个结点如果知道了单链表的长度，那么访问倒数第k个结点就很容易了。假设单链表长度为n，则倒数第k个结点即是第n-k+1个结点使用两个指针front和rear，均从表头开始同步向表尾方向移动初始时，先令front前进k步，当个“排头兵”这样front和rear指向的位置相距k个结点然后两个指针同步前进当front到达表尾时，rear即位于倒数第k个结点查找倒数第k个结点程序查找单链表的中间结点使用两个指针，并同时从表头开始向表尾方向移动，一个指针一次走两步，另一个指针一次走一步。这样，当“排头兵”指针到达表尾时，后面的指针即指向链表的中间结点。与findKth函数中一样，两个指针分别是front和rear程序将单链表逆置对于单链表的其他结点，让middle所指结点的next域指向left所指结点，即left所指结点的原后继（middle所指）变为它的新前驱。然后，三个指针依次后移一个位置当所有结点中的next域都转向后，再将head所指的头结点链接在表头处程序验证程序ThankYou!全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第三章栈和队列学习目标掌握栈和队列的逻辑定义、特点及基本操作，了解它们的逻辑表示方法及使用场掌握栈的两种存储方式及各自的特点，掌握两种方式下基本操作的实现及复杂度分析掌握队列的两种存储方式及各自的特点，掌握两种方式下基本操作的实现，重点掌握循环队列的实现及复杂度分析掌握结合了栈和队列特点的双端队列了解线性表与栈及队列的关系灵活运用栈和队列的基本操作，设计算法解决与此相关的实际问题本章主要内容栈12进一步讨论栈与队列3队列4栈和队列的应用栈和队列是线性表的两个经典特例，它们都是操作受限的线性表，即操作的位置需要满足各自的条件因为这些条件的特殊性，使得实现各自的操作时过程简捷，效率更高第一节

栈栈是一种特殊的线性表，它的特殊性体现在操作的位置上。在含n个元素的线性表中进行插入或删除时，操作位置可以有n+1个或n个当将操作位置限定在线性表的同一端时，得到的数据结构就是栈它是一种受限的线性表栈的定义及其基本操作定义3-1栈（stack）是限定仅在一端进行插入和删除的线性表能进行插入和删除的这一端称为栈顶，线性表的另一端称为栈底在栈顶插入一个元素称为入栈（push）、进栈或压栈，从栈顶删除一个元素称为出栈（pop）或退栈栈的表示将栈S表示为：S=(a0,a1,…,an-1)

通常指定an-1一端为栈顶，a0一端是栈底栈中元素个数n称为栈的长度，当n=0时，称为空栈栈具有后进先出（LIFO，LastInFirstOut）的特性只要栈不空，就允许出栈只要栈不满，就允许入栈当没有其他的特殊限制时，对于同一个入栈序列，可能会得到很多个合理正确的出栈序列栈的基本操作出栈序列个数

例3-1设有5个元素1,2,3,4,5依次入栈，以push(x)表示x入栈，pop(x)表示x出栈，试写出得到出栈序列2,1,4,3,5的操作过程操作过程为push(1),push(2),pop(2),pop(1),push(3),

push(4),pop(4),pop(3),push(5),pop(5)例3-2依次读入数据元素序列a,b,c,d,e,f,g并入栈。下列选项中，不可能是出栈序列的是（）A．d,e,c,f,b,g,aB．c,d,b,e,f,a,gC．e,f,d,g,c,b,aD．f,e,g,d,a,c,b答案为D例3-3一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是n，则第i（1<i≤n）个输出的元素是（）A．不确定B．n-i+1C．iD．n-i答案为B例3-4元素a,b,c,d,e依次进入初始为空的栈中，在所有可能的出栈序列中，以元素d开头的序列个数是（）A．3 B．4 C．5 D．6

答案为B例3-5入栈序列是1,2,3,4，出栈序列是2,4,3,1，则栈的容量最小是（）。A．1B．2C．3D．4答案为C栈的存储及其实现栈有两种主要的存储方式顺序存储链式存储顺序存储方式使用数组保存栈元素，得到的是顺序栈链式存储方式使用单链表保存栈元素，得到的是链式栈顺序栈及其实现在顺序栈中，栈中的元素保存在一维数组中，将栈底定义在数组下标为0的位置同时使用一个变量标记栈顶的位置，即栈顶位置栈顶位置也称为栈顶指针顺序栈的定义typedefintELEMType; //以int类型为例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是数组最大容量，已定义的常量 inttop; //栈顶位置}SeqStack;顺序栈的基本操作栈顶位置top的两种定义方式本书采用(a)的方式初始化栈、清空栈判空、判满入栈入栈时，新元素放在element[top]处，然后top加1第1个元素入栈时放在数组下标为0的位置因为数组空间有限，最大容量是maxSize，所以入栈时需要判定栈不能是满的出栈出栈时，需要先将top值减1，然后将element[top]处的值通过参数x返回出栈时需要判定栈不是空的获取栈顶元素效率top的值既是保存下一个入栈元素的位置，也是栈中所含元素个数的计数器因为栈的入栈操作及出栈操作都在栈顶进行，所以入栈、出栈、获取栈顶元素时都不需要移动栈中已有的元素，故时间复杂度都是O(1)判定栈空及栈满等操作的时间复杂度也是O(1)例3-6也可以将数组下标最大的一端作为栈底若一个栈保存在数组V[0..n-1]中，初始时栈顶指针top为n，则下列选项中，能够正确实现x入栈操作的语句序列是（）。A．top=top+1;V[top]=x;B．V[top]=x;top=top+1;C．top=top-1;V[top]=x;D．V[top]=x;top=top-1;答案为C对顶栈数组的两个端点分别作为两个栈的栈底左侧栈占用数组0到k的单元，栈顶在k+1位置右侧栈占用数组m-1到h的单元，栈顶在h-1位置此时必须满足k<h，才能保证两个栈不会重叠栈S1入栈时，栈顶值增大，出栈时栈顶值减小栈S2刚好相反，入栈时栈顶值减小，出栈时栈顶值增大例3-7若栈采用顺序存储方式存储，现有两个栈共享空间V[0..m-1]，栈1的底在v[0]，栈2的底在V[m-1]，初始时，栈1的栈顶top1=0，栈2的栈顶top2=m-1。则栈满的条件是（）A．|top2-top1|==0B．top1==top2+1C．top1+top2==m-1D．top1==top2答案为B链式栈所谓的链式栈，可以看作是一个仅在表头位置进行操作的单链表将头指针所指的这一端作为栈顶，表尾一端作为栈底入栈操作及出栈操作都可以通过头指针完成。所以，在链式栈中，可以只定义头指针，尾指针及头结点都可以不定义链式栈的定义typedefintELEMType;typedefstructnode{ //链式栈结点

ELEMTypedata; structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack; //链式栈初始化栈初始时是个空栈，所以指向栈顶的指针赋值NULL出栈仅当栈不为空时才能执行出栈操作，所以pop函数中要先判断栈不为空出栈后，将栈顶元素的值通过x返回给调用者元素所占用的空间要释放掉清空栈及判栈空入栈入栈时，需要创建一个新结点，并将新结点插入在栈顶位置顺序栈与链式栈的比较实现顺序栈和链式栈的所有操作都只需要常数时间，因此栈的两种实现方式的优劣仅体现在它们的存储效率上顺序栈需要预先申请一个固定长度的一维数组，并自始至终全部占用，当栈中元素个数相对较少时，空间浪费较大链式栈的长度虽然可变，但是每个元素都需要一个指针域，这又产生了结构性空间开销栈与函数调用栈是保存调用信息的最佳结构系统内部会开辟一个函数调用栈用来保存函数在调用过程中所需要的一些信息第二节

队列队列也是一种特殊的线性表，其特殊性也体现在操作的位置上它具有优先的特性，即先来的先得到服务这种先来先服务的特性称为先进先出（FirstInFirstOut），简称FIFO队列的定义及其基本操作定义3-2队列（queue）是只能在表的一端插入、在另一端删除的线性表能进行插入的一端称为队列尾，简称队尾；能进行删除的一端称为队列头，简称队头在队尾插入元素称为入队（enqueue），从队头删除元素称为出队（dequeue）仍然可以沿用线性表的方法来表示队列，队列Q可以表示为 Q=(a0,a1,…,an-1)a0称为队头元素，an-1称为队尾元素，元素个数n称为队列长度当给定队列的入队序列后，仅能得到一个出队序列，而且是与入队序列完全相同的序列。这是由队列先进先出的特性决定的队列的定义队列中元素的类型是ELEMType，另外，还有指标队头和队尾的两个量定义如下所示typedefintELEMType;intfront,rear; //队头、队尾指针队列的操作定义队列的存储及实现与线性表及栈一样，队列也有两种实现方式，分别得到顺序队列和链式队列顺序队列使用一个一维数组A（下标从0到n-1）来保存队列，假定队列中含有m（m≤n）个元素选择A[0]作为队头，那么A[m-1]就是队尾当出队时，队头A[0]从数组中删除，此时要依次将后面的m-1个元素均前移一个位置这种情况下出队操作的时间开销是O(m)存储结构现在交换队头和队尾的位置，选择A[m-1]是队头，那么A[0]是队尾入队时，队列中原有的m个元素均需后移一个位置，腾出A[0]的位置放置新元素此时入队操作的时间开销将为O(m)存储结构可以使用变量front指示队头位置，使用变量rear指示队尾位置称front为队头指针，rear为队尾指针表示的是数组下标通常，front指示的是队头元素所在的位置，rear指示的是队尾元素后面的空位置按照惯例，还是将第一个入队的元素保存在数组下标0的位置入队的新元素放置到所有元素的后面经过若干次入队、出队操作后，含m个元素的队列的示意图如下所示，其中阴影部分表示队列中的元素实际占用的数组单元

a0…am-1

↑front

↑rear

当再进行若干次入队操作后，rear会到达数组的末尾，即最后一个下标位置。之后再进行入队操作时，导致数组下标越界。但数组的前半段可能会因出队操作而有空闲的单元

x…y

↑front

↑rear可以重复利用数组中前面的空闲单元保存后续入队的元素…v

……u…

↑rear

↑front

例3-8设队列保存在最大容量为7的数组A中，从空队列开始，依次执行下列各步操作，分别画出得到的队列示意图依次将5,12,9,37入队列将5,12依次出队列，并依次将25,8入队列将16入队列，再将9出队列，再将7,4入队列循环队列顺序队列都实现为循环队列在循环队列中，入队操作会涉及到队尾rear值的变化，rear=(rear+1)%n，出队操作会涉及到队头front值的变化，front=(front+1)%n，其中n是数组的大小可以把这个数组想象成一个首尾相接的圆环，A[n-1]的后面是A[0]“循环”一词的含义正是如此空与满数组满时，rear==front条件rear==front也代表空队列解决方法：让数组中始终剩余至少一个空位置。当数组中仅有一个空位置时，就认为已经达到队列的最大长度了，队列已满初始时，front=0且rear=0例3-9已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）A．0,0B．0,n-1C．n-1,0D．n-1,n-1答案是B循环队列的定义typedefintELEMType;typedefstruct{

ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循环队列初始化构造一个空队列，队头和队尾指针均赋初值0清空队列队列置空也得到一个空队列，可以将队头和队尾指针均赋值0，和初始化队列的结果一样也可以让队头和队尾指针的值相等，表示是一个空队列判空与判满队列为空的条件是rear==front队列为满的条件是(rear+1)%n==front求队列长度入队与出队链式队列链式队列采用带头指针及尾指针的单链表作为队列的存储结构单链表的头指针可以当作队头指针front，尾指针可以当作队尾指针rear链式队列的定义typedefintELEMType;typedefstructnode{ //链式队列中结点 ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //链式队列 LinkQueueNode*front,*rear; //队头指针、队尾指针}LinkQueue;初始化、清空队列判空循环队列中，当队头指针和队尾指针相等时，队列为空空链式队列中，队头指针和队尾指针都为NULL在内存足够大的情况下，链式队列通常不会满入队列出队例3-10若使用不带头结点的单链表存储队列，则进行入队列操作时（）。A．仅需要修改队头指针，不需要修改队尾指针B．仅需要修改队尾指针，不需要修改队头指针C．队尾指针一定要修改，队头指针也一定要修改D．队尾指针一定要修改，队头指针可能要修改答案为D采用链式方式实现队列时，也可以配合使用一个空闲单元链表，使得入队、出队时尽量少地调用malloc函数及free函数在链式队列中，可以将这两个链表合在一起，形成一个圆环，即使用一个循环链表来表示链式队列及对应的空闲单元链表。在这个循环链表中，结点分为两部分，一部分结点用来保存实际数据，另一部分结点是空闲结点带空闲单元链表的链式队列初始状态第一个元素入队第三节

进一步讨论栈与队列双端队列输入受限的双端队列输出受限的双端队列例3-11若以1,2,3,4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（）。A．1,2,3,4B．4,1,3,2C．4,2,3,1D．4,2,1,3答案是C例3-12循环队列存放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。下列判断队空和队满的条件中，正确的是（）。A．队空：end1==end2；队满：end1==(end2+1)modMB．队空：end1==end2；队满：end2==(end1+1)mod(M-1)C．队空：end2==(end1+1)modM；队满：end1==(end2+1)modMD．队空：end1==(end2+1)modM；队满：end2==(end1+1)mod(M-1)答案是A栈与队列的相互模拟使用栈来模拟队列使用栈模拟的队列类型定义typedefstruct{

SeqStackS,T;}simuQueue; //队列typedefintELEMType;初始化入队列出队列判空、判满使用队列来模拟栈使用队列模拟的栈类型typedefstruct{

SeqQueueP,Q;}simuStack; //使用队列来模拟栈typedefintELEMType;初始化、清空栈判空、判满求长度入栈操作出栈第四节

栈和队列的应用——括号的匹配检查程序中有很多符号是成对出现的，并且它们的出现次序必须正确，可以嵌套但不能交错“左”符号称为“开”符号，“右”符号称为“闭”符号如果表达式中符号匹配正确，则表达式称为平衡的表达式可以用栈来实现检验符号平衡性的算法检验括号匹配算法的思想从左至右扫描给定的符号串，忽略所有非括号的符号当遇到开括号时，保存它当遇到一个闭括号时，看看它是否对应于最近遇到的开括号如果是，则丢掉开括号，并继续扫描符号串如果能扫描完整个符号串，且没有遇到不匹配的情况，则给定的符号串代表的表达式是平衡的可以使用栈来保存遇到的开括号表达式不平衡的情况刚扫描到的闭括号与栈顶开括号不匹配，说明括号有交错已扫描到表达式尾，但栈不空，说明开括号数多于闭括号数扫描到闭括号时发现栈为空，说明缺少与此闭括号对应的开括号检验括号平衡性算法的实现检验括号平衡性算法例3-13检查表达式[a+(d+e)]时栈的变化过程例3-14检查表达式{[(])}时栈的变化过程表达式的计算表达式的表示形式及计算次序中缀表达式： <操作数><运算符><操作数> c*(a+b)前缀表达式 <运算符><操作数><操作数>后缀表达式 <操作数><操作数><运算符>将中缀表达式转变为后缀表达式——手算给中缀表达式中的每个运算符加括号，这样的表达式称为带完全括号的中缀表达式接下来，将每个运算符右移，紧贴在对应的闭括号的前面最后，去掉括号得到后缀表达式将中缀表达式转变为后缀表达式——算法自左至右扫描中缀表达式，当遇到操作数时，直接输出它。当遇到运算符时，不能像操作数那样直接输出，而是保存在栈中。当满足一定的条件时才输出栈顶的运算符当读到表达式中的一个运算符时，将它与栈内运算符进行比较。分以下情况考虑若栈内运算符的优先级高于栈外运算符的优先级，则输出栈内运算符，继续比较栈外运算符与栈内运算符若栈外运算符的优先级高于栈内运算符的优先级，则栈外运算符入栈，继续读入表达式的下一个符号若已经读到表达式末尾，则依次出栈栈中的全部运算符部分运算符优先级表运算符+,-*,/,%()#栈内优先级351-0栈外优先级2481-例3-15将中缀表达式1+2*3转换为后缀表达式算法——获取算符优先级转换算法将中缀表达式转变为后缀形式的算法后缀表达式计算从左至右扫描后缀表达式当遇到操作数时，操作数进栈当遇到运算符时，从栈中弹出两个操作数，并进行运算符所代表的运算，结果仍放到栈中因为栈的后进先出的特性，故从栈中先弹出的操作数是运算符的右操作数，后弹出的是左操作数例3-16计算后缀表达式123*+值的过程计算表达式算法计算后缀表达式算法打印杨辉三角形杨辉三角形的前8行相邻两行的对应关系打印算法打印杨辉三角形算法ThankYou!全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第四章数组、广义表和串学习目标掌握数组、广义表和串的基本概念掌握数组按行主序及按列主序的存储方式及二维数组地址计算方法掌握特殊矩阵的存储方式及相应的地址计算方法理解广义表的概念，掌握广义表的表示及基本运算了解模式匹配概念，掌握串的模式匹配算法本章主要内容数组及广义表12串第一节

数组及广义表数组是程序设计语言中的重要语法成分，很多语言都定义了数组类型以C语言为例，它定义了一维数组，数组元素还可以是数组，由此得到数组的数组，即多维数组一般地将n（n≥2）维数组看作是n-1维数组的数组从数据结构的角度来理解，一维数组可以作为线性表的存储结构，数组中保存的各元素可以组成一个线性表多维数组在系统内部都对应一个隐含的一维数组，所以多维数组也是一种线性表例如二维数组就是以一维数组为元素的线性表数组的每个元素都是形如(index,value)的二元对，index是数组下标，也称为索引，value是对应于该下标的数值任何两个元素的index值都不相同数组的基本操作Create(); //创建一个空的数组Store(index,value);//添加数据(index,value)//同时删除有相同index值的数据对（若存在）Retrieve(index);//返回下标为index的value值例4-1用数组表示一个星期每天的最高温度hightem={(星期日,30),(星期一,28),(星期二,29),(星期三,32),(星期四,28),(星期五,30),(星期六,31)}数组上的操作Store(星期一,29);Retrieve(星期五);也可以约定使用0到6来分别表示星期日到星期六，此时，数组hightem可表示为hightem={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}数组的顺序存储方式数组的顺序存储有两种形式。以二维数组为例，它的元素可以按行排列，也可以按列排列所谓按行排列，就是先排数组的第一行，紧随其后排第二行，依此类推所谓按列排列，就是先排数组的第一列，紧随其后排第二列，依此类推最终都是将数组中的全部元素排列成一个序列C语言中多维数组下标的形式：[i1][i2][i3]…[ik]ij（1≤j≤k）为非负整数声明值为整型类型的k维数组DkArrayintDkArray[u1][u2][u3]…[uk];每一维的下标取值范围是：0≤ij<uj（1≤j≤k）数组最多可容纳n=u1

u2

u3

…

uk个整数所需要的内存空间sizeof(DkArray)=n

sizeof(int)个字节若开始地址为start，则占用的空间将延伸至start+sizeof(DkArray)-1。intD2Array[3][6];对应一个3行6列的矩阵通常int占4个字节数组D2Array中含有18个元素共占用18

4=76个字节编号对上述的下标表格按行自上而下、同一行中自左至右进行连续编号，从0开始按行优先把二维数组中的下标映射到0到n-1之间的某个整数的方式称为行主序，也称为行主映射按列优先，对下标表格从第一列开始，从上到下进行连续编号，直到最后一列映射函数行主序所对应的映射函数为 map(i1,i2)=i1

u2+i2

其中u2是数组的列数列主序所对应的映射函数为 map(i1,i2)=i2

u1+i1

其中u1是数组的行数例4-3二维数组A[10][5]采用行主序方式存储，每个数据元素占4个存储单元，若A[0][4]的存储地址是1000，则A[8][4]的存储地址是多少？解：给定的数组A是10行5列，需要从A[0][4]的存储地址反推出数组A的首地址，然后再计算A[8][4]的存储地址行主序所对应的映射函数为map(i1,i2)=i1

u2+i2本题中：u2=5，map(0,4)=4每个元素占4个存储单元 A[0][0]的存储地址=1000-4

4=984根据计算公式，A[8][4]的映射编号是 map(8,4)=8

5+4=44存储地址为984+44

4=1160换一种计算方法A[0][4]和A[8][4]之间的元素个数是 8

5=40A[0][4]与A[8][4]之间的偏移量 =40

4A[8][4]的存储地址 =A[0][4]的存储地址+ A[0][4]与A[8][4]之间的偏移量 =1000+160=1160示例三维数组D3Array[3][2][4]按行主序下标排列的形式对于三维数组ThrDimenArray[u1][u2][u3]，其行主序的映射函数应为 map(i1,i2,i3)=i1

u2

u3+i2

u3+i3排列规律所有第一维值为i1的元素都排在第一维值大于i1的元素之前。第一维值相同的元素数目为u2

u3。因此第一维值小于i1的元素数目为i1

u2

u3，第一维值等于i1且第二维值小于i2的元素数目为i2

u3，第一维值等于i1第二维值等于i2且第三维值小于i3的元素数目为i3矩阵的压缩存储对称矩阵和三角矩阵从节省存储空间的角度考虑，对称矩阵和上（下）三角矩阵，都可以只保存矩阵中约一半的元素，从而可以节省差不多一半的存储空间这样的存储形式称为压缩存储压缩存储对于对称矩阵，因为对角线以上及以下的元素对称相等，所以只需要保存其中的一半及对角线上的元素即可对于上三角矩阵或下三角矩阵，仅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩阵有n行n列，则这三种形式下需要保存的元素个数为n

(n+1)/2三角部分

例4-4设有一个10行10列的下三角矩阵A，采用行优先压缩存储方式，保存A中第一个元素a00的地址是100，保存a11的地址是108，则保存元素a44的地址是（）A．115B．156C．160D．212答案为B稀疏矩阵稀疏矩阵该矩阵只有10个非零元素，每个非零元素用一个三元组表示三元组表三元组表应是一个有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元组再按列的大小排列对应前例的三元组表i0012234455j1200521405v891-3121624615-7稀疏矩阵的存储结构typedefstruct{ inti,j; //存储非零元素的下标

ELEMTypev; //存储非零元素的值}triTerm;typedefstruct{ introws,cols; //矩阵的行数、列数 intterms; //非零元素个数

triTermtri[maxSize]; //三元组表}SparseMatrix;输入三元组生成三元组表的程序矩阵转置矩阵转置即是行、列互换，i行的元素放置到i列，这也意味着，j列的元素放置在j行。如果矩阵是n

m的，则转置后得到的矩阵是m

n的很容易想到，将三元组表中的每个三元组项的i与j互换，即可得到转置后矩阵的三元组表但是这样转换后得到的三元组表不再按行主序排列，不便于后续操作的实现所以要实现的矩阵转置程序，必须得到一个按行主序排列的三元组表思路可以像readSparseMatrix函数那样处理，读入原矩阵的一个三元组，插入到目标矩阵的三元组表中可以使用一个临时计数数组，记录原矩阵的每个三元组在目标矩阵的三元组表中的插入位置，以辅助完成转置操作，由此避免了三元组的移动，高效率地实现转置操作不失一般性，设原矩阵A的行数是rows，列数是cols。则转置后矩阵B的行数是cols，列数是rows。三元组的个数没有改变A中处于0列的元素，将是B中处于0行的元素。所以B的三元组表中的最前面的元素，是A中列值为0的元素。接下来是A中列值为1的元素，依此类推，最后是A中列值为cols-1的元素。使用临时数组ColSize来保存统计结果前例中的矩阵，临时数组ColSize内容在B的三元组表中，为各行元素预留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素对于A的三元组(0,1,8)和(4,1,24)，转置后分别为(1,0,8)和(1,4,24)，它们应该保存在上述第二部分，即位置3和位置4中故由ColSize数组中的元素值，从前向后依次相加，得到RowNext的值012345603577810转置算法数组的应用走迷宫是实验心理学中的一个经典问题不失一般性，使用一个m行n列的矩阵maze表示迷宫，让机器人R寻找从maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宫的唯一出口）间的可行路径任一时刻，R在迷宫中的位置用行、列号[i][j]来表示，这时它有4个方向可以进行试探，即从图上看是上、下、左、右设下一位置是[g][h]，显然[g][h]