




已阅读5页,还剩2页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构知识点归纳算法基本特性1有穷性有限时间2确定性算法确切3可行性存在基本操作4有输入05有输出1好的算法1正确性(CORRECTNESS)2可读性(READABILITY)3健壮性(ROBUSTNESS)4高效率与低存储量需求数据结构研究数据之间的逻辑关系描述,称为数据的逻辑结构,强调从逻辑上来观察数据之间的关系,描述数据间的逻辑关系数据的存储结构是其逻辑结构在计算机存储器中的实现,研究数据的存储结构就是研究数据和数据之间关系的计算机表示。抽象数据类型ABSTRACTDATATYPE简称ADT是指一个数学模型以及定义在该模型上的一组操作是对数据结构的一种更准确的抽象描述,忽略了数据结构的具体实现步骤,将注意力集中在数据的基本操作上,通过基本操作描述数据的逻辑关系。顺序映象以相对固定的存储位置表示数据关系链式映象用指示数据元素存储地址的指针(附加信息)表示数据元素间的逻辑关系线性表是N个数据元素的有限序列,通常记作(A1,A2,A3,AN)TYPEDEFSTRUCTSTATUSINITLIST_SQSQLIST/构造一个空的顺序表LINTLENGTHLELEMELEMTYPEMALLOCLIST_INIT_SIZESIZEOFELEMTYPEINTLISTSIZEIFLELEMEXITOVERFLOW/存储分配失败SQLISTLLENGTH0/空表长度为0LLISTSIZELIST_INIT_SIZE/初始存储容量STATUSDETROYLIST_SQSQLISTIFLELEMRETURNERROR/INITLIST_SQ/若表L不存在FREELELEM/若表L已存在,回收动态分配的存储空间LELEMNULLLLENGTH0LLISTSIZE0RETURNOK/DETROYLIST_SQSTATUSLISTINSERT_SQSQLIST/I值不合法IFLLENGTHLLISTSIZE/当前存储空间已满,再分配、扩大空间NEWBASEELEMTYPEREALLOCLELEM,LLISTSIZELISTINCREMENTSIZEOFELEMTYPEIFNEWBASEEXITOVERFLOW/存储分配失败试卷结构与试题类型(100分),占70单项选择题(4选1,10个)20分判断题(10个)10分填空题(10个,每空2分)20分简答题操作题(5个)25分算法填空(3个算法)15分读算法,说明功能(2个算法)10分LELEMNEWBASE/新基址LLISTSIZELISTINCREMENT/增加存储容量Q/Q指示INSERT位置,第I个FORPPQPP1P/INSERT位置及之后的元素右移QELLENGTH/INSERTE,表长增1RETURNOK/LISTINSERT_SQSTATUSLISTDELETE_SQSQLISTI的合法值为1ILLENGTH,这时用LELEMI1读取的数据元素才有意义IFILLENGTHRETURNERROR/I值不合法或表为空时,不执行删除操作ELELEMI1/被删除元素的值赋给EFORJIJSSTACKSIZE/若栈满则追加存储空间SBASEELEMTYPEREALLOCSBASE,SSTACKSIZESTACKINCREMENTSIZEOFELEMTYPEIFSBASEEXITOVERFLOW/存储分配失败STOPSBASESSTACKSIZESSTACKSIZESTACKINCREMENTSTOPE/元素E插入栈顶,后修改栈顶指针RETURNOK/STOPESTOP/PUSHRETURNOK/GETTOPTYPEDEFSTRUCTELEMTYPEBASE/初始化时分配存储空间的基址INTFRONT/队头指针,指向队头元素INTREAR/队尾指针,指向队尾元素的下一个位置SQQUEUE“一用对头指针和队尾指针时,要注意其引用方式”STATUSENQUEUE_SQSQQUEUE/队满QBASEQREARE/将元素E插入队尾QREARQREAR1MAXSIZE/修改队尾指针RETURNOK/ENQUEUE_SQTYPEDEFSTRUCTQNODE/链队列结点的类型定义ELEMTYPEDATASTRUCTQNODENEXTQNODE,QUEUEPTRSTATUSINITQUEUESQQUEUEQQBASECHARMALLOCMAXSIZEOFCHARQFRONTQREAR0RETURNOK树是N个结点的有限集合,在任一棵非空树中(1)有且仅有一个称为根的结点。(2)其余结点可分为若干个互不相交的集合,且这些集合中的每一集合本身又是一棵树,称为根的子树。二叉树是一个结点有限集合,如果该集合不空,它一定是由一个根结点、一棵左子树和/或一棵右子树组成。性质1在二叉树的第I层上至多有2I1个结点I1。性质2深度为K的二叉树上至多含2K1个结点K1。性质3对任何一棵二叉树,若它含有N0个叶子结点、N2个度为2的结点,则必存在关系式N0N21性质4具有N个结点的完全二叉树的深度为LOG2N1。性质5若对含N个结点的完全二叉树从上到下且从左至右进行1至N的编号,则对完全二叉树中任意一个编号为I的结点1若I1,则结点I是二叉树的根,无双亲,否则,编号为I/2的结点为其双亲;2若2IN,则结点I无左孩子,否则,编号为2I的结点为其左孩子;3若2I1N,则结点I无右孩子,否则,编号为2I1的结点为其右孩子。VOIDPREORDERTRAVERSEBITREET,STATUSVISITELEMTYPEESTATUSDEQUEUE_SQSQQUEUE/队空EQBASEQFRONT/取队头元素EQFRONTQFRONT1MAXSIZE/修改队头指针RETURNOK/ENQUEUE_SQTYPEDEFSTRUCT/链队列的表头结点的类型定义QUEUEPTRFRONT/队头指针,指向链表的头结点QUEUEPTRREAR/队尾指针,指向队尾结点LINKQUEUE/采用二叉链表存贮二叉树,VISIT是访问结点的函数/本算法先序遍历以T为根结点指针的二叉树IFT/若二叉树不为空VISITTDATA;/访问根结点PREORDERTRAVERSETLCHILD,VISIT/先序遍历T的左子树PREORDERTRAVERSETRCHILD,VISIT/先序遍历T的右子树/PREORDERTRAVERSE中序非递归遍历VOIDINORDERTRAVERSEBITREET,VOIDVISITTELEMTYPEINITSTACKSPTWHILEP|STACKEMPTYSIFPPUSHS,PPPLCHILD/根指针进栈,遍历左子树ELSEPOPS,PVISITPDATAPPRCHILD/根指针退栈,遍历右子树VOIDLEAFBITREET/采用二叉链表存贮二叉树,N为全局变量,用于累加二叉树的统计叶子结点的个数,初始化N0IFTIFTLCHILDNULL/若T所指结点为叶子结点则计数ELSELEAFTLCHILDLEAFTRCHILD双亲表示类型定义DEFINEMAX_TREEE_SIZE100TYPEDEFSTRUCTPTNODEELEMTYPEDATAINTPARENT/双亲位置域PTNODETYPEDEFSTRUCTPTNODENODESMAX_TREE_SIZEINTR,N/R为根的位置,N为结点数PTREE孩子兄弟表示法类型定义TYPEDEFSTRUCTCSNODEELEMTYPEDATASTRUCTCSNODEFIRSTCHILD,/指向第一个孩子NEXTSIBLING/指向下一个兄弟CSNODE,CSTREE树的孩子链表类型定义TYPEDEFSTRUCTCTNODE/孩子结点INTCHILDSTRUCTCTNODENEXTCHILDPTRTYPEDEFSTRUCTELEMTYPEDATACHILDPTRFIRSTCHILD/孩子链表头指针CTBOXTYPEDEFSTRUCTCTBOXNODESMAX_TREE_SIZEINTN,R/结点数和根的位置CTREE图有向图顶点的度、入度(邻接矩阵中该顶点所在纵排非零元素的总个数)、出度(邻接矩阵中该顶点所在横排非零元素的总个数)强)连通图在无(有)向图G中,若对任何两个顶点V、U都存在从V到U的路径强)连通分量(有)无向图G的极大连通子图称为G的(强连通分量)连通分量生成树包含无向图G的所有顶点的极小(最少数目的边)连通子图称为G的生成树。邻接矩阵邻接表有向图的邻接表有向图的逆邻接表V0V4V3V1V220V013422110034V0V1V2V300123V0V2V3V1VEXDATAFIRSTARC1230ADJVEXNEXTV0V1V2V3第页0123V0V2V3V1VEXDATAFIRSTARC3002V0V1V2V3查找表由同一类型的数据元素(或记录)构成的集合。静态查找表只作查询和检索操作的查找表。动态查找表在查找过程中同时作插入或删除操作的查找表。记录由若干数据项构成的数据元素。关键字能标识一个数据元素(或记录)的数据项。主关键字能唯一地标识一个记录的关键字。次关键字用以识别若干记录的关键字。学号姓名专业年龄20030001王洪计算机1720030002李文计算机1820030003谢军计算机1820030004张辉信息工程2020030005李文信息工程19查找静态查找顺序表的查找顺序查找有序表的查找折半查找特点无排序要求;存储结构顺序、链式;平均查找长度ASLSSN1/2INTSEARCH_SEQSSTABLEST,KEYTYPEKEY/在顺序表ST中顺序查找其关键字等于KEY的数据元素。若找到,则函数值为该元素在表中的位置,否则为0。STELEM0KEYKEY/“哨兵”,免去查找过程中每一步都要检测整个表是否查找完毕FORISTLENGTHEQKEY,STELEMIKEYI/空操作,从后往前比较RETURNI/若找到返回该元素在表中的位置/若表中不存在待查元素,则第0个元素即哨兵满足条件,所以I0/SEARCH_SEQ查找表用有序表表示时查找方法折半查找(二分查找)折半查找的特点要求元素按关键字有序排列。存储结构顺序平均查
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年选任总经理协议样本
- 2025年医疗行业股权投资合作策划协议书样本
- 2025年委托培养合同协议
- 2025年工程保密协议规范示例
- 2025年金融公司保密协议范本
- 理赔业务风险培训持续性风险基础知识点归纳
- 理赔业务风险管理跨部门信息传递风险基础知识点归纳
- 人工智能在医疗健康领域的创新应用
- 开发民俗体验的现状及总体形势
- 大寒营销新突破
- 运维管理培训
- 2024年四川乐山中考满分作文《有一束光照亮了我》
- 2025年广东省佛山市南海区中考一模英语试题(原卷版+解析版)
- 部编2024版历史七年级下册期末(全册)复习卷
- 人大代表应聘简历
- 23《海底世界》说课稿- 2023-2024学年统编版语文三年级下册
- 支气管镜术后护理课件
- 《代营业厅》课件
- 梵高星空课件
- 上海工程技术大学第2学期《机械原理》课程期末试卷及答案
- 2024年辅警招聘笔试题库
评论
0/150
提交评论