数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表21哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例例. 按要求编写算法完成下列问题按要求编写算法完成下列问题：1. 假设红假设红、白白、蓝每种颜色的花盆至少有一盆蓝每种颜色的花盆至少有一盆，亦亦即即 n = 3，杂乱的排在一起杂乱的排在一起，编写一个高效算法编写一个高效算法使花盆按红使花盆按红、白白、蓝的顺序排序蓝的顺序排序。假设每组输入为假设每组输入为：一个整数一个整数N，表示有表示有N个花盆个花盆。然后然后N个整数个整数，每个整数为每个整数为1（若为红花盆若为红花盆）、）、2（若为白花盆若为白花盆）或或3（若为蓝花盆若为蓝花盆），），每个整数用每个整数用空格分开空格分开。输入输入N = 0时程序结束时程序结束。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表22哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院#include#includevoid main() char flower100,*r,*y,*w, temp;int count;cinflower;count=strlen(flower);r=flower; y=w=&flowercount-1;while(r-y0) switch (*y) case r: temp=*r; *r=*y; *y=temp; r+; break;case y: y-;break;case w: temp=*y; *y=*w; *w=temp; y-; w-; break;coutflower;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表23哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.1 2.1 线性表的抽象数据型线性表的抽象数据型线性表的抽象数据型线性表的抽象数据型2.2 2.2 线性表的实现线性表的实现线性表的实现线性表的实现2.3 2.3 栈栈（栈栈（StackStack）2.4 2.4 队列队列（队列队列（QueueQueue）2.5 2.5 串串（串串（StringString）2.6 2.6 数组数组（数组数组（ArrayArray）2.7 2.7 广义表广义表（广义表广义表（Generalized ListGeneralized List）第第第第 2 2 章章章章 线性表线性表（线性表线性表（Liner ListLiner List）数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表24哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院知识点知识点：线性表的逻辑结构和各种存储表示方法线性表的逻辑结构和各种存储表示方法定义在逻辑结构上的各种基本运算定义在逻辑结构上的各种基本运算（操作操作）在各种存储结构上如何实现这些基本运算在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性各种基本运算的时间复杂性特殊线性表特殊线性表数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表25哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院重点重点：熟练掌握顺序表和单链表上实现的各种算法及相关熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析的时间复杂性分析难点难点：使用本章所学的基本知识设计有效算法解决与线性使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题表相关的应用问题数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表26哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.1 2.1 线性表的抽象数据型线性表的抽象数据型线性表的抽象数据型线性表的抽象数据型 定义定义 线性表是由线性表是由n(n0)n(n0)个相同类型的元素组成的有序个相同类型的元素组成的有序集合集合。记为记为：( a( a1 1,a,a2 2,a,a3 3, ,a ai i- -1 1,a,ai i,a,ai+1i+1, , a an n ) )其中其中： n为线性表中元素个数为线性表中元素个数，称为线性表的长度称为线性表的长度；当当n=0时时，为空表为空表，记为记为（ ）。）。 ai为线性表中的元素为线性表中的元素，类型定义为类型定义为elementtype a1为表中第为表中第1个元素个元素，无前驱元素无前驱元素；an为表中最后一个为表中最后一个元素元素，无后继元素无后继元素；对于对于ai-1,ai,ai+1(1in)，称称ai-1为为ai的直接前驱的直接前驱，ai+1为为ai的直接后继的直接后继。(位置概念位置概念！）！） 线性表是有限的线性表是有限的，也是有序的也是有序的。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表27哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院线性表线性表 LIST = ( D , R)D = ai| aiElementset , i = 1, 2, , n, n 0 R = H H = | ai-1, ai D , i = 2 , , n 数学模型数学模型数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表28哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作：设设L的型为的型为LIST线性表实例线性表实例，x 的型为的型为elementtype的元素实例的元素实例，p 为位置变量为位置变量。所有操作描述为所有操作描述为： Insert(x, p, L) Locate(x, L) Retrive(p, L) Delete(p, L) Previous(p, L), Next(p, L) Makenull( L) First( L) End(L)数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表29哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例例：设计函数设计函数 Deleval（LIST &L, elementtype d) ，其功能其功能为删除为删除 L 中所有值为中所有值为 d 的元素的元素。void Deleval( LIST &L, elementtype d ) position p ;p = First( L ) ;while ( p != End( L ) ) if ( same( Retrieve( p, L ), d ) )Delete(p, L ) ;elsep = Next(p, L ) ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表210哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2 2.2 线性表的实现线性表的实现线性表的实现线性表的实现问题问题：确定数据结构确定数据结构（存储结构存储结构）实现型实现型LIST，并在此基础上并在此基础上 实现各个基实现各个基本操作本操作。存储结构的三种方式存储结构的三种方式： 连续的存储空间连续的存储空间（数组数组） 静态存储静态存储 非连续存储空间非连续存储空间指针指针（链表链表） 动态存储动态存储 游标游标（连续存储空间连续存储空间+动态管理思想动态管理思想） 静态链表静态链表数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表211哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院顺序表顺序表是指用一组地址连续的存储单元依次存储线性表的数据元素是指用一组地址连续的存储单元依次存储线性表的数据元素。特点特点元素之间的逻辑关系元素之间的逻辑关系（相继相继/相邻关系相邻关系）用物理上的相邻关系来表示用物理上的相邻关系来表示（用用物理上的连续性刻画逻辑上的相继性物理上的连续性刻画逻辑上的相继性）；）；是一种随机存储结构是一种随机存储结构，也就是可以随机存取表中的任意元素也就是可以随机存取表中的任意元素，其存储位其存储位置可由一个简单直观的公式来表示置可由一个简单直观的公式来表示。由于高级语言中数组类型具有这种由于高级语言中数组类型具有这种特性特性，通常都用数组描述通常都用数组描述。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表212哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表213哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.1 2.2.1 线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图2-1 线性表的数组实现线性表的数组实现存储池容量存储池容量第第 i 个元素个元素1 i last数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表214哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院类型定义类型定义：# define maxlength 100struct LIST elementtype elementsmaxlength; int last;线性表线性表 L:L:LIST L;位置类型位置类型：typedef int position;表示表示：L.elementsp / L的第的第p个元素个元素L.last L的长度的长度，最后元素的位置最后元素的位置数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表215哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作实现操作实现： void Insert ( elementtype x, position p, LIST &L) position q ;if (L.last = maxlength 1) error( “ 表满表满 ” ) ；else if ( p L.last +1 ) | ( p = p; q - )L.elements q + 1 = L.elements q ;L.last = L.last + 1 ;L.elements p = x ; /时间复杂性时间复杂性：O(n) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表216哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 position Locate ( elementtype x ,LIST L ) position q ;for ( q = 1; q L.last )error( “指定元素不存在指定元素不存在” ) ;elsereturn ( L.elements p ) ; /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表218哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 void Delete( position p , LIST &L) position q ;if ( ( p L.last ) | ( p 1 ) )error ( “指定位置不存在指定位置不存在” ) ；elseL.last = L.last 1;for ( q = p ; q = L.last ; q + )L.elements q = L.elements q + 1 ; /时间复杂性时间复杂性：O(n) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表219哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 position Previous( position p , LIST L ) if ( ( p L.last ) )error ( “前驱元素不存在前驱元素不存在” ) ;elsereturn ( p 1 ); /时间复杂性时间复杂性：O(1) position Next( position p , LIST L ) if ( ( p = L.last ) )error ( “前驱元素不存在前驱元素不存在” ) ;elsereturn ( p + 1 ); /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表220哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 position End( LIST L ) return( L.last + 1 ); / O(1) position First( LIST L ) return ( 1 ); /复杂性复杂性：O(1) position Makenull( LIST &L ) L.last = 0 ;return ( L.last +1 ); /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表221哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.2 2.2.2 线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现单链表单链表：一个线性表由若干个结点组成一个线性表由若干个结点组成，每个结点均含有两个域每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域存放元素的信息域和存放其后继结点的指针域，这样就形成一个单这样就形成一个单向链接式存储结构向链接式存储结构，简称单向链表或单向线性链表简称单向链表或单向线性链表。结构特点结构特点：逻辑次序和物理次序不一定相同逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示元素之间的逻辑关系用指针表示；需要额外空间存储元素之间的关系需要额外空间存储元素之间的关系；非随机存储结构非随机存储结构数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表222哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院结点形式结点形式elementnext结点信息结点信息下一结点地址下一结点地址celltypeLIST header ;position p , q;a1a2a3anheaderqp数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表223哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院线性表的型线性表的型typedef celltype *LIST;位置型位置型typedef celltype *position;LIST header ;position p , q;a1a2a3anheaderqpa2: ( *p ).element ; q: ( *p ).next ;a2: pelement ;q: pnext ;记法记法:struct celltype elementtype element ;celltype *next ; ; /结点型结点型类型定义类型定义：数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表224哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院插入元素插入元素:pa1xheaderqai-1aixpqanxqp(a) 表头插入元素(b) 中间插入元素(c) 表尾插入元素q = new celltype ;qelement = x ;qnext = pnext ;pnext = q ;或或:temp = pnext ;pnext = new celltype ;pnextelement = x ;pnextnext = temp ;讨论表头结点的作用讨论表头结点的作用？数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表225哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院删除元素删除元素:q = pnext ;pnext = qnext ;delete q ;或或：q = pnext ;pnext = pnextnext ;delete q ;讨论结点讨论结点 ai 的位置的位置 p？a1header(a) 删除第一个元素删除第一个元素a2qpai-1aipq(b) 删除中间元素删除中间元素ai+1anan-1qp(c) 删除表尾元素删除表尾元素数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表226哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作： position End ( LIST L) position q ;q = L ;while ( qnext != NULL ) q = qnext ;return ( q ) ; /时间复杂性时间复杂性：O(n) Lqa1a2a3an数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表227哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 void Insert ( elementtype x, position p) position q ;q = new celltype ;q element = x ;q next = p next ;p next = q ; /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表228哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院void Insert (LIST &L, position p , int x) LIST q , s;s=L;while(s-next!=p)s=s-next;q=new celltypeq-element=x;q-next=s-next;s-next=q;完整的插入算法数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表229哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作： position Locate ( elementtype x, LIST L ) position p ;p = L ;while ( pnext != Null )if ( pnextelement = x ) return p ;elsep = pnext ;return p ; /时间复杂性时间复杂性：O(n) Lpa1a2a3an数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表230哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 elementtype Retrieve ( position p) return ( p next element ); /时间复杂性时间复杂性：O(1) void Delete ( position p) position q ;if ( pnext != NULL ) q = p next ;p next = q next ;delete q ; /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表231哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作：position Previous ( position p) position q ;if ( p = Lnext )error ( “不存在前驱元素不存在前驱元素” ) ；else q = L ;while ( qnext != p )q = qnext ;return q ; /时间复杂性时间复杂性：O(n) Lqa1a2a3an数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表232哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作： position Next ( position p) position q ;if ( pnext = NULL )error ( “不存在后继元素不存在后继元素” ) ；else q = pnext;return q ; /时间复杂性时间复杂性：O(1) position Makenull ( LIST &L ) L = new celltype ;Lnext = NULL;return L ; /时间复杂性时间复杂性：O(1) 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表233哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作： position First ( LIST L ) return L; /时间复杂性时间复杂性：O(1) 例例：遍历线性链表遍历线性链表，按照线性表中元素的顺序按照线性表中元素的顺序，依次访问表中依次访问表中的每一个元素的每一个元素，每个元素只能被访问一次每个元素只能被访问一次。void Travel( LIST L ) position p ;p = Lnext ;while ( p != NULL) cout pelement ;p = pnext ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表234哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院静态链表静态链表 与与 动态链表的动态链表的 比较比较顺序存储顺序存储固定固定，不易扩充不易扩充随机存取随机存取插入删除费时间插入删除费时间估算表长度估算表长度，浪费空间浪费空间比较参数比较参数表的容量表的容量存取操作存取操作时间时间空间空间链式存储链式存储灵活灵活，易扩充易扩充顺序存取顺序存取访问元素费时间访问元素费时间实际长度实际长度，节省空间节省空间数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表235哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院作业作业：链表的维护与文件形式的保存链表的维护与文件形式的保存要求要求用链表结构的有序表表示某商场家电的库存模型用链表结构的有序表表示某商场家电的库存模型。当有提货或进货时当有提货或进货时需要对该链表进行维护需要对该链表进行维护。每个工作日结束之后每个工作日结束之后，将该链表中的数据以文将该链表中的数据以文件形式保存件形式保存，每日开始营业之前每日开始营业之前，需将以文件形式保存的数据恢复成链需将以文件形式保存的数据恢复成链表结构的有序表表结构的有序表。链表结点的数据域包括家电名称链表结点的数据域包括家电名称、品牌品牌、单价和数量单价和数量，以单价的升序以单价的升序体现链表的有序性体现链表的有序性。程序功能包括程序功能包括：创建表创建表、营业开始营业开始（读入文件恢复读入文件恢复链表数据链表数据）、）、进货进货（插入插入）、）、提货提货（更新或删除更新或删除）、）、查询信息查询信息、更新信更新信息息、营业结束营业结束（链表数据存入文件链表数据存入文件）等等。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表236哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.3 2.2.3 线性表的游标实现线性表的游标实现线性表的游标实现线性表的游标实现静态链表静态链表：把线性表的元素存放在数组的单元中把线性表的元素存放在数组的单元中（不一定按逻辑顺序连续不一定按逻辑顺序连续存放存放），），每个单元不仅存放元素本身每个单元不仅存放元素本身，而且还要存放其后继元素所而且还要存放其后继元素所在的数组单元的下标在的数组单元的下标（游标游标）。）。存储池存储池数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表237哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院结点形式结点形式elementnext结点信息结点信息下一结点位置下一结点位置spacestr73LM9availabled65c-1-0 a108e-1-4-1-11b2121多个线性多个线性表共用一表共用一个存储池个存储池讨论与单链表的区别讨论与单链表的区别？数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表238哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院d65c-1/-/0 a108e-1/-/4-1/-/11b2121012345678910111273LM9available类型定义类型定义：typedef struct elementtype element ;int next ; spacestr; /结点类型结点类型spacestr SPACE maxsize ;/存储池存储池typedef int position，cursor;cursor av; /游标变量游标变量，标识线性表标识线性表存储池存储池数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表239哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院元素元素：SPACE i .element “型型”为为elementtype( 基本基本、复合复合)下一元素位置下一元素位置：SPACE i .next “型型”为为 int类似指针链表类似指针链表，对游标实现的线性表仍设表对游标实现的线性表仍设表头结点头结点。线性表线性表：L = ( a, b, c ) L = 7 M = ( d, e ) M = 373LM9availabled65c-1/-/0 a108e-1/-/4-1/-/11b21210123456789101112存储池存储池空闲表空闲表：available = 9数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表240哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院-1234 56789101112-10123456789101112SPACE0avvoid Initialize(spacestr &SPACE, int *av) int j; / 依次链接池中结点依次链接池中结点for (j=0; jnext-next;q=p-next;L-next-next=NULL;while(p!=null)p-next=L-next;L-next=p;p=q;q=q-next;方法二方法二:线性表由线性表由q来表示来表示p=null;w=q;while(w!=null)w=w-next;q-next=p;p=q;q=w;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表244哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.4 2.2.4 双向链表双向链表双向链表双向链表双向连表双向连表：在单向链表中在单向链表中，对每个结点增加对每个结点增加一个域一个域，用一指向该结点的前驱结点用一指向该结点的前驱结点。线性线性表的这种存储结构称为双向链表表的这种存储结构称为双向链表。/* 结点类型结点类型 */struct dcelltype elementtype element ;dcelltype *next, *previous ; ;/* 表和位置的类型表和位置的类型 */typedef dcelltype *DLIST ;typedef dcelltype *position ;优点优点：实现双向查找实现双向查找（单链表不易做到单链表不易做到）表中的位置表中的位置i i 可以用指示含有第可以用指示含有第i i 个结点个结点的指针表示的指针表示。缺点缺点：空间开销大空间开销大。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表245哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院dcelltype结点形式结点形式element next结点信息结点信息后继结点指针后继结点指针previous前驱结点指针前驱结点指针ai-1a iai+1pheaderan tail数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表246哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作：删除位置删除位置p的元素的元素：void Delete( position p)if (p-previous!=NULL)ppreviousnext = pnext;if (pnext!=NULL)pnext previous = pprevious ;delete p;void Insert( elementtype x, position p) position q ;q = new dcelltype ;qelement = x ;ppreviousnext = q ;qprevious = pprevious ;qnext = p ;pprevious = q ; ai-1a iai+1p数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表247哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.5 2.2.5 环形链表环形链表环形链表环形链表单向线性链表单向线性链表双向线性链表双向线性链表单向循环链表单向循环链表双向循环链表双向循环链表对线性链表的改进对线性链表的改进，解决解决“单单向操作向操作”的问题的问题；改进后的链改进后的链表表，能够从任意位能够从任意位置元素开始置元素开始，访问表中的每一访问表中的每一个元素个元素。单向环形链表单向环形链表：在在( (不带表头结点不带表头结点) )的单向链表中的单向链表中，使末尾结点的指使末尾结点的指针域指向头结点针域指向头结点，得到一个环形结构得到一个环形结构；用指向末尾结点的指针标识用指向末尾结点的指针标识这个表这个表。存储结构存储结构: :与单向链表相同与单向链表相同( (略略）a1a2a3anR左端结点左端结点右端结点右端结点R空表空表数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表248哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作：在表左端插入结点在表左端插入结点Insert(x,First(R),R); Linsert(x,R)void Linsert( elementtype x , LIST &R ) celltype *p ;p = new celltype ;pelement = x ;if ( R = NULL ) pnext = p ; R = p ; else pnext = Rnext ; Rnext = p ; 在表右端插入结点在表右端插入结点Insert(x,END(R),R); Rinsert(x,R)void Rinsert( elementtype x , LIST &R ) Linsert (x,R ) ; R = Rnext ; a1a2xanRpxpR数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表249哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作：从表左端删除结点从表左端删除结点Delete(First(R),R); Ldelete(R)void Ldelete( LIST &R ) celltype *p ;if ( R = NULL )error ( “空表空表” );else p = Rnext ; Rnext = pnext ; if ( p = R )R=NULL;delete p ; xpRpa1a2anR数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表250哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院双向环形链表双向环形链表：a a1 1 a ai ia an n R R双向环形链表的结构与双向连表结构相同双向环形链表的结构与双向连表结构相同，只是将表头元素的空只是将表头元素的空previousprevious域指向表尾域指向表尾，同时将表尾的空同时将表尾的空nextnext域指向表头结点域指向表头结点，从而形成从而形成向前和向后的两个环形链表向前和向后的两个环形链表，对链表的操作变得更加灵活对链表的操作变得更加灵活。举例举例：设计算法设计算法，将一个单向环形链表反向将一个单向环形链表反向。头元素变成尾头元素变成尾元素元素，尾元素变成新的头元素尾元素变成新的头元素，依次类推依次类推。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表251哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院a1a2a3anRanan-1an-2a1Rvoid Revers( LIST &R ) position p, q, s;q = R; p= Rnext ; R= Rnext ; while ( p -next!= R ) s = q ; q = p ;p = pnext ; qnext =s ;p-next=q;R-next=p; 算法如下算法如下：存储结构定义略存储结构定义略数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表252哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院约瑟夫问题约瑟夫问题: :n个人围成一个圆圈个人围成一个圆圈，首先首先，第第1个人从个人从1开始开始，顺时针报顺时针报数数, 报到第报到第m个人个人，令其出列令其出列。然后再从下一个人开始然后再从下一个人开始，从从1顺顺时针报数时针报数，报到第报到第m个人个人，再令其出列再令其出列，如此下去如此下去, 直到圆直到圆圈中只剩一个人为止圈中只剩一个人为止。此人即为优胜者此人即为优胜者。 算法基本思路算法基本思路？ 用什么数据结构用什么数据结构？void Josephus ( List &Js, int n, int m) celltype *p=Js, *pre=NULL;for (int i=0; in-1; i+) for (int j=0; jnext; cout“出列的人是出列的人是”datanext =p-next; delete p;p=pre-next;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表253哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.2.6 2.2.6 多项式的代数运算多项式的代数运算多项式的代数运算多项式的代数运算结点类型结点类型：struct polynode int coef ；int exp ；polylink *link ；;typedef polynode *polypointer ；结点结构结点结构coefcoefexpexplinklink系数系数指数指数下一项地址下一项地址数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表254哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例如例如：多项式多项式 p ( x ) = 3x14+ 2x8+ 1 采用链表表示如下采用链表表示如下：3142810P算法算法Attch (c, e, d) 建立一个新结点建立一个新结点，其系数其系数 coef =c，指数指数exp=e；并把它链到并把它链到 d 所指结点之后所指结点之后，返回该结点指针返回该结点指针。polypointer Attch ( int c , int e , polypointer d ) polypointer x ;x = new polynode ; xcoef = c ; xexp = e ;dlink = x ;return x ; ;算法算法 padd 实现两个多项式实现两个多项式a，b 相加相加 ；c(x) = a(x) + b(x)数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表255哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院polypointer Padd (polypointer a , polypointer b ) polypointer p, q, d, c ;int x ;p = alink ; q = blink ;c = new polynode ; d = c ;while ( (p != NULL) & (q != NULL) )switch ( compare ( pexp, qexp ) ) case = :x = pcoef + qcoef ;if ( x ) d = attch( x, pexp, d ) ;p = plink ; q = qlink ;break ;case :d = Attch( pcoef, pexp, d );数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表256哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院p =plink ;break ;case :d = Attch( qcoef, qexp, d ) ;q = qlink ; break ;while ( p != NULL ) d = Attch( pcoef, pexp, d ) ;p = plink ;while ( q !=NULL ) d = Attch( qcoef, qexp, d ) ;q = qlink ;dlink = NULL ;p = c ; c = clink ; delete p ;return c ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表257哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.3 2.3 栈栈（栈栈（StackStack）栈是线性表的一种特殊形式栈是线性表的一种特殊形式，是一种限定性数据结构是一种限定性数据结构，也就是在对线性也就是在对线性表的操作加以限制后表的操作加以限制后，形成的一种新的数据结构形成的一种新的数据结构。定义定义：是限定只在表尾进行是限定只在表尾进行插入和删除操作的线性表插入和删除操作的线性表。栈又称为栈又称为后进先出后进先出(Last In First Out )(Last In First Out )的线性表的线性表。简称简称LIFOLIFO结构结构。a1a2an-1anInsertDeletetopbottom栈底栈顶栈示意图数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表258哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.3 2.3 栈栈栈栈栈的基本操作栈的基本操作 MakeNull ( S ) Top ( S ) Pop ( S ) Push ( x , S ) Empty ( S ) 举例举例：利用栈实现行编辑处理利用栈实现行编辑处理。设定符号设定符号“# #”为擦讫符为擦讫符，用以删用以删除除“# #”前的字符前的字符；符号符号“ ”为删为删行符行符，用以删除当前编辑行用以删除当前编辑行。原理原理：一般字符进栈一般字符进栈；读字符读字符擦讫符退栈擦讫符退栈；删行符则清栈删行符则清栈算法算法：void LineEdit( ) STACK ；char c ;MakeNull ( S );c = getchar ( ) ;while ( c != n ) if ( c = # )Pop ( S );else if ( c = )MakeNull ( S );elsePush ( c , S );c = getchar( );逆序输出栈中所有元素逆序输出栈中所有元素；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表259哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.3.1 2.3.1 2.3.1 2.3.1 栈的数组实现栈的数组实现栈的数组实现栈的数组实现顺序栈示意图anaia3a2a1-maxlength-13210top类型定义类型定义：enum Boolen TRUE, FALSEtypedef struct elementtype elementsmaxlength;int top ; STACK ;STACK S ;栈的容量栈的容量：maxlength 1 ;栈空栈空：S.top = 0 ;栈满栈满：S.top = maxlength 1 ;栈顶元素栈顶元素：S.elements S.top ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表260哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院 void MakeNull( STACK &S ) S.top = 0 ; Boolean Empty( STACK S ) if ( S.top next=NULL;void Push ( Elementtype x, STACK &S)STACK stk;stk=new node;stk-val=elm;stk-next=S-next;S-next=stk;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表264哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院void Pop ( STACK &S)STACK stk;if ( S-next )stk=S-next;S-next=stk-next;delete stk;Elementtype Top (STACK S)if(S-next)return(S-next-val);elsereturn NULL;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表265哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院boolean Empty(STACK S)if (S-next)return FALSE;else return TRUE;1、多个栈共用一个存储空间的讨论多个栈共用一个存储空间的讨论STACK maxlength bot1top1bot2top2bot3top3top2botntopn 0Maxlength-1botn+1botitopi数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表266哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例例、使用游标形式使得三栈共享使用游标形式使得三栈共享设用一个类型为设用一个类型为STATICLISTSTATICLIST的一维数组的一维数组AmAm存储空间建立三个栈存储空间建立三个栈. .其中前其中前三个单元的三个单元的nextnext存放三个栈顶的指针存放三个栈顶的指针, ,第四个单元起共享第四个单元起共享. .编写一算法编写一算法从键盘输入从键盘输入n n个整数按下列条件进栈个整数按下列条件进栈: :(1)(1) t80t80进进1 1栈栈(2)(2) 80=t=10080=t100t100进进3 3栈栈datanext0 1 2 m-1如果输入数据为如果输入数据为:100,30,68,90,120:100,30,68,90,120后结果应如下后结果应如下: :100306890120567004300 1 2 3 4 5 6 7 8 9 10 11 12 再输入数据为再输入数据为:60,156,85:60,156,85后结果变化后结果变化60581567985610数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表267哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院struct nodeint data;int next;typedef struct node Node;void Share(Node A) int i,top;for(i=0;i3;i+)Ai.next=0;for(i=3;in;i+)Ai.next=i+1;An-1=0;/初始化初始化top=3;for(i=1;it;Aj.data=t;top=top+;if(t100)Aj.next=A2.next;A2.next=j;else Aj.next=A1.next;A1.next=j;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表268哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2 2 2 2、 栈的简单应用栈的简单应用栈的简单应用栈的简单应用例例1 1 算术表达式中括号作用域合法性的检查算术表达式中括号作用域合法性的检查int Correct (char ext, int n) / 数组数组ext用于存储表达式用于存储表达式STACK S;int j =1;MakeNull(S);while (表达式没有结束时表达式没有结束时)if (expj是左括号是左括号) / 左括号左括号 , , (Push ( extj, S )if (extj是右括号是右括号) / 右括号右括号 , , ) x = Top(S); / 取栈首元素比较取栈首元素比较if (x与与extj匹配匹配) Pop(S);else return FALSE; j + +;if ( ! Empty ( S ) ) return FALSE;else return TRUE;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表269哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例例2 2 表达式求值表达式求值前缀表达式前缀表达式（波兰式波兰式）表达式表达式：中缀表达式中缀表达式后缀表达式后缀表达式（逆波兰式逆波兰式）例如例如：*+abab( a + b ) * ( a b) ( a + b ) * ( a b)ab+ab*高级语言中高级语言中，采用类似自然语言的中缀表达式采用类似自然语言的中缀表达式，但计算机对中缀表达式但计算机对中缀表达式的处理是很困难的的处理是很困难的，而对而对后缀后缀或前缀表达式则显得非常简单或前缀表达式则显得非常简单。后缀表达式的特点后缀表达式的特点：在后缀表达式中在后缀表达式中，变量变量（操作数操作数）出现的顺序与中出现的顺序与中缀表达式顺序相同缀表达式顺序相同。后缀表达式中不需要括弧定义计算顺序后缀表达式中不需要括弧定义计算顺序，而由运算而由运算（操作符操作符）的位置来确定运算顺序的位置来确定运算顺序。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表270哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院.将中缀表达式转换成后缀表达式将中缀表达式转换成后缀表达式对中缀表达式从左至右依次扫描对中缀表达式从左至右依次扫描，由于操作数的顺序保由于操作数的顺序保持不变持不变，当遇到操作数时直接输出当遇到操作数时直接输出；为调整运算顺序为调整运算顺序，设立设立一个栈用以保存操作符一个栈用以保存操作符，扫描到操作符时扫描到操作符时，将操作符压入栈将操作符压入栈中中，进栈的原则是保持栈顶操作符的优先级要高于栈中其他进栈的原则是保持栈顶操作符的优先级要高于栈中其他操作符的优先级操作符的优先级，否则否则，将栈顶操作符依次退栈并输出将栈顶操作符依次退栈并输出，直直到满足要求为止到满足要求为止。遇到遇到“（”进栈进栈，当遇到当遇到“）”时时，退栈输出直到退栈输出直到“）”为止为止。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表271哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例如例如：中缀表达式中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为其转换成后缀表达式则为a b c * + d e * f + g * +转换过程需要用到栈转换过程需要用到栈，具体过程如下具体过程如下：1）如果遇到操作数如果遇到操作数，就直接将其输出就直接将其输出。/读到读到a，直接输出直接输出2）如果遇到操作符如果遇到操作符，则将其放入到栈中则将其放入到栈中，遇到左括号时也将其放入栈中遇到左括号时也将其放入栈中。/读到读到“+”，将其放入到栈中将其放入到栈中；读到读到b，直接输出直接输出/读到读到“*”，因为栈顶元素因为栈顶元素“+”优先级比优先级比“ * ” 低低，所以将所以将“ * ”直接压入直接压入栈中栈中；读到读到c，直接输出直接输出。此时栈和输出情况如下此时栈和输出情况如下：此时栈和输出的情况如下此时栈和输出的情况如下：数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表272哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院/读到读到 + ，因为栈顶元素因为栈顶元素 * 的优先级比它高的优先级比它高，所以弹出所以弹出 * 并输出并输出， 同理同理，栈栈中下一个元素中下一个元素“ + ”优先级与读到的操作符优先级与读到的操作符“ + ”一样一样，所以也要弹出并输出所以也要弹出并输出。然后再将读到的然后再将读到的 + 压入栈中压入栈中。此时栈和输出情况如下此时栈和输出情况如下：/下一个读到的为下一个读到的为(，它优先级最高它优先级最高，所以直接放入到栈中所以直接放入到栈中。/读到读到d，将其直接输出将其直接输出。此时栈和输出情况如下此时栈和输出情况如下：/读到读到 * ，由于只有遇到由于只有遇到 ) 的时候左括号的时候左括号(才会弹出才会弹出，所以所以 * 直接压入栈中直接压入栈中。/读到读到e，直接输出直接输出。此时栈和输出情况如下此时栈和输出情况如下：数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表273哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院/读到读到“ + ”，弹出弹出“ * ”并输出并输出，然后将然后将“+”压入栈中压入栈中。/读到读到f，直接输出直接输出。此时栈和输出情况此时栈和输出情况：/接下来读到接下来读到“）”，则直接将栈中元素弹出并输出直到遇到则直接将栈中元素弹出并输出直到遇到(为止为止。这里右括号前只有一这里右括号前只有一个操作符个操作符+被弹出并输出被弹出并输出。/读到读到 * ，压入栈中压入栈中。读到读到g，直接输出直接输出。/此时输入数据已经读到末尾此时输入数据已经读到末尾，栈中还有两个操作符栈中还有两个操作符“*”和和 + ，直接弹出并输出直接弹出并输出。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表274哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院. . 由后缀表达式计算表达式的值由后缀表达式计算表达式的值对后缀表达式从左至右依次扫描对后缀表达式从左至右依次扫描，与与相反相反，遇到操作数遇到操作数时时，将操作数进栈保留将操作数进栈保留；当遇到操作符时当遇到操作符时，从栈中退出两个操从栈中退出两个操作数并作相应运算作数并作相应运算，将计算结果进栈保留将计算结果进栈保留；直到表达式结束直到表达式结束，栈中唯一元素即为表达式的值栈中唯一元素即为表达式的值。假定待求值的后缀表达式为假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下则其求值过程如下：1）遍历表达式遍历表达式，遇到的数字首先放入栈中遇到的数字首先放入栈中，此时栈如下所示此时栈如下所示：2）接着读到接着读到“+”，则弹出则弹出3和和2，执行执行3+2，计算结果等于计算结果等于5，并将并将5压入到栈中压入到栈中。3）读到读到8，将其直接放入栈中将其直接放入栈中。4）读到读到“*”，弹出弹出8和和5，执行执行8*5，并将结果并将结果40压入栈中压入栈中。而后过程类似而后过程类似，读到读到“+”，将将40和和5弹出弹出，将将40+5的结果的结果45压入栈压入栈.以此类推以此类推。最最后求的值后求的值288数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表275哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3 3、栈与递归问题栈与递归问题一一、递归条件递归条件采用递归方法来解决问题采用递归方法来解决问题，必须符合以下三个条件必须符合以下三个条件：1 1、可以把要解决的问题转化为一个新问题可以把要解决的问题转化为一个新问题，而这个新的问题的解决方而这个新的问题的解决方法仍与原来的解决方法相同法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减只是所处理的对象有规律地递增或递减。2 2、可以应用这个转化过程使问题得到解决可以应用这个转化过程使问题得到解决。3 3、必定要有一个明确的结束递归的条件必定要有一个明确的结束递归的条件。二二、递归实例递归实例例例1 1：使用递归的方法求使用递归的方法求n! n! 当当n1n1时时，求求n!n!的问题可以转化为的问题可以转化为n*(nn*(n- -1)!1)!的新问题的新问题。德罗斯特效应德罗斯特效应递归的视觉效应递归的视觉效应数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表276哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院f(1)f(2)f(3)f(4)f(5)top2*f(1) f(2)=2*f(1)4*f(3) f(4)=4*f(3)3*f(2) f(3)=3*f(2)5*f(4) f(5)=5*f(4)1 f(1)=1 计算计算5的阶乘的阶乘（5！=5*4*3*2*1）int f(int n) if ( n = = 1) return (1);else return ( n * f(n-1);数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表277哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院递归的执行过程递推递推回归回归递归终递归终止项止项特点特点：(1) 递归必须有递归必须有递归结束递归结束条件条件；(2) 递归过程首先是递归过程首先是一级一级递推一级一级递推（即当前调用未结束又引出下一层调即当前调用未结束又引出下一层调用用），），而满足递归结束条件时结束递推而满足递归结束条件时结束递推，再再一级一级的回归一级一级的回归（即一级一即一级一级再返回上一级的调用继续完成上一级的未完成的操作级再返回上一级的调用继续完成上一级的未完成的操作）。）。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表278哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院void print(int w) int i;if ( w!=0) print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);若若w为为3时时，运行结果运行结果：1，2，2，3，3，3，例例2 2 递归的执行情况分析递归的执行情况分析数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表279哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院递归调用执行情况如下递归调用执行情况如下：主程序主程序(1)print(w)w=3; 3print(2);（1）w=3 top(2) 输出输出：3, 3, 3w2print(1);（2）w=2 （1）w=3 top(3) 输出输出：2, 2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)输出输出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3) 输出输出：2, 2(2) 2(1) 3top(4)输出输出：1(3) 1(2) 2(1) 3top(2) 输出输出：3, 3, 3 (1 ) 3top返回返回(3) 1(2) 2(1) 3top(4) 0结束结束(1)if ( w!=0) print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”); 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表280哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院问题描述问题描述：一个三位数一个三位数abcabc如果满足如果满足abcabc = a3 + b3 + c3 = a3 + b3 + c3 那么就把那么就把这个数叫做水仙花数这个数叫做水仙花数。如果一个如果一个N N位数所有数码的位数所有数码的N N次方的和加起来等于这个数字本身次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数我们把这样的数叫做广义水仙花数，容易看出来水仙花数是容易看出来水仙花数是N = 3N = 3的广的广义水仙花数义水仙花数。现在现在，任务是任务是，输入一个输入一个m (m 7) m (m m) /类似于类似于base case if (curNum = curSum) printf(%d/n, curNum);else if (deep = m) int start = (deep = 1); /第一位不为第一位不为0 for (int i = start; i max(n-1,arr)return arrn-1;elsereturn max(n-1,arr);int mymax(int from, int to)int mid,t1,t2;if (from=to) return afrom;elsemid=(from+to)/2;t1=mymax(from,mid);t2=mymax(mid+1,to);return (t1t2)?t1:t2;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表283哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院int findmax(int s,int l,int r)int m,x,y;if(l=r) return sl;if(l+1=r) return sl sr ? sl : sr;m=(l+r)/2;x= findmax (s,l,m); y= findmax(s,m+1,r);return x y ? x : y;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表284哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4 2.4 2.4 2.4 排队或队列排队或队列（排队或队列排队或队列（QueueQueueQueueQueue）队列是对线性表的插入和删除操作加以限定的另一种限队列是对线性表的插入和删除操作加以限定的另一种限定性数据结构定性数据结构。 定义定义 将线性表的插入和删除操作分别限制在表的两端进行将线性表的插入和删除操作分别限制在表的两端进行，和栈相反和栈相反，队列是一种先进先出队列是一种先进先出（First In First OutFirst In First Out，简称简称 FIFO FIFO 结构结构）的线性表的线性表。a a1 1，a a2 2，a a3 3， ，a an n- -1 1， a an n出队列出队列入队列入队列，插入插入，排队排队删除删除，出队出队队头队头队尾队尾队列示意图队列示意图frontfrontrearrear操作操作：MakeNull(Q)、Front(Q)、EnQueue(x, Q)、DeQueue(Q)、Empty(Q)数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表285哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4.1 2.4.1 2.4.1 2.4.1 队列的指针实现队列的指针实现队列的指针实现队列的指针实现元素的元素的“型型”：struct celltype elementtype element ；celltype *next ； ；队列的队列的 “型型”：struct Queue celltype *front ；celltype *rear ；;a1a2anQ.frontQ.rear队列的指针实现示意图队列的指针实现示意图数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表286哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4.1 2.4.1 队列的指针实现队列的指针实现队列的指针实现队列的指针实现操作操作： void MakeNull( Queue &Q ) Q.front = new celltype ;Q.frontnext = Null ;Q.rear = Q.front ; Boolean Empty(Queue Q ) if ( Q.front = Q.rear )return True ;elsereturn False ; elementtype Front (Queue Q ) return Q.frontnext-element ; 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表287哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4.1 2.4.1 队列的指针实现队列的指针实现队列的指针实现队列的指针实现 void EnQueue ( elementtype x, Queue &Q ) Q.rearnext = new celltype ;Q.rear = Q.rearnext ;Q.rearelement = x ;Q.rearnext = NULL ; void DeQueue ( Queue &Q ) celltype *temp ;if ( Empty( Q ) )error ( “空队列空队列” ) ;else temp = Q.frontnext ;Q.frontnext = tempnext ;delete temp ;if ( Q.frontnext = NULL )Q.rear = Q.front ; 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表288哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.4.2 2.4.2 队列的数组实现队列的数组实现队列的数组实现队列的数组实现队列的队列的 “型型”：struct Queue elementtype element maxlength ;int front ；int rear ；;a1a2a3a4 anQfrontrearmaxlength右图右图：队列队列Q状态状态1随着不断有元素出队和进队随着不断有元素出队和进队（插入和删除插入和删除），队列的状队列的状态由态由1 1变成变成2 2；此时此时a an n占据队占据队列的最后一个位置列的最后一个位置；第第n+n+1 1个元素无法进队个元素无法进队, ,但实际上但实际上，前面部分位置空闲前面部分位置空闲。“假溢出假溢出“maxlengtha1a2a3a4a5a6 anQfrontrear下图下图：队列队列Q状态状态2数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表289哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院解决假溢出的方法有多种解决假溢出的方法有多种；一是通过不断移动元素位置一是通过不断移动元素位置，每当有元素出队列时每当有元素出队列时，后面的元素前移一个位置后面的元素前移一个位置，使队头元使队头元素始终占据队列的第一个位置素始终占据队列的第一个位置。第二种方法是采用第二种方法是采用循环队列循环队列。Q.rearQ.front01maxlength-1队列队列Q插入元素插入元素：Q.rear = (Q.rear + 1） % maxlength删除元素删除元素：Q.front = (Q.front + 1） % maxlength队空队空：(Q.rear + 1）% maxlength = Q.front队满队满：(Q.rear + 1 ) % maxlength = Q.front?数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表290哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院0 01 12 23 34 45 5rearrearfrontfrontJ4J4J5J5J6J60 01 12 23 34 45 5J9J9J8J8J7J7frontfrontrearrearJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfronfront初始状态初始状态初始状态初始状态循环队列出入队图示循环队列出入队图示循环队列出入队图示循环队列出入队图示队空队空：队空队空：front=rearfront=rearfront=rearfront=rear队满队满：队满队满：front=rearfront=rearfront=rearfront=rear数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表291哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院问题问题：如何解决循环队列中队空与队满状态相同如何解决循环队列中队空与队满状态相同？方法一方法一：约定队列头指针在队列尾指针的下一位置上约定队列头指针在队列尾指针的下一位置上(即空出一个位置即空出一个位置）；）；方法二方法二：另设一个标志位用以区别队空与队满两种状态另设一个标志位用以区别队空与队满两种状态；结论结论：两种方法的代价是相同的两种方法的代价是相同的。操作操作：int addone( int i ) return ( ( i + 1）% maxlength ) ; void MakeNull ( Queue &Q) Q.front = 0 ;Q.rear = maxlength 1; boolean Empty(Queue Q ) if ( addone(Q.rear) = Q.front )return TRUE ;elsereturn FALSE ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表292哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院操作操作： elementtype Front( Queue Q ) if ( Empty( Q ) )return NULL ;elsereturn (Q.elements Q. front ); void EnQueue (Elementtype x, Queue &Q ) if ( addone ( addone( Q.rear ) ) =Q.front )error ( “队列满队列满” ) ;else Q.rear = addone ( Q.rear ) ;Q.elements Q.rear = x ; void DeQueue ( Queue &Q ) ; if ( Empty( Q ) )error ( “空队列空队列” ) ;else Q.front = addone ( Q.front ) ; ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表293哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2014/9/24队列使用的原则队列使用的原则凡是符合先进先出原则的凡是符合先进先出原则的服务窗口和排号机服务窗口和排号机、打印机的缓冲区打印机的缓冲区、分时系统分时系统、树型结构树型结构的层次遍历的层次遍历、图的广度优先搜索等等图的广度优先搜索等等举例举例约瑟夫出圈问题约瑟夫出圈问题：n个人排成一圈个人排成一圈，从第一个开始报数从第一个开始报数，报到报到m的人出的人出圈圈，剩下的人继续开始从剩下的人继续开始从1报数报数，直到所有的人都出圈为止直到所有的人都出圈为止。舞伴问题舞伴问题：假设在周末舞会上假设在周末舞会上，男士们和女士们进入舞厅时男士们和女士们进入舞厅时，各自排各自排成一队成一队。跳舞开始时跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞则较长的那一队中未配对者等待下一轮舞曲曲。现要求写算法模拟上述舞伴配对问题现要求写算法模拟上述舞伴配对问题。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表294哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.5 2.5 2.5 2.5 串串串串( String )( String )( String )( String )串是线性表的一种特殊形式串是线性表的一种特殊形式，表中每个元素的类型为字符型表中每个元素的类型为字符型，是一个有限的字符序列是一个有限的字符序列。串的基本形式可表示成串的基本形式可表示成：S = aS = a1 1a a2 2a a3 3aan n ；其中其中：char char a ai i； 0 0 i i n n ；n 0 n 0 ； 当当 n = 0 n = 0 时时，为空串为空串。n n 为串的长度为串的长度 ；C C 语言中串有两种实现方法语言中串有两种实现方法：1 1、字符数组字符数组，如如：char str110 char str110 ；2 2、字符指针字符指针，如如：char *str2 char *str2 ；操作操作：string MakeNull( ) ;Boolean IsNull ( S ) ;void In( S, a ) ;int Len( S ) ;void Concat( S1, S2 ) ;string Substr( S, m, n ) ;Boolean Index( S, S1 ) ;2.5.1 2.5.1 2.5.1 2.5.1 抽象数据型串抽象数据型串抽象数据型串抽象数据型串数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表295哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院例例1 1、将串将串T T 插在串插在串S S 中第中第 i i 个字符之后个字符之后INSERT( S, T, i )INSERT( S, T, i )。void Insert( STRING &S, STRING T, int i ) STRING t1, t2 ;if ( ( i Len( S ) )error 指定位置不对指定位置不对 ;elseif ( IsNull( S ) ) S = T ;elseif ( IsNull ( T ) ) t1 = Substr( S, 1, i ) ;t2 = Substr( S, i + 1, Len( S ) );S = Concat( t1, Concat( T, t2 ) );数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表296哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院void Delete( STRING &S, STRING T )void Delete( STRING &S, STRING T ) STRING t1, t2 ; STRING t1, t2 ;int m, n ;int m, n ;m = Index( S, T ); m = Index( S, T ); if ( m=0 )if ( m=0 )error error 串串S S中不包含子串中不包含子串T T ; ;elseelse n = Len( T ) ; n = Len( T ) ;t1 = Substr( S, 1, m t1 = Substr( S, 1, m - - 1 ) ;1 ) ;t2 = Substr( S, m + n, Len( S ) );t2 = Substr( S, m + n, Len( S ) );S = Concat( t1, t2);S = Concat( t1, t2); 例例2 2、从串从串 S S 中将子串中将子串 T T 删除删除Delete( S, T )Delete( S, T )。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表297哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.5.2 2.5.2 2.5.2 2.5.2 串的实现串的实现串的实现串的实现1 1、串的顺序存储串的顺序存储采用连续的存储空间采用连续的存储空间（数组数组），），自第一个元素开始自第一个元素开始，依次存储字符依次存储字符串中的每一个字符串中的每一个字符。char str 10 =char str 10 =“ChinaChina”；C h i n a 00 1 2 3 4 5 6 7 8 9str串的顺序存储串的顺序存储操作操作：MakeNull，IsNull，In，Len，Concat，Substr，Index2 2、串的链式存储串的链式存储定长结点定长结点构造线性链表构造线性链表，elementelement类型为类型为charchar，自第一个元素开始自第一个元素开始，依依次存储字符串中的每一个字符次存储字符串中的每一个字符。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表298哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.5.2 2.5.2 串的实现串的实现串的实现串的实现i na Chstr1struct node char data ;node *link ; ;typedef node *STRING1;STRING1 str1 ; struct node char data4 ;node *link ; ;typedef node *STRING2 ;STRING2 str2 ; C h i nC str2假设地址量假设地址量（link）占用占用 2 个字节个字节5/155/12数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表299哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2 2、串的链式存储串的链式存储int Index ( STRING1 S, S1 )struct node *p, *q, *i ;int t ;if ( ( S1 != NULL ) & ( S != NULL ) ) t = 1 ; i = S ; q = S1 ;p=S;do if ( pdata = qdata ) q = qlink ;if ( q = NULL ) return( t ) ;p = plink ;else t = t + 1 ; i = ilink ;p = i ; q = S1 ; while ( p != NULL ) ;return 0 ; Index(S,S1)若若S1是是S的子串则返回的子串则返回S1首字符在首字符在S中的位置中的位置；否则否则，返回返回0；操作操作：数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2100哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3 3、模式匹配算法模式匹配算法1 1）简单的匹配算法简单的匹配算法：一旦某个字符匹配失败一旦某个字符匹配失败，从头开始从头开始。( (本次匹配起点后一个字符开始本次匹配起点后一个字符开始）主串主串S=000000000000000000000000000000001S=000000000000000000000000000000001模式串模式串 T=00000001T=00000001，指针要回朔指针要回朔4545次次。52个零个零数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2101哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院设主串设主串S=“ababcabcacbab”，模式串模式串T=“abcac”第第1趟匹配趟匹配主串主串ababcabcacbabi=3模式串模式串abcj=3匹配失败匹配失败第第2趟匹配趟匹配主串主串ababcabcacbabi=2模式串模式串abcj=1匹配失败匹配失败第第3趟匹配趟匹配主串主串ababcabcacbabi=7模式串模式串abcacj=5匹配失败匹配失败第第4趟匹配趟匹配主串主串ababcabcacbabi=4模式串模式串abcj=1匹配失败匹配失败第第5趟匹配趟匹配主串主串ababcabcacbabi=5模式串模式串abcj=1匹配失败匹配失败第第6趟匹配趟匹配主串主串ababcabcacbabi=6模式串模式串abcacj=6匹配成功匹配成功数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2102哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院int Index_BF ( char* S, char* T, int pos=1) /* S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 */i = pos;j = 1;/ 从第一个位置开始比较while (i=S0 & j T0) return i-T0;elsereturn 0;/ 返回与模式第一字符相等/ 的字符在主串中的序号/ 匹配不成功数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2103哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院BruteBrute- -ForceForce算法的时间复杂性算法的时间复杂性主串主串S S长长n,n,模式串模式串T T长长m m。可能匹配成功的位置可能匹配成功的位置（1 1n n- -m+1)m+1)。最好的情况下最好的情况下，模式串的第模式串的第1 1个字符失配个字符失配设匹配成功在设匹配成功在S S的第的第i i个字符个字符，则在前则在前i i- -1 1趟匹配中共比较了趟匹配中共比较了i i- -1 1次次，第第i i趟趟成功匹配共比较了成功匹配共比较了m m次次，总共比较了总共比较了（i i- -1+m1+m）次次。所有匹配成功的可能所有匹配成功的可能共有共有n n- -m+1m+1种种，所以在等概率情况下的平均比较次数所以在等概率情况下的平均比较次数：最好情况下算法的平均时间复杂性最好情况下算法的平均时间复杂性O(n+m)O(n+m)。111111( 1)( 1)()12n mn miiip imimm nn m 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2104哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院最坏的情况下最坏的情况下，模式串的最后模式串的最后1 1个字符失配个字符失配设匹配成功在设匹配成功在S S的第的第i i个字符个字符，则在前则在前i i- -1 1趟匹配中共比较了趟匹配中共比较了(i(i- -1)*m1)*m次次，第第i i趟成功匹配共比较了趟成功匹配共比较了m m次次，总共比较了总共比较了( (i*mi*m）次次。共需要共需要n n- -m+1m+1趟比趟比较较，所以在等概率情况下的平均比较次数所以在等概率情况下的平均比较次数：设设nmnm，最坏情况下的平均时间复杂性为最坏情况下的平均时间复杂性为O(n*m)O(n*m)。11111()(2)12n mn miiimp i mim nmnm 数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2105哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院KMPKMP算法算法-改进的模式匹配算法改进的模式匹配算法 为什么为什么BFBF算法时间性能低算法时间性能低？在每趟匹配不成功时存在大量在每趟匹配不成功时存在大量回溯回溯，没有利用已经部分没有利用已经部分匹配匹配的结果的结果。 如何在匹配不成功时主串不回溯如何在匹配不成功时主串不回溯？主串不回溯主串不回溯，模式模式就需要就需要向右滑动向右滑动一段距离一段距离。 . .如何确定模式的滑动距离如何确定模式的滑动距离？利用已经得到的利用已经得到的“部分匹配部分匹配”的结果将模式向右的结果将模式向右“滑动滑动”尽可能远的一段距离尽可能远的一段距离(nextj)(nextj)后后，继续进行比较继续进行比较数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2106哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院第第1 1趟匹配趟匹配第第2 2趟匹配趟匹配第第3 3趟匹配趟匹配i=3a b a b c a b c a c b a ba b cj=3i=3-7a b a b c a b c a c b a ba b c a cj=1i=7-11a b a b c a b c a c b a ba b c a cj=2-6假设主串假设主串ababcabcacbab,ababcabcacbab,模式模式abcac(abcac(01112)01112), ,改进算法改进算法的匹配过程如下的匹配过程如下：数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2107哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院问题问题：假定主串为假定主串为 S1S2Sn ，模式串为模式串为 T1T2Tm无回溯无回溯匹配问题变为匹配问题变为：当当主串主串中的第中的第i个字符和个字符和模式模式串中串中第第j个字符出现不匹配个字符出现不匹配，主串主串中的第中的第i个字符应该与个字符应该与模式模式串串中的中的哪个字符哪个字符匹配匹配（无回溯无回溯）？）？进一步思考进一步思考假定主串中第假定主串中第i个字符与模式串第个字符与模式串第k个字符相比较个字符相比较，则应有则应有T1T2Tk-1 = Si-(k-1)Si-(k-2)Si-1问题可能有多个问题可能有多个k，取哪一个取哪一个？数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2108哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院假设主串为假设主串为s1s2.sns1s2.sn，模式串为模式串为t1t2.tmt1t2.tm，当当sisitjtj时时，主串的第主串的第i i个元素到底要与模式串的哪个元素进行比较个元素到底要与模式串的哪个元素进行比较，设为设为tktk，显然显然kj,kj,如下如下：主串主串S S si-jsi-j+1si-j+2si-ksi-k+1si-k+2si-2si-1si子串子串P P.t1t2 tj-ktj-k+1tj-k+2tj-2tj-1tj下一次比较下一次比较tk的位置的位置t1t2. tk-2tk-1tk说明说明：tj-k+1tj-k+2tj-1=t1t2tk-2tk-1数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2109哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2014/9/24 T T1 1T T2 2TTk k- -1 1T Tj j- -(k(k- -1)1)T Tj j- -(k(k- -2)2)TTj j- -1 1说明了什么？说明了什么？k 与与 j 具有函数关系具有函数关系，由当前失配位置由当前失配位置 j ，可以计算出滑动可以计算出滑动位置位置 k（即比较的新起点即比较的新起点）；）；滑动位置滑动位置k 仅与模式串仅与模式串自身自身T有关有关，而与主串无关而与主串无关。 T T1 1T T2 2TTk k- -1 1T Tj j- -(k(k- -1)1)T Tj j- -(k(k- -2)2)TTj j- -1 1的物理意义是什么？的物理意义是什么？模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的?kmax k |1kj 且T T1 1T T2 2TTk k- -1 1T Tj j- -(k(k- -1)1)T Tj j- -(k(k- -2)2)TTj j- -1 1从j-1位往左数k-1位从第1位往数右k-1位数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2110哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院令k = next j ，则：next j 0 当j1时/不比较max k | 1kj 且T1Tk-1=Tj-(k-1)Tj-11 其他情况k = next j 实质是找实质是找T T1 1T T2 2TTj j- -1 1中中中中的的最长相同的前缀最长相同的前缀( (T T1 1T T2 2TTk k- -1 1) )和后缀和后缀( (T Tj j- -(k(k- -1)1)T Tj j- -(k(k- -2)2)TTj j- -1 1) )。模式中相似部分越多模式中相似部分越多，则则nextj函数越大函数越大表示模式表示模式 T 字符之间的相关度越高字符之间的相关度越高，模式串向右滑动得越远模式串向右滑动得越远，与主串进行比较的次数越少与主串进行比较的次数越少，时间复杂度就越低时间复杂度就越低。仍是一个模式匹配的过程仍是一个模式匹配的过程, ,只是主串和模式串在同一个串只是主串和模式串在同一个串T T中中。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2111哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院nextjj , nextj1时时，nextj的值为的值为：模式串的位置从模式串的位置从1到到j-1构成的串构成的串中所出现的首尾相同的子串的最大长度加中所出现的首尾相同的子串的最大长度加1。当无首尾相同的子串时当无首尾相同的子串时nextj的值为的值为1。/nextj=1表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2116哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院下面给出求下面给出求next函数的伪码函数的伪码void get_next(SString T, int &next) /求模式串求模式串T的的next函数并存入函数并存入next数组数组int i = 1;next1 = 0; int j = 0;while (i T0) /T0中存放数组长度中存放数组长度 if( j=0|Ti=Tj)+i; +j; nexti=j;else j= nextj;/get_next数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2117哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院KMPKMP算法实现步骤算法实现步骤：1.1.在串在串S S和串和串T T中分别设比较的起始下标中分别设比较的起始下标i i和和j j；2. 2. 循环直到循环直到S S中所剩字符长度小于中所剩字符长度小于T T的长度或的长度或T T中所有字中所有字符均比较完毕符均比较完毕2.12.1如果如果Si=TjSi=Tj，继续比较继续比较S S和和T T的下一个字符的下一个字符；否则否则2.22.2将将j j向右滑动到向右滑动到nextjnextj位置位置，即即j=nextjj=nextj；2.3 2.3 如果如果j=0j=0，则将则将i i和和j j分别加分别加1 1，准备下一趟比较准备下一趟比较；3. 3. 如果如果T T中所有字符均比较完毕中所有字符均比较完毕，则返回匹配的起始下标则返回匹配的起始下标；否则返回否则返回0 0；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2118哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院KMP算法算法int Index_KMP(char *s , char *t,int pos=1) /求串求串s的第的第pos个字符开始找首次与个字符开始找首次与t串相等的子串串相等的子串int i = pos;int j = 1;while (i = s0& jt0) return i-t0;/成功返回位置成功返回位置else return -1;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2119哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.6 2.6 2.6 2.6 数组数组数组数组( ARRAY )( ARRAY )( ARRAY )( ARRAY )2.6.1 2.6.1 2.6.1 2.6.1 抽象数据型数组抽象数据型数组抽象数据型数组抽象数据型数组数组是由下标数组是由下标（indexindex）和值和值（valuevalue）组成的序对组成的序对（indexindex，valuevalue）的集合的集合。也可以定义为是由相同类型的数据元素组成有限序列也可以定义为是由相同类型的数据元素组成有限序列。数组在内存中是采用一组连续的地址空间存储的数组在内存中是采用一组连续的地址空间存储的，正是正是由于此种原因由于此种原因，才可以实现下标运算才可以实现下标运算。所有数组都是一个一维向量所有数组都是一个一维向量。数组数组1：( a1, a2, a3, , ai , , an) ;数组数组2：( a11, , a1n, a21, , a2n, , aij , , am1, , amn) ;1im, 1jn ;数组数组3: ( a111, , a11n, a121, , a12n, , aijk , , amn1, , amnp) ;1 i m, 1 j n , 1 k p ;数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2120哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.6.1 2.6.1 2.6.1 2.6.1 数组的抽象数据型数组的抽象数据型数组的抽象数据型数组的抽象数据型n n 维数组中含有维数组中含有b bi i 个数据元素个数据元素, ,每个元素都受着每个元素都受着 n n 个关系的约束个关系的约束。在每个关系中在每个关系中，元素元素a aj1j2j1j2jnjn（0 j0 ji i bbi i- -2 2）都有一个直接后继元素都有一个直接后继元素。i=1n因此因此，数组仍是一种特殊形式的线性表数组仍是一种特殊形式的线性表。对二维数组可以理对二维数组可以理解成一维数组解成一维数组，其每个元素又是一个一维数组其每个元素又是一个一维数组；以此类推以此类推，所谓所谓n n 维数组同样如此维数组同样如此。操作操作：Create( ）；）；建立一个空数组建立一个空数组 ; int A Retrieve(array，index）；）；返回第返回第 index 个元素个元素 ; AijStore（array，index，value）；）；在数组在数组array中中，为第为第index个元素赋值个元素赋值value; Aij=6注注：由于高级语言中都提供了数组由于高级语言中都提供了数组，本课略去操作本课略去操作。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2121哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.6.2 2.6.2 2.6.2 2.6.2 数组的实现数组的实现数组的实现数组的实现1 1、数组的顺序存储数组的顺序存储数组的顺序表示数组的顺序表示，指的是在计算机中指的是在计算机中，用一组连续的存用一组连续的存储单元来实现数组的存储储单元来实现数组的存储。目前的高级程序设计语言都是这目前的高级程序设计语言都是这样实现的样实现的。两种存储方式两种存储方式：一是按行存储一是按行存储（C C语言语言、PASCALPASCAL等等）二是按列存储二是按列存储（FORTRANFORTRAN等等）A00 A01 A02A10 A11 A12A =A00A01A02A10A11A12A00A10A01A11A02A12第一行第一行第二行第二行第一列第一列第二列第二列第三列第三列elementtype A23 ；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2122哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院aij0n-10m-1aij前面的元素个数=i nj整行数本行中aij前面的元素个数aij前面的元素个数=整行数每行元素个数+本行中按行优先存储的寻址-二维数组每行元素个数Loc(aij)Loc(a00)(i n j )c数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2123哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院按行优先存储的寻址-多维数组n（n2）维数组一般也采用按行优先和按列优先两种存储方法。Loc(aijk) = Loc(a000) +( im2m3+ jm3+ k )c数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2124哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2. 2. 特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一矩阵中很多值相同的元素并且它们的分布有一定的规律定的规律。稀疏矩阵稀疏矩阵：矩阵中有很多零元素矩阵中有很多零元素。压缩存储的基本思想是压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间存储空间； 对对零零元素元素不分配不分配存储空间存储空间。aij对称矩阵的压缩存储对称矩阵的压缩存储对称矩阵特点对称矩阵特点：a aijij= =a ajiji只存储下三角部分的元素只存储下三角部分的元素。62844788421696058295 736A 47aij在一维数组中的序号= i(i+1)/2+ j+1一维数组下标从0开始aij在一维数组中的下标k= i(i+1)/2+ j(ij)k= j (j+1)/2+ i(ij)0in-10 jn-112iaij三角矩阵的压缩存储三角矩阵的压缩存储-下三角矩阵只存储下三角部分的元素只存储下三角部分的元素。3cccc62ccc81cc460c2957矩阵中任意一个元素aij在一维数组中的下标k与i、j的对应关系：k= i(i+1)/2+ j(ij)k= n(n+1)/2+ i(ij)0in-1对角线上方的常数只存一个对角线上方的常数只存一个n-10 j12iA 478稀疏矩阵的压缩存储稀疏矩阵的压缩存储 -三元组顺序表三元组顺序表如何只存储非零元素如何只存储非零元素？稀疏矩阵中的非零元素的分布没有规律稀疏矩阵中的非零元素的分布没有规律。将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为：(行号行号，列号列号，非零元素值非零元素值)三元组表三元组表typedef struct int i，j ；ElemType v ； Triple ；typedef struct Triple dataMaxSize+1；int mu，nu，tu； TSMatrix；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2128哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2014/9/24稀疏矩阵的压缩存储稀疏矩阵的压缩存储 -三元组顺序表三元组顺序表如何存储三元组表如何存储三元组表？按行优先的顺序排列成一个线性表按行优先的顺序排列成一个线性表。15 00 22 0 -150 11 300000060000000091 00000A=7（非零元个数非零元个数）5（矩阵的行数矩阵的行数）6 （矩阵的列数矩阵的列数）数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2129哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2014/9/24稀疏矩阵的压缩存储稀疏矩阵的压缩存储 -三元组顺序表如何存储三元组表如何存储三元组表？按行优先的顺序排列成一个线性表按行优先的顺序排列成一个线性表。15 00 22 0 -150 11 300000060000000091 00000A=7（非零元个数非零元个数）5（矩阵的行数矩阵的行数）6（矩阵的列数矩阵的列数）rowrowcolcolitemitem0001510322205-15311114123523664091数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2130哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0M =i j v1 2 121 3 931 -346 1443 245 2 1861 156 4 -7T = M=0 0 -3 0 0 15120 0 0 18 09 0 0 24 0 00 0 0 0 0 -70 0 0 0 0 00 0 14 0 0 00 0 0 0 0 0a.datai j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14b.data数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2131哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院3、数组的链接式存储数组的链接式存储多维数组多维数组, ,特别是稀疏矩阵可以采用链接式存储特别是稀疏矩阵可以采用链接式存储。LEFT UP ROW COL VOL结点形式结点形式：结点类型结点类型：strucrt node node *LEFT ， *UP ；int ROW ， COL ；valuetype VAL； ；二维数组二维数组A（矩阵矩阵）的链接表示如下的链接表示如下。50 0 0 0A= 10 0 20 00 0 0 0-30 0 -60 5数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2132哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院-1101030 -300050-1-1-1-1122032 -60-1-1335-1数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2133哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院2.7 2.7 广义表广义表（广义表广义表（General ListsGeneral Lists）广义表示线性表的一种推广结构广义表示线性表的一种推广结构，线性表要求是相同的元素类型线性表要求是相同的元素类型，而广义表中的元素可以取不同类型而广义表中的元素可以取不同类型，可以是最基本的不可再分割可以是最基本的不可再分割的的“原子原子”，也可以是广义表本身也可以是广义表本身。广义表广义表是由零个原子是由零个原子，或若干个原子或若干个广义表组成的有穷或若干个原子或若干个广义表组成的有穷序列序列。通常将广义表表示为通常将广义表表示为：A = A = （a a1 1，a a2 2， ，a an n）其中其中，A A 是名称是名称，元素个数元素个数 n n 是表的长度是表的长度；若若 a ai i不是不是原子原子，则称其为则称其为A A的子表的子表。注意广义表的递归性注意广义表的递归性。数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2134哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院长度长度：广义表广义表LS中的直接元素的个数中的直接元素的个数；深度深度：广义表广义表LS中括号的最大嵌套层数中括号的最大嵌套层数。表头表头：广义表广义表LS非空时非空时，称第一个元素为称第一个元素为LS的表头的表头；表尾表尾：广义表广义表LS中除表头外其余元素组成的广义表中除表头外其余元素组成的广义表。例如例如：A = A = （a a，（，（b b，a a，b b），（），），（），c c，（，（2 2）；）；B = B = （）；（）；C = C = （e e ）；）；D = D = （A A，B B，C C ）；）；E = E = （a a，E E ）；）；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2135哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院结论结论：广义表的元素可以是子表广义表的元素可以是子表，子表的元素还可以是子表子表的元素还可以是子表， ，广义表是一个多层次的结构广义表是一个多层次的结构；一个广义表可以被其他广义表所共享一个广义表可以被其他广义表所共享。广义表是一个递归的表广义表是一个递归的表，即广义表可以是其本身的子表即广义表可以是其本身的子表。操作操作：Cal（ L ）；）；返回广义表返回广义表 L 的第一个元素的第一个元素Cdr（ L ）；）；返回广义表返回广义表 L 除第一个元素以外的所有元素除第一个元素以外的所有元素Append（ L，M ）；）；返回广义表返回广义表 L + MEqual（ L，M ）；）；判判 广义表广义表 L 和和 M 是否相等是否相等Length（ L ）；）；求广义表求广义表 L 的长度的长度数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2136哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院广义表的存储结构广义表的存储结构广义表的存储结构广义表的存储结构struct listnode listnode *link ；boolean tag ；union char data ；listnode *dlink ； ； ；typedef listnode *listpointer ；数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2137哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院fatAfbfc A=(a, (b,c)ttt BB=(A, A,( )fat CC=(a, C)广义表实例广义表实例数据结构与算法数据结构与算法第二章第二章第二章第二章 线线线线 性性性性 表表表表2138哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院广义表的操作广义表的操作广义表的操作广义表的操作boolean Equal( listpointer S, T ) boolean x, y ;y = False ;if ( ( S = NULL ) & ( T = NULL ) )y = True ;else if ( ( S != NULL ) & ( T != NULL ) )if ( Stag = Ttag ) if ( Stag = FALSE if ( Selement.data = Telement.data )x = True ;else x = False ;elsex = Equal( Selement.data,Telement.data );if ( x= True )y = Equal( Slink, Tlink ) ;return y ;存储结构的定义本章小结本章小结知识点知识点：线性表线性表、栈栈、队列队列、串串、（、（多维多维）数组数组、广义表广义表知识点体系结构知识点体系结构ADT基本数据结构ADT定义定义定义及相关术语定义及相关术语逻辑结构逻辑结构逻辑结构及其特征逻辑结构及其特征基本操作基本操作（算法算法）存储结构存储结构（描述描述）ADT实现实现存储结构特点存储结构特点存储结构存储结构操作操作（算法算法）实现实现算法的性能算法的性能应用应用静态的静态的动态的动态的静态的静态的动态的动态的线性表知识点总结逻辑结构存储结构基本概念抽象数据类型定义线性表定义逻辑特征ADT定义基本操作顺序存储链接存储其他存储顺序表的特点顺序表类定义基本操作的实现及时间性能单链表的特点单链表类定义基本操作的实现及时间性能比较循环链表双链表静态链表间接寻址知识点总结特殊线性表栈队 列串栈的定义操作特性ADT定义队列定义操作特性ADT定义串的定义基本概念ADT定义链栈链队列顺序存储链接存储逻辑结构存储结构逻辑结构逻辑结构存储结构存储结构比较模式匹配顺序比较栈循环比较队列基本操作的实现时间性能基本操作的实现时间性能广义线性表知识点总结多维数组广义表逻辑结构存储结构逻辑结构存储结构数组的定义基本操作ADT定义顺序存储压缩存储特殊矩阵对称矩阵三角矩阵对角矩阵按行优先按列优先基本概念广义表定义表头、表尾长度、深度ADT定义链接存储十字链表稀疏矩阵转置算法寻址的计算方法