《数据的增删改查询算法》由会员分享，可在线阅读，更多相关《数据的增删改查询算法（60页珍藏版）》请在金锄头文库上搜索。
1、数据的增删改查询算法,2018/10/23,2018/10/23,2018/10/23,用SQL实现数据的增,数据插入：INSERT语句的功能是向指定的表中插入由VALUES指定的行或子查询的结果（1）插入元组：插入元组的INSERT语句基本格式如下：INSERT INTO(,.)VALUES(，.)该语句的功能是将VALUES子句中各常量组成的元素添加到所指定的表中。表中新元组的列1值为常量1，以此类推（2）插入子查询结果：子查询可用在INSERT语句中，将生成的结果集插入到指定的表中。插入子查询结果的INSERT语句格式如下：INSERT INTO(,.) INTO子句中得列数要和SELE
2、CT子句中得表达式个数一致，数据类型也要一致,2018/10/23,例如：在Student表中插入Scome出生时间列,2018/10/23,2018/10/23,用SQL实现数据的删,数据删除：SQL语言中删除数据可以使用DELETE语句来实现。其基本格式如下：DELETEFROMWHERE该语句的功能是从指定的表中删除满足条件的元组。若省略WHERE子句，表示删除表中的所有行。注意：DELETE删除的是表中的数据，而不是表的结构。,2018/10/23,例如：删除SC中得002行,2018/10/23,2018/10/23,用SQL实现数据的改,数据修改：SQL语言中用于修改表数据行的语句
3、是UPDATE其基本格式如下：UPDATEASSET=,=.WHERE该语句的功能是修改指定表中满足WHERE子句指定条件的元组。其中SET子句给出需修改的列及其新值。若不使用WHERE子句，则更新所有记录的指定列值,2018/10/23,例如：更新学号为001的学生年龄为25,2018/10/23,2018/10/23,用SQL实现数据的查询,数据查询：SQL用SELECT语句进行数据库查询，SELECT语句 的基本格式如下：SELECTALL|DISTINCT,.FROM,.WHERE -WHERE子句，指定查询条件GROUP BY -GROUP BY子句，指定分组表达式HAVING -H
4、AVING子句，指定分组过滤条件ORDER BYASC|DESC -ORDER子句，指定排序表达式和顺序整个SELECT语句的含义是：根据WHERE子句的条件表达式，从FROM子句指定的基本表或试图中找出满足条件的元组，再按SELECT子句中得目标列表表达式，选出元组中得分量形成结果表。其中的定义如下：* -选择当前表或视图的所有列|.*|.*|.* -选择指定的表或视图的所有列|列名AS -选择指定的列| -选择表达式其中，和是表或列的临时替代名称,2018/10/23,用SQL实现数据的查询,单表查询 选择表中指定的列选择满足条件的元组（即行）,2018/10/23,用SQL实现数据的查询
5、,对查询结果排序,2018/10/23,用SQL实现数据的查询,2018/10/23,用SQL实现数据的查询,使用集函数,2018/10/23,用SQL实现数据的查询,对查询结果分组,2018/10/23,例如：查询所有学生的学号和姓名,2018/10/23,用SQL实现数据的查询,多表查询 连接查询：若一个查询同时涉及两个或两个以上的表，则称为连接查询。结果通常是含有参加连接运算的两个或多个表的指定列的表。连接查询有两种形式，一种是采用连接谓词，形式如下：BETWEENAND另一种是以JOIN关键字指定的连接，包含内连接(INNER JOIN)和外连接（OUTER JOIN）。 内连接按照O
6、N所指定的连接条件合并两个表，返回满足条件的行。语法格式为：FROMJOINON=外连接包含满足连接条件的行和相应表中的所有行，而连接谓词和内连接查询中，只有满足连接条件的行。,2018/10/23,用SQL实现数据的查询,嵌套查询：在SQL语言中，一个SELECT-FROM-WHERE语句称为一个查询块，在WHERE子句或HAVING子句所表示的条件中，可以使用另一个查询的结果（即一个查询块）作为条件的一部分，这种将一个查询块嵌套在另一个查询块的WHERE子句的条件查询称为嵌套查询。如：SELECT 客户姓名 -外层查询或父查询FROM KHBWHERE 客户编号 IN（SELECT 客户编
7、号） -内层查询或子查询FROM SPDGBWHERE 商品编号=10010001）下层查询块“SELECT 客户编号 FROM SPDGB WHERE 商品编号=10010001”是嵌套在上层查询块“SELECT 客户姓名 FROM KHB WHERE 客户编号 IN”的条件中的,2018/10/23,用SQL实现数据的查询,集合查询多个SELECT语句的结果集可以进行集合操作。集合操作主要包括：并（UNION）、交（INTERSECT）、差（EXCEPT）例如：查询订购了编号为“10010001”或“10020001”商品的客户的编号SELECT 客户编号FROM SPDGBWHERE 商
8、品编号=10010001UNIONSELECT 客户编号FROM SPDGBWHERE 商品编号=10020001,2018/10/23,用SQL实现数据的查询,视图查询：首先进行有效性检查，检查查询的表、视图是否存在。如果存在，那么从系统表中取出视图的定义，把定义中得子查询和用户的查询结合起来，转换成等价的对基本表的查询，然后在执行转换以后的查询,2018/10/23,例如：查询分数低于90的学生的学号和年龄,2018/10/23,（a）建立Course表（b）建立SC表（c）建立Student表,算法,算法：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多
9、个操作,（Algorithm）,算法特点,算法设计的要求,正确性,可读性,健壮性,衡量标准：程序对于典型、苛刻而带有刁难性的输入数据是否能够得出满足说明要求的结果,可读性好有助于人对算法的理解，难懂的程序易于隐藏错误，难以调试和修改,当输入数据非法时，算法也能适当做出反应或进行处理，而不是产生莫名其妙的输出结果,1,2,3,执行时间最短的算法 低存储量即算法执行过程中所需要的最大存储空间最小,效率与低存储量,4,算法效率的度量,2018/10/23,度量一个算法的执行时间（即该算法编制的程 序在计算机上运行时所消耗的时间）有两种方法：,事后统计的方法：不同算法的程序可通过计算机内部的及时功能得
10、到的时间统计数据以分辨优劣（所得的统计量依赖于计算机软硬件等环境因素，容易掩盖算法本身的优劣，一般不用）,依据的算法选用何种策略问题的规模 事前分析估算的方法 书写程序的语言编译程序所产生的机器代码的质量机器执行指令的速度,查找表：一种在实际应用中大量使用的数据结构,静态查找表：（1）（2）,动态查找表：（1）（2）（3）（4）,静态表查找类型,2018/10/23,静态查找表,顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字（数据元素或记录中某个数据项的值，用它可以标识一个数据元素或记录）和给定值比较相等则查找成功，找到所查记录；反之，若直至第一个记录
11、，其关键字和给定值比较都不等，则表明没有查找记录，查找不成功int Search Seq(SSTable ST,KeyType key)/在顺序表ST中顺序查找其关键字等于key的数据元素，若找到，则/函数值为该元素在表中的位置，否则为0.ST.elem0.key=key; /把key放在0位置for(i=ST.length;!EQ(ST.elemi.key,key) -i);/从后往前找return i; /找不到时，i为0,2018/10/23,静态查找表,有序表的查找：先确定待查记录所在的范围（区间），然后缩小范围直到找到或找不到该记录为止，过程如下折半查找算法描述所示：当n较大时，平均
12、查找长度近似为：,2018/10/23,静态表查找,静态最优查找树：即带权内路径长度之和PH值取最小的二叉树（构造静态查找树花费的时间代价较高，一般不用）其中：n为二叉树上结点的个数（即有序表的长度）；hi为第i个结点在二叉树上得层次数；节点的权 （i=1，2，.，n），其中pi为结点的查找概率，c为某个常量,2018/10/23,次优查找树：即PH值在所有具有同样权值的二叉树中近似为最小，类似于折半查找。在查找概率不等时，可用次优查找树表示静态查找树，故又称静态树表，按有序表构造次优查找树的算法如下：,静态表查找,2018/10/23,静态表查找,索引顺序表查找：Search函数可用分块查找
13、来实现。此查找法，除表本身外还需建立一个“索引表”。如图所示，先将表分为几块，索引表中得是每块的起始地址和关键字，查找过程分两步，先确定待查记录所在的块，然后在块中顺序查找,动态查找表特点,表结构本身是在查找过程中动态生成的，即对于给定值key若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录,动态表查找类型,2018/10/23,动态表查找（一）,二叉排序树查找：它的查找过程和次优二叉树类似。即当二叉排序树不空是，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找，查找过程如
14、以下算法所描述,2018/10/23,考虑到二叉排序树是一种动态数表，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入，为此，需将算法改成如下：,2018/10/23,增(即插入数据),二叉排序树在查找的过程中，当树中不存在关键字等于给定值的结点时进行插入，插入算法如下：,2018/10/23,删除数据,在二叉排序树上删去一个结点：假设在二叉排序树上被删结点为*p（指向结点的指针为p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，下边分3种情况进行讨论：,对于一般的二叉树来说，删去树中一个结点时没有意义的。因为它将使以被删
15、结点为根的子树成为森林，破坏了整棵树的结构。然而对于二叉排序树来说，删去一个结点相当于删去有序序列中得一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。,2018/10/23,（3）若*p结点的左子树和右子树均不空。如图（b）在删去*p结点之前，序列为 ，在删去*p之后，为保持其他元素之间的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，如图（c）所示；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继），如图（d）所示，当以直接前驱*s替代*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可,2018/10/23,二叉排序树删除算法,2018/10/23,动态表查找（二）,平衡二叉树的查找过程和二叉排序树的过程相同,平 空树 衡 左、右子树都是平衡二叉树 二 具有以下两 叉 个性质的树 左子树和右子树的深度之差 树 （平衡因子）绝对值不超过1,
