weixin_39839968
weixin_39839968
2020-12-04 13:58

图片有的不显示.br标签和a标签直接显示出来.版本0.1.0. 文本如下

数据结构概论

数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图:

常用的线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则是在内存中数据的一种组织、存储的方式。

顺序表

顺序表将元素一个接一个的存入一组连续的存储单元中,在内存物理上是连续的。如下图:

顺序表存储密度较大,节省空间;但需要事先确定容量,在时间性能方面,读运算较快,时间复杂度为O(1);查找运算为O(n/2),和链表同样;插入运算和删除运算如果要操作中间一个元素,比如3,那么就需要把3后面的元素全部进行移动,因此时间复杂度相对链表要大一些,插入时间复杂度最好为O(0)或最坏为O(n);删除时间复杂度为O([n-1]/2);

链表

链表拥有很多结点,每个结点前半部分是数据域,后半部分是指针域,指针域指针指向下一个结点;链表可分为单链表、循环链表和双链表。

单链表:



从上图可以看出,单链表的上一个结点指针指向下一个结点,最后一个结点的指针域为null。 结点的删除:

删除一个结点,如删除上图中q结点,只需将p结点中的指针域指向a3,然后将a2释放掉(free)即可。 结点的插入:

插入一个结点,如插入上图中s结点,首先将s的指针域指向a2(也就是把s的next赋值为p的next),然后将p结点的指针域指向x即可(p的next指向x)。

循环链表

循环链表与单链表唯一不同之处是,循环链表的最后一个结点指针不为空,而是指向头结点。结点的插入和删除和单链表非常相似,就不再示范了。

双链表

双链表拥有一前一后两个指针域,从两个不同的方向把链表连接起来,如此一来,从两个不同的方向形成了两条链,因此成为双链表。因此,双链表的灵活度要大于单链表。 结点的删除:

双链表的操作比单链表要稍显复杂(按照单链表思路来做其实也不难),如上图,要删除p节点,首先需要将a1的后驱指向a3,然后将a3的前驱指向a1,最后将p节点释放掉即可。 结点的插入:

如上图,插入q结点,首先要按照方向,将步骤拆分,首先将q节点的前驱指向p结点后驱,紧接着将x后驱指向a2;然后按照顺序完成图中所示的3、4步即可。(经 三位童鞋的指正,发现此处有误,正确插入方法可查看评论,为保留错误原文不做改动!不懂具体插入过程可移步:http://hiphotos.baidu.com/zhidao/pic/item/b58f8c54fee5c3663a2935e0.jpg) 从空间性能来看,链表的存储密度要差一些,但在容量分配上更灵活一些。从时间性能来看,查找运算与顺序存储相同,插入运算和删除运算的时间复杂度为O(1),要更优于顺序存储,但读运算则弱一些,为O([n+1]/2),最好为1,最坏为n。

上面提到栈属于一个逻辑概念,栈的实现可以用顺序也可以用链式。它遵循先进后出原则,如下图:

Java中测试代码如下:


package com.snail.test;

import java.util.Stack;

public class TestStack {

    public static void main(String[] args) {

        Stack<string> stack = new Stack<string>();
        stack.push("NO1");
        stack.push("NO2");
        stack.push("NO3");

        System.out.println("初始数量:" + stack.size());

        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }   

        System.out.println("取完后的数量:" + stack.size());
    }
}
</string></string>

输出结果顺序为:初始数量:3,NO3,NO2,NO1,取完后的数量:0。

队列

队列遵循先进先出的原则,如下图:

Java中测试代码如下:


package com.snail.test;  

/** 
 * 
 *  Zang XT 
 */  
