We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图: 常用的线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则是在内存中数据的一种组织、存储的方式。
顺序表将元素一个接一个的存入一组连续的存储单元中,在内存物理上是连续的。如下图: 顺序表存储密度较大,节省空间;但需要事先确定容量,在时间性能方面,读运算较快,时间复杂度为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步即可。(经@llhhyy1989 @voteforvip @wanghuan203 三位童鞋的指正,发现此处有误,正确插入方法可查看评论,为保留错误原文不做改动!不懂具体插入过程可移步: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()); } }
输出结果顺序为:初始数量:3,NO3,NO2,NO1,取完后的数量:0。
队列遵循先进先出的原则,如下图: Java中测试代码如下:
package com.snail.test; /** * * @author 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()); } }
运行结果顺序为:初始数量3,NO1,NO2,NO3,取出后数量0。 队列还有一种形式为循环队列,如下图: 循环队列有两个指针,头指针head和尾指针tail,尾指针一般指向的不是队尾元素实际地址,而是指向实际地址的下一个空地址,因此,循环队列一般牺牲最后一个空间,用来计算该队列是否满了,判断方式是tail+1 = head,既该队列已满。
是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结点的子树。 对于树的定义还需要注意两点:
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点,除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4,因为这棵树结点的度的最大值是结点D的度3,所以树的度也为3 结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent),同一个双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说,D,B,A都是它的祖先。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D,G,H,I,如图5所示。
从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。显然在图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>,其中V是顶点的有穷非空集合,E是边的集合。在图中顶点的前驱和后继是不设限制的,因此图描述的是一种网状关系。
若边是无序的或者说是无向的,则称此图是无向图。若无向图中有边(vi,vj)(无向图中边用圆括号表示),则显然(vj,vi)和(vi,vj)是同一条边。
若边是有序的或者说是有向的,则称此图是有向图。若有向图中有边<vi,vj>(有向图中边用尖括号表示),则显然<vj,vi>和<vi,vj>不是同一条边。有向图中的边也称为弧(arc),对于弧<vi,vj>,vi是弧尾(边的起点),vj是弧头(边的终点)。 示例图 无向图 G1=<V1,E1> V1={v0,v1,v2,v3,v4} E1={(v0,v1),(v0,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4)} 有向图 G2=<V2,E2> V2={v0,v1,v2,v3} E2={<v0,v1>,<v0,v2>,<v2,v0>,<v2,v3>,<v3,v0>}
所谓的图的存储,主要是想从存储结构中表达各顶点之间的联系,也就是表现图中的边。因为顶点总是很好存储的,如最常见的一维数组存储边:
| 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改为为相应的权值即可,在邻接表中顶点结构体则需添加成员表示权值。
概论看不懂没关系.后面会用更简单的方法介绍.听起来吓人那就对了
The text was updated successfully, but these errors were encountered:
暂不支持html标签,只支持纯markdown的文本,后面可能会加入markdown中嵌套html的功能
Sorry, something went wrong.
http://www.wandoujia.com/apps/cn.ifreedomer.com.androidguide 上面的链接是我做的app.用了你的markdown.大面积使用了.你可以看有啥不对的
棒棒哒!用了一下,关于markdown的地方我提几点建议吧
建议很不错~下个星期加上算法的内容在一起更新哈.
No branches or pull requests
数据结构概论
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图:
常用的线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则是在内存中数据的一种组织、存储的方式。
顺序表
顺序表将元素一个接一个的存入一组连续的存储单元中,在内存物理上是连续的。如下图:
顺序表存储密度较大,节省空间;但需要事先确定容量,在时间性能方面,读运算较快,时间复杂度为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步即可。(经@llhhyy1989 @voteforvip @wanghuan203 三位童鞋的指正,发现此处有误,正确插入方法可查看评论,为保留错误原文不做改动!不懂具体插入过程可移步:http://hiphotos.baidu.com/zhidao/pic/item/b58f8c54fee5c3663a2935e0.jpg)
从空间性能来看,链表的存储密度要差一些,但在容量分配上更灵活一些。从时间性能来看,查找运算与顺序存储相同,插入运算和删除运算的时间复杂度为O(1),要更优于顺序存储,但读运算则弱一些,为O([n+1]/2),最好为1,最坏为n。
栈
上面提到栈属于一个逻辑概念,栈的实现可以用顺序也可以用链式。它遵循先进后出原则,如下图:
Java中测试代码如下:
输出结果顺序为:初始数量:3,NO3,NO2,NO1,取完后的数量:0。
队列
队列遵循先进先出的原则,如下图:
Java中测试代码如下:
运行结果顺序为:初始数量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结点的子树。
对于树的定义还需要注意两点:
二、树的结点
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度(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>,其中V是顶点的有穷非空集合,E是边的集合。在图中顶点的前驱和后继是不设限制的,因此图描述的是一种网状关系。
无向图
若边是无序的或者说是无向的,则称此图是无向图。若无向图中有边(vi,vj)(无向图中边用圆括号表示),则显然(vj,vi)和(vi,vj)是同一条边。
有向图
若边是有序的或者说是有向的,则称此图是有向图。若有向图中有边<vi,vj>(有向图中边用尖括号表示),则显然<vj,vi>和<vi,vj>不是同一条边。有向图中的边也称为弧(arc),对于弧<vi,vj>,vi是弧尾(边的起点),vj是弧头(边的终点)。
示例图
无向图 G1=<V1,E1> V1={v0,v1,v2,v3,v4} E1={(v0,v1),(v0,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4)}
有向图 G2=<V2,E2> V2={v0,v1,v2,v3} E2={<v0,v1>,<v0,v2>,<v2,v0>,<v2,v3>,<v3,v0>}
图的存储
所谓的图的存储,主要是想从存储结构中表达各顶点之间的联系,也就是表现图中的边。因为顶点总是很好存储的,如最常见的一维数组存储边:
顶点
| 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,此时的邻接矩阵如下:
显然,由于是无向图,该矩阵是对称的。邻接矩阵所需的存储空间的大小与边数无关,而与顶点数有关。它所需的空间复杂度是O(n^2),n是顶点数。
同样的,若是使用邻接表来存储无向图G1,邻接表如下:
邻接表实质就是链式存储。
对于有权图,在邻接矩阵中只需把1改为为相应的权值即可,在邻接表中顶点结构体则需添加成员表示权值。
常用概念
环:在一条路径中,只有第一个顶点和最后一个顶点相同,这条路径就是环(cycle)或回路。
路径长度:路径上边的数目。
在有向图中,任意两个顶点之间都有一条有向的路径,则称该有向图是强连通图。
概论看不懂没关系.后面会用更简单的方法介绍.听起来吓人那就对了
The text was updated successfully, but these errors were encountered: