欢迎来到人人文库网! | 帮助中心 人人文库renrendoc.com美如初恋!
人人文库网
首页 人人文库网 > 资源分类 > DOC文档下载

13 数据结构与算法.doc

  • 资源大小:67.50KB        全文页数:5页
  • 资源格式: DOC        下载权限:游客/注册会员/VIP会员    下载费用:5
游客快捷下载 游客一键下载
会员登录下载
下载资源需要5

邮箱/手机号:
您支付成功后,系统会自动为您创建此邮箱/手机号的账号,密码跟您输入的邮箱/手机号一致,以方便您下次登录下载和查看订单。注:支付完成后需要自己下载文件,并不会自动发送文件哦!

支付方式: 微信支付    支付宝   
验证码:   换一换

友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

13 数据结构与算法.doc

武汉三维教育C语言考试研究中心网址WWWSELFCAPNET第一章数据结构与算法第1页共5页第一章数据结构与算法考点一算法算法是指解题方案的准确而完整的描述。算法的基本特征1可行性程序必须得到满意的结果,所以要考虑算法的可行性;2确定性算法中每一步都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;3有穷性算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;4拥有足够的情报。算法的基本要素1算法的控制结构。2对数据对象的运算和操作;基本运算和操作包括算术运算、逻辑运算、关系运算、数据传输。算法的3种基本控制结构顺序结构、选择结构、循环结构。算法基本设计方法列举法、归纳法、递推、递归、减半递推技术、回溯法。算法复杂度1时间复杂度指执行算法所需要的计算工作量;2空间复杂度指执行这个算法所需要的内存空间;指令系统一个计算机系统能执行的所有指令的集合;考点二逻辑结构和存储结构1.数据结构的基本概念1数据结构指相互有关联的数据元素的集合。2数据结构研究的3个方面①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;③对各种数据结构进行的运算。2.逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成B(D,R)其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。例如,如果把一年四季看作一个数据结构,则可表示成B(D,R)D{春季,夏季,秋季,冬季}R{(春季,夏季),(夏季,秋季),(秋季,冬季)}3存储结构数据的存储结构是指数据的逻辑结构在计算机中的表示。一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接等存储结构。有序线性表既可以采用顺序存储结构,也可以采用链式存储结构。考点三线性结构与非线性结构武汉三维教育C语言考试研究中心网址WWWSELFCAPNET第一章数据结构与算法第2页共5页根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型线性结构与非线性结构。1线性结构必须满足的两个两个条件①有且只有一个根结点;②每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。2栈、队列、串等都线性结构。非线性结构数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。3线性表的顺序存储结构具有以下两个基本特点①线性表中所有元素所占的存储空间是连续的;②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。元素AI的存储地址为ADRAIADRA1I1K,ADRA1为第一个元素的地址,K代表每个元素占的字节数。线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。4顺序表的运算查找、插入、删除。考点四栈和队列栈形象的比喻小学课本上讲乌鸦喝水用的杯子。限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用TOP表示栈顶位置,用BOTTOM表示栈底。栈的基本运算1插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。栈是支持子程序调用的数据结构。队列形象比喻在食堂里打饭时排的长队,先来先服务指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。REAR指针指向队尾,FRONT指针指向队头。当表中没有元素时称为空队列。队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。队列运算包括1入队运算从队尾插入一个元素;(2)退队运算从队头删除一个元素。循环队列队列的头指针指向队列的尾指针,循环队列是队列的顺序存储结构。考点五链表在链式存储方式中,要求每个结点由两部分组成1用于存放数据元素值,称为数据域,2用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。链式存储方式既可用于表示线性结构,也可用于表示非线性结构。1线性链表线性表的链式存储结构称为线性链表。武汉三维教育C语言考试研究中心网址WWWSELFCAPNET第一章数据结构与算法第3页共5页在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表中的元素。线性单链表中,HEAD称为头指针,HEADNULL(或0)称为空表。如果是双向链表的两指针左指针(LLINK)指向前件结点,右指针(RLINK)指向后件结点。线性链表的基本运算查找、插入、删除。2带链的栈栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。考点六二叉树及其基本性质1)二叉树及其基本概念树是一种简单的非线性结构,所有元素之间具有明显的层次特性。具有以下两个特点①非空二叉树只有一个根结点;②每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。度结点的左右子树的个数,每一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树,在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。树的度即为二叉树中最大的度的数。叶子结点既没有左子树也没有右子树的结点。例如,一个家族中的族谱关系如图11所示A有后代B,C;B有后代D,E;C有后代F;典型的二叉树如图11所示父结点(根)在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个称为树的根结点。例如上图,结点A是树的根结点。子结点和叶子结点在树的结构中,每一个节点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。例如上图,结点D、E、F都为叶子结点。度在树结构中,一个结点拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。例如上图,根结点A和结点B的度为2,结点C的度为1,叶子结点D、E、F的度为0。所以,树的度为2。深度定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。例如上图,根结点A在第1层,结点B、C在第2层,结点D、E、F在第3层。该树的深度为3。子树在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。ABCDEF武汉三维教育C语言考试研究中心网址WWWSELFCAPNET第一章数据结构与算法第4页共5页1二叉树基本性质二叉树具有以下几个性质性质1在二叉树的第K层上,最多有2K1(K≥1)个结点;性质2深度为M的二叉树最多有2M1个结点;性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。性质4具有N个结点的二叉树,其深度至少为[LOG2N]1,其中[LOG2N]表示取LOG2N的整数部分。1)满二叉树与完全二叉树满二叉树除最后一层外,每一层上的所有结点都有两个子结点完全二叉树除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。2)二叉树的遍历二叉树的遍历1前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;并且,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。例如,对图11中的二叉树进行前序遍历的结果(或称为该二叉树的前序序列)为A,B,D,E,C,F。2中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。例如,对图11中的二叉树进行中序遍历的结果(或称为该二叉树的中序序列)为D,B,E,A,C,F。3后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。例如,对图11中的二叉树进行后序遍历的结果(或称为该二叉树的后序序列)为D,E,B,F,C,A。考点七顺序查找查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表示查找失败。例如,在一维数组21,46,24,99,57,77,86中,查找数据元素98,首先从第1个元素21开始进行比较,与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,所以查找成功。如果查找数据元素100,则整个线性表扫描完毕,仍未找到与100相等的元素,表示线性表中没有要查找的元素。在下列两种情况下也只能采用顺序查找1如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。2即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。有序表,存储的数据从小到大有规律存放考点八二分法查找二分法查找,也称拆半查找,是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件用顺序存储结构;线性表是有序表。二分法查找只适用于顺序存储的有序表。例如,长度为8的线性表关键码序列为6,13,27,30,38,46,47,70,被查元素为38,首先将与线性表的中间项比较,即与第4个数据元素30相比较,38大于中间项30的值,则在线性表38,46,47,70继续查找;接着与中间项比较,即与第2个元素46相比较,38小于46,则在线性表38继续查找,最后一次比较相等,查找成功。顺序查找法每一次比较,只将查找范围减少1,而二分法查找,每比较一次,可将查找范围减少为原来的一半,效率大大提高。武汉三维教育C语言考试研究中心网址WWWSELFCAPNET第一章数据结构与算法第5页共5页对于长度为N的有序线性表,在最坏情况下,二分法查找只需比较LOG2N次,而顺序查找需要比较N次。考点九排序技术1交换类排序法①冒泡排序法首先,从表头开始往后扫描线性表,逐次比较相邻两个元素的大小,若前面的元素大于后面的元素,则将它们互换,不断地将两个相邻元素中的大者往后移动,最后最大者到了线性表的最后。然后,从后到前扫描剩下的线性表,逐次比较相邻两个元素的大小,若后面的元素小于前面的元素,则将它们互换,不断地将两个相邻元素中的小者往前移动,最后最小者到了线性表的最前面。对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时已经排好序。在最坏的情况下,冒泡排序需要比较次数为NN1/2。②快速排序法任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等于基准元素的排序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序。2插入类排序法①简单插入排序法,最坏情况需要NN1/2次比较;②希尔排序法,最坏情况需要ON15次比较。3选择类排序法①简单选择排序法,最坏情况需要NN1/2次比较;②堆排序法,最坏情况需要ONLOG2N次比较。相比以上几种除希尔排序法外,堆排序法的时间复杂度最小。上述排序技术中,最坏情况下比较次数最少的是堆排序法。

注意事项

本文(13 数据结构与算法.doc)为本站会员(baixue100)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网(发送邮件至[email protected]或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

网站客服QQ:2846424093    人人文库上传用户QQ群:460291265   

[email protected] 2016-2018  renrendoc.com 网站版权所有   南天在线技术支持

经营许可证编号:苏ICP备12009002号-5