【图文】数据结构与算法(C++)讲队列_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构与算法(C++)讲队列
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)当前位置： >>
C语言算法与数据结构
算法与数据结构刘建圻粤嵌教育第一章 概论基础知识 ? 时间复杂度 ? 空间复杂度?1.1 基本概念和术语数据(Data) ：是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。 数据元素(Data Element) ：是数据的基本单位，在 程序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。 数据项是数据的不可分割的最小单位。数据项是对客观 事物某一方面特性的数据描述。 数据对象(Data Object)：是性质相同的数据元素的集 合，是数据的一个子集。如字符集合C={?A‘,‘B‘,‘C,…} 。数据结构(Data Structure)：是指相互之间具有(存在 )一定联系(关系)的数据元素的集合。元素之间的相互联 系(关系)称为逻辑结构。数据元素之间的逻辑结构有四 种基本类型，如图1-3所示。① 集合：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。② 线性结构：结构中的数据元素之间存在一对一的 关系。③ 树型结构：结构中的数据元素之间存在一对多的 关系。 ④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。图1-3四类基本结构图1.1.3 数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例2：设数据逻辑结构B=（K，R）K={k1, k2, …, k9}R={ &k1, k3&，&k1, k8&，&k2, k3&，&k2, k4&，&k2, k5&，&k3, k9&， &k5, k6&，&k8, k9&，&k9, k7&，&k4, k7&，&k4, k6& }画出这逻辑结构的图示，并确定那些是起点，那些是终点数据元素之间的关系可以是元素之间代表某种含义 的自然关系，也可以是为处理问题方便而人为定义的 关系，这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系，相应的结构称为逻辑结构。1.1.4 数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的 存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法： 顺序表示和非顺序表示。由此得出两种不同的存储结构： 顺序存储结构和链式存储结构。C 顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。C 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表 示数据元素之间的逻辑结构(关系)。例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。 C 顺序结构：数据元素存放的地址是连续的； C 链式结构：数据元素存放的地址是否连续没有要 求。数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构，而算法的实 现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结 构体类型表示链式存储结构。数据结构的三个组成部分： 逻辑结构： 数据元素之间逻辑关系的描述D_S=（D，S）存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作： 对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图1-4所示。逻辑结构线性表 树 图图1-4物理结构顺序存储结构链式存储结构复合存储结构逻辑结构与所采用的存储结构数据的逻辑结构线性结构 受限线性表 线性表推广 数组 集合 广义表非线性结构 树形结构 一般树 二叉树 图状结构 有向图 无向图一般线性表栈和队列 串图1-5数据逻辑结构层次关系图1.1.5 数据类型数据类型(Data Type)：指的是一个值的集合和定 义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 在C 语言中数据类型有：基本类型和构造类型。数据结构不同于数据类型，也不同于数据对象，它 不仅要描述数据类型的数据对象，而且要描述数据对象 各元素之间的相互关系。1.1.6 数据结构的运算数据结构的主要运算包括： ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构； ⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access)； ⑹ 对一个数据结构(中的数据元素)进行修改 (Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。1.2 抽象数据类型抽象数据类型(Abstract Data Type ，简称ADT)：是 指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述， 与其在计算 机内的表示和实现无关。因此，不论ADT的内部结构如 何变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基 本操作集。ADT的一般定义形式是： ADT &抽象数据类型名&{ 数据对象： &数据对象的定义&数据关系： &数据关系的定义&基本操作： &基本操作的定义& } ADT &抽象数据类型名&C 其中数据对象和数据关系的定义用伪码描述。 C 基本操作的定义是：&基本操作名&(&参数表&)初始条件： &初始条件描述& 操作结果： &操作结果描述&C 初始条件：描述操作执行之前数据结构和参数应满足的条件;若不满足，则操作失败，返回相应的出 错信息。 C 操作结果：描述操作正常完成之后，数据结构的 变化状况和 应返回的结果。1.3 算法分析初步1.3.1 算法算法(Algorithm)：是对特定问题求解方法(步骤)的一种 描述，是指令的有限序列，其中每一条指令表示一个或 多个操作。 算法具有以下五个特性 ① 有穷性： 一个算法必须总是在执行有穷步之后结 束，且每一步都在有穷时间内完成。 ② 确定性：算法中每一条指令必须有确切的含义。 不存在二义性。且算法只有一个入口和一个出口。 ③ 可行性： 一个算法是能行的。即算法描述的操作 都可以通过已经实现的基本运算执行有限次来实现。④ 输入： 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。 ⑤ 输出： 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。一个算法可以用多种方法描述，主要有：使用自然 语言描述；使用形式语言描述；使用计算机程序设计语 言描述。算法和程序是两个不同的概念。一个计算机程序是 对一个算法使用某种程序设计语言的具体实现。算法必 须可终止意味着不是所有的计算机程序都是算法。1.3.2 算法设计的要求评价一个好的算法有以下几个标准 ① 正确性(Correctness )： 算法应满足具体问题的 需求。② 可读性(Readability)： 算法应容易供人阅读和交 流。可读性好的算法有助于对算法的理解和修改。③ 健壮性(Robustness)： 算法应具有容错处理。当 输入非法或错误数据时，算法应能适当地作出反应 或进行处理，而不会产生莫名其妙的输出结果。 ④ 通用性(Generality)： 算法应具有一般性 ，即算 法的处理结果对于一般的数据集合都成立。⑤ 效率与存储量需求： 效率指的是算法执行的时 间；存储量需求指算法执行过程中所需要的最大存 储空间。一般地，这两者与问题的规模有关。1.3.3 算法效率的度量算法执行时间需通过依据该算法编制的程序在计算 机上运行所消耗的时间来度量。其方法通常有两种：事后统计：计算机内部进行执行时间和实际占用空间的 统计。 问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。与此相关的因素有：C 依据算法选用何种策略；C 问题的规模；C 程序设计的语言； C 编译程序所产生的机器代码的质量； C 机器执行指令的速度；撇开软硬件等有关部门因素，可以认为一个特定算 法“运行工作量”的大小，只依赖于问题的规模（通 常用n表示），或者说，它是问题规模的函数。算法分析应用举例算法中基本操作重复执行的次数是问题规模n的某 个函数，其时间量度记作 T(n)=O(f(n))，称作算法的 渐近时间复杂度(Asymptotic Time complexity)，简称时 间复杂度。 一般地，常用最深层循环内的语句中的原操作的执 行频度(重复执行的次数)来表示。 “O‖的定义： 若f(n)是正整数n的一个函数，则 O(f(n)) 表示? M≥0 ，使得当n ≥ n0时，| f(n) | ≤ M | f(n0) | 。 表示时间复杂度的阶有： O(1) ：常量时间阶 O(Sn) ：对数时间阶 O (n)：线性时间阶 O(nSn) ：线性对数时间阶O (nk)： k≥2 ，k次方时间阶 例１ 两个n阶方阵的乘法for(i=1，i&=n; ++i) for(j=1; j&=n; ++j) { c[i][j]=0 ;for(k=1; k&=n; ++k)c[i][j]+=a[i][k]*b[k][j] ; } 由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3 时间复杂度为T(n)=O(n3) 例２ {++x; s=0 ;}将x自增看成是基本操作，则语句频度为１，即时 间复杂度为Ｏ(1) 。如果将s=0也看成是基本操作，则语句频度为２，其时 间复杂度仍为Ｏ(1)，即常量阶。 例３ for(i=1; i&=n; ++i){ ++x; s+= }语句频度为：2n，其时间复杂度为：O(n) ，即为线性 阶。 例４ for(i=1; i&=n; ++i) for(j=1; j&=n; ++j){ ++x; s+= }语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平 方阶。定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m) 例５ for(i=2;i&=n;++i) for(j=2;j&=i-1;++j) {++x; a[i,j]=x; } 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方 阶。 C 一个算法时间为O(1)的算法，它的基本运算执行 的次数是固定的。因此，总的时间由一个常数（即 零次多项式）来限界。而一个时间为O(n2)的算法则 由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其 关系为： O(1)&O(Sn)&O(n)&O(nSn)&O(n2)&O(n3)C 指数时间的关系为：O(2n)&O(n!)&O(nn) 当n取得很大时，指数时间算法和多项式时间算法 在所需时间上非常悬殊。因此，只要有人能将现有指 数时间算法中的任何一个算法化简为多项式时间算法， 那就取得了一个伟大的成就。C 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例1：素数的判断算法。Void prime( int n)/* n是一个正整数 */{ int i=2 ; while ( (n% i)!=0 && i*1.0& sqrt(n) ) i++ ; if (i*1.0&sqrt(n) ) printf(D&d 是一个素数\n‖ , n) ; else printf(D&d 不是一个素数\n‖ , n) ; } 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.0& sqrt(n) ) 决定，显然i*1.0& sqrt(n) ，时 间复杂度O(n1/2)。例2：冒泡排序法。Void bubble_sort(int a[]，int n) { change= for (i=n-1; change=TURE; i&1 && --i) for (j=0; j&i; ++j) if (a[j]&a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } C 最好情况：0次 C 最坏情况：1+2+3+?+n-1=n(n-1)/2 C 平均时间复杂度为： O(n2)1.3.4 算法的空间分析空间复杂度(Space complexity) ：是指算法编写成 程序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： C 指令常数变量所占用的存储空间; C 输入数据所占用的存储空间; C 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 C 一维数组a[n]： 空间复杂度 O(n) C 二维数组a[n][m]： 空间复杂度 O(n*m)第2章线性表线性结构是最常用、最简单的一种数据结构。而线 性表是一种典型的线性结构。其基本特点是线性表中的 数据元素是有序且是有限的。在这种结构中： ① 存在一个唯一的被称为“第一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前 驱； ④ 除最后一个元素外，每个元素均有唯一一个直接 后继。② 存在一个唯一的被称为“最后一个”的数据元素；2.1 线性表的逻辑结构2.1.1 线性表的定义线性表(Linear List) ：是由n(nR0)个数据元素(结 点)a1，a2， …an组成的有限序列。该序列中的所有结 点具有相同的数据类型。其中数据元素的个数n称为线 性表的长度。 当n=0时，称为空表。当n&0时，将非空的线性表记作： (a1，a2，…an)a1称为线性表的第一个(首)结点，an称为线性表的最后 一个(尾)结点。a1，a2，…ai-1都是ai(2QiQn)的前驱，其中ai-1是ai的直 接前驱; ai+1，ai+2，…an都是ai(1Qi Qn-1)的后继，其中ai+1是ai 的直接后继。2.1.2 线性表的逻辑结构线性表中的数据元素ai所代表的具体含义随具体应 用的不同而不同，在线性表的定义中，只不过是一个抽 象的表示符号。 ◆ 线性表中的结点可以是单值元素(每个元素只有一 个数据项) 。 例1: 26个英文字母组成的字母表： (A，B，C、…、Z）例2 ： 某校从1978年到1983年各种型号的计算机拥有量 的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数 (2，3，4，…，J，Q，K，A)◆ 线性表中的结点可以是记录型元素，每个元素含 有多个数据项 ，每个项称为结点的一个域 。每个元 素有一个可以唯一标识每个结点的数据项组，称为 关键字。例4 ： 某校2001级同学的基本情况：{(?‘， ‘张里户’，‘男’，06/24/1983)， (?‘， ‘张化司’，‘男’，08/12/1984) …， (?‘， ‘李利辣’，‘女’，08/12/1984) }◆ 若线性表中的结点是按值(或按关键字值)由小到 大(或由大到小)排列的，称线性表是有序的。◆ 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。◆ 对线性表的数据元素可以访问、插入和删除。2.1.3 线性表的抽象数据类型定义ADT List{数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, nR0 }数据关系：R = {&ai-1, ai& | ai-1, ai∈D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L；ListLength( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回TRUE，否则返回 FALSE； …. GetElem( L, i, &e ) 初始条件：线性表L已存在，1QiQListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1QiQListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List2.2 线性表的顺序存储2.2.1 线性表的顺序存储结构顺序存储 ：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。顺序存储的线性表的特点：◆ 线性表的逻辑顺序与物理顺序一致; ◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。设有非空的线性表：(a1，a2，…an) 。顺序存储如图 2-1所示。Loc(a1) Loc(ai)+(i-1)* l… a1 a2 … ai … an …图2-1 线性表的顺序存储表示在具体的机器环境下：设线性表的每个元素需占用 l个存储单元，以所占的第一个单元的存储地址作为数 据元素的存储位置。则线性表中第i+1个数据元素的存 储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之 间满足下列关系： LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l在高级语言(如C语言)环境下：数组具有随机存取 的特性，因此，借助数组来描述顺序表。除了用数组来 存储线性表的元素之外，顺序表还应该有表示线性表的 长度属性，所以用结构类型来定义顺序表类型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int S typedef int ElemT typedef struct sqlist { ElemType Elem_array[MAX_SIZE] ; } SqL2.2.2 顺序表的基本操作顺序存储结构中，很容易实现线性表的一些操作： 初始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。1 顺序线性表初始化Status Init_SqList( SqList *L ) {L-&length= 0 ;return OK ; }2顺序线性表的插入在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的 第i(1QiQn)个位置上插入一个新结点e，使其成为线性 表： L=(a1，…a i-1，e，ai，ai+1，…，an)实现步骤(1) 将线性表L中的第i个至第n个结点后移一个位置。 (2) 将结点e插入到结点ai-1之后。(3) 线性表长度加1。算法描述Status Insert_SqList(Sqlist *L，int i ，ElemType e) { if ( i&0||i&L-&length-1) return ERROR ; if (L-&length&=MAX_SIZE) { printf(D线性表溢出!\n‖); return ERROR ; } for ( j=L-&lengthC1; j&=i-1; --j ) L-&Elem_array[j+1]=L-&Elem_array[j];/* i-1位置以后的所有结点后移 */L-&Elem_array[i-1]=e; L-&length++ ; return OK ;/* 在i-1位置插入结点 */}时间复杂度分析在线性表L中的第i个元素之前插入新结点，其时间 主要耗费在表中结点的移动操作上，因此，可用结点的 移动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率 为Pi，不失一般性，设各个位置插入是等概率，则 Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 总的平均移动次数： Einsert=∑pi*(n-i+1) (1QiQn)∴ Einsert=n/2 。即在顺序表上做插入运算，平均要移动表上一半结 点。当表长n较大时，算法的效率相当低。因此算法的 平均时间复杂度为O(n)。3 顺序线性表的删除在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除 结点ai(1QiQn)，使其成为线性表：L= (a1，…ai-1，ai+1，…，an)实现步骤(1) 将线性表L中的第i+1个至第n个结点依此向前移 动一个位置。 (2) 线性表长度减1。算法描述ElemType Delete_SqList(Sqlist *L，int i){ ElemTif (L-&length==0) { printf(D线性表L为空!\n‖); return ERROR; } else if ( i&1||i&L-&length ) { printf(D要删除的数据元素不存在!\n‖) ; return ERROR ; } else { x=L-&Elem_array[i-1] ; /*保存结点的值*/ for ( k= k&L-& k++) L-&Elem_array[k-1]=L-&Elem_array[k];/* i位置以后的所有结点前移 */L-&length--; return (x); }}时间复杂度分析删除线性表L中的第i个元素，其时间主要耗费在表 中结点的移动操作上，因此，可用结点的移动来估计算 法的时间复杂度。 设在线性表L中删除第i个元素的概率为Pi，不失 一般性，设删除各个位置是等概率，则Pi=1/n，而删除 时移动结点的次数为n-i。 则总的平均移动次数： Edelete=∑pi*(n-i) (1QiQn) ∴ Edelete=(n-1)/2 。 即在顺序表上做删除运算，平均要移动表上一半结 点。当表长n较大时，算法的效率相当低。因此算法的 平均时间复杂度为O(n)。4 顺序线性表的查找定位删除在线性表 L= (a1，a2，…，an) 中删除值为x的第一 个结点。实现步骤(1) 在线性表L查找值为x的第一个数据元素。 (2) 将从找到的位置至最后一个结点依次向前移动一 个位置。 (3) 线性表长度减1。算法描述Status Locate_Delete_SqList(Sqlist *L，ElemType x)/* 删除线性表L中值为x的第一个结点 */{ int i=0 ,while (i&L-&length) /*查找值为x的第一个结点*/ { if (L-&Elem_array[i]!=x ) i++ ; else { for ( k=i+1; k& L-& k++) L-&Elem_array[k-1]=L&Elem_array[k]; L-&length--; } } if (i&L-&length) { printf(D要删除的数据元素不存在!\n‖) ; return ERROR ; } return OK;时间复杂度分析时间主要耗费在数据元素的比较和移动操作上。 首先，在线性表L中查找值为x的结点是否存在;其次，若值为x的结点存在，且在线性表L中的位置为i ， 则在线性表L中删除第i个元素。设在线性表L删除数据元素概率为Pi，不失一般性， 设各个位置是等概率，则Pi=1/n。◆ 比较的平均次数： Ecompare=∑pi*i(1QiQn)∴ Ecompare=(n+1)/2 。◆ 删除时平均移动次数：Edelete=∑pi*(n-i) (1QiQn)∴ Edelete=(n-1)/2 。 平均时间复杂度：Ecompare+Edelete=n ， 即为O(n)2.3 线性表的链式存储2.3.1 线性表的链式存储结构链式存储 ：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链 表。 存储链表中结点的一组任意的存储单元可以是连 续的，也可以是不连续的，甚至是零散分布在内存中 的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。为了正确表示结点间的逻辑关系，在存储每个结点 值的同时，还必须存储指示其直接后继结点的地址(或 位置)，称为指针(pointer)或链(link)，这两部分组成了 链表中的结点结构，如图2-2所示。 链表是通过每个结点的指针域将线性表的n个结点 按其逻辑次序链接在一起的。每一个结只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一 个头结点(头指针)head指向第一个结点。头结点的数据 域可以不存储任何信息(或链表长度等信息)。data nextdata ：数据域，存放结点的值。next ：指针 域，存放结点的直接后继的地址。图2-2 链表结点结构单链表是由表头唯一确定，因此单 链表可以用头指针的名字来命名。……1100例1、线性表L=(bat，cat，eat，fat， hat)其带头结点的单链表的逻辑状态和物理 存储方式如图2-3所示。headhat NULL …… cat 1305 eat 370013001305……bat 130037003695head bat图2-3cateatfathat ?fat 1100带头结点的单链表的逻辑状态、物理存储方式……1 结点的描述与实现C语言中用带指针的结构体类型来描述 typedef struct Lnode { ElemT/*数据域，保存结点的值 */ /*指针域*/struct Lnode *}LN/*结点的类型 */2 结点的实现结点是通过动态分配和释放来的实现，即需要时分 配，不需要时释放。实现时是分别使用C语言提供的标 准函数：malloc() ，realloc()，sizeof() ，free() 。动态分配p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间， 并将其首地址放入指针变量p中。动态释放free(p) ;系统回收由指针变量p所指向的内存区。P必须是最近一 次调用malloc函数时的返回值。3 最常用的基本操作及其示意图 ⑴ 结点的赋值LNode *p; p=(LNode*)malloc(sizeof(LNode)); p-&data=20; p-&next=NULL ;p20 NULL⑵常见的指针操作…pq …p① q=a … 操作前 p a b 操作前 p … …a … 操作后 q p …② q=p-&…a b 操作后 p a b 操作后 q a p③ p=p-&…④ q-&next=(a)… pa b 操作前 qa c b……………b…… 操作前c … 操作后q … a bp … x 操作前 p … x y …(b)…q aby q…⑤ q-&next=p-& q (a)… p a b y x q 操作前 a q b操作后… a b p … y x 操作后 p y ……… ……(b)…… x 操作前 p … xaby…操作后2.3.2 单线性链式的基本操作1 建立单链表假设线性表中结点的数据类型是整型，以32767作 为结束标志。动态地建立单链表的常用方法有如下两种： 头插入法，尾插入法。⑴ 头插入法建表从一个空表开始，重复读入数据，生成新结点， 将读入数据存放到新结点的数据域中，然后将新结点插 入到当前链表的表头上，直到读入结束标志为止。即每 次插入的结点都作为链表的第一个结点。算法描述LNode *create_LinkList(void)/* 头插入法创建单链表,链表的头结点head作为返回值 */{ LNode *head, *p; head= (LNode *) malloc( sizeof(LNode)); head-&next=NULL; /* 创建链表的表头结点head */ while (1) { scanf(D%d‖, &data) ; if (data==32767) p= (LNode *)malloc(sizeof(LNode)); pC&data= /* 数据域赋值 */pC&next=headC& headC&next=/* 钩链，新创建的结点总是作为第一个结点 */} return (head); }(2) 尾插入法建表头插入法建立链表虽然算法简单，但生成的链表 中结点的次序和输入的顺序相反。若希望二者次序一致， 可采用尾插法建表。该方法是将新结点插入到当前链表 的表尾，使其成为当前链表的尾结点。算法描述LNode *create_LinkList(void)/* 尾插入法创建单链表,链表的头结点head作为返回值 */{ LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode)); p-&next=NULL; /* 创建单链表的表头结点head */ while (1) { scanf(D%d‖,& data); if (data==32767) q= (LNode *)malloc(sizeof(LNode)); qC&data= /* 数据域赋值 */ qC&next=pC& pC&next=q; p=/*钩链，新创建的结点总是作为最后一个结点*/} return (head); }无论是哪种插入方法，如果要插入建立的单线性 链表的结点是n个，算法的时间复杂度均为O(n)。对于单链表，无论是哪种操作，只要涉及到钩链( 或重新钩链)，如果没有明确给出直接后继，钩链(或 重新钩链)的次序必须是“先右后左”。2 单链表的查找(1) 按序号查找 取单链表中的第i个元素。对于单链表，不能象顺序表中那样直接按序号i访 问结点，而只能从链表的头结点出发，沿链域next逐个 结点往下搜索，直到搜索到第i个结点为止。因此，链 表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅 当1QiQn时，i的值是合法的。算法描述ElemType Get_Elem(LNode *L ， int i) { LNode *p;p=L-& j=1; /* 使p指向第一个结点 */ while (p!=NULL && j&i) { p=pC& j++; } /* 移动指针p , j计数 */ if (j!=i) return(-32768) ; else return(p-&data);/* p为NULL 表示i太大; j&i表示i为0 */} 移动指针p的频度： i&1时：0次; i∈[1,n]：i-1次；i&n：n次。 ∴时间复杂度: O(n)。(2) 按值查找按值查找是在链表中，查找是否有结点值等于给定 值key的结点? 若有，则返回首次找到的值为key的结点 的存储位置；否则返回NULL。查找时从开始结点出发， 沿链表逐个将结点的值和给定值key作比较。算法描述LNode *Locate_Node(LNode *L，int key)/* 在以L为头结点的单链表中查找值为key的第一个结点 */{ LNode *p=LC&while ( p!=NULL&& pC&data!=key) if (pC&data==key) else { printf(D所要查找的结点不存在!!\n‖); p=pC&retutn(NULL);}}算法的执行与形参key有关，平均时间复杂度为O(n)。3 单链表的插入插入运算是将值为e的新结点插入到表的第i个结 点的位置上，即插入到ai-1与ai之间。因此，必须首先找 到ai-1所在的结点p，然后生成一个数据域为e的新结点q， q结点作为p的直接后继结点。算法描述void Insert_LNode(LNode *L，int i，ElemType e)/* 在以L为头结点的单链表的第i个位置插入值为e的结点 */{ int j=0; LNode *p，*q;p=LC& while ( p!=NULL&& j&i-1) { p=pC& j++; }if (j!=i-1) printf(Di太大或i为0!!\n ‖); else { q=(LNode *)malloc(sizeof(LNode)); qC&data=e; qC&next=pC& pC&next=q; }}设链表的长度为n，合法的插入位置是1QiQn。算 法的时间主要耗费移动指针p上，故时间复杂度亦为 O(n)。4 单链表的删除⑴ 按序号删除删除单链表中的第i个结点。 为了删除第i个结点ai，必须找到结点的存储地址。 该存储地址是在其直接前趋结点ai-1的next域中，因此， 必须首先找到ai-1的存储位置p，然后令pC&next指向ai的 直接后继结点，即把ai从链上摘下。最后释放结点ai的 空间，将其归还给“存储池”。设单链表长度为n，则删去第i个结点仅当1QiQn 时是合法的。则当i=n+1时，虽然被删结点不存在，但 其前趋结点却存在，是终端结点。故判断条件之一是pC &next!=NULL。显然此算法的时间复杂度也是O(n)。算法描述void Delete_LinkList(LNode *L， int i)/* 删除以L为头结点的单链表中的第i个结点 */{ int j=1; LNode *p，*q; p=L; q=L-& while ( p-&next!=NULL&& j&i) { p=q; q=qC& j++; } if (j!=i) printf(Di太大或i为0!!\n ‖); else { pC&next=qC& free(q); } }⑵ 按值删除删除单链表中值为key的第一个结点。 与按值查找相类似，首先要查找值为key的结点是 否存在? 若存在，则删除；否则返回NULL。算法描述void Delete_LinkList(LNode *L，int key)/* 删除以L为头结点的单链表中值为key的第一个结点 */{LNode *p=L, *q=LC& while ( q!=NULL&& qC&data!=key) { p=q; q=qC& } if (qC&data==key) { p-&next=q-& free(q); } else printf(D所要删除的结点不存在!!\n‖);}算法的执行与形参key有关，平均时间复杂度为O(n)。 从上面的讨论可以看出，链表上实现插入和删除运 算，无需移动结点，仅需修改指针。解决了顺序表的插 入或删除操作需要移动大量元素的问题。变形之一：删除单链表中值为key的所有结点。 与按值查找相类似，但比前面的算法更简单。基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下 一个结点，直到所有的结点都检查。算法描述void Delete_LinkList_Node(LNode *L，int key)/* 删除以L为头结点的单链表中值为key的第一个结点 */{LNode *p=L, *q=LC& while ( q!=NULL) { if (qC&data==key) { p-&next=q-& free(q); q=p-& } else { p=q; q=qC& } }}变形之二：删除单链表中所有值重复的结点，使得所有结点的 值都不相同。与按值查找相类似，但比前面的算法更复杂。基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有 值和该结点的值相同，则删除之；然后检查下一个结点， 直到所有的结点都检查。算法描述void Delete_Node_value(LNode *L)/* 删除以L为头结点的单链表中所有值相同的结点 */{LNode *p=L-&next, *q, * while ( p!=NULL) /* 检查链表中所有结点 */ { *q=p, *ptr=pC&/* 检查结点p的所有后继结点ptr */while (ptr!=NULL) { if (ptrC&data==p-&data) { q-&next=ptr-& free(ptr); ptr=q-& } else { q= ptr=ptrC& } }p=p-& } }5 单链表的合并设有两个有序的单链表，它们的头指针分别是La 、 Lb，将它们合并为以Lc为头指针的有序链表。合并前 的示意图如图2-4所示。Lc pc La Lb -2 4 9pa -7 312 …… …… 23 ? 15 ?pb图2-4 两个有序的单链表La ，Lb的初始状态合并了值为-7，-2的结点后示意图如图2-5所示。La Lc Lb -2 pc图2-5pa -7 3 4 pb 12 9 …… ……23 ? 15 ?合并了值为-7 ，-2的结点后的状态算法说明算法中pa ，pb分别是待考察的两个链表的当前结 点，pc是合并过程中合并的链表的最后一个结点。算法描述LNode *Merge_LinkList(LNode *La， LNode *Lb)/* 合并以La, Lb为头结点的两个有序单链表 */{ LNode *Lc, *pa , *pb , *pc, *Lc=L pc=L pa=La-& pb=Lb-& while (pa!=NULL && pb!=NULL) { if (pa-&data&pb-&data) { pc-&next= pc= pa=pa-& }/* 将pa所指的结点合并，pa指向下一个结点 */if (pa-&data&pb-&data) { pc-&next= pc= pb=pb-& }/* 将pa所指的结点合并，pa指向下一个结点 */if (pa-&data==pb-&data) { pc-&next= pc= pa=pa-& ptr= pb=pb-& free(ptr) ; }/* 将pa所指的结点合并，pb所指结点删除 */} if (pa!=NULL) pc-&next= else pc-&next= /*将剩余的结点链上*/ free(Lb) ; return(Lc) ; }算法分析若La ，Lb两个链表的长度分别是m，n，则链表合 并的时间复杂度为O(m+n) 。2.3.3 循环链表循环链表(Circular Linked List)：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的 头结点，整个链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中 的其它结点，使得表处理更加方便灵活。 图2-6是带头结点的单循环链表的示意图。head head a1 a2 …… an空表图2-6 单循环链表示意图非空表循环链表的操作对于单循环链表，除链表的合并外，其它的操作和 单线性链表基本上一致，仅仅需要在单线性链表操作算 法基础上作以下简单修改： ⑴ 判断是否是空链表：head-&next== ⑵ 判断是否是表尾结点：p-&next==2.4 双向链表双向链表(Double Linked List) :指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的 指针域prior，一个指向其直接后继的指针域next。这样 形成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般增加头指针也能使双 链表上的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入的。1 双向链表的结点及其类型定义双向链表的结点的类型定义如下。其结点形式如 图2-7所示，带头结点的双向链表的形式如图2-8所示。typedef struct Dulnode { ElemT struct Dulnode *prior , * }DulNprior data nexthead ? ? ?空双向链表 图2-7 双向链表结点形式head a1 a2……an ?非空双向链表 图2-8 带头结点的双向链表形式双向链表结构具有对称性，设p指向双向链表中的 某一结点，则其对称性可用下式描述： (p-&prior)-&next=p=(p-&next)-&结点p的存储位置存放在其直接前趋结点p-&prior的 直接后继指针域中，同时也存放在其直接后继结点p&next的直接前趋指针域中。2 双向链表的基本操作(1) 双向链表的插入 将值为e的结点插入双向链表中。插入前后链表的变化如图2-9所示。p p ai+1 S e……ai…… ……图2-9 双向链表的插入ai S eai+1……① 插入时仅仅指出直接前驱结点，钩链时必须注意 先后次序是： “先右后左” 。部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode));S-&data=e;S-&next=p-& p-&next-&prior=S; p-&next=S; S-&prior=p;/* 钩链次序非常重要 */② 插入时同时指出直接前驱结点p和直接后继结点q， 钩链时无须注意先后次序。部分语句组如下：S=(DulNode *)malloc(sizeof(DulNode));S-&data=e; p-&next=S; S-&prior=p; S-&next=q; q-&prior=S;(2)双向链表的结点删除设要删除的结点为p ，删除时可以不引入新的辅助 指针变量，可以直接先断链，再释放结点。部分语句组 如下： p-&prior-&next=p-& p-&next-&prior=p-& free(p);注意：与单链表的插入和删除操作不同的是，在双向链 表中插入和删除必须同时修改两个方向上的指针域的指 向。2.5 一元多项式的表示和相加1 一元多项式的表示一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn ，由n+1个 系数唯一确定。则在计算机中可用线性表(p0 ，p1 ，p2 ， … ，pn )表示。既然是线性表，就可以用顺序表和链表 来实现。两种不同实现方式的元素类型定义如下：(1) 顺序存储表示的类型 typedef struct { /*系数部分*/ /*指数部分*/ } ElemT (2) 链式存储表示的类型 typedef struct ploy { /*系数部分*/ /*指数部分*/ struct ploy * } P2 一元多项式的相加不失一般性，设有两个一元多项式： P(x)=p0+p1x+p2x2+ … +pnxn ， Q(x)=q0+q1x+q2x2+ … +qmxm (m&n) R(x)=P(x)+ Q(x)R(x)由线性表R((p0+q0) ，(p1+q1) ，(p2+q2) ， … ， (pm+qm) ， … ， pn)唯一表示。⑴ 顺序存储表示的相加线性表的定义typedef struct{ ElemType a[MAX_SIZE] ; }S 用顺序表示的相加非常简单。访问第5项可直接访 问：L.a[4].coef ， L.a[4].expn(2) 链式存储表示的相加当采用链式存储表示时，根据结点类型定义，凡是 系数为0的项不在链表中出现，从而可以大大减少链表 的长度。一元多项式相加的实质是：C 指数不同： 是链表的合并。 C 指数相同： 系数相加，和为0，去掉结点，和不为0，修改结点的系数域。算法之一：就在原来两个多项式链表的基础上进行相加，相加 后原来两个多项式链表就不在存在。当然再要对原来 两个多项式进行其它操作就不允许了。算法描述Ploy *add_ploy(ploy *La， ploy *Lb)/* 将以La ，Lb为头指针表示的一元多项式相加 */{ ploy *Lc , *pc , *pa , *pb ,*Lc=pc=L pa=La-& pb=Lb-&while (pa!=NULL&&pb!=NULL){ if (pa-&expn&pb-&expn) { pc-&next= pc= pa=pa-& if (pa-&expn&pb-&expn) }/* 将pa所指的结点合并，pa指向下一个结点 */{ pc-&next= pc= pb=pb-&}/* 将pb所指的结点合并，pb指向下一个结点 */else { x=pa-&coef+pb-& if (abs(x)&=1.0e-6)/* 如果系数和为0，删除两个结点 */{ ptr= pa=pa-& free(ptr) ; ptr= pb=pb-& free(ptr) ; } else/* 如果系数和不为0，修改其中一个结 点的系数域，删除另一个结点 */{ pc-&next= pa-&coef=pc= pa=pa-& ptr= pb=pb-& free(pb) ; }} }/* end of while */if (pa==NULL) pc-&next= else pc-&next= return (Lc) ; }算法之二：对两个多项式链表进行相加，生成一个新的相加后 的结果多项式链表，原来两个多项式链表依然存在， 不发生任何改变，如果要再对原来两个多项式进行其 它操作也不影响。算法描述Ploy *add_ploy(ploy *La， ploy *Lb)/* 将以La ，Lb为头指针表示的一元多项式相加，生成一个 新的结果多项式 */{ ploy *Lc , *pc , *pa , *pb , * Lc=pc=(ploy *)malloc(sizeof(ploy)) ; pa=La-& pb=Lb-& while (pa!=NULL&&pb!=NULL){ if (pa-&expn&pb-&expn){ p=(ploy *)malloc(sizeof(ploy)) ; p-&coef=pa-& p-&expn=pa-& p-&next=NULL ;/* 生成一个新的结果结点并赋值 */pc-&next= pc= pa=pa-& }/* 生成的结点插入到结果链表的最后，pa指向下 一个结点 */if (pa-&expn&pb-&expn){ p=(ploy *)malloc(sizeof(ploy)) ;p-&coef=pb-& p-&expn=pb-& p-&next=NULL ;/* 生成一个新的结果结点并赋值 */pc-&next= pc= pb=pb-&/* 生成的结点插入到结果链表的最后，pb指 向下一个结点 */}if (pa-&expn==pb-&expn) { x=pa-&coef+pb-& if (abs(x)&=1.0e-6)/* 系数和为0，pa, pb分别直接后继结点 */{ pa=pa-& pb=pb-& } else /* 若系数和不为0，生成的结点插入到结果链表的最后， pa, pb分别直接后继结点 */{ p=(ploy *)malloc(sizeof(ploy)) ; p-&coef= p-&expn=pb-& p-&next=NULL ;/* 生成一个新的结果结点并赋值 */pc-&next= pc=pa=pa-& pb=pb-&} } }/* end of while */if (pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p-&coef=pb-& p-&expn=pb-&p-&next=NULL ;/* 生成一个新的结果结点并赋值 */pc-&next= pc= pb=pb-& }if (pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p-&coef=pb-& p-&expn=pa-& p-&next=NULL ;/* 生成一个新的结果结点并赋值 */pc-&next= pc= pa=pa-&}return (Lc) ;}第3章 栈和队列栈和队列是两种应用非常广泛的数据结构，它们都 来自线性表数据结构，都是“操作受限”的线性表。 栈在计算机的实现有多种方式：◆ 硬堆栈：利用CPU中的某些寄存器组或类似的硬 件或使用内存的特殊区域来实现。这类堆栈容量有限， 但速度很快； ◆ 软堆栈：这类堆栈主要在内存中实现。堆栈容量 可以达到很大。在实现方式上，又有动态方式和静态 方式两种。 本章将讨论栈和队列的基本概念、存储结构、基本 操作以及这些操作的具体实现。3.1 栈3.1.1 栈的基本概念1 栈的概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out) 或先进后出FILO (First In Last Out)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。设栈S=(a1，a2，…an)，则a1称 为栈底元素，an为栈顶元素，如图31所示。进栈（push）出栈(pop)top栈中元素按a1，a2，…an的次序 进栈，退栈的第一个元素应为栈顶元 素。即栈的修改是按后进先出的原则 bottom 进行的。 图3-1an ?? ai ?? a2 a1顺序栈示意图2 栈的抽象数据类型定义ADT Stack{ 数据对象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 }数据关系：R ={&ai-1, ai&|ai-1，ai∈D, i=2,3,…,n }基本操作：初始化、进栈、出栈、取栈顶元素等 } ADT Stack3.1.2 栈的顺序存储表示栈的顺序存储结构简称为顺序栈，和线性表相类似， 用一维数组来存储栈。根据数组是否可以根据需要增大， 又可分为静态顺序栈和动态顺序栈。 ◆ 静态顺序栈实现简单，但不能根据需要增大栈的 存储空间； ◆ 动态顺序栈可以根据需要增大栈的存储空间，但 实现稍为复杂。3.1.2.1 栈的动态顺序存储表示采用动态一维数组来存储栈。所谓动态，指的是栈 的大小可以根据需要增加。◆ 用bottom表示栈底指针，栈底固定不变的；栈顶 则随着进栈和退栈操作而变化。用top(称为栈顶指针 )指示当前栈顶位置。 ◆ 用top=bottom作为栈空的标记，每次top指向栈顶 数组中的下一个存储位置。 ◆ 结点进栈：首先将数据元素保存到栈顶(top所指 的当前位置)，然后执行top加1，使top指向栈顶的下 一个存储位置;◆ 结点出栈：首先执行top减1，使top指向栈顶元 素的存储位置，然后将栈顶元素取出。 图3-2是一个动态栈的变化示意图。top top bottomtop空栈 bottom 元素a进栈 topabottom 元素b，c进栈c b atop bottom 元素c退栈b abottom 元素d，e，f进栈f e d b a图3-2 (动态)堆栈变化示意图基本操作的实现1 栈的类型定义#define STACK_SIZE 100 #typedef int ElemT typedef struct sqstack/* 栈初始向量大小 */#define STACKINCREMENT 10 /* 存储空间分配增量 */{ ElemType *ElemType * }SqS/* 栈不存在时值为NULL *//* 栈顶指针 */ /* 当前已分配空间，以元素为单位 */2 栈的初始化Status Init_Stack(void){ SqStack S ;S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType)); if (! S.bottom) return ERROR; S.top=S. return OK ; }/* 栈空时栈顶和栈底指针相同 */S. stacksize=STACK_SIZE;3 压栈(元素进栈)Status push(SqStack S , ElemType e){ if (S.top-S.bottom&=S. stacksize-1){ S.bottom=(ElemType *)realloc((S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType)); /* 栈满，追加存储空间 */if (! S.bottom) return ERROR; S.top=S.bottom+S.S. stacksize+=STACKINCREMENT ;} *S.top=e; S.top++ ; /* return OK;栈顶指针加1，e成为新的栈顶 */4 弹栈(元素出栈)Status pop( SqStack S, ElemType *e )/*弹出栈顶元素*/{ if ( S.top== S.bottom ) return ERROR ; S.top-- ; e=*S. return OK ;/* 栈空，返回失败标志 */}3.1.2.2 栈的静态顺序存储表示采用静态一维数组来存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变 化的，◆ 栈底固定不变的；栈顶则随着进栈和退栈操作而 变化，用一个整型变量top(称为栈顶指针)来指示当 前栈顶位置。◆ 用top=0表示栈空的初始状态，每次top指向栈顶 在数组中的存储位置。◆ 结点进栈：首先执行top加1，使top指向新的栈 顶位置，然后将数据元素保存到栈顶(top所指的当前 位置)。◆ 结点出栈：首先把top指向的栈顶元素取出，然 后执行top减1，使top指向新的栈顶位置。 若栈的数组有Maxsize个元素，则top=Maxsize-1时 栈满。图3-3是一个大小为5的栈的变化示意图。toptop top bottom top bottom 空栈aTop=1 1个元素进栈c b atopb abottom Top=2 元素c进栈e d b aTop=4 栈满bottomTop=3 3个元素进栈bottom图3-3 静态堆栈变化示意图基本操作的实现1 栈的类型定义# define MAX_STACK_SIZE 100# typedef int ElemT/* 栈向量大小 */typedef struct sqstack{ ElemType stack_array[MAX_STACK_SIZE] ; }SqS2 栈的初始化SqStack Init_Stack(void){ SqStack S ;S.bottom=S.top=0 ; return(S) ; }3 压栈(元素进栈)Status push(SqStack S , ElemType e)/* 使数据元素e进栈成为新的栈顶 */{ if (S.top==MAX_STACK_SIZE-1)return ERROR; S.top++ ; return OK;/* /* 栈满，返回错误标志 */ 栈顶指针加1 */S.stack_array[S.top]= /* e成为新的栈顶 *//* 压栈成功 */}4 弹栈(元素出栈)Status pop( SqStack S, ElemType *e )/*弹出栈顶元素*/{ if ( S.top==0 ) return ERROR ; S.top-- ;/* 栈空，返回错误标志 */*e=S.stack_array[S.top] ;return OK ;}当栈满时做进栈运算必定产生空间溢出，简称“上 溢”。上溢是一种出错状态，应设法避免。当栈空时做退栈运算也将产生溢出，简称“下溢”。 下溢则可能是正常现象，因为栈在使用时，其初态或终 态都是空栈，所以下溢常用来作为控制转移的条件。3.1.3 栈的链式存储表示1 栈的链式表示栈的链式存储结构称为链栈，是运算受限的单链表。 其插入和删除操作只能在表头位置上进行。因此，链栈 没有必要像单链表那样附加头结点，栈顶指针top就是 链表的头指针。图3-4是栈的链式存储表示形式。链栈的结点类型说明如下： typedef struct Stack_Node { ElemT struct Stack_Node * } Stack_Ntop 空栈? topa4 a3 a2a1 ?图3-4 链栈存储形式非空栈2链栈基本操作的实现(1) 栈的初始化Stack_Node *Init_Link_Stack(void) { Stack_Node * top=(Stack_Node *)malloc(sizeof(Stack_Node )) ; top-&next=NULL ;return(top) ;}(2) 压栈(元素进栈)Status push(Stack_Node *top , ElemType e) { Stack_Node * p=(Stack_Node *)malloc(sizeof(Stack_Node)) ;if (!p) return ERROR;/* 申请新结点失败，返回错误标志 */p-&data= p-&next=top-& top-&next=/* 钩链 */return OK;}(3) 弹栈(元素出栈)Status pop(Stack_Node *top , ElemType *e)/* 将栈顶元素出栈 */{ Stack_Node *ElemTif (top-&next==NULL )return ERROR ; top-&next=p-& free(p) ;/* 栈空，返回错误标志 /* 取栈顶元素 */ */ */p=top-& e=p-&/*修改栈顶指针return OK ;}3.2 栈的应用由于栈具有的“后进先出”的固有特性，因此，栈 成为程序设计中常用的工具和数据结构。以下是几个栈 应用的例子。3.2.1 数制转换十进制整数N向其它进制数d(二、八、十六)的转换 是计算机实现计算的基本问题。 转换法则：该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d 其中：div为整除运算,mod为求余运算例如 (1348)10= (2504)8，其运算过程如下：n n div 8 n mod 81348168 21 216821 2 040 5 2采用静态顺序栈方式实现 void conversion(int n , int d)/*将十进制整数N转换为d(2或8)进制数*/{ SqStack S ;int k, * }S=Init_Stack(); while (n&0) { k=n% push(S , k) ; n=n//* 求出所有的余数，进栈 */while (S.top!=0){ pop(S, e) ;/* 栈不空时出栈，输出 */printf(D%1d‖ , *e) ; } }3.2.2括号匹配问题在文字处理软件或编译程序设计时，常常需要检查 一个字符串或一个表达式中的括号是否相匹配?匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以 在从左至右扫描过程中把所遇到的左括号存放到堆栈中。 每当遇到一个右括号时，就将它与栈顶的左括号(如果 存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到 的左括号进行匹配，若匹配成功，继续读入；否则匹配 失败，返回FLASE。算法描述#define TRUE 0 #define FLASE -1SqStack S ;S=Init_Stack() ; /*堆栈初始化*/ int Match_Brackets( ) { char ch , scanf(D%c‖ , &ch) ;while (asc(ch)!=13){ if ((ch==?(‘)||(ch==?[‘)) push(S , ch) ; else if (ch==?]‘) { x=pop(S) ; if (x!=?[‘) { printf(D‘[‘括号不匹配”) ; return FLASE ; } } else if (ch==?)‘) { x=pop(S) ; if (x!=?(‘) { printf(D‘(‘括号不匹配”) ; return FLASE ;} } }if (S.top!=0) { printf(D括号数量不匹配！”) ; return FLASE ; } else return TRUE ; }3.2.2 栈与递归调用的实现栈的另一个重要应用是在程序设计语言中实现递归 调用。递归调用：一个函数(或过程)直接或间接地调用自己本身，简称递归(Recursive)。 递归是程序设计中的一个强有力的工具。因为递归 函数结构清晰，程序易读，正确性很容易得到证明。 为了使递归调用不至于无终止地进行下去，实际上 有效的递归调用函数(或过程)应包括两部分：递推规则 (方法)，终止条件。例如：求n!1当n=0时终止条件 递推规则Fact(n)=n*fact(n-1) 当n&0时为保证递归调用正确执行，系统设立一个“递归工 作栈”，作为整个递归调用过程期间使用的数据存储区。 每一层递归包含的信息如：参数、局部变量、上一 层的返回地址构成一个“工作记录” 。每进入一层递 归，就产生一个新的工作记录压入栈顶；每退出一层递 归，就从栈顶弹出一个工作记录。从被调函数返回调用函数的一般步骤：(1) 若栈为空，则执行正常返回。⑵ 从栈顶弹出一个工作记录。 ⑶ 将“工作记录”中的参数值、局部变量值赋给相 应的变量；读取返回地址。 ⑷ 将函数值赋给相应的变量。(5) 转移到返回地址。3.3队 列3.3.1 队列及其基本概念1 队列的基本概念队列(Queue)：也是运算受限的线性表。是一种先 进先出(First In First Out ，简称FIFO)的线性表。只允 许在表的一端进行插入，而在另一端进行删除。 队首(front) ：允许进行删除的一端称为队首。 队尾(rear) ：允许进行插入的一端称为队尾。 例如：排队购物。操作系统中的作业排队。先进入 队列的成员总是先离开队列。队列中没有元素时称为空队列。在空队列中依次 加入元素a1, a2, …, an之后，a1是队首元素，an是队尾元 素。显然退出队列的次序也只能是a1, a2, …, an ，即队 列的修改是依先进先出的原则进行的，如图3-5所示。出队a1 , a2 , … , an队首 队尾入队图3-5 队列示意图2 队列的抽象数据类型定义ADT Queue{ 数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n &= 0 }数据关系：R = {&ai-1, ai& | ai-1, ai∈D, i=2,3,…,n } 约定a1端为队首，an端为队尾。 基本操作：Create()：创建一个空队列；EmptyQue()：若队列为空，则返回true ，否则返 回flase ； ?? InsertQue(x) ：向队尾插入元素x；DeleteQue(x) ：删除队首元素x；} ADT Queue3.3.2 队列的顺序表示和实现利用一组连续的存储单元(一维数组) 依次存放从队 首到队尾的各个元素，称为顺序队列。对于队列，和顺序栈相类似，也有动态和静态之分。 本部分介绍的是静态顺序队列，其类型定义如下：#define MAX_QUEUE_SIZE 100typedef struct queue { ElemType Queue_array[MAX_QUEUE_SIZE] ;}SqQ3.3.2.1 队列的顺序存储结构设立一个队首指针front ，一个队尾指针rear ，分 别指向队首和队尾元素。 ◆ 初始化：front=rear=0。 ◆ 入队：将新元素插入rear所指的位置，然后rear加 1。 ◆ 出队：删去front所指的元素，然后加1并返回被删 元素。 ◆ 队列为空：front=rear。 ◆ 队满：rear=MAX_QUEUE_SIZE-1或front=rear。在非空队列里，队首指针始终指向队头元素，而队 尾指针始终指向队尾元素的下一位置。顺序队列中存在“假溢出”现象。因为在入队和出 队操作中，头、尾指针只增加不减小，致使被删除元素 的空间永远无法重新利用。因此，尽管队列中实际元素 个数可能远远小于数组大小，但可能由于尾指针巳超出 向量空间的上界而不能做入队操作。该现象称为假溢出。 如图3-6所示是数组大小为5的顺序队列中队首、队尾指 针和队列中元素的变化情况。Q.rearQ.rear Q.rear a3 a2 a1 Q.frontQ.fronta5 a4Q.rearQ.front (a) 空队列 Q.front(b) 入队3个元素 (c) 出队3个元素(d) 入队2个元素图3-6 队列示意图3.3.2.2循环队列为充分利用向量空间，克服上述“假溢出”现象的 方法是：将为队列分配的向量空间看成为一个首尾相接 的圆环，并称这种队列为循环队列(Circular Queue)。 在循环队列中进行出队、入队操作时，队首、队尾 指针仍要加1，朝前移动。只不过当队首、队尾指针指 向向量上界(MAX_QUEUE_SIZE-1)时，其加1操作的 结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if (i+1==MAX_QUEUE_SIZE) i=0;elsei++ ;其中： i代表队首指针(front)或队尾指针(rear)用模运算可简化为：i=(i+1)%MAX_QUEUE_SIZE ; 显然，为循环队列所分配的空间可以被充分利用， 除非向量空间真的被队列元素全部占用，否则不会上溢 。因此，真正实用的顺序队列是循环队列。例：设有循环队列QU[0，5]，其初始状态是front=rear=0，各种操作后队列的头、尾指针的状态变 化情况如下图3-7所示。rear front front0 54d1 2 3 rear 50 41 3e2 b 501 2 bfrontg4rear3g(a) 空队列(b) d, e, b, g入队(c) d, e出队rearreark j 50 41front 2 bk j 5k1200 41 3r2 p rearj 5front3igfronti43i(d) i, j, k入队(e) b, g出队(f) r, p, s, t入队图3-7 循环队列操作及指针变化情况入队时尾指针向前追赶头指针，出队时头指针向前 追赶尾指针，故队空和队满时头尾指针均相等。因此， 无法通过front=rear来判断队列“空”还是“满”。解 决此问题的方法是：约定入队前，测试尾指针在循环意 义下加1后是否等于头指针，若相等则认为队满。即： ◆ rear所指的单元始终为空。◆ 循环队列为空：front=rear 。 ◆ 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。循环队列的基本操作1 循环队列的初始化SqQueue Init_CirQueue(void) { SqQueue Q ; Q.front=Q.rear=0; return(Q) ; }2 入队操作Status Insert_CirQueue(SqQueue Q , ElemType e)/* 将数据元素e插入到循环队列Q的队尾 */{ if ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)return ERROR;/* 队满，返回错误标志*/Q.Queue_array[Q.rear]= /* 元素e入队 */Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;/* 队尾指针向前移动 */return OK;/* 入队成功*/}3 出队操作Status Delete_CirQueue(SqQueue Q, ElemType *x )/* 将循环队列Q的队首元素出队 */{ if (Q.front+1== Q.rear)return ERROR ;/* 队空，返回错误标志*/*x=Q.Queue_array[Q.front] ; /* 取队首元素 */Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;/* 队首指针向前移动 */return OK ; }3.3.3 队列的链式表示和实现1 队列的链式存储表示队列的链式存储结构简称为链队列，它是限制仅 在表头进行删除操作和表尾进行插入操作的单链表。需要两类不同的结点：数据元素结点，队列的队首 指针和队尾指针的结点，如图3-8所示。 数据元素结点类型定义： typedef struct Qnode { ElemType }QNdata数据元素结点front rear指针结点struct Qnode *图3-8 链队列结点示意图指针结点类型定义：typedef struct link_queue{ QNode *front , * }Link_Q2 链队运算及指针变化链队的操作实际上是单链表的操作，只不过是删 除在表头进行，插入在表尾进行。插入、删除时分别修 改不同的指针。链队运算及指针变化如图3-9所示。front rear(a) 空队列∧front rear(b) x入队x ∧front rearx(c) y再入队y ∧front rearx(d) x出队y ∧图3-9 队列操作及指针变化3 链队列的基本操作⑴ 链队列的初始化LinkQueue *Init_LinkQueue(void){ LinkQueue *Q ; QNode *p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */ p-&next=NULL ; Q=(LinkQueue *)malloc(sizeof(LinkQueue)) ;/* 开辟链队的指针结点 */Q.front=Q.rear=return(Q) ; }⑵ 链队列的入队操作在已知队列的队尾插入一个元素e ，即修改队尾指 针(Q.rear)。 Status Insert_CirQueue(LinkQueue *Q , ElemType e)/* 将数据元素e插入到链队列Q的队尾 */{ p=(QNode *)malloc(sizeof(QNode)) ;if (!p) return ERROR;/* 申请新结点失败，返回错误标志 */p-&data= p-&next=NULL ; return OK;}/* 形成新结点 */Q.rear-&next= Q.rear= /* 新结点插入到队尾 */⑶ 链队列的出队操作Status Delete_LinkQueue(LinkQueue *Q, ElemType *x) { QNode * if (Q.front==Q.rear) return ERROR ; /* 队空 */ p=Q.front-& /* 取队首结点 */ *x=p-&Q.front-&next=p-&/* 修改队首指针 */if (p==Q.rear) Q.rear=Q./* 当队列只有一个结点时应防止丢失队尾指针 */free(p) ; return OK ;⑷ 链队列的撤消void Destroy_LinkQueue(LinkQueue *Q )/* 将链队列Q的队首元素出队 */{ while (Q.front!=NULL) { Q.rear=Q.front-&/* 令尾指针指向队列的第一个结点 */free(Q.front); Q.ront=Q. }/* 每次释放一个结点 *//* 第一次是头结点，以后是元素结点 */}第5章 数组和广义表数组是一种人们非常熟悉的数据结构，几乎所有的 程序设计语言都支持这种数据结构或将这种数据结构 设定为语言的固有类型。数组这种数据结构可以看成 是线性表的推广。科学计算中涉及到大量的矩阵问题，在程序设计 语言中一般都采用数组来存储，被描述成一个二维数 组。但当矩阵规模很大且具有特殊结构(对角矩阵、三 角矩阵、对称矩阵、稀疏矩阵等)，为减少程序的时间 和空间需求，采用自定义的描述方式。 广义表是另一种推广形式的线性表，是一种灵活 的数据结构，在许多方面有广泛的应用。5.1 数组的定义数组是一组偶对(下标值，数据元素值)的集合。 在数组中，对于一组有意义的下标，都存在一个与其对 应的值。一维数组对应着一个下标值，二维数组对应着 两个下标值，如此类推。数组是由n(n&1)个具有相同数据类型的数据元素a1， a2，…，an组成的有序序列，且该序列必须存储在一块 地址连续的存储单元中。◆ 数组中的数据元素具有相同数据类型。 ◆ 数组是一种随机存取结构，给定一组下标，就可 以访问与其对应的数据元素。 ◆ 数组中的数据元素个数是固定的。5.1.1 数组的抽象数据类型定义1 抽象数据类型定义ADT Array{数据对象：ji= 0,1,…,bi-1 , 1,2, …,D = { aj1j2…jn | n&0称为数组的维数，bi是数组第i维的 长度，ji是数组元素第i维的下标，aj1j2…jn∈ElemSet } 数据关系：R = {R1, R2, …, Rn}Ri={&aj1j2 …ji…jn , aj1j2 …ji+1…jn&|0QjkQbk-1 ， 1QkQn且k≠i，0QjiQbi-2， aj1j2 …ji+1…jn∈D }基本操作： ……由上述定义知，n维数组中有b1?b2 ? … ? bn个数据 元素，每个数据元素都受到n维关系的约束。2直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长 的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)m?n，则 A=(α1，α2，…，αp) (p=m或n) 其中每个数据元素αj是一个列向量(线性表) ：αj =(a1j ，a2j ，…，amj) 1QjQn或是一个行向量： αi =(ai1 ，ai2 ，…，ain) 如图5-1所示。 1QiQma11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn(a) 矩阵表示形式a11 a12 … a1na21 a22 … a2nA= …………… am1 am2 … amn列向量的一维数组形式(b)A=a11 a21 ┆ am1(c)a12 a1n a22 ┆ a2n ┆ ┆ ┆ am2 ┆ amn行向量的一维数组形式图5-1 二维数组图例形式5.2 数组的顺序表示和实现数组一般不做插入和删除操作，也就是说，数组 一旦建立，结构中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储的方法来表示数 组。问题：计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有 个次序约定问题。即必须按某种次序将数组元素排成一 列序列，然后将这个线性序列存放到内存中。 二维数组是最简单的多维数组，以此为例说明多维 数组存放(映射)到内存一维结构时的次序约定问题。通常有两种顺序存储方式⑴ 行优先顺序(Row Major Order) ：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。对 二维数组，按行优先顺序存储的线性序列为： a11,a12,…,a1n, a21,a22,…a2n ,……, am1,am2,…,amn PASCAL、C是按行优先顺序存储的，如图5-2(b)示。⑵ 列优先顺序(Column Major Order) ：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量 之后，对二维数组，按列优先顺序存储的线性序列为： a11,a21,…,am1, a12,a22,…am2, ……, an1,an2,…,anmFORTRAN是按列优先顺序存储的，如图5-2(c)。a11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn(a) 二维数组的表示形式…a11 a12… a1n a21 a22 … a2n 第 1 行 第 2 行…a11 a21… am1 a12 a22 … am2 第 1 列 第 2 列┆┆第 m 行┆┆第 n 列am1 am2 … Amna1m a2m … amn图5-2 二维数组及其顺序存储图例形式……(b) 行优先顺序存储(c) 列优先顺序存储设有二维数组A=(aij)m?n，若每个元素占用的存储单 元数为l(个)，LOC[a11]表示元素a11的首地址，即数组 的首地址。1以“行优先顺序”存储⑴ 第1行中的每个元素对应的(首)地址是：LOC[a1j]=LOC[a11]+(j-1)?l LOC[a2j]=LOC[a11]+n?l +(j-1)?l ……… j=1,2, …,n j=1,2, …,n (2) 第2行中的每个元素对应的(首)地址是：⑶ 第m行中的每个元素对应的(首)地址是：LOC[amj]=LOC[a11]+(m-1)?n?l +(j-1)?l …,n j=1,2,由此可知，二维数组中任一元素aij的(首)地址是：LOC[aij]=LOC[a11]+[(i-1)?n +(j-1)]?li=1,2, …,m j=1,2, …,n(5-1)根据(5-1)式，对于三维数组A=(aijk)m?n?p，若每个 元素占用的存储单元数为l(个)，LOC[a111]表示元素a111 的首地址，即数组的首地址。以“行优先顺序”存储在 内存中。 三维数组中任一元素aijk的(首)地址是： LOC(aijk)=LOC[a111]+[(i-1)?n?p+(j-1)?p+(k-1)]?l (52) 推而广之，对n维数组A=(aj1j2…jn) ，若每个元素占 用的存储单元数为l(个)，LOC[a11 …1]表示元素a11 …1的 首地址。则 以“行优先顺序”存储在内存中。n维数组中任一元素aj1j2…jn的(首)地址是： LOC[aj1j2…jn]=LOC[a11 …1]+[(b2?…?bn)?(j1-1) + (b3?…?bn)?(j2-1)+ …+ bn?(jn-1-1)+ (jn-1)] ?l(5-3)2以“列优先顺序”存储⑴ 第1列中的每个元素对应的(首)地址是： LOC[aj1]=LOC[a11]+(j-1)?l j=1,2, …,m (2) 第2列中的每个元素对应的(首)地址是：LOC[aj2]=LOC[a11]+m?l +(j-1)?l………j=1,2, …,m⑶ 第n列中的每个元素对应的(首)地址是： LOC[ajn]=LOC[a11]+ (n-1)?m?l +(j-1)?l …,m LOC[aij]=LOC[a11]+[(i-1)?m+(j-1)]?l i=1,2, …,n j=1,2, …,m j=1,2,由此可知，二维数组中任一元素aij的(首)地址是：(5-1)5.3 矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数 学对象，在高级语言编程时，通常将一个矩阵描述为一 个二维数组。这样，可以对其元素进行随机存取，各种 矩阵运算也非常简单。对于高阶矩阵，若其中非零元素呈某种规律分布或 者矩阵中有大量的零元素，若仍然用常规方法存储，可 能存储重复的非零元素或零元素，将造成存储空间的大 量浪费。对这类矩阵进行压缩存储：◆ 多个相同的非零元素只分配一个存储空间；◆ 零元素不分配空间。5.3.1 特殊矩阵特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵。1对称矩阵若一个n阶方阵A=(aij)n?n中的元素满足性质： aij=aji 1Qi,jQn且i≠j 则称A为对称矩阵，如图5-3所示。1 5 A= 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 a11 a21 a22 A= a31 a32 a33 ……… … an1 an2 … ann图5-3 对称矩阵示例对称矩阵中的元素关于主对角线对称，因此，让 每一对对称元素aij和aji(i≠j)分配一个存储空间，则n2个 元素压缩存储到n(n+1)/2个存储空间，能节约近一半的 存储空间。 不失一般性，假设按“行优先顺序”存储下三角 形(包括对角线)中的元素。 设用一维数组(向量)sa[0…n(n+1)/2]存储n阶对称 矩阵，如图5-4所示。为了便于访问，必须找出矩阵A 中的元素的下标值（i,j）和向量sa[k]的下标值k之间的 对应关系。K 1 sa 2 3 4 … n(n-1)/2 … n(n+1)/2 a11 a21 a22 a31 a32 a33 … an1 an2 … ann图5-4 对称矩阵的压缩存储示例若iRj：ai j在下三角形中，直接保存在sa中。ai j之 前的i-1行共有元素个数： 1+2+…+(i-1)=i?(i-1)/2 而在第i行上，ai j之前恰有j-1个元素，因此，元素ai j保 存在向量sa中时的下标值k之间的对应关系是： k=i?(i-1)/2+j-1 iRj 若i&j：则aij是在上三角矩阵中。因为aij=aji，在向 量sa中保存的是aji 。依上述分析可得： k=j?(j-1)/2+i-1 i&j 对称矩阵元素ai j保存在向量sa中时的下标值k与 （i,j）之间的对应关系是： i?(i-1)/2+j-1K=当iRj时1Qi,jQ nj?(j-1)/2+i-1当i&j时(5-4)根据上述的下标对应关系，对于矩阵中的任意元 素aij，均可在一维数组sa中唯一确定其位置k；反之， 对所有k=1,2, …,n(n+1)/2，都能确定sa[k]中的元素在矩 阵中的位置(i,j)。 称sa[0…n(n+1)/2]为n阶对称矩阵A的压缩存储。2三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元 素均为常数c(一般为0)。下三角矩阵正好相反，它的主 对角线上方均为常数，如图5-5所示。a11 a12 … a1n c a22 … a2n … … … c c … ann(a) 上三角矩阵示例a11 c … c a21 a22 … c … … … an1 an2 … ann(b) 下三角矩阵示例图5-5 三角矩阵示例三角矩阵中的重复元素c可共享一个存储空间，其 余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存 储到向量sa[0…n(n+1)/2]中，其中c存放在向量的第1个 分量中。 上三角矩阵元素ai j保存在向量sa中时的下标值k与 （i,j）之间的对应关系是：i?(i-1)/2+j-1 K= n?(n+1)/2当iRj时1Qi,jQ n当i&j时(5-5)下三角矩阵元素ai j保存在向量sa中时的下标值k与 （i,j）之间的对应关系是：i?(i-1)/2+j-1 K= n?(n+1)/2 当iQj时 当i&j时1Qi,jQn(5-6)3对角矩阵矩阵中，除了主对角线和主对角线上或下方若干 条对角线上的元素之外，其余元素皆为零。即所有的非 零元素集中在以主对角线为了中心的带状区域中，如图 5-6所示。a11 a12 0 …. 0 a21 a22 a23 0 …. 0 0 a32 a33 a34 0 …. 0 … … … …. 0 …. 0 …. 0 an-1 n-2 an-1 n-1 an-1 n 0 0 an n-1 an nA=图5-6 三对角矩阵示例如上图三对角矩阵，非零元素仅出现在主对角(ai i,1QiQn)上、主对角线上的那条对角线(ai i+1,1QiQn-1) 、 主对角线下的那条对角线上(ai+1 i,1QiQn-1)。显然，当| i-j |&1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述 条件： 当| i-j |&(k-1)/2时， ai j=0对角矩阵可按行优先顺序或对角线顺序，将其压缩 存储到一个向量中，并且也能找到每个非零元素和向量 下标的对应关系。 仍然以三对角矩阵为例讨论。 当i=1，j=1、2，或i=n， j=n-1、n或1&i&n-1,j=i-1、i、i+1的元素aij外，其余元素都是0。对这种矩阵，当以按“行优先顺序”存储时， 第1 行和第n行是2个非零元素，其余每行的非零元素都要是 3个，则需存储的元素个数为3n-2。K sa 1 2 3 4 5 6 7 8 … 3n-3 3n-2 a11 a12 a21 a22 a23 a32 a33 a34 … an n-1 ann图5-7 三对角矩阵的压缩存储示例如图5-7所示三对角矩阵的压缩存储形式。数组sa 中的元素sa[k]与三对角矩阵中的元素aij存在一一对应关 系，在aij之前有i-1行,共有3?i-1个非零元素，在第i行， 有j-i+1个非零元素，这样，非零元素aij的地址为：LOC[ai j] =LOC[a11] +[3?i-1+(j-i+1)]?l=LOC[a11]+(2?i+j)?l上例中，a34对应着sa[10] , k=2?i+j=2?3+4=10 称sa[0…3?n-2]是n阶三对角矩阵A的压缩存储。 上述各种特殊矩阵，其非零元素的分布都是有规律 的，因此总能找到一种方法将它们压缩存储到一个向量 中，并且一般都能找到矩阵中的元素与该向量的对应关 系，通过这个关系，仍能对矩阵的元素进行随机存取。5.3.2稀疏矩阵稀疏矩阵(Sparse Matrix)：对于稀疏矩阵，目前还没有一个确切的定义。设矩阵A是一个n?m的矩阵中有 s个非零元素，设 δ=s/(n?m)，称δ为稀疏因子，如果 某一矩阵的稀疏因子δ满足δQ0.05时称为稀疏矩阵，如 图5-8所示。0 12 0 0 -3 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4A= 0 0 24 0 0 2 0 00 18 0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 0 0 -6 0 0 0 0图5-8 稀疏矩阵示例5.3.2.1稀疏矩阵的压缩存储对于稀疏矩阵，采用压缩存储方法时，只存储非0 元素。必须存储非0元素的行下标值、列下标值、元素 值。因此，一个三元组(i, j, aij)唯一确定稀疏矩阵的一 个非零元素。 如图5-8的稀疏矩阵A的三元组线性表为：( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )1 三元组顺序表若以行序为主序，稀疏矩阵中所有非0元素的三元组， 就可以得构成该稀疏矩阵的一个三元组顺序表。1三元组顺序表若以行序为主序，稀疏矩阵中所有非0元素的三元 组，就可以得构成该稀疏矩阵的一个三元组顺序表。 相应的数据结构定义如下：⑴ 三元组结点定义#define MAX_SIZE 101ttypedef struct{ }T/* 行下标 */ /* 列下标 *//* 元素值 */⑵ 三元组顺序表定义typedef struct {/* 行数 */ }TM/* 列数 *//* 非0元素个数 */Triple data[MAX_SIZE] ; 图5-8所示的稀疏矩阵及其相应的转置矩阵所对应 的三元组顺序表如图5-9所示。7 8 9 1 1 3 3 4 4 5 6 7rn行数 cn列数 tn元素个数 2 12 3 9 1 -3 8 4 3 24 6 2 2 18 7 -7 4 -68 7 9 1 2 2 3 3 4 6 7 8rn行数 cn列数 tn元素个数 3 -3 1 12 5 18 1 9 4 24 7 -6 4 2 6 -7 2 4row col value(a) 原矩阵的三元组表row col value(b)转置矩阵的三元组表图5-9 稀疏矩阵及其转置矩阵的三元组顺序表矩阵的运算包括矩阵的转置、矩阵求逆、矩阵的加 减、矩阵的乘除等。在此，先讨论在这种压缩存储结构 下的求矩阵的转置的运算。一个m?n的矩阵A，它的转置B是一个n?m的矩阵， 且b[i][j]=a[j][i]，0QiQn，0QjQm，即B的行是A的列， B的列是A的行。 设稀疏矩阵A是按行优先顺序压缩存储在三元组表 a.data中，若仅仅是简单地交换a.data中i和j的内容，得 到三元组表b.data，b.data将是一个按列优先顺序存储 的稀疏矩阵B，要得到按行优先顺序存储的b.data，就 必须重新排列三元组表b.data中元素的顺序。求转置矩阵的基本算法思想是：① 将矩阵的行、列下标值交换。即将三元组表中的 行、列位置值i 、j相互交换；② 重排三元组表中元素的顺序。即交换后仍然是按 行优先顺序排序的。方法一： 算法思想：按稀疏矩阵A的三元组表a.data中的列次序依次找到相应的三元组存入b.data中。每找转置后矩阵的一个三元组，需从头至尾扫描 整个三元组表a.data 。找到之后自然就成为按行优先的 转置矩阵的压缩存储表示。按方法一求转置矩阵的算法如下：void TransMatrix(TMatrix a , TMatrix b){ int p , q , b.rn=a. b.cn=a. b.tn=a./* 置三元组表b.data的行、列数和非0元素个数 */if (b.tn==0)printf(D The Matrix A=0\n‖ );else{ q=0; for (col=1; col&=a. col++)/* 每循环一次找到转置后的一个三元组 */for (p=0 ;p&a. p++)/* 循环次数是非0元素个数 */if (a.data[p].col==col) { b.data[q].row=a.data[p]. b.data[q].col=a.data[p]. b.data[q].value=a.data[p].q++ ;} } }算法分析：本算法主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(cn?tn)，即矩阵 的列数和非0元素的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=1; col&=++col)for(row=0 ; row&=++row)b[col][row]=a[row][col] ; 其时间复杂度为O(n?m)。当非零元素的个数tn和 m?n同数量级时，算法TransMatrix的时间复杂度为 O(m?n2)。由此可见，虽然节省了存储空间，但时间复杂度却 大大增加。所以上述算法只适合于稀疏矩阵中非0元素 的个数tn远远小于m?n的情况。方法二(快速转置的算法)算法思想：直接按照稀疏矩阵A的三元组表a.data的次序依次顺序转换，并将转换后的三元组放置于三元组表 b.data的恰当位置。前提：若能预先确定原矩阵A中每一列的(即B中每一行)第一个非0元素在b.data中应有的位置，则在作转 置时就可直接放在b.data中恰当的位置。因此，应先求 得A中每一列的非0元素个数。 附设两个辅助向量num[ ]和cpot[ ] 。◆ num[col]：统计A中第col列中非0元素的个数；◆ cpot[col] ：指示A中第一个非0元素在b.data中的 恰当位置。显然有位置对应关系：cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2QcolQa.cn例图5-8中的矩阵A和表5-9(a)的相应的三元组表可 以求得num[col]和cpot[col]的值如表5-1：表5-1 num[col]和cpot[col]的值表col 1 2 3 4 5 6 7 8 num[col] 1 2 2 1 0 1 1 1 cpot[col] 1 3 5 6 6 7 8 9快速转置算法如下：void FastTransMatrix(TMatrix a, TMatrix b) { int p , q , col , int num[MAX_SIZE] , copt[MAX_SIZE] ; b.rn=a. b.cn=a. b.tn=a./* 置三元组表b.data的行、列数和非0元素个数 */if (b.tn==0) printf(D The Matrix A=0\n‖ ) ; else { for (col=1 ; col&=a. ++col) num[col]=0 ;/* 向量num[]初始化为0 */for (k=1 ; k&=a. ++k) ++num[ a.data[k].col] ;/* 求原矩阵中每一列非0元素个数 */for (cpot[0]=1, col=2 ; col&=a. ++col) cpot[col]=cpot[col-1]+num[col-1] ;/* 求第col列中第一个非0元在b.data中的序号 */for (p=1 ; p&=a. ++p){ col=a.data[p]. q=cpot[col] ; b.data[q].row=a.data[p]. b.data[q].col=a.data[p]. b.data[q].value=a.data[p].++cpot[col] ;} } }/*至关重要!!当本列中*/2 行逻辑链接的三元组顺序表将上述方法二中的辅助向量cpot[ ]固定在稀疏矩阵 的三元组表中，用来指示“行”的信息。得到另一种 顺序存储结构：行逻辑链接的三元组顺序表。其类型 描述如下：#define MAX_ROW 100typedef struct { Triple data[MAX_SIZE] ; int int rpos[MAX_ROW]; rn ,cn ,/* 非0元素的三元组表 */ /* 各行第一个非0位置表 *//* 矩阵的行、列数和非0元个数 */}RLSM稀疏矩阵的乘法设有两个矩阵：A=(aij)m?n ，B=(bij)n?p 则： C=(cij)m?p 其中 cij=∑aik?bkj 1QkQn ， 1QiQm ，1QjQp 经典算法是三重循环： for ( i=1 ; i&= ++i) for ( j=1 ; j&= ++j) { c[i][j]=0 ; for ( k=1 ; k&= ++k) c[i][j]= c[i][j]+a[i][k]?b[k][j]; } 此算法的复杂度为O(m?n?p)。设有两个稀疏矩阵A=(aij)m?n ，B=(bij)n?p ，其存储 结构采用行逻辑链接的三元组顺序表。算法思想：对于A中的每个元素a.data[p](p=1, 2, … ,a.tn)，找到B中所有满足条件：a.data[p].col=b.data[q].row的元素b.data[q]，求得 a.data[p].value?b.data[q].value，该乘积是cij中的一部 分。求得所有这样的乘积并累加求和就能得到cij。 为得到非0的乘积，只要对a.data[1…a.tn] 中每个 元素(i，k，aik)(1QiQa.rn，1QkQa.cn) ，找到b.data 中所有相应的元素(k，j，bkj)(1QkQb.rn，1QjQb.cn) 相乘即可。则必须知道矩阵B中第k行的所有非0元素， 而b.rpos[ ]向量中提供了相应的信息。b.rpos[row]指示了矩阵B的第row行中第一个非0元 素在b.data[ ]中的位置(序号)，显然，b.rpos[row+1]-1 指示了第row行中最后一个非0元素在b.data[ ]中的位置( 序号) 。最后一行中最后一个非0元素在b.data[ ]中的位 置显然就是b.tn 。 两个稀疏矩阵相乘的算法如下： void MultsMatrix(RLSMatrix a, RLSMatrix b, RLSMatrix c)/* 求矩阵A 、B的积C=A?B，采用行逻辑链接的顺序表 */{ elemtype ctemp[Max_Size] ;int p , q , arow , ccol , brow , if (a.cn!=b.rn) { printf(DError\n‖) ; exit(0); }else{c.rn=a. c.cn=b. c.tn=0 ; if (a.tn*b.tn!=0)/* 初始化C *//* C 是非零矩阵 */{ for (arow=1 ; arow&=a. ++arow) { ctemp[arow]=0 ; /* 当前行累加器清零 */c.rpos[arow]=c.tn+1; p=a.rops[arow];for ( ; p&a.rpos[arow+1];++p)/* 对第arow行的每一个非0元素 */{ brow=a.data[p]./* 找到元素在b.data[]中的行号 */if (brow&b.cn) t=( b.rpos[brow+1];for (q=b.rpos[brow] ; q& ++q){ ccol=b.data[q]./* 积元素在c中的列号 */ctemp[ccol]+=a.data[p].value*b.data[q]. }}/* 求出c中第arow行中的非0元素 */for (ccol=1 ; ccol&=c. ++ccol) if ( ctemp[ccol] !=0 ) { if ( ++c.tn&MAX_SIZE) { printf(DError\n‖) ; exit(0); }elsec.data[c.tn]=(arow , ccol , ctemp[ccol]) ; } } } }3 十字链表对于稀疏矩阵，当非0元素的个数和位置在操作过 程中变化较大时，采用链式存储结构表示比三元组的 线性表更方便。 矩阵中非0元素的结点所含的域有：行、列、值、 行指针(指向同一行的下一个非0元)、列指针(指向同一 列的下一个非0元)。其次，十字交叉链表还有一个头结 点，结点的结构如图5-10所示。row col value down right(a) 结点结构rn cn tn down right(b) 头结点结构图5-10 十字链表结点结构由定义知，稀疏矩阵中同一行的非0元素的由right 指针域链接成一个行链表， 由down指针域链接成一个 列链表。则每个非0元素既是某个行链表中的一个结点， 同时又是某个列链表中的一个结点，所有的非0元素构 成一个十字交叉的链表。称为十字链表。 此外，还可用两个一维数组分别存储行链表的头指 针和列链表的头指针。对于图5-11(a)的稀疏矩阵A ，对 应的十字交叉链表如图5-11(b)所示，结点的描述如下： typedef struct Clnode { int row , /* 行号和列号 */ /* 元素值 */ struct Clnode *down , * }OLN /* 非0元素结点 */typedef struct Clnode { /* 矩阵的行数 */ /* 矩阵的列数 */ A. /* 非0元素总数 */ A.rchead ? OLNode * 1 2 12 OLNode * ? } CrossL0 0 A= 0 0 12 0 5 0 0 0 0 0 0 -4 0 0 0 3 0 0 32 5 ? ??2 5 -4 ? ?43 3 ? ?(b) 稀疏矩阵的十字交叉链表(a) 稀疏矩阵图5-11 稀疏矩阵及其十字交叉链表5.4 广义表广义表是线性表的推广和扩充，在人工智能领域 中应用十分广泛。 在第2章中，我们把线性表定义为n(nR0 )个元素a1, a2 ,…, an的有穷序列，该序列中的所有元素具有相同的 数据类型且只能是原子项(Atom)。所谓原子项可以是一 个数或一个结构，是指结构上不可再分的。若放松对元 素的这种限制，容许它们具有其自身结构，就产生了广 义表的概念。广义表(Lists，又称为列表 )：是由n(n R0)个元素组成的有穷序列： LS=(a1，a2，…，an)其中ai或者是原子项，或者是一个广义表。LS是广义 表的名字，n为它的长度。若ai是广义表，则称为LS 的子表。 习惯上：原子用小写字母，子表用大写字母。 若广义表LS非空时： ◆ a1(表中第一个元素)称为表头；◆ 其余元素组成的子表称为表尾；(a2，a3，…，an)◆ 广义表中所包含的元素(包括原子和子表)的个数称 为表的长 度。 ◆ 广义表中括号的最大层数称为表深 (度)。 有关广义表的这些概念的例子如表5-2所示。表5-2广义表及其示例DA B e a b c d C广 义 表A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E) F=(())表长n 表深h0 1 2 3 2 1 0 1 2 3 ∞ 2图5-12 广义表的图形表示广义表的重要结论：⑴ 广义表的元素可以是原子，也可以是子表，子表 的元素又可以是子表， …。即广义表是一个多层次 的结构。表5-2中的广义表D的图形表示如图5-12所示。 (2) 广义表可以被其它广义表所共享，也可以共享其 它广义表。广义表共享其它广义表时通过表名引用。 (3) 广义表本身可以是一个递归表。 (4) 根据对表头、表尾的定义，任何一个非空广义表 的表头可以是原子，也可以是子表， 而表尾必定是 广义表。5.4.1 广义表的存储结构由于广义表中的数据元素具有不同的结构，通常 用链式存储结构表示，每个数据元素用一个结点表示。 因此，广义表中就有两类结点： ◆ 一类是表结点，用来表示广义表项，由标志域， 表头指针域，表尾指针域组成; ◆ 另一类是原子结点，用来表示原子项，由标志域， 原子的值域组成。如图5-13所示。 只要广义表非空，都是由表头和表尾组成。即一 个确定的表头和表尾就唯一确定一个广义表。标志tag=0 原子的值(a) 原子结点标志tag=1 表头指针hp(b) 表结点表尾指针tp图5-13 广义表的链表结点结构示意图相应的数据结构定义如下： typedef struct GLNode { /* 标志域，为1：表结点;为0 ：原子结点 */ union { /* 原子结点的值域 */ struct { struct GLNode *hp , * } /* ptr和atom两成员共用 */ }G } GLN /* 广义表结点类型 */例： 对A=()，B=(e)，C=(a, (b, c, d) )，D=(A, B, C)， E=(a, E)的广义表的存储结构如图5-14所示。A=NULL B 1 ∧ 0 e 1 0 a E10 a1∧C11∧1 0 c 1 ∧0 b D 1 ∧ 1 10 d ∧1图5-14 广义表的存储结构示意图对于上述存储结构，有如下几个特点： (1) 若广义表为空，表头指针为空；否则，表头指针 总是指向一个表结点，其中hp指向广义表的表头结点 (或为原子结点，或为表结点) ，tp指向广义表的表 尾(表尾为空时，指针为空，否则必为表结点)。 (2) 这种结构求广义表的长度、深度、表头、表尾的 操作十分方便。 (3) 表结点太多，造成空间浪费。也可用图5-15所示 的结点结构。tag=0 原子的值 表尾指针tp(a) 原子结点tag=1 表头指针hp 表尾指针tp(b) 表结点图5-15 广义表的链表结点结构示意图第6章 树和二叉树树型结构是一类非常重要的非线性结构。直观地， 树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用，例如在编译 程序中，用树来表示源程序的语法结构；在数据库系统 中，可用树来组织信息；在分析算法的行为时，可用树 来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构，主要介绍树 和二叉树的概念、术语，二叉树的遍历算法。树和二叉 树的各种存储结构以及建立在各种存储结构上的操作及 应用等。6.1 树的基本概念6.1.1 树的定义和基本术语1 树的定义树(Tree)是n(nR0)个结点的有限集合T，若n=0时称 为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n&1时，其余的结点被分为m(m&0)个互不相交 的子集T1, T2, T3…Tm，其中每个子集本身又是一棵 树，称其为根的子树(Subtree)。 这是树的递归定义，即用树来定义树，而只有一个 结点的树必定仅由根组成，如图6-1(a)所示。2 树的基本术语⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。⑵ 结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为 树的度。A B A E(a) 只有根结点C F GDH I N JK图6-1 树的示例形式LM(b) 一般的树如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点 M的度是0，树的度是3 。⑶ 叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为 0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外，分支结点又称为内部结点。 如图6-1(b)中结点H、I、J、K、L、M、N是叶子 结点，而所有其它结点都是分支结点。⑷ 孩子结点、双亲结点、兄弟结点一个结点的子树的根称为该结点的孩子结点(child) 或子结点；相应地，该结点是其孩子结点的双亲结点 (parent)或父结点。如图6-1(b)中结点B 、C、D是结点A的子结点，而 结点A是结点B 、C、D的父结点；类似地结点E 、F是 结点B的子结点，结点B是结点E 、F的父结点。 同一双亲结点的所有子结点互称为兄弟结点。 如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、 F是兄弟结点。⑸ 层次、堂兄弟结点规定树中根结点的层次为1，其余结点的层次等于 其双亲结点的层次加1。 若某结点在第l(lR1)层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点E、F、G、H、I、J。⑹ 结点的层次路径、祖先、子孙从根结点开始，到达某结点p所经过的所有结点成 为结点p的层次路径(有且只有一条)。结点p的层次路径上的所有结点（p除外）称为p的 祖先(ancester) 。以某一结点为根的子树中的任意结点称为该结点的 子孙结点(descent)。⑺ 树的深度(depth)：树中结点的最大层次值，又称为树的高度，如图6-1(b)中树的高度为4。⑻ 有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有 序树，否则称为无