通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

程序员教程-4章-数据结构与算法

2425人浏览 / 0人评论 | 作者:whisper  | 分类: 软考程序员  | 标签: 软考  | 

作者:whisper

链接:http://proprogrammar.com:443/article/30

声明:请尊重原作者的劳动,如需转载请注明出处


    目录结构

  4.1 线性结构

    4.1.1 线性表

      1 线性表的定义

      2 线性表的存储结构

      3 线性表的应用

    4.1.2 栈和队列

      1 栈

      2 队列

    4.1.3 串

      1 串的定义及基本运算

  4.2 数组

    1 数组

    2 矩阵

  4.3 树与二叉树

    4.3.1 树的基本概念

    4.3.2二叉树

      1 二叉树的性质

      2 满二叉树和完全二叉树

      3 二叉树的存储结构

      4 二叉树的遍历

    4.3.3 树和森林

      1 树和森林与二叉树的相互转换

      2 树和森林的遍历

    4.3.4 最优二叉树

    4.3.5 二叉查找树

  4.4图

    1 基本概念

    2 图的存储结构

  4.5 查找

    4.5.1 顺序查找与折半查找

      1 顺序查找

      2 折半查找

      3 索引顺序查找

    4.5.2 树表查找

      1 在二叉查找树中查找

      2 在二叉查找树中插入

    4.5.3 哈希表及哈希查找

  4.6 算法

    4.6.1 算法概述

      1 算法与数据结构

      2 算法效率

      3 算法的描述

    4.6.2 排序算法

      1 简单排序

      2 希尔排序

      3 快速排序

      4 堆排序

      5 归并排序

      6 内部排序方法小节

      7 外部排序

    4.6.3 递归算法

    4.6.4 字符串运算

      1 基本的字符串运算

      2 串的模式匹配

    4.6.5 图的相关算法

      1 图的遍历算法

      2 最小生成树求解算法

      3 拓扑排序

      4 求单源点的最短路径算法

  心情不好,时间不够,一切从简。。。

  数据结构描述数据元素的集合及元素间的关系和运算。在数据结构中,元素之间的相互关系称为数据的逻辑结构。按照逻辑关系的不同将数据结构分为线性结构和非线性结构,其中,线性结构包线括性表、栈、队列、串,非线性结构主要包括树和图。数据元素及元素之间关系的存储形式称为存储结构,有顺序存储和链接存储两种基本形式

  4.1 线性结构

    4.1.1 线性表:线性表是最基本的线性结构的一种抽象,主要的基本运算有插入、删除和查找,常采用顺序存储和链式存储两种存储方式来实现。链表分为双向链表,循环链表,静态链表

      3 线性表的应用:选首领

    4.1.2 栈和队列

    栈和队列是程序中常用的两种数据结构,它们的逻辑结构与线性表相同,其特点在于运算受到了限制:栈按“后进先出”的规则进行操作,队列按“先进先出”的规则进行操作,故称运算受限的线性表

      1 栈

      1)栈的定义及基本运算:基本运算:初始化栈,判空栈,入栈,出栈,读栈顶元素

      2)栈的存储结构:栈的顺序存储,栈的链式存储

      3)栈的应用:表达式求值,括号匹配,在计算机语言的实现以及将递归过程转变为非递归过程的处理

      2 队列

      1 允许插入元素的一端称为队尾,允许删除元素的一端称为队头

      基本运算:初始化队列,判队空,入队,出队,读队头元素

      2 队列的存储结构:顺序存储,链式存储

      3 队列的应用:需要排队的场合:如操作系统中处理打印任务的打印队列、离散事件的计算机模拟

    4.1.3 串

      1 串的定义及基本运算

      (1)基本术语:串长,空串,空格串,子串,串相等,串比较

      (2) 串的基本操作:赋值操作,连接操作,求串长,串比较

      2 串的存储结构:顺序存储和链式存储

  4.2 数组

              这里介绍多维数组的逻辑结构和存储结构、特殊矩阵和矩阵的压缩存储

    2 矩阵

    (1)特殊矩阵:对称矩阵,三角矩阵,对角矩阵

  4.3 树与二叉树

  树结构是一种非常重要的非线性结构,该结构中一个数据元素可以有两个或两个以上的直接后继元素,可以用来描述客观世界中广泛存在的层次关系

    4.3.1 树的基本概念

    双亲、孩子和兄弟;结点的度;叶子结点;内部结点树的高度;有序(无序)树;森林

    4.3.2 二叉树:二叉树是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成

      1 二叉树的性质

      性质1:二叉树第i层(i>=1)上至多有2^(i-1)个结点

      性质2:深度为k的二叉树至多有2^k - 1个结点(k >=1)

      性质3:对任何一棵二叉树,若其终端结点(叶子)数为n0,度为2的结点数为n2,则n0=n2+1。对二叉树中结点的度求和即得到分支的数目,而二叉树中结点总数恰好比分支数目多1,由此可对性质3进行证明:总度数(n1+2n2)=总结点数(n0+n1+n2)-1

      2 满二叉树和完全二叉树

      3 二叉树的存储结构:顺序存储,链式存储

      4 二叉树的遍历:遍历是按某种策略访问树中的所有结点,且对每个结点仅访问一次的过程:先序,中序和后序3种遍历方法

    4.3.3 树和森林

    树的孩子兄弟表示法为实现树、森林与二叉树的相互转换奠定了基础

                    2 树和森林的遍历:先根遍历和后根遍历

    4.3.4 最优二叉树:又称哈夫曼树,是一类带权路径长度最短的树

    4.3.5 二叉查找树:又称二叉排序树或二叉检索树

  4.4 图

              在图中,任意两个结点之间都可能有直接的关系,所以图中一个结点的前驱和后继的数目是没有限制的

    1 基本概念:有向图;无向图;完全图;度,出度和入度;路径;子图;强连通图;网(带权图)

    2 图的存储结构:邻接矩阵,邻接链表

  4.5 查找

  对于含有n个记录的表,查找成功时的平均查找长度定义为

      解释:Pi为查找某元素的概率,Ci为找到表中其关键码与给定值相等的记录时,和给定值已进行过比较的关键码个数

    4.5.1 顺序查找与折半查找

      1 顺序查找

      2 折半查找

      3 索引顺序查找:又称分块查找

    4.5.2 树表查找

      1 在二查找树中查找

      2 在二叉查找树中插入

    4.5.3 哈希表及哈希查找

      (2)处理冲突:开放定址法,链地址法

  4.6 算法

    4.6.1 算法概述:算法是问题求解过程的精确描述,它为解决某一特定类型的问题规定了一个运算过程

    算法特性:有穷性,确定性,可行性,输入和输出

    一个算法的优劣可以从以下几个方面考查:正确性,可读性,健壮性,效率

      1 算法与数据结构:程序=数据结构+算法

      2 算法效率:时间复杂度,空间复杂度

      3 算法的描述:流程图,NS盒图,伪代码和决策表

    4.6.2 排序算法

    稳定排序,非稳定排序;内部排序,外部排序

    1 简单排序:

    1)直接插入排序

             2)冒泡排序

          2 希尔排序

           3 快速排序

             4 堆排序:大顶堆(大根堆),小顶堆(小根堆)

             5 归并排序

            6 内部排序方法小节