import java.util.Queue;  
import java.util.LinkedList;  
public class TestQueue {  
    public static void main(String[] args) {  
        Queue<string> queue = new LinkedList<string>();  

        queue.offer("NO1");  
        queue.offer("NO2");  
        queue.offer("NO3");  

        System.out.println("初始数量" + queue.size());  
        String str;  
        while((str=queue.poll())!=null){  
            System.out.println(str);  
        }  
        System.out.println("取出后数量" + queue.size());  
    }  
}  
</string></string>

运行结果顺序为:初始数量3,NO1,NO2,NO3,取出后数量0。 队列还有一种形式为循环队列,如下图:

循环队列有两个指针,头指针head和尾指针tail,尾指针一般指向的不是队尾元素实际地址,而是指向实际地址的下一个空地址,因此,循环队列一般牺牲最后一个空间,用来计算该队列是否满了,判断方式是tail+1 = head,既该队列已满。

一、树(Tree)定义

是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中: (1)有且仅有一个特定的称为根(root)的结点。 (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如图1所示:

树的定义之中还用到了树的概念,即递归定义。如图2中的子树T1和T2就是根结点A的子树。当然D,G,H,I组成的的树又是B结点的子树,E,J 组成的树是C结点的子树。

对于树的定义还需要注意两点: 1. n>0时根结点是唯一的,不可能存在多个根结点。 2. m>0时,子树的个数没有限制,但它们一定是互不相交的。如图3中的两个结构就不符合树的定义,因为它们都有相交的子树。

二、树的结点

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点,除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4,因为这棵树结点的度的最大值是结点D的度3,所以树的度也为3

结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent),同一个双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说,D,B,A都是它的祖先。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D,G,H,I,如图5所示。

三、结点的层次(Level)

从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。显然在图6中D,E,F都是堂兄弟,而 G,H,I 与 J也是堂兄弟。树中结点的 最大层次称为树的深度(Depth)或高度,当前树的深度为4(注:也有一些书是定义为branches的个数,此时认为 深度为3)。

若将树中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该树为有序树(OrderedTree);否则称为无序树(UnorderedTree)。注意:若不特别指明,一般讨论的树都是有序树。 森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。对于图1的树而言,图2的两棵子树其实就可以理解为森林。树和森林的概念相近。删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。 对比线性表与树的结构,它们有很大不同,如图7所示。

图概述

图(Graph)是一种比线性结构和树形结构都要复杂的数据结构。简单讲,图是由表示数据元素的的集合V和表示数据之间关系的集合E组成。其中,数据元素常称作顶点(vertex),数据之间的关系常称作边(edge)。故图可记为G=,其中V是顶点的有穷非空集合,E是边的集合。在图中顶点的前驱和后继是不设限制的,因此图描述的是一种网状关系。

无向图

若边是无序的或者说是无向的,则称此图是无向图。若无向图中有边(vi,vj)(无向图中边用圆括号表示),则显然(vj,vi)和(vi,vj)是同一条边。

有向图

若边是有序的或者说是有向的,则称此图是有向图。若有向图中有边(有向图中边用尖括号表示),则显然和不是同一条边。有向图中的边也称为弧(arc),对于弧,vi是弧尾(边的起点),vj是弧头(边的终点)。 示例图 无向图 G1= V1={v0,v1,v2,v3,v4} E1={(v0,v1),(v0,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4)} 有向图 G2= V2={v0,v1,v2,v3} E2={,,,,}



图的存储

所谓的图的存储,主要是想从存储结构中表达各顶点之间的联系,也就是表现图中的边。因为顶点总是很好存储的,如最常见的一维数组存储边:

顶点

| v0 | v1 | v2 | v3 | v4 |

或者是

| A | B | C | D | E

邻接矩阵(adjacency matrix)和邻接表(adjacency list)是图的两种常见存储方式。 如上,无向图G1,对于顶点Vi和顶点Vj,若有边,则(Vi,Vj)=1,否则(Vi,Vj)=0。显然(Vi,Vi)=0,此时的邻接矩阵如下:


