数据结构和算法设计-知识点

数据结构知识点归纳算法基本特性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查找表用有序表表示时查找方法折半查找（二分查找）折半查找的特点要求元素按关键字有序排列。存储结构顺序平均查