选取排序方法时需要考虑的主要因素有:待排序的记录个数n;记录本身的大小;关键码的分布情况;对排序稳定性的要求;语言工具的条件;辅助空间的大小;依据这些因素,可以得到以下几点结论:

    (1)若待排序的记录数n较小时,可采用插入排序和简单选择排序

    (2)若待排序记录按关键码基本有序,则宜采用直接插入排序或冒泡排序

    (3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法,例如快速排序、堆排序或归并排序

    当待排序的关键码随机分布时,快速排序的平均时间最短;堆排序只需一个辅助存储空间,并且不会出现在快速排序中可能出现的最坏情况。

    7 外部排序

             4.6.3 递归算法

    这类问题具有的特点是:整个问题的解决可以分为两部分,第一部分是一些特殊或基本的情况,可直接解决,即始基;第二部分与原问题相似,可用类似的方法解决,但比原问题的规模小。由于第二部分比整个问题的规模小,所以每次递归时第二部分的规模都在缩小,如果最终缩小为第一部分的情况则结束递归。因此,通过递归不断地分解问题,将子问题的解进行综合,完成原问题的求解。

    4.6.4 字符串运算

    1 基本的字符串运算:求串长,串拷贝,串比较

    2 串的模式匹配:模式串(或子串)在主串中的定位操作通常称为串的模式匹配

    1)基本的模式匹配算法:

    2)改进的模式匹配算法:KMP算法

    4.6.5 图的相关算法

    1 图的遍历算法

    1)深度优先搜索

    2)广度优先搜索

    2 最小生成树求解算法

    1)生成树的概念:设图G=(V,E)是个连通图,如果其子图是一棵包含G的所有顶点的树,则该子图称为G的生成树

    2)最小生成树:对于连通网来说,边是带权值的,生成树的各边也带权值,于是就把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。

    (1)普里姆算法思想(从顶点出发)

    (2)克鲁斯卡尔算法思想(从边出发)

    3 拓扑排序:

    1)AOV网

    2)拓扑排序

    4 求单源点的最短路径算法

    迪杰斯特拉算法:relax方法(修订最短路径)


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!