搜索
数据结构学习总结壹、研究对象及基本概念首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。二、从存储结构划分各自的定义及特点：1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。2、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.插入、删除灵活(不必移动节点，只要改变节点中的指针)。查找结点时链式存储要比顺序存储慢。3、索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。索引项的一般形式一般是关键字、地址。线性结构:逻辑结构非线性结构线性表、栈、队列、串、数组树结构图结构顺序结构链式结构索引结构散列结构物理结构4、散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。特点：散列是能一种快速实现访问的存储方式。三、操作算法1、算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。2、五个重要特性：（1）有穷性；（2）确定性；（3）可行性；（4）输入；（5）输出。3、算法设计要求：（1）正确性；（2）可读性；（3）健壮性；（4）效率与低存储量需求。效率的度量：算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。存储空间度量：一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。四、一些基本概念1.数据数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。2.数据元素数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。4.数据对象性质相同的元素的集合叫做数据对象。贰、线性结构一、线性表1.1[定义]线性表是由n(n≥0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②ai为线性表中的元素，类型定义为elemtype③a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1in)，称ai-1为ai的直接前驱，ai+1为ai的直接后继。④线性表是有限的，也是有序的。抽象数据型线性表：线性表LIST=(D,R)D={ai|ai∈Elementset,i=1,2,…,n,n≥0}R={H}H={ai-1,ai|ai-1,ai∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为elemtype的元素实例，p为位置变量。所有操作描述为：①Insert(x,p,L)②Locate(x,L)③Retrieve(p,L)④Delete(p,L)⑤Previous(p,L),Next(p,L)⑥MakeNull(L)⑦First(L)⑧End(L)1.2线性表的实现：①顺序表：把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。特点：元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。②单链表：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个单向链接式存储结构，简称单向链表或单向线性链表。结构特点：逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；需要额外空间存储元素之间的关系；非随机存储结构一些操作：③双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为双向链表。优点：实现双向查找（单链表不易做到）表中的位置i可以用指示含有第i个结点的指针表示。缺点：空间开销大。④单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识这个表。⑤双向环形链表的结构与双向连表结构相同，只是将表头元素的空previous域指向表尾，同时将表尾的空next域指向表头结点，从而形成向前和向后的两个环形链表，对链表的操作变得更加灵活。二、栈栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。定义：是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出(LastInFirstOut)的线性表。简称LIFO结构。即先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。实现：顺序栈：链栈：三、队列队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—firstinfirstout）线性表。队列的指针实现：队列的数组实现：在顺序队列中，每次在队尾插入一个元素时，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。循环队列：在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有Maxlength-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%Maxlength。四、串字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为s=“a1a2···an”(n=0)。它是编程语言中表示文本的数据类型。串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。串中所含字符的个数称为该串的长度(或串长)。当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（平凡子串不包括自身）。串的两种最基本的存储方式是顺序存储方式和链接存储方式。基本与线性表的存储一样，只是存储的内容是字符。五、数组和广义表1、数组是由下标（index）和值（value）组成的序对（index，value）的集合。也可以定义为是由相同类型的数据元素组成有限序列。数组在内存中是采用一组连续的地址空间存储的，正是由于此种原因，才可以实现下标运算。所有数组都是一个一维向量。数组的顺序存储；数组的压缩存储：⑴特殊矩阵若n阶矩阵A中的元素满足下述性质aij=aji1≤i,j≤n则称n阶对称阵。对于对称矩阵,为实现节约存储空间,我们可以为每一对对称元素分配一个存储空间，这样,原来需要的n2个元素压缩存储到n(n+1)/2个元素空间。对称关系：设sa[0..n(n+1)/2]做为n阶对称阵A的存储结构,则Sa[k]和aij的一一对应关系为:i(i+1)/2+j当i≥jk=j(j+1)/2+i当ij（2）、稀疏矩阵中，零元素的个数远远多于非零元素的个数。为实现压缩存储，考虑只存储非零元素。2、广义表广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。（1）广义表常用表示①E=()E是一个空表，其长度为0。②L=(a，b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表③A=(x，L)=(x，(a，b))A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。④B=(A，y)=((x，(a，b))，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。⑤C=(A，B)=((x，(a，b))，((x，(a，b))，y))C的长度为2，两个元素都是子表。⑥D=(a，D)=(a，(a，(a，(…))))D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。（2）广义表的深度一个表的深度是指表展开后所含括号的层数。叁、非线性结构一、树1、一个结点x组成的集{x}是一棵树，这个结点x也是这棵树的根。2、假设x是一个结点，T1，T2，…，Tk是k棵互不相交的树，我们可以构造一棵新树：令x为根，并有k条边由x指向树T1，T2，…，Tk。这些边也叫做分支，T1，T2，…，Tk称作根x的树之子树（SubTree）。树的逻辑结构特点：除根结点之外，每株子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。即一对多的关系，反映了结点之间的层次关系。森林是n≥0株互不相交的树的集合。二叉树:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点和两棵分别称为左子树和右子树的、互不相交的二叉树组成。结构特点:每个结点最多只有两个孩子结点，即结点的度不大于2,子树有左右之别，子树的次序（位置）不能颠倒。下图为其五种基本形态：满二叉树：高度为K且有2K-1个结点的二叉树称为满二叉树。完全二叉树：设二叉树高度为K，称满足下列性质的二叉树为完全二叉树（1）所有的叶都出现在K或K-1层；（2）K-1层的所有叶都在非终结结点的右边；（3）除了K-1层的最右非终结结点可能有一个（只能是左分支）或两个分支之外，其余非终结结点都有两个分支。二叉树的性质：1、二叉树的第i层最多有2i-1个结点。(i=1)2、高度为K的二叉树最多有2K-1个结点。(K=1)3、对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋14、具有n(n0)个结点的完全二叉树的高度为┌log2(n+1)┐或└log2n┘+15、完全（或满）二叉树的顺序存储结构及其性质：如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号,1,2,…,n，且使该编号对应于数组的下标，则有以下关系：若i=1,则i是根结点，无父结点；若i1,则ii/2若2*in,则i有左儿子且为2*i；否则，i无左儿子；