数据结构栈、查找、串和队列ppt.ppt

版权所有, 1997 (c) Dale Carnegie int top; sqstktp; sqstktp s; s.top表示栈顶指示器， s.elems.top表示栈顶元素 9 链栈结构形式及特点 顺序栈的不足之处: 难以为它确定适当 的存储空间的大 小 链栈的结构特点: 使用一个链表来表 示一个栈， Data nextData next 栈顶栈顶 NULL NULL 栈底栈底 10 链栈结构形式及特点 使用一个链表来表示一个栈，链和栈之间存在以 下的对应关系： 链尾元素相当于栈底元素 链头元素相当于栈顶元素，链头指针相当于栈顶指针。 入栈操作相当于从链头插入一个元素 出栈操作相当于从链头删除一个元素 11 链栈的类型定义 struct node elemtp data; struct node *next; ； typedef struct node nodetp; typedef struct node *link; typedef link linked_stack; 链栈可以用一个指向栈顶的指针型变量top来表示，其定义如下 ： linked_stack top; 当topNULL时，这个栈就成为空栈， 当top不等于NULL时，就可以通过top指针来访问栈顶元素。 datanext 12 顺序栈的类定义 const int deflen=10; template class Tsxz private: elemtp *elem; int top,maxlen; public: Tsxz(int maxsz=deflen); Tsxz()delete elem; bool push (elemtp el); elemtp pop( ); elemtp gettop( ); bool full()return top=-1; bool empt()return top=maxlen-1; ; 13 顺序栈的构造函数及析构函数 template Tsxz: Tsxz(int maxsz) maxlen=maxsz; top=-1; elem=new elemtpmaxlen; ; 功能：按指定的长度分配顺序表空间，并设置maxlen 及top变量初值 Tsxz()delete elem; 功能：释放已分配的存储空间 14 顺序栈的入栈操作 操作的表示形式 template bool Tsxz: push (elemtp el); 参数：el表示入栈的元素，其类型为元素类型elemtp 功能：在顺序栈中插入元素el，并使el成为栈顶。 处理过程： （1） 判是否栈满，若栈满则返回false，否则： （2）栈顶指针加1，将el送入栈顶并返回true。 15 入栈操作 处理过程： (1) 判是否栈满， 若栈满则返回 false，否则： (2) 栈顶指针加1， 将X送入栈顶并返 回true S.top S.elem S.top S.elem X X 16 入栈操作程序代码 template bool Tsxz: push (elemtp el) int i; if (top=maxlen-1) return(false); else top=top+1; elemtop=el; return(true); ; ; 17 顺序栈的出栈操作 template elemtp Tsxz:pop( ) 功能：若指定的栈非空，则从栈中取出栈顶元素并返回该元 素，否则输出相应的信息。 处理过程： （1）判栈是否为空栈，若为空栈则输出相应的信息，否则： （2）栈顶指针减1并返回原栈顶元素。 程序代码： template elemtp Tsxz:pop( ) if (top=-1) return NULL; else return(elemtop-); ; 18 出栈操作 处理过程： （1）判栈是否为空 栈，若为空栈则 返回空元素NULL ，否则： （2）栈顶指针减1 并返回原栈顶元 素。 S.top S.elem S.top S.elem X X 19 顺序栈的取栈顶操作 template elemtp Tsxz: gettop( ) 功能：若指定的栈非空则返回栈顶元素，否则输出相应的信息 。 处理过程：判栈是否为空栈，若为空栈则输出相应的信息否则 返回栈顶元素。 程序代码： template elemtp Tsxz:gettop( ) if (top=-1) return NULL; else return(elemtop); ; 20 链栈结点的类定义 结点类Tnode中的数据包括结点中的元素值及指针值， 其构造函数有两个参数d和n分别设置到这两个数据中 。Tlz与Tnode都定义成类模板，且Tlz是Tnode的友元 ，可访问Tnode类中的私有数据。 template class Tlz; template class Tnode friend class Tlz ; private: elemtp data; Tnode *next; Tnode(elemtp d=0, Tnode *n=NULL) :data(d),next(n) ; ; 21 链栈的类定义 template class Tlz private: Tnode *top; public: Tlz():top(NULL); Tlz(); void init()top=NULL; void prnt(); elemtp pop(); void push (elemtp el); bool empt()return top=NULL; ; 22 链栈的入栈操作 含义：将一个元素推入指定的链栈中 el top top elel 23 入栈操作 template void Tlz : push(elemtp el) 功能：在当前链栈中插入元素el，使el成为栈顶元素 。 处理过程： （1）生成一个新的结点，并令其元素值为el。 （2）将该结点从栈顶插入到链栈中。 程序代码： Tnode *p; p= new Tnode ; p-data=el; p-next=top; top=p; ; 24 链栈的出栈操作 含义：从链栈中弹出栈顶结点并返回该结点中的元 素值 el top top 返回返回elel 25 出栈操作表示形式 template elemtp Tlz :pop(); 功能：从当前链栈中弹出栈顶结点并返回该结点中的元素 值 处理过程： （1）判链栈是否为空，若为空栈则返回空元素。 （2）保存栈顶结点的元素值于el，并修改栈顶指针使之指 向其后继。 （3）置返回函数值为el。 elemtp el; if (top = NULL) return NULL; else el = top-data; top = top-next; return(el); ; 26 括号配对检查程序 处理过程 对输入表达式进行扫描， 当遇到左括号时，左括号入栈； 当遇到右括号时，首先从栈顶弹出一个元素，并 比较弹出元素是否与右括号匹配，如果两者不匹 配，则返回出错信息并结束处理。否则扫描继续 ， 当表达式全部扫描完时如果栈为空，说明括号配 对正确返回正常信息。 27 括号配对检查程序 执行过程中栈的变化 # ( ) () # ( # 当前读入符号 28 括号配对检查程序 主程序 (由顶向下的程序设计方法) String st; st=Edit1-Text; if ( parenthesis(st) ) ShowMessage(“the paren is valid“); else ShowMessage(“the paren is invalid“); 29 括号配对检查程序 函数的表示形式 bool parenthesis (String st) 功能：对st中的输入表达式括号配对的合法性进行检 查，如果合法则返回true,否则返回false。 在程序中，变量lz1表示由链栈类Tlz所生成的实体 ，字符型的变量ch，symb分别表示从栈顶弹出的 字符与从输入表达式中读入的当前字符。 bool parenthesis (String st) bool valid; int i; char ch,symb; valid=true; lz1-push(#); symb=st2; i=3; 30 括号配对检查程序 while (symb!=#) i=i+1; else if (symb是左括号) lz1-push(symb); symb=sti; i=i+1; else if (lz1-empt() valid=false; else ch=lz1-pop(); if (ch与symb 配对) valid=true; symb=sti; i=i+1; else valid=false; return valid; 31 表达式求值 表达式的组成 例：#3*(7-2)# 运算符 * - 运算量 3 7 2 32 表达式求值 运算符间的优先关系 根据运算规则，规定算符的优先法则 假设Q1、Q2分别为两个操作符，用关系运算 符、=、 33 表 达 式 求 值 算法的基本处理过程如下： (1)置OPND、OPRT栈为空，并将#推入栈中。 (2)依次读入表达式中的单词， 若为操作量则操作量进OPND栈； 若为操作符则将OPRT中的栈顶操作符与该操作符进行优 先比较，并根据比较的结果分别进行处理： 若ch push(#); symb=lzForm-Edit1-Text2; i=3; while (symb!=.) if ( symb为运算量 ) sopnd-push( StrToInt(symb); symb=lzForm-Edit1-Texti; i+; else ch= soprt-gettop(); 比较ch与symb的优先级并进行不同的处理； if (soprt-empt() ShowMessage(IntToStr(sopnd-gettop(); else ShowMessage(“输入表达式有误“); 37 表达式求值 程序说明 在该程序中sopnd、soprt分别表示操作量栈和操作 符栈，它们都是由Tlz类生成的实体，在这种链栈 类中栈元素的类型分别为int与char。编辑框 Edit1用于接受输入表达式。为了简便起见，假设 表达式中的运算量只能是一位整数并以.为结 束。 38 表达式求值 比较ch与symb的优先级并进行不同的处理； switch( rela(ch,symb) ) casepush(symb); symb=lzForm-Edit1-Texti;i+; break; case =: soprt-pop(); symb=lzForm-Edit1-Texti;i+; break; case : op= soprt-pop(); b= sopnd-pop(); a= sopnd-pop(); sopnd-push( oprt(a,b,op) ; 39 演示 结束 40 版权所有, 1997 (c) Dale Carnegie ; rectp; rectp rn+1; 说明：为了使逻辑序号与存储下标一致，定义rn+1 记录存放在r1至 rn 查找过 程 无监视所无监视所 设置监视所设置监视所 45 无监视所的查找函数 int srch(rectp r,int n, keytp k); 参数r表示查找表，其长度为n+1，在r中存放n个记录 ，参数k表示指定的关键字。 功能：若存在关键字等于k的记录，则返回该记录在 顺序表中的序号，否则返回值为0。 处理过程：从表中第一个记录开始，逐个进行记录的 关键字与给定值的比较，若某个记录的关键字与给 定值的相等，则查找成功返回该记录的序号，反之 ，若直至最后一个记录，其关键字与给定值都不等 ，则查找不成功返回0。 46 无监视所的查找函数 程序代码 int srch(rectp r,int n, keytp k) int i; i=1; while (ri.key!=k) else return(i); ; 循环控制条件由二个关系式组成，关系式 (ri.key!=k)表示关键字等于k的记录还没有找到 ，而关系式(i ri.key，i=1,2n-1，参数k 表示指定的关键字。 功能：在有序表r中若存在关键字等于k的记录，则返回 该记录在有序表中的序号，否则返回值为0。 基本思想：二分查找的基本过程是先将整个的查找表看 作为查找范围，经过中间项关键字与指定值的比较， 逐次将查找范围折半缩小，直至找到或找不到该记录 为止。 51 有序表的查找 处理过程： （1）置查找范围初态：low=1, hig=n; （2）对当前的查找范围进行以下的处理： 求中项mid=(low+hig)/ 2; 将指定值k与中项的关键字值进行比较，若等于则返 回中项的序号mid；若小于则查找上部即low不变， hig=mid-1；若大于则查找下部即 hig 不变， low=mid+1。 （3）重复执行上述过程2，直至查到返回mid或当 lowhig时返回0。 52 二分查找非递归函数程序代码 int bisrch(rectp r,int n, keytp k) int low,hig,mid; bool found; low=1; hig=n; found=false; while (low 第三次循环 454= 54 二分查找非递归函数执行实例： 假设n=11,有序查找表中的关键字序列为： 5 13 19 21 37 56 64 75 80 88 92 则使用上述算法分别查找k=22的执行过程如下： lowhigmidK?rmid.key 第一次循环 1116 第三次循环 454 第四次循环 555hig返回0 55 有序表的查找 递归算法 int bisrch1(rectp r,keytp k,int l, int h); 参数r表示有序查找表，参数k表示指定的关键字,l,h分 别表示查找范围的下界，上界。 功能：在有序表r中若存在关键字等于k的记录，则返回 该记录在有序表中的序号，否则返回值为0。 处理过程： （1）若lh,则返回0，否则： （2）求中项m=(l+h)/ 2;将指定值k与中项的关键字值进 行比较，若相等则返回中项的序号m；若小于则查找上 部即以（r,k,l,m-1）为参数递归地调用本过程；若大 于则查找下部即以（r,k,m+1,h）为参数递归地调用本 过程。 56 二分查找递归函数 程序代码 int bisrch1(rectp r,keytp k,int l, int h) int m; if (lh) return(0); else m=(l+h)/ 2; if (k=rm.key ) return(m); else if (k bisrch（r,k,1,5）- bisrch（r,k,4,5）- 返回4 对于k=22：bisrch（r,k,1,11）- bisrch（r,k,1,5）- bisrch（r,k,4,5） - bisrch（r,k,5,5）- bisrch（r,k,5,4） - lh,返回0 58 静态树表的查找 判定树 通常称描述查找过程的二叉树为判定树。树中的每 个结点表示查找表中的一个记录，结点中的值为 该记录在表中的位置序号。 3 3 1 14 4 2 25 5 3 3 1 1 4 4 2 2 5 5 59 判定树与带权路径长度PH PH0.1*2 + 0.2*3 + 0.1*1 + 0.4*2 + 0.2*3 = 2.3 PH0.1*3 + 0.2*2 + 0.1*3 + 0.4*1 + 0.2*2 = 1.8 3 3 1 14 4 2 25 5 3 3 1 1 4 4 2 2 5 5 4 4 2 25 5 3 3 1 1 0.10.10.20.2 0.10.10.40.40.20.2 60 静态树表的查找 最优查找树 对于一个有序的查找序列(r1, r2, rn), 其各结点中的权值为(w1, w2, wn)， 构造一棵二叉(判定)树，其各结点的路径长度 即层次数为(h1, h2, hn), 如果PH的值最小，则该二叉树称为最优查找树 。 61 静态树表的查找 次优查找树 可以使用一种既非常近似又非常有效的算法构造成一棵二叉 树,其PH的值近似地达到最小。这种二叉树称为次优查找 树. 次优查找树的构造方法: 设有序序列为 (rl, rl+1, rh), 结点中的权值为(wl, wl+1, wh)， 在有序序列中取第i（l Tnode *Tpxrc : sear0(elemtp el,Tnode *pxrc) 其中el表示要查找的结点关键码，pxrc表示指向排序二 叉树根结点的指针。 功能：若在pxrc所指的排序二叉树中存在关键码等于el 的结点，则返回指向该结点的指针，否则返回空指针 NULL。 处理过程：若pxrc为空，则返回空指针NULL，否则： (1) 若el小于pxrc所指结点的关键码，则在pxrc所指结 点的左子树中查找，即以左子树根结点指针为参数递 归调用本函数； 若el大于pxrc所指结点的关键码，则在pxrc所指结点 的右子树中查找，即以右子树根结点指针为参数递归 调用本函数； 否则返回pxrc。 71 排序二叉树的查找（递归函数 ） template Tnode *Tpxrc : sear0(elemtp el,Tnode *pxrc) if (pxrc=NULL ) return(NULL); else if (el = pxrc-data) return(pxrc); else if (el data) return(sear0( el,pxrc-lchild); else return(sear0( el,pxrc-rchild); ; 接口函数： template Tnode *Tpxrc : sear(elemtp el) return(sear0(el,root); 72 排序二叉树的查找（非递归函数 ） template Tnode *Tpxrc : sear1(elemtp el) 功能：在当前的排序二叉树中查找元素值为el的结点， 并返回该结点的指针。 处理过程： 设置p为根结点。若p为空，返回空指针NULL，否则 (1)若el小于p所指结点的关键码，则令p指向所指结点的 左儿子；若el大于p所指结点的关键码，则令p指向所 指结点的右儿子； 重复(1)直至p为空或p所指结点的关键码与el相等； 返回p。 73 排序二叉树的查找（非递归函数 ） template Tnode *Tpxrc : sear1(elemtp el) Tnode *p; p=root; while(p!=NULL) if (el data) p=p-lchild; else if (el p-data) p=p-rchild; else break; return(p); 74 排序二叉树的查找 执行实例 在以下的排序二叉树中 （1）查52 （2）查53 5757 4343 1818 61615252 1616 25251414 3232 75 具有插入功能的查找（递归） template void Tpxrc : inst0(Tnode *p,Tnode * else if (p-data data ) inst0( p,pxrc-lchild); else inst0( p,pxrc-rchild); ; 77 具有插入功能的查找（接口函数） template void Tpxrc :inst(elemtp el)； 功能为：在当前的排序二叉树上查找关键字等于给定值 el的结点，当查找成功时输出相应的信息，否则建立 一个新结点并插入在当前排序二叉树的适当位置中。 Tnode *p; p = sear(el); if (p != NULL ) ShowMessage(“HAVE FOUND “); else p=new Tnode ; p-data=el; p-lchild=NULL; p-rchild=NULL; inst0(p,root); 78 具有插入功能的查找（非递归） template void Tpxrc : inst1(elemtp el) 其参数与递归函数相同，其处理过程与非递归的查找算 法相类 实现技巧：设置一个指针型的变量q表示当前结点指针p 的双亲。在查找不成功的情形下，p=NULL,而新建的结 点正好要挂在q的左支或右支上。 处理过程： (1)令p为root，在p所指的排序二叉树中搜索关键码等于 el的结点（按以上介绍的非递归查找算法），并设置q ； (2)若未找到则生成一个关键字值为el的新结点p，若为 空树则令root=p否则按大小将p挂在q的左支或右支上 。 79 具有插入功能的查找（非递归） template void Tpxrc :inst1(elemtp el) Tnode *p,*q; int tag; tag=0; p=root; while (p != NULL) if (el data) p=p-lchild; else if (el p-data) p=p-rchild; else tag=1; ; if (tag = 0) p=new Tnode ; p-data=el;p-lchild=NULL;p-rchild=NULL; if (root=NULL)root=p; else if (el data) q-lchild= p; else q-rchild=p; ; 80 B树的结构特点 B树也是一种动态的查找树，可将B树看作为排序 二叉树的扩展。 在排序二叉树的结点中存放一个关键字并连接二棵子 树，但一个m阶的B树，每个结点中最多可以有m 个分支，m-1个关键字。其结构的特点是： 平衡、有序、多路 用于文件目录管理 81 B树的结构特点 平衡、有序、多路 45 10050 24 312 3037 5390 6170 平衡：所有的叶节点都在同一层上，可看作为查找的失败节 点 82 B树的查找 查找过程： （1）顺指针查找结点 （2）在结点中顺序查找 在B树上进行查找的过程也就是这二种基本操作交叉进 行的过程。 结果信息： （1）指向结点的指针pt; （2）结点中的关键字序号i； （3）是否成功的标记tag; 当tag=1时表示查找成功，返 回pt结点中的第i个关键字；当tag=0时表示查找不成 功，等于k的关键字应插入到pt结点中的第i个与第i+1 个关键字之间； 例： 在上述B树的查找关键字为37的节点 83 B树的插入 情形1：插入关键字的结点在插入后关键字的个 数不超过m-1 24 3037 45 84 B树的插入 情形2：插入关键字的结点在插入后关键字的个数超过m-1， 则进行分裂处理。假设当前处理的结点由q指向，以m/2（取 整）为界，将结点q分裂成二个结点，前面部分仍由q指向， 后面部分由q1指向，而中间的一个关键字带着指针q1被上 挤到双亲结点中。 24 2637 45 30 24 26 37 45 30 85 B树的插入 情形3：在执行情形2的上挤处理后，双亲结点中的关键字 个数超过了m-1个，则必须以该双亲结点为当前结点，进行相同 的处理，也就是说要继续上挤直至根结点。一旦根结点中 的关键字个数超过了m-1个，对根结点进行分裂处理后，整个B 树的层树即增加一层。 2470 45 bt 70 45 24 bt 86 B+树的结构特点 B树是由一个有序序列和一个层次索引所组成。 有n棵子树的结点中含有n个关键字。 所有的叶子结点中包含了全部关键字的信息，及相应的记录指 针，且叶子结点本身依关键字的大小自小而大顺序链接。 21443751 5910 1563 72859791 15594472 97 59 97 sqt root 87 m阶B+树的形成过程： 1. 将一个有序序列中的关键字分成若干组合，每一个组合作为一 个结点，每个结点中的关键字个数都小于或等于m。这些结点就 构成了B树最低层中的所有叶子结点。 2. 建立一层索引。即将当前层的结点分成若干组，每一组包括一 些结点，但每一组中的结点个数都小于或等于m，然后对每一组 建立一个索引结点，该结点中的关键字是由该组中各结点的最 大关键字组成。这一过程形成了一个由当前层索引结点组成的 新一层的结点序列。 3. 用相同的处理过程为新一层的结点序列再建立索引，逐层向上 ，直至建立根结点， 21443751 5910 1563 72859791 15594472 97 59 97 sqt root 88 B+树的查找： B树既可以进行顺序查找又可以进行随机查找。通常在B树上 设置二个头指针，一个指向根结点，另一个指向关键字最小的 叶结点。因此既可以从最小的关键字起对B树进行顺序查找， 又可以从根结点开始对B树进行随机查找。 查找时，即使结点上的值等于给定的值，也要继续查找到叶结点 。因此对B树，不管查找成功与否，每次查找都走了一条从根 到叶结点的路径。 21443751 5910 1563 72859791 15594472 97 59 97 sqt root 89 哈希表 哈希表的概念 通过建立记录的关键字与存储地址的对应关系，使得 直接可以由关键字得到记录的存储地址。这种转换 过程称为映射，相应的查找方法称为哈希查找。 addr(Ri)=H(Ri .key) 其中，函数H称为哈希函数，H（K）的值称为哈希地址 ，由关键字的值K得到存储地址H（K）的过程称为映 射。 90 哈希表 哈希函数的例 （1）取关键字中第一个字母在字母表中的序号作为 哈希函数。 （2）先求关键字的第一个和最后一个字母在字母表 中的序号之和，若比30（表长）大，则减去30。 222828170409 F2(key) 081919082002 F1(key) HENAN （河南） SHANG HAI（上 海） SHANXI （山西） HEBEI（ 河北） TINGJIN （天津） BEIJING （北京） key 91 哈希表 冲突： 不同的关键字可能得到同一个哈希地址，即key1key2 ，而H(key1)= H(key2)，这种现象称为冲突。 具有相同函数值的关键字对该哈希函数来说称为同义 词。 决定冲突可能性大小主要有以下一些因素： （1）装填因子，即查找表中已存入元素的个数n与哈 希表的存储空间长度m之比。 （2）哈希函数以及解决冲突的方法。 92 哈希函数 直接地址法： 方法：取关键字或关键字的某个线性函数值为哈希地址 。即： H(key)=key 或 H(key)= a * key + b 例：查找表是一张人口数字统计表， 若该查找表以年龄作为关键字，则哈希函数取关键字自 身，这样可以直接由年龄得到相应的记录的存储地址 ； 若以年份作为关键字，起始年份为1949，则哈希函数可 取关键字加一常数即H(key)=key 1948； 特点：不会发生冲突，而且构造方法特别简单。但只适 用于关键字分布基本连续，且关键字集合较小的情形 。 93 哈希函数 数字分析法 方法：通过分析关键字集合中的每一位数码的分布情 况，找出数码分布均匀的若干位作为哈希地址。 例如：有如下8个关键字，每个关键字由七位十进数组成： K1 = 6151141 K2 = 6103274 K3 = 6111034 K4 = 6138299 K5 = 6120874 K6 = 6170924 K7 = 6140637 K8 = 6145694 第3、5位数字重复较少即分布较均匀，于是取第3、5 位数字作为哈希地址即： H(K1)=51, H(K2)=02, H(K3)=10, H(K4)=32, 特点：数字分析法适用于关键字为数字的情形，且可 能出现的关键字均事先知道。 94 哈希函数平方取中法： 方法：平方取中法是取关键字平方后的中间几位数作 为哈希地址。由于平方后的中间几位数与原关键字 的每一位数字都相关。因此只要关键字的分布是随 机的，由平方取中法所得到的哈希地址也应该是随 机的。所截取的位数由表长确定。 例：关键字为十进制4位，表长为1000，则可取平方后 的第2、3、4位作为哈希地址。 1200 1440000 440 特点：适用于关键字为数字、且分布较均匀的情形。 95 哈希函数 折叠法： 方法：将关键字分成几段，每一段的长度等于地址的 位数，然后取这几段的叠加和（舍去进位）作为哈 希地址 。 例：身份证号码为430204540628231,采用移位叠加和 间界叠加得到哈希地址分别为429和033 特点：适用于关键字为数字、且为数较多的情形。 96 哈希函数 除留余数法 方法：将关键字被某个不大于哈希表表长m的数p除， 并取其余数为哈希地址。即： H(key)= key MOD p (p=0) 其中，s是串的名，也称为串变量。单引号内的字符 序列为串值；ai (1in)可以是字母、数字或其 它字符。 例如： a = Datab = Structure c = DataStructured = Data Structure 105 基本术语 长度 串中所包含的字符个数n 空串 长度为0的串 子串 串中任意个连续的字符组成的子序列 主串 包含子串的串称为该子串的主串 位置 字符在序列中的序号 子串的位置 子串的第一个字符在主串中的位置 例如对于上述给出的串a、b、c、d 长度分别为4、9、13和14；并且a和b都是c和d的子 串，a在c和d中的位置都是1，而b在c中的位置是5 ，在d中的位置则是6。 106 主要的基本操作 求子串 substring(s,start,len) 返回值为串s中第 start个字符起，长度为len的字符序列 插入 insert(s,pos,t) 在串s的第pos个字符之后插 入串t 删除 delete(s,pos,len) 从串s中删去第pos个字符 起长度为len的子串 定位 position(s,t) 若t在s中存在，则返回t在主串 s中的位置，否则函数值为0 替换 replace(s,t,v) 操作结果是以串v替换所有在 串s中出现的和非空串t相等的子串 判相等 equal(s,t) 若s和t相等，则返回true否则返 回false。 求长度 length(s) 返回s中字符的个数 107 串的存储方式 串的存储结构串的存储结构 顺序存储结构 链式存储结构（一般不使用）链式存储结构（一般不使用） 堆式存储结构 108 顺序存储结构类型定义 const maxlen = 允许的串最大长度; typedef struct int curlen; char ch maxlen; strtp; 109 堆式存储结构 存储空间 系统中设置一个容量很大、地 址连续的存储空间作为串值的可利用空 间，当建立一个新串时，系统就从这个 空间中分配一个大小和串长相同的空间 存储新串。 映象空间 同时建立一个串的描述符来指示 串的地址及长度，系统中所有串的描述 符构成了一张从串名到串的映射表即构 成了映象空间。 B E IJ E N G ITEM SL a13 b54 c18 110 顺序串的类定义 const int deflen=50; class Tstr private: char *ch; int curlen; int maxlen; public: Tstr(String s=“abc“,int sz=deflen); void init(String s); void subs(int pos,int len,Tstr int position(Tstr t); void dele(int pos,int len); void inst(int pos,Tstr t); void replace(Tstr t,Tstr r); ; 111 顺序串类定义 的构造函数 功能：按指定的长度分配存储串的空间，拷贝s并设置 maxlen及curlen变量初值。 说明：这里对参数s与sz都指定了缺省值，在实例化时 ，可以不指定参数或只指定字符串初值一个参数。但 在静态定义类的实例时，如果完全省去参数则应将括 号也一起省去。 程序代码： Tstr:Tstr(String s,int sz) int i,len; ch=new charsz; StrPCopy(ch,s); curlen=s.Length(); maxlen=sz; ; 112 求子串操作 操作的含义 s s subsub Pos+Pos+lenlen-1-1 pospos lenlen 113 求子串操作 void Tstr:subs(int pos,int len, Tstr 功能：在当前串中截取从pos开始的长len的子串，并将其 复制入字符串t中。 处理过程： (1)检查参数的合法性，即当pos curlen 或pos s.curlen-pos+1时，则按截尾法对len进行调 整 (4)（3）将当前串中从pos开始的长度为len的内容复制到串 t中 114 求子串操作 参数的范围 1poss.curlen 1lens.curlen-pos+1 但当lens.curlen-pos+1 可将其调整为lens.curlen-pos+1， 即当截取长度超出最大可供截取长度，则将其缩短 例如s的长度为10， pos=8, len的范围应该在1与3之 间，如果len指定为5，则可将其调整为3 115 求子串操作程序代码 void Tstr:subs(int pos,int len, Tstr char *s; if (pos curlen)|(lencurlen-pos+1) len= curlen-pos+1; t.curlen=len; for(i=0;it.curlen ) return(i-t.curlen); else return(0); ; 120 删除操作 操作的含义 删除删除前前 Pos+Pos+lenlen-1-1 pospos 删除删除后后 121 删除操作 void Tstr:dele(int pos,int len); 功能：在当前串中删除从pos开始的，长度为len的子串 处理过程： (1) 检查参数的合法性，即当pos curlen 或pos, len s.curlen-pos+1时，则按截尾法对len进行调整。 1.(3)删除当前串中从pos开始的长度为len的子串， 即重新形成当前串中pos开始至新串串尾的新串长度 (curlen-len)-pos+1个字符，这些字符分别由相隔len 个位置的对应字符前移而来，如图5.7所示。 122 删除操作 参数的范围 1poss.curlen 1lens.curlen-pos+1 但当lens.curlen-pos+1 可将其调整为lens.curlen-pos+1， 即当删除长度超出最大可删除长度时对其进行调整 例如s的长度为10， pos=8, len的范围应该在1与3之 间，如果len指定为5，则可将其调整为3 123 删除操作程序代码 void Tstr:dele(int pos,int len) int i; if (poscurlen) | (lencurlen-pos+1 ) len=curlen-pos+1; for (i=pos; i s.curlen-len 即pos+len s.curlen 时 循环一次也没执行（无需 移动） 125 插入操作 操作的含义 插入后插入后 S S 新串的长度新串的长度lenlen pospos 插入插入前前 S S t t t. t.curlencurlen 后移部分的长度后移部分的长度 n n 126 插入操作 void Tstr:inst(int pos,Tstr t); 功能：在当前串中pos指示的位置起插入串t。 处理过程： (1)当插入位置超出合法值或当前串长已达最大值，即当 pos maxlen 或curlen = maxlen时，显示出错 信息并终止。 (2) 当插入位置合法，即当1poscurlen1时，则将串 t插入当前串中pos开始的位置，如图5.8所示。其中，如 当前串与t之和超过了当前串的最大长度，则采用截尾法 截去超长部分，如图5.9所示。 (3) 当插入位置在串长范围以外但小于等于串长最大值， 即当curlen+1 maxlen 或poscurlen+1 else if (curlen=maxlen) ShowMessage(“overflow“); else tlen=t.curlen; if (pos curlen+1) pos=curlen+1; if (curlen + tlen 0) for (i=1;ilen) break; else chpos+i- 1=t.chi; curlen=len; ; ; 130 插入操作 字符的后移 数据的后移 （后移是从后面的字符开始移动） for (i=1;ilen 不必再移 这是超长的情形 因此，整个数据移动过程可使用下列循环语句来表示 : for (i=0;ilen) break; else chpos+i-1=t.chi; 132 替换操作 操作的含义 S S pospos t t r r r r 133 替换操作 void Tstr:replace(Tstr t,Tstr r); 功能为在当前串中用子串r替换子串t。 处理过程： (1)查找子串t在主串中的位置； (2) 在主串中删除子串t； (3) 在主串中原来t的位置上插入子串r。 134 替换操作程序代码 void Tstr:replace(Tstr t,Tstr r) int pos; pos=position(t); if (pos=0) ShowMessage(“infeasible“); else dele(pos,t.curlen); inst(pos,r); ; ; 135 演示 结束 136 版权所有, 1997 (c) Dale Carnegie struct node *next; ; typedef struct node *link; typedef struct link front; link rear; lquetp; lquetp lq1; 当lq1.front=lq1.rear时，这个队列就成为空队 列，否则，lq1.front-next指向队头结点，而 lq1.rear指向队尾结点。 datanext front rear 145 顺序队列的结构形式 用一组地址连续的存储单元来依次存储队列中 的各个元素。 空队列及队列的变化 j5 j4 Elem0max-1 Max-1 rear front d c b a d front rear rear front f e d rear rear front front 146 顺序队列类型定义 const int max队列中允许存放元素个数的最大值 ； typedef struct elemtp elemmax; int front,rear; squetp； squetp sq1； sq1.elemsq1.front表示队头元素 sq1.elemsq1.rear-1 表示队尾元素 147 顺序队列状态判别 判队列为空：front=rear 判队列满rear=max （但这是假溢出） 当队列非空时，可执行如下的出队操作： data=elemfront+; 当队列非满时，可执行如下的入队操作： elemrear+=data; 148 循环队列 为了避免假溢出 可使用循环队列 空队列 队列中有一个元素 队列满 1 0 front rear 1 0 front rear 1 0 front rear 149 循环队列状态判别 判队列为空：front=rear 判队列满(rear+1) % max = front 当队列非空时，可执行如下的出队操作： data=elemfront; front=(front+1) % max; 当队列非满时，可执行如下的入队操作： elemrear=data; rear= (rear+1) % max; 150 循环队列类定义 const int deflen=12; template class Tcq private: int front,rear,len; elemtp *elem; public: Tcq(int sz=deflen); bool enq (elemtp el); elemtp dlq(); int leng(); bool empt(); bool full(); ; 151 循环队列类的构造函数 template Tcq : Tcq(int sz) len=sz; elem=new elemtplen; front=0; rear=0; ; 功能：按参数中指定的长度分配循环队列的空间 ， 并设置front、rear变量初值。 152 循环队列入队操作 template bool Tcq : enq (elemtp el) 功能：在循环队列中插入元素el。若循环队列未满， 则插入el为新的队尾元素并返回函数值true，否则 队列的状态不变且返回函数值false。 处理过程： (1) 判是否队列满，若队列满则返回false， （2）否则：将el从队尾插入队列，尾指针加1并返回 true。 153 循环队列入队操作程序代码 template bool Tcq : enq (elemtp el) if ( (rear+1)% len = front ) return(false); else elemrear=el; rear= (rear+1)% len; return(true); ; 154 循环队列出队操作 template elemtp Tcq : dlq(); 功能：若循环队列