V0  V1  V2  V3  V4
V0  0   1   1   0   0
V1  1   0   0   1   0
V2  1   0   0   1   1
V3  0   1   1   0   1
V4  0   0   1   1   0

显然,由于是无向图,该矩阵是对称的。邻接矩阵所需的存储空间的大小与边数无关,而与顶点数有关。它所需的空间复杂度是O(n^2),n是顶点数。 同样的,若是使用邻接表来存储无向图G1,邻接表如下:

邻接表实质就是链式存储。 对于有权图,在邻接矩阵中只需把1改为为相应的权值即可,在邻接表中顶点结构体则需添加成员表示权值。

常用概念
  • 顶点的度(degree):与顶点关联的边的数目,记为D(v)。特别的,在有向图中,把顶点v作为终点的弧的数目是入度(in degree),记为ID(v);把顶点v作为起点的弧的数目是出度(out degree),记为OD(v)。显然,D(v)=ID(v)+OD(v)。
  • 顶点v1和顶点v2若是有边相连的,则称它们是相邻的(adjacent)。
  • 用n表示顶点数,e表示边数。则无向图中e是0,n(n-2)/2;有向图中e是[0,n(n-1)]。
  • 边数较少的图称为稀疏图(sparse graph),边数较多则称为稠密图(dense graph)。
  • 完全图:任意两个顶点之间都有边相关联的是完全图。完全图中边数达到最大。细分为无向完全图和有向完全图。
  • 有时边是带有权值的,这个权值可以表示从一个顶点到另一个顶点的距离、代价、耗费等。这样的图也称为带权图。
  • 子图:设G=是一个图,V1是V的子集,E1是E的子集,且E1中的边只与V1中的顶点有关,则称G1=是G的的子图(subgraph)。
  • 路径:在无向图中顶点序列:vi,vj,…,vk,且相邻两顶点之间是有边的,则这个序列构成一条路径。在有向图中,构成路径的不仅是要有边,而且边的方向正确:只能是起点到终点。
  • 简单路径:路径中不存在重复顶点,则是简单路径(simple path)。 环:在一条路径中,只有第一个顶点和最后一个顶点相同,这条路径就是环(cycle)或回路。 路径长度:路径上边的数目。
  • 无环图:没有环的图(acyclic graph)。在有向图中,那就是有向无环图。
  • 在无向图中,若顶点vi和vj是有路径的,则称vi和vj是连通的(connected)。若图中任意两个顶点都是连通的,则称该图是连通图。
  • 连通分量:无向图中的极大连通子图。(所谓的极大是指再加入任意一个顶点,则不连通) 在有向图中,任意两个顶点之间都有一条有向的路径,则称该有向图是强连通图。
  • 强连通分量:有向强连通的极大子图称为有向图的强连通分量或强连通分支。

概论看不懂没关系.后面会用更简单的方法介绍.听起来吓人那就对了

该提问来源于开源项目:zzhoujay/Markdown

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

4条回答

  • weixin_39804059 weixin_39804059 4月前

    暂不支持html标签,只支持纯markdown的文本,后面可能会加入markdown中嵌套html的功能

    点赞 评论 复制链接分享
  • weixin_39839968 weixin_39839968 4月前

    http://www.wandoujia.com/apps/cn.ifreedomer.com.androidguide
    上面的链接是我做的app.用了你的markdown.大面积使用了.你可以看有啥不对的

    点赞 评论 复制链接分享
  • weixin_39804059 weixin_39804059 4月前

    棒棒哒!用了一下,关于markdown的地方我提几点建议吧 1. 显示markdown内容的TextView最好设置一点左右padding(上下也可以设置一点),看起来会好一点。 2. 解析markdown时应采用异步的方式去做,而且最好在加载过程中加个progress dialog

    点赞 评论 复制链接分享
  • weixin_39839968 weixin_39839968 4月前

    建议很不错~下个星期加上算法的内容在一起更新哈.

    点赞 评论 复制链接分享