第四章数据库设计基础.doc
《第四章数据库设计基础.doc》由会员分享,可在线阅读,更多相关《第四章数据库设计基础.doc(43页珍藏版)》请在咨信网上搜索。
1、个人收集整理 勿做商业用途第一章 数据结构与算法 一、内容要点 (一)算法 1算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,没有二义性,同时该规则将在有限次运算后可终止。 1)算法的基本特征 (1)可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的,因此,它总是受到计算工具的限制,使执行产生偏差。 如:计算机的数值有效位是有限的,当大数和小数进行运算时,往往会因为有效位数的影响而使小数丢失,因此,在算法设计时,应该考虑到这一点。 (2)确定性 算法的设计必须是每一个步骤都有明确的定义,不
2、允许有模糊的解释,也不能有多义性。 例如,一个实际的问题,小宝和萍萍共有12个苹果,小宝比萍萍多4个,请问小宝和萍萍各有几个苹果?这个问题,我们可以立一个方程组x+y=12和xy=4来求解,要求x和y的值,公式是正确的,但如何让计算能够进行计算,我们的算法不能把公式直接输进去,而应该设计出解题的步骤和过程。 即设计的算法是计算工具所能够正常解决问题的过程. (3)有穷性 算法的有穷性,即在一定的时间是能够完成的,即算法应该在计算有限个步骤后能够正常结束。 例如,在数学中的无穷级数,在计算机中只能求有限项,即计算的过程是有穷的。 (4)拥有足够的情报 算法的执行与输入的数据和提供的初始条件相关,
3、不同的输入或初始条件会有不同的输出结果,提供准确的初始条件和数据,才能使算法正确执行。 2)算法的基本要素 一是数据对象的运算和操作,二是算法的控制结构。 (1)算法中对数据的运算和操作 算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列. (2)算法的控制结构 算法的功能不仅取决于所选用的操作,而且还与各操作之间的顺序有关。 在算法中,操作的执行顺序又称算法的控制结构,一般的算法控制结构有三种:顺序结构、选择结构和循环结构。 在算法描述是,有相关的工具对这三种结构进行描述,常用的描述工具有:流程图、N-S结构图和算
4、法描述语言等. 3)算法设计的基本方法 为用计算机解决实际问题而设计的算法,即是计算机算法。 通常的算法设计有如下几种: (1)列举法 列举法的基本思想是,根据提出的问题,列举出所有可能的情况,并用问题中给定的条件检验哪些是满足条件的,哪些是不满足条件的。列举法通常用于解决“是否存在或“有哪些可能”等问题。 例如,我国古代的趣味数学题:“百钱买百鸡”、“鸡兔同笼”等,均可采用列举法进行解决。 使用列举法时,要对问题进行详细的分析,将与问题有关的知识条理化、完备化、系统化,从中找出规律. (2)归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系.归纳是一种抽象,即从
5、特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举,因此,该方法得到的结论只是一种猜测,还需要进行证明。 (3)递推 递推,即是从已知的初始条件出发,逐次推出所要求的各个中间环节和最后结果.其中初始条件或问题本身已经给定,或是通过对问题的分析与化简而确定. 递推的本质也是一种归纳,递推关系式通常是归纳的结果。 例如,裴波那契数列,是采用递推的方法解决问题的。 (4)递归 在解决一些复杂问题时,为了降低问题的复杂程序,通常是将问题逐层分解,最后归结为一些最简单的问题.这种将问题逐层分解的过程,并没有对问题进行求解,而只是当解决了最后的问题那些最简单的问题后,再沿着原来分解的逆过程
6、逐步进行综合,这就是递归的方法. 递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己,称为直接递归调用;如果一个算法A调用另一个算法B,而算法B又调用算法A,则此种递归称为间接递归调用。 (5)减半递推技术 减半递推即将问题的规模减半,然后,重复相同的递推操作. 例如,一元二次方程的求解。 (6)回溯法 有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤,也不能使用无限的列举。对于这类问题,只能采用试探的方法,通过对问题的分析,找出解决问题的线索,然后沿着这个线索进行试探,如果试探成功,就得到问题的解,如果不成功,再逐步回退,换别的路线进行试探。这种方法,即称为回溯法. 如人
7、工智能中的机器人下棋。 2算法复杂度 算法的复杂度包括时间复杂度和空间复杂度。 1)时间复杂度 即实现该算法需要的计算工作量.算法的工作量用算法所执行的基本运算次数来计算。 同一个问题规模下,如果算法执行所需要的基本次数取决于某一特定输入时,可以用以下两种方法来分析算法的工作量: 算法工作量=f(n) (1)平均性态 用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设x是某个可能输入中的某个特定输入,p(x)是x出现的概率,t(x)是算法在输入为x时所执行的基本运算次数,则算法的平均性态定义为:Dn表示当规模为n时,算法执行时所有可能输入的集合。 (2)最坏情况复杂度 指在规模
8、为n时,算法所执行的基本运算的最大次数.它定义为: 例如,在具有n个元素的数列中搜索一个数x. 平均性态: 即该数在数列中任何位置出现的数列是相同的,也有可能不存在,存在的概率为q。 如果有一半的机会存在,则概率q为1/2,平均性态: 如果查找的元素一定在数列中,则每个数存在的概率即为1,则平均性态为: 最坏情况分析:即要查找的元素X在数列的最后或不在数列中,显然,它的最坏情况复杂度为:2)算法的空间复杂度 指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间,如执行过程中工作单元以及某种数据结构所需要的附加
9、存储空间等。 (二)数据结构的基本概念 1概念 数据结构是指相互有关联的数据元素的集合。它包括以下两个方面: 表示数据元素的信息 表示各数据之间的前后件关系 1)数据的逻辑结构 是指反映数据元素之间的逻辑关系的数据结构。 数据的逻辑结构有两个要素: 数据元素的集合,记作D 数据之间的前后件关系,记作R 则数据结构B=(D,R) 2)数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构,或数据的物理结构。 即数据存储时,不仅要存放数据元素的信息,而且要存储数据元素之间的前后件关系的信息。 通常的数据存储结构有顺序、链接、索引等存储结构. 2数据结构的图形表示 数据结构的图
10、形表示有两个元素: 中间标有元素值的方框表示数据元素,称为数据结点 用有向线段表示数据元素之间的前后件关系,即有向线段从前件结点指向后件结点 注意:在结构图中,没有前件的结点称为根结点,没有后件的结点称为终端结点,也称叶子结点。 3线性结构与非线性结构 如果一个数据元素都没有,该数据结构称为空数据结构;在空数据结构中插入一个新的元素后数据结构变为非空数据结构;将数据结构中的所有元素均删除,则该数据结构变成空数据结构。 如果一个非空的数据结构满足如下条件,则该数据结构为线性结构: 有且只有一个根结点 每一个结点最多只有一个前件,也最多只有一个后件 线性结构又称线性表. 注意:在线性结构表中插入或
11、删除元素,该线性表仍然应满足线性结构。 (三)线性表及其顺序存储结构 1基本概念 线性表是最常用的数据结构,它由一组数据元素组成。 注意:这里的数据元素是一个广义的数据元素,并不仅仅是指一个数据。如,矩阵、学生记录表等. 非空线性表的结构特征: 有且只有一个根结点,它无前件 有且只有一个终端结点,它无后件 除根结点和终端结点之外,所有的结点有且只有一个前件和一个后件。线性表中结点的个数称为结点的长度n。当n=0时,称为空表。 2顺序存储结构 顺序存储结构的特点: 线性表中所有的元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 通常,顺序存储结构中,线性表中每一个
12、数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。 线性表的顺序存储结构下的基本运算: 在指定位置插入一个元素 删除线性表中的指定元素 查找某个或某些特定的元素 线性表的排序 按要求将一个线性表拆分为多个线性表 将多个线性表合并为一个线性表 复制线性表 逆转一个线性表 3线性表的基本操作 1)顺序表的插入运算 在顺序存储结构的线性表中插入一个元素。 注意:找到插入位置后,将插入位置开始的所有元素从最后一个元素开始顺序后移。另外,在定义线性表时,一定要定义足够的空间,否则,将不允许插入元素。 2)顺序表的删除运算 在顺序在存储结构的线性表中删除一个元素。 注意:找到删除的
13、数据元素后,从该元素位置开始,将后面的元素一一向前移动,在移动完成后,线性表的长度减1 如果一个数据结构不满足线性结构,则称为非线性结构。(四)栈和队列 1栈及其基本运算 1)栈 栈是一种特殊的线性表,它是限定在一端进行插入和删除的线性表.它的插入和删除只能在表的一端进行,而另一端是封闭的,不允许进行插入和删除操作。 在栈中,允许插入和删除操作一端称为栈顶,不允许插入和删除操作的一端则称为栈底。栈顶的元素总是最后被插入的元素,也是最先被删除的元素。它遵循的原则是:先进后出或后进先出. 堆栈指针总是指向栈顶元素的。 2)栈的顺序存储及其运算 在栈的顺序存储空间S(1:m)中,S(bottom)通
14、常为栈底元素,S(top)为栈顶元素。Top=0表示栈空;top=m表示栈满。 1)入栈运算 即在栈的顶部插入一个新元素。操作方式是:将栈顶指针加1,再将元素插入至指针所指的位置. 2)退栈运算 退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是:先将栈顶元素赋给指定的变量,再将栈顶指针减1. 3)读栈顶元素 将栈顶元素赋给某一指定变量,但栈顶指针不变。 2队列及其基本运算 1)队列 队列即是允许在一端进行插入,而在另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个尾指针指向队尾;允许删除的一端称为队首,通常用一个队首指针指向排队元素的前一个位置。 队列遵循的规则是:先进先出或后
15、进后出 2)循环队列及其运算 队列的顺序存储结构一般采用循环队列的形式。 循环队列,即是次队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。 在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从排头指针front指向的后一个位置到队尾指针rear指向的位置之间所有的元素均为队列中的元素。 循环队列的初始状态为空,即rear=front=m。这里m即为队列的存储空间。 循环队列的基本运算:入队运算和退队运算. 入队运算:每进行一次入队运算,队尾指针加1。当队尾指针rear=m+1时,即表示队列空间的尾部已经放置
16、了元素,则下一个元素应该旋转到队列空间的首部,即rear=1 退队运算:每退队一个元素,排头指针加1。当排头指针front=m+1时,即排头指针指向队列空间的尾部,退队后,排头指针指向队列空间的开始,即front=1。 在队列操作时,循环队列满时,front=rear,队列空时,也有rear=front,即在队列空或满时,排头指针和队尾指针均指向同一个位置.要判断队列空或满时,还应增加一个标志,s值的定义: 判断队列空与队列满的条件下: 队列空的条件:s=0 队列满的条件:s=1、front=rear (1)入队运算 即在队尾加入一个新元素.这个运算有两个基本操作:首先,将队尾指针加1,即re
17、ar=rear+1,当rear=m+1时,置rear=1,然后,将新元素插入到队尾指针指向的位置。 当循环队列非空(s=1),且front=rear时,队列满,不能进行入队操作。此情况称“上溢”。 (2)退队操作 即将队首的元素赋给一个指定的变量。该运算也有两个基本操作:首先,将排头指针加1,即front=front+1,当front=m+1时,置front=1,然后,将排头指针指向的元素赋给指定的变量。 当循环队列为空(s=0)时,不能进行退队运算。此种情况称为“下溢”。 (五)线性链表 1基本概念 前面的线性表均是采用顺序存储结构及在顺序存储结构下的运算. 1)顺序存储的优点: 结构简单
18、运算方便 2)顺序存储结构的缺点: 要在顺序存储的线性表中插入一个新元素或删除一个元素时,为了保证插入或删除后的线性表仍然为顺序存储。在插入或删除元素时,需要移动大量的数据元素,因此运算效率较低。 如果一个线性表分配顺序存储空间后,如果出现线性表的存储空间已满,但还需要插入元素时,会发生“上溢”错误. 在实际应用时,可能有多个线性表同时使用存储空间,这样给存储空间的分配带来问题,有可能使有的队列空间不够或过多造成浪费。 基于上述情况,对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构,而应采用链式存储结构. 3)链式存储结构 假设每一个数据结点对应一个存储单元,该存储单元称为存储结点,
19、简称结点。 在链式存储方式中,要求每一个结点由两部分组成:一部分用于存放数据元素,你为数据域;另一部分用于存放指针,称为指针域.该指针用于指向该结点的前一个或后一个结点。 在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系不一致,而数据元素之间的逻辑关系是由指针域来确定的。 链式存储结构既可以用于线性结构,也可用于非线性结构。 4)线性链表 线性表的链式存储结构称为线性链表。 将存储空间划分成若干的小块,每块占用若干个字节,这些小块称为存储结点. 将存储结点分为两个部分,一部分用于存储数据元素的值,称为数据域;另一部分用于存储元素之间的前后件关系,
20、即存放下一个元素在存储序号(即存储地址),即指向后件结点,称为指针域。 在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点(即存放第一个元素的地址)。线性表中最后一个元素没有后件,因此,线性链表中的最后一个结点的指针域为空(用Null或0表示),表示链终结. 在线性链表中,各元素的存储序号是不连续的,元素间的前后件关系与位置关系也是不一致的.在线性链表中,前后件的关系依靠各结点的指针来指示,指向表的第一个元素的指针HEAD称为头指针,当HEAD=NULL时,表示该链表为空。 对于线性链表,可以从头指针开始,沿着各结点的指针扫描到链表中的所有结点。 这种线性链表称为线性单链表
21、,即可以从表头开始向后扫描链表中的所有结点,而不能从中间或表尾结点向前扫描位于该结点之前的元素. 这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。在某些应用时,如果对链表中的元素设置两个指针域,一个为指向前件的指针域,称为左指针(LLink),一个为指向后件的指针域,称为右指针(RLink)。则这种链表是双向链表。 5)带链的栈 带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点,这种带链的栈称为可利用栈。 当需要存储结点时,即从可利用的栈的顶部取出栈顶结点;当系统要释放一个存储结点时,将该结点空间放回到可利用栈的栈顶。 即在计算机中所有空闲的空间,均可以以结点的方式链
22、接到可利用栈中,随着其他线性链表中结点的插入与删除,可利用栈处于动态变化之中,即可利用栈经常要进行退栈和入栈操作。 6)带链的队列 队列也是线性表,也可利用链式存储结构来进行保存。 2线性链表的基本运算 线性链表包括的基本运算: 在链表中包含指定元素的结点之前插入一个新元素 在链表中删除包含指定元素的结点 将两个线性链表按要求合并成一个线性链表 将一个线性链表按要求进行分解 逆转线性链表 复制线性链表 线性链表的排序 线性链表的查找 1)线性链表中查找指定的元素 在线性链表中查找元素X:从头指针指向的结点开始往后沿指针进行扫描,直到后面已没有结点或下一个结点的数据域为X为止。 元素的查找,经常
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 数据库 设计 基础
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。