数据结构笔记.doc
《数据结构笔记.doc》由会员分享,可在线阅读,更多相关《数据结构笔记.doc(27页珍藏版)》请在咨信网上搜索。
1、数据结构笔记基础:数据结构与算法(一) 数据结构基本概念数据(data):是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素(data element):是数据的基本单位,在计算机中通常被当做一个整体进行考虑和处理数据对象(data object):性质相同的数据元素的集合,是数据的一个子集数据结构(data structure):相互之间存在一种或多种特定关系的数据元素的集合4类基本结构:集合、线性结构、树形结构、图形(网状)结构数据结构的形式定义为数据结构是一个二元组 Data Structure = (D,S),其中D是数据元素的有限集,S
2、是D上关系的有限集数据结构定义中的“关系”描述的是数据元素之间的逻辑关系,因此又称为数据的逻辑结构数据结构在计算机中的表示(映像)称为物理结构(存储结构)计算机中表示信息的最小单位是二进制中的一位,叫做 位(bit),一到若干位组成一个位串表示一个数据元素,这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种:顺序映像、非顺序映像,并由此得到两种存储结构:顺序存储、链式存储,前者运用相对位置表示数据元素间的逻辑结构,后者借助指针 任何一个算法的设计取决于数据(逻辑)结构,而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种:原子类型、结构类型,前者
3、不可分解(例如int、char、float、void ),后者结构类型由若干成分按某种结构组成,可分解,成分既可以是非结构的也可以是结构的(例:数组)抽象数据类型(Abstract Data Type ):是指一个数学模型及定义在该模型上的一组操作(P8)抽象数据类型格式如下:ADT抽象数据类型名数据对象:数据关系:数据操作:ADT抽象数据类型名基本操作格式如下:基本操作名(参数表)初始条件:操作结果:多形数据类型(polymorphic data type):是指其值得成分不确定的数据类型(P9)抽象数据类型可由固有数据类型来表示和实现(二) 算法(概念)和算法分析(时、空性能)算法(alg
4、orithm):对特定问题求解步骤的一种描述算法5特性:有穷、确定、可行、输入、输出1、有穷性:算法必须在可接受的时间内执行有穷步后结束2、确定性:每条指令必须要有确切含义,无二义性,并且只有唯一执行路径,即对相同的输入只能得相同输出3、可行性:算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入:一个算法有一到多个输入,并取自某个特定对象合集5、输出:一个算法有一到多个输出,这些输出与输入有着某些特定关系的量算法设计要求(好算法):正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求,并能有合理的处理方式。算法效率的度量:(1) 事
5、后统计:程序运行结束后借助计算机内部计时功能,缺点一是必须先运行依据算法编制的程序,二是受限于计算机软硬件,导致掩盖了算法本身的优劣(2) 事前分析估计: 消耗时间影响因素:算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模(通常用整数量n表示),记为问题规模的函数算法时间取决于控制结构(顺序,分支,循环)和固有数据类型操作的综合效果书写格式:T(n)= O(f(n) f(n)为n的某个函数时间复杂度:算法的渐近时间复杂度(asymptotic time complexity),它表示随问题规模的增大,算法执行时间的增长率和f(n)的增长
6、率相同以循环最深层原操作为度量基准频度:该语句重复执行的次数算法的存储空间需求:空间复杂度(space complexity):算法所需存储空间度量,记作 S(n)= O(f(n),其中n为问题规模的大小一、线性表(一) 线性表基本概念线性表(linear_list):n个数据元素的有限序列结构特点:存在唯一的被称作“第一个”、“最后一个”的数据元素,且除了第一个以外每个元素都有唯一前驱,除最后一个以外都有唯一后继在复杂线性表中存在:数据项-记录-文件,例如每个学生情况为一个记录,它由学号、性别.数据项组成,多个学生记录组成一个文件在形如(a1,.,ai-1,ai,ai+1,.,an)中,ai
7、-1领先于ai,ai领先于ai+1,且形成直接前驱元素,直接后继元素关系元素个数n定义为线性表长度,n=0为空表相关操作算法见书(P20)(二) 线性表顺序存储结构和链式存储结构(1)线性表顺序表示和实现线性表顺序存储在一组连续的存储单元中,链式存储则不要求;顺序结构可以随机访问,链式结构可以无限扩容确定存储位置(计算公式):第i个元素:LOC(ai)= LOC(a1)+(i-1)*L L是偏移量,即每个元素占用存储单元第ai+1个元素:LOC(ai+1)= LOC(ai)+L a1(起始地址或基地址)C语言下标从“0”开始,则表中第i个元素是L.elem i-1当对线性表进行操作时,被操作元
8、素后面的元素角标会相应变化(前移、后移),算法(P24)(2)线性表链式表示和实现特点:用一组任意的存储单元存储线性表的数据元素(存储单元不一定连续)结点存储数据元素及直接后继的存储位置信息,两个域:数据域和指针域,指针域中存储的信息称为指针或链,仅含有一个指针域故又称线性链表或单链表链表的插入:先增加一条指针再修改原指针头指针指向第一个数据元素的存储位置,最后一个结点的指针为空(NULL)链表表示方法及算法(P28)单链表第一个结点前加一个头结点Head,其数据域可为空也可存储一些附加信息(链长等)假设p是指向线性表中i个元素(ai)的指针,则p-next是指向i+1个数据元素在单链表中,取
9、得第i个元素必须从头指针开始寻找,因此单链表是非随机的存储结构线性表指逻辑结构,从抽象数据层面来说顺序表和链表指物理存储结构逻辑结构:离散、线性、层次、网状应用见书算法二、栈和队列(一) 栈的基本概念栈(stack)是限定仅在表尾进行插入或删除操作的线性表表尾为栈顶,表头为栈底,遵循后进先出原理(last in first on,LIFO),不含元素则为空栈操作:在栈顶插入(入栈)和删除(出栈),栈初始化、判空、取栈顶元素(算法P45)(二) 栈的顺序存储和链式存储顺序栈,即栈的顺序存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置初
10、始栈时不应限定栈的最大容量,基本做法是先为栈分配一个基本容量,然后在应用过程中,不够用再逐段扩大(算法P46)(三) 递归栈与递归的实现:一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递归函数阶乘函数、2阶Fibonacci数列、Ackerman函数、3阶Hanoi问题(多阶呢?)(P54)函数调用函数执行过程笔记(P56)(四) 队列队列先进先出(first in first out,FIFO),队尾一端插入,队首一端删除元素(日常排队)队列与栈均有八种基本操作(P59),队列一般用链表实现,栈用顺序表实现双端队列(限定操作的队列)(P60)(五) 栈和队列的应用链队列、循
11、环队列(P60),离散事件模拟(银行接待工作(P65)(六) 特殊矩阵的压缩存储如何存储矩阵的元,使矩阵的运算有效进行。高级语言常用二维数组存储阵元面对如高阶矩阵,多值相同矩阵和多零元素矩阵进行压缩存储节省空间压缩存储:为多个值相同的元只分配一个空间,对零元不分配值相同元素或零元素具有分布规律则称为特殊矩阵,反之为稀疏矩阵具体应用与算法(P95)三、树与二叉树(一) 树的基本概念树是非线性数据结构,以分支关系定义的层次结构树是n(n=0)个结点的有限集详见(P118),基本术语(P120)(二) 二叉树1. 二叉树的定义及其主要特征: 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左
12、子树”(left subtree)和“右子树”(right subtree)。性质:1.2.3.满二叉树:完全二叉树: 4. 5.2. 二叉树的顺序存储结构和链式存储结构顺序存储,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点依次存储在如上定义的一位数组下标为i-1的分量中。123456789链式存储,每个结点中至少包含三个域,左指针,数据,右指针,称作“二叉链表”增加一个双亲指针域,则称作“三叉链表” 详见P126-1273. 二叉树的遍历遍历二叉树,每个结点均被访问一次,且仅有一次。在限定先左后右的访问序列后,有三种遍历方式:先序(
13、DLR),中序(LDR),后续(LRD)P129 算法6.1(波兰式)层次遍历,无论那种遍历方式,对含n个结点的二叉树,时间复杂度都为O(n),空间复杂度也为O(n)。4. 线索二叉树的基本概念和构造摘要:对于n个结点的二叉树,在二叉链存储结构中有n+1(2n-(n-1)个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索概念:加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。构造方法:(三) 树与森林1. 树的存储结构 链表结构:1.双亲表示法 2.孩子表示法 3.孩子兄弟表示法 详见P1352.
14、 森林与二叉树转换 左孩子右兄弟3. 树与森林的遍历 先序、中序遍历,详见P139 当以二叉链表做树的存储结构时,树的先序 = 二叉树先序、树的后序 = 二叉树中序(四) 树与二叉树的应用1. 二叉排序树 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。 定义:二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;(4)没有键值相等的节点。 查找:步骤:若根结点
15、的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。若子树为空,查找不成功。2. 平衡二叉树(AVL) 定义:它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度 之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1=bf=1图一,图二都是BST,但只有图一是AVL tree3. 哈夫曼(Huffman)树和哈夫曼编码哈夫曼树是一类带权路径长度最短的树,又称最优树。路径和路径长度概念:从树中一个结点到另一个结点之间的分支构成这两
16、个结点之间的路径,路径上的分支数目称为路径长度。树的路径长度是从树根到每一结点的路径长度之和。推广到一般情况,考虑带权结点:结点的带权路径长度为从该结点到树根之间的路径长度与结点上的权值的乘积,树的带权路径长度为树中所有叶子结点的带权路径长度之和,记作WPL= 带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树哈夫曼算法构造哈夫曼树(P145)哈夫曼编码 前缀编码:设计长短不等的编码,任一字符的编码都不是另一个字符的编码的前缀 利用二叉树来设计前缀编码 约定左分支表示字符“0”右分支表示字符“1”则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。一般情况,当带有权值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击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。