数据结构基础
1）数据结构的基本概念及有关术语：
数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。它可以是一个不可分割的原子项，也可以由多个数据项组成。
数据类型是指一个类型和定义在这个类型上的操作集合。
数据结构（data structure）指数据元素之间存在的关系
数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被称为数据结构。
根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图，其中树结构和图又称为非线性结构。P2
数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。
而数据的存储结构是逻辑结构在计算机存中的实现，是依赖于计算机的。
数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。
数据的存储结构被分为顺序结构、结构、索引结构、散列结构四种
算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法分析主要包含时间代价和空间代价两个方面。
时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。
空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。
算法的时间及空间复杂性
度量算法的时间效率
算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。T(n)=O(f(n))
度量算法的空间效率
空间复杂度指算法在执行时为解决问题所需要的额外存空间，不包括输入数据所占用的存储空间。 S(n)=O(f(n))
2）基本数据结构及其操作：
线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,a(n-1)组成的有限序列。P36 线性表的逻辑结构：
其中，元素ai的数据类型可以是整数、浮点数、字符或类；n是线性表的元素个数，称为线性长度。若n=0,则为空表；若n>0,ai(0 线性表的存储结构（顺序存储、链式存储） 线性表的顺序存储结构使用一组连续的存单元依次存放线性表的数据元素，元素在存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。顺序存储的线性表也称为顺序表。 线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。 插入、删除操作 单链表的插入操作： ①空表插入/头插入 if(head==null) head=new Node else { Node q.next=head; head=q; } ②中间插入/尾插入 Node q.next=p.next; p.next=q; 单链表的删除操作： ③头删除 head = head.next; ④中间/尾删除 if (p.next!=null) p.next = p.next.next; 双链表的插入操作： q = new DLinkNode(x); q.prev = p.prev; q.next = p; p.prev.next = q; p.prev = q; 双链表的删除操作： p.prev.next = p.next; if (p.next!=null) (p.next).prev = p.prev; 3）数组是一种数据结构，数据元素具有相同的数据类型。 数组逻辑结构与存储结构的关系：数组采用的是顺序存储结构，即使用一组连续的存单元依次存放线性表的数据元素，元素在存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。所以数组的存储结构表现其存储结构。 4）栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。允许操作的一段称为栈顶，不允许操作的一端称为栈底。栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的栈称为空栈。栈的插入和删除只允许在栈顶进行，每次入栈即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。 逻辑结构 存储结构 采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链式栈。 进栈、出栈操作：链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点的作用不明显。采用不带头结点的单链表实现栈。单链表的第一个结点为站定结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新结点；出栈操作是删除栈顶结点并返回栈顶元素值，再使top指向新的栈顶结点。 5）队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。允许入队的一端称为队尾，允许出队的一端称为队头。向队列中插入元素的过程成为入队，删除元素的过程成为出队。没有元素的队列称为空队列。由于插入和删除操作分别在队尾和队头进行，最先入队的元素总是最先出队，因此队列也称为先进先出表。 逻辑结构 存储结构 采用顺序存储结构的栈称为顺序队列，采用链式存储结构的栈称为链式队列。 循环队列：如果循环使用顺序队列的连续存储单元，则将顺序队列设计成在逻辑上首尾相接的循环结构，称为顺序循环队列。 进队、出队操作：以不带头结点的单链表实现链式队列。设指针front和rear分别指向队头和队尾结点，入队操作将结点链在队尾结点之后，并使front指向新的队尾结点； 出队操作，当队列不空时，取得队头结点值，删除该节点，并使front指向后续结点。 6）二叉树是n（n>=0）个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归定义的。 二叉树的性质 性质1：若根结点的层次为1，则二叉树第i层最多有2i1（i≥1）个结点。 性质2：在高度为k的二叉树中，最多有2k1个结点（k≥0）。 性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。 性质4：一棵具有n个结点的完全二叉树，其高度。 性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤i ＜n）的结点，有： ①若i=0，则i为根结点，无父母结点；若i>0， 则i的父母结点序号为。 ②若2i+1＜n，则i的左孩子结点序号为2i+1；否 则i无左孩子。 ③若2i+2＜n，则i的右孩子结点序号为2i+2；否 则i无右孩子。 二叉树的存储结构 1.二叉树的顺序存储结构 顺序存储结构仅适用于完全二叉树跟满二叉树。 2.二叉树的链式存储结构 二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。虽然二叉树是非线性结构，但遍历二叉树访问结点的次序是线性的，而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。 孩子优先： 先根次序：访问根结点，遍历左子树，遍历右子树。 中根次序：遍历左子树，访问根结点，遍历右子树。 后根次序：遍历左子树，遍历右子树，访问根结点 二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树。 哈夫曼树定义为带权外路径长度最短的二叉树 路径长度：从根结点到所有结点的路径长度之和 (a)、(b)、（c）、(d)的路径长度为1x2+2x2+3x2=12 外路径长度：从根结点到所有叶子结点的路径长度之和 (a)、(b)、（c）、(d)的外路径长度为2+3x2+1=9 从根到X结点的带权路径长度是X结点的权值与从根到X结点路径长度的乘积。所有叶子结点的带权路径长度之和称为二叉树的带权外路径长度。 二叉树的带权外路径长度 7）检索方法： （P259）顺序查找算法描述为：从线性表的一端开始，依次将每个元素的关键字与给定值进行比较，若有相等者，则查找成功；否则比较继续，直到比较完所有元素，仍未有相等者，则查找不成功，给出结果信息。平均查找长度为（n+1）/2,查找一个元素的平均比较次数为n，查找失败需比较n+1次，时间复杂度为O(n)。 查找成功的平均查找长度： 1 WPL() n i i i w l - = =? ∑ ) ( 2 1 2 )1 ( 1 1 ) ( 1 1 成功 n O n n n n i n c p ASL n i i n i i = + = + ? = = ? =∑ ∑ = = 查找失败的平均查找长度： （P262）二分查找又叫折半查找，时间复杂度为O(log2n)。 折半查找算法分析 8）排序方法： 直接插入排序总的关键码比较次数为n^2/4，总的记录移动个数也约为n^2/4；二分法插入排序关键码比较次数为O(nlog2n),记录移动个数为O(n^2)；shell排序法的关键码 ) ( ) 1 ( ) ( 1 1 不成功 n O n n n c p ASL n i i n i i = = ? = ? =∑ ∑ = = 比较次数和记录移动个数均为n^1.3左右。冒泡排序的最坏时间复杂度为O(n2),最好的时间复杂度为O(n)，算法的平均时间复杂度为O(n2)。快速排序的最坏时间为O(n^2)，平均时间复杂度为(nlgn)。 插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。 直接插入排序 数据序列已排序（最好情况）的时间复杂度为O（n） 数据序列反序排列（最坏情况）的时间复杂度为O（n的平方） 数据序列随机排列的时间复杂度为O（n的平方） 折半插入排序 希尔排序
相关主题
文本预览