### 一、树的定义 定义：树是n个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可以分为m个互不相交的有限集T1、T2、...Tm，其中每一个集合本身又是一棵树，并且称为根的子树。 对于树的定义还需要强调两点： 1.n>0时根节点是唯一的； 2.m>0时，子树的个数没有限制，但他们一定是互不相交的。 结点的分类 结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶子结点（leaf），度不为0的结点称为分支结点。树的度是树内各结点的度的最大值，如图所示树的度为3。  结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称为兄弟。结点的祖先是从根到该节点所经分支上的所有结点。以某结点为根的子树中任一结点都称为该结点的子孙。  树的层次（Level）的概念：  树中结点的最大层次称为树的深度（Depth）。 最后，对比线性表与树的结构：  ### 二、树的抽象数据类型 下面给出树的一些基本和常用操作：  ### 三、二叉树的定义 二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不交互的、分别称为根节点的左子树和右子树的二叉树组成。 特殊二叉树： 1.满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树就称为满二叉树。  2.完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1=1）; 性质2：深度为K的二叉树至多有2^k-1个结点（k>=1）； 性质3：对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 性质4：具有n个结点的完全二叉树的深度为【log2n】+1（【x】表示不大于x的最大整数） ### 四、二叉树的存储结构 1.二叉树的顺序存储结构：   顺序存储一般适用于完全二叉树 2.二叉链表 二叉树每个结点最多有两个孩子，所以为它涉及一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。如图所示：  二叉链表的结点结构定义代码如下：  结构示意图如下：  ### 五、遍历二叉树 二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。 二叉树的遍历方法 1.前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。如图所示：（根左右）  2.中序遍历：（左根右）  3.后序遍历（左右根）  4.层序遍历：  下面来看一下前序遍历算法 二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了：  中序遍历算法：  后序遍历算法：  ### 六、二叉树的建立 为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，如图：  扩展二叉树就可以做到一个遍历序列确定一个二叉树了，上图的前序遍历序列就是AB#D##C##。有了这样的准备，我们就可以来看看如何生成一棵二叉树了。实现算法如下：   ### 七、霍夫曼树及其应用 最基本的压缩编码方法-霍夫曼编码，在介绍霍夫曼编码前，我们必须得介绍霍夫曼树，而介绍霍夫曼树。带权路径长度WPL最小的二叉树称作霍夫曼树。也有不少树中称为最优二叉树。  二叉树a的WPL=315，二叉树b的WPL=220。 下面介绍一下霍夫曼树的构造： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图： [](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832079219.png) 虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图： [](http://images.cnblogs.com/cnblogs_com/Jezze/201112/20111223183207124.png) 再依次建立哈夫曼树，如下图： [](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832082109.jpg) 其中各个权值替换对应的字符即为下图： [](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832085730.jpg) 所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010 下面研究一下霍夫曼编码： 一般地，设需要编码的字符集为{d1,d2,......dn},各字符在电文中出现的次数或频率的集合为{w1,w2,......wn}，以d1,d2,......dn作为叶子结点，以w1,w2,......wn作为相应叶子结点的权值来构造一棵霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符编码，这就是霍夫曼编码。 例子：我们在发送电报的时候用到了六个字母，其出现的概率分别为：A 27，B 8，C 15， D 15，E 30，F 5,合起来正好是百分之百。 怎么获得霍夫曼编码呢？ 首先按照比率作为权值画霍夫曼树，然后将左分支代表0，右分支代表1，如图：  从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符编码，即：  这样就获得了霍夫曼编码。

### 一、串的定义 串（string）是由零个或多个字符组成的有限序列，又名叫字符串。 一般记作： s="a1a2a3...an"; 字符串的基本操作方法：  ### 二、串的存储结构 1.串的顺序存储结构：串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。 2.串的链式存储结构：总的来说不如顺序存储灵活，性能也不如顺序存储结构好。 ### 三、朴素的模式匹配算法 子串的定位操作通常称作串的模式匹配，是串中最重要的操作之一。 算法如下： ~~~ /*操作Index的实现算法*/ //T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串，则返回第一个这样的子串在S中的位置，否则返回0 int Index(String S,String T,int pos) { int n,m,i; String sub; if (pos > 0) { n = StrLength(S); m = StrLength(T); i = pos; while (i <= n-m+1) { SubString (sub,S,i,m); //取主串第i个位置，长度与T相等子串给sub if (StrCompare(sub,T) != 0) //如果不相等 ++i; else return i; } } return 0; } ~~~ ### 四、KMP模式匹配算法 我们可以忍受朴素模式匹配算法的低效吗?也许不可以，也许无所谓。但在很多年前我们的科学家们，觉得像这种有多个0和1重复字符的字符串，却需要挨个遍历的算法是非常糟糕的事情。于是有三位前辈，发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称为KMP算法。 kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。  #### kmp算法思想 我们首先用一个图来描述kmp算法的思想。在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论： - A段字符串是f的一个前缀。 - B段字符串是f的一个后缀。 - A段字符串和B段字符串相等。 所以前移k位之后，可以继续比较位置i的前提是f的前i-1个位置满足：**长度为i-k-1的前缀A和后缀B相同**。只有这样，我们才可以前移k位后从新的位置继续比较。  所以kmp算法的核心即是计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。  #### next数组计算 理解了kmp算法的基本原理，下一步就是要获得字符串f每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next数组。在这里要注意一点，next数组表示的是长度，下标从1开始；但是在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。由上图我们可以看到，如果位置i和位置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。由此我们可以写出求next数组的代码（java版）： ** ~~~ public int[] getNext(String b) { int len=b.length(); int j=0; int next[]=new int[len+1];//next表示长度为i的字符串前缀和后缀的最长公共部分，从1开始 next[0]=next[1]=0; for(int i=1;i0&&b.charAt(i)!=b.charAt(j))j=next[j]; if(b.charAt(i)==b.charAt(j))j++; next[i+1]=j; } return next; } ~~~ 上述代码需要注意的问题是，我们求取的next数组表示长度为1到m的字符串f前缀的最大公共长度，所以需要多分配一个空间。而在遍历字符串f的时候，还是从下标0开始(位置0和1的next值为0，所以放在循环外面)，到m-1为止。代码的结构和上面的讲解一致，都是利用前面的next值去求下一个next值。 #### 字符串匹配 计算完成next数组之后，我们就可以利用next数组在字符串O中寻找字符串f的出现位置。匹配的代码和求next数组的代码非常相似，因为匹配的过程和求next数组的过程其实是一样的。假设现在字符串f的前i个位置都和从某个位置开始的字符串O匹配，现在比较第i+1个位置。如果第i+1个位置相同，接着比较第i+2个位置；如果第i+1个位置不同，则出现不匹配，我们依旧要将长度为i的字符串分割，获得其最大公共长度next[i]，然后从next[i]继续比较两个字符串。这个过程和求next数组一致，所以可以匹配代码如下（java版）： ~~~ public void search(String original, String find, int next[]) { int j = 0; for (int i = 0; i < original.length(); i++) { while (j > 0 && original.charAt(i) != find.charAt(j)) j = next[j]; if (original.charAt(i) == find.charAt(j)) j++; if (j == find.length()) { System.out.println("find at position " + (i - j)); System.out.println(original.subSequence(i - j + 1, i + 1)); j = next[j]; } } } ~~~ 上述代码需要注意的一点是，每次我们得到一个匹配之后都要对j重新赋值。 #### 复杂度 kmp算法的复杂度是O(n+m)，可以采用均摊分析来解答，具体可参考算法导论。

### 一、栈的定义 栈（stack）是限定尽在表尾进行插入和删除操作的**线性表**。 我们把允许插入和删除的一端成为栈顶（top），另一端成为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（LIFO)的线性表。 图示出栈入栈操作：  ### 二、栈的抽象数据类型 图示栈的各项操作：  由于栈本身就是一个线性表，那么上一章我们讨论了线性表的顺序存储和链式存储，对于栈来说也是同样适用的。 ### 三、栈的顺序存储结构及实现 来看一下栈的结构定义：  若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此常把空栈的判定条件定位top等于-1。 看一下示意图：  下面看一下push操作的代码：  出栈pop，代码如下：  两者都没有涉及到任何循环语句，因此时间复杂度均为O（1）。 ### 四、栈的链式存储结构及实现 栈的链式存储结构，简称链栈。 链栈的结构代码如下：  进栈操作：    出栈操作：   上述操作也不包含循环，因此时间复杂度都是O（1）。 对于顺序栈和链栈的选择：如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好些。 ### 五、栈的应用-递归 递归的最经典例子：（斐波那契额数列）  代码如下：  递归的定义：我们把一个直接调用自己或通过一系列的调用语句间接地调用自己得函数，称为递归函数。 递归程序最可怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。 ### 六、栈的应用-四则运算表达式求值 我们介绍一种不需要括号的后缀表达法，我们把它称为逆波兰（RPN）。 我们来看一个例子：对于运算:9+(3-1)*3+10/2,其逆波兰表达式为：9 3 1 - 3 * 10 2 / +    这种表达式是反人类的表达式，但是是顺计算机的，我们也就忍忍吧！ 计算规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈，进行计算，将计算结果再入栈，一直重复直到获取结果。 ### 七、队列的定义 定义：队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出（FIFO）的线性表。 队列的抽象数据类型：  循环队列的定义：我们把队列的这种头尾相连的顺序存储结构称为循环队列。 判断队列满的条件是：（rear+1)%QueueSize==front 计算队列长度的公式：（rear-front+QueueSize）%QueueSize 循环队列的顺序存储结构代码如下：  循环队列的初始化代码如下：  循环队列求队列长度代码如下：   循环队列的入队操作代码如下：  循环队列的出队操作代码如下：  循环队列面临着数组可能会溢出的问题，我们还要研究一下不用担心队列长度的链式存储结构。 ### 八、队列的链式存储结构及实现 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。  链队列的结构为：  队列链式存储结构--入队操作  代码如下：  队列链式存储结构--出队操作  代码如下：  总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。 ### 九、总结回顾 栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。 它们均可以使用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。 对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是O（n）的时间复杂度编程了O（1）。

### 一、线性表定义 线性表：零个或多个数据元素的**有限**序列。（零个的时候是空表） 线性表的特性是：除了第一个元素（只有后继）和最后一个元素（只有前驱），每个元素都只有一个前驱和后继。 ### 二、线性表的抽象数据类型 线性表的抽象数据类型定义如下：   ### 三、线性表的顺序存储结构 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。 来看线性表顺序存储结构代码：  发现描述顺序存储结构需要三个属性： 1.储存空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。 2.线性表的最大存储容量：数组长度MaxSize。 3.线性表的当前长度：length。 下面再讨论一下地址的计算方法：  ### 四、顺序存储结构的插入与删除 获得元素的操作：   插入操作：  删除操作：   线性表的顺序存储结构的优缺点： 优点：1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间2.可以快速地存取表中任一位置的元素。 缺点：1.插入和删除操作需要移动大量元素2.当线性表长度变化较大时，难以确定存储空间的容量3.造成存储空间的碎片。 ### 五、线性表的链式存储结构 n个节点链结成一个链表，即为线性表的链式存储结构，因为此链表的每一个节点中只包含一个指针域，所以叫做单链表。  把链表中第一个节点的存储位置叫做头指针，最后一个节点指针为空。  一般为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，成为头结点。头结点的**数据域可以不保存任何信息**。 头指针和头结点的异同： **头指针**是指向头结点的指针；头指针具有标识作用，所以常用头指针冠以链表的名字；无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 **头结点**是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（也可以存放链表的长度）；有了头结点，对在第一个元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；头结点不一定是链表的必须元素。  结点的概念：结点由存放数据元素的**数据域**存放后继结点的**指针域**组成。 假设P是指向线性表的第i个元素的指针，则该节点aI的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点aI的指针域可以用p->next来表示，p->next的值是一个指针。如果p->data=ai,那么p->next->data=aI+1。即：  ### 六、单链表的读取   由上面程序看出来，获取链表获取第i个元素比较麻烦。 ### 七、单链表的插入与删除 插入结点：  删除结点：  由算法可以看出，插入和删除对于链表来说每次只需要简单地通过赋值移动指针而已，时间复杂度都是O(1),显然，对于插入和删除数据越频繁的操作，单链表的效率优势就越是明显。 ### 八、单链表的整表创建 头插法：   尾插法：   ### 九、单链表的整表删除  十、单链表结构与顺序存储结构优缺点  ### 十一、循环链表 将单链表的终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。  下面研究一下循环链表的合并：  分成4步： 1.p=rearA->next; 2.rearA->next=rearB->next->next; 3.rearB->next=p; 4.free(p). ### 十二、双向链表 双向链表概念：双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。  双向链表插入操作：  同样也分成4步： 1.s->prior=p; 2.s->next=p->next; 3.p->next->prior=s; 4.p->next=s. 双向链表的删除操作：  分成3步： 1.p->prior->next=p->next; 2.p->next->prior=p->prior; 3.free(p). ### 十三、总结 

什么是算法？1+1=2算不算算法？严格讲算法不分难易，能解决数学问题的方法都叫算法。 哈，下面让我们看一下严格的定义吧：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。 ### 一、数据结构和算法的关系 数据结构和算法什么关系？这不是介绍数据结构的文章吗，为什么扯到算法了呢？ 如果上一章你看了的话，应该会记得一个公式：**程序设计=数据结构+算法**。（牛人就是牛人，一个公式就说明了所有的关系）通俗地来讲这个数据结构和算法的关系就像梁山伯和祝英台、罗密欧和朱丽叶的关系。只谈数据结构和只谈算法是没有意义的，它们俩在一起才能碰撞出智慧的火花！ ### 二、算法优劣的比较 上过小学的童鞋（废话）应该都遇到过这样一个经典的问题吧：1+2+3+...+100，要解决这样一个问题，程序改怎么写？凭你的智商相信这个难不住你吧： ~~~ public class Add { public static void main(String args[]) { int sum = 0; int n = 100; for (int i = 1; i <= 100; i++) { sum = sum + i; } System.out.println(sum); } } ~~~ 最近在用Java,就用Java写了啊，算法其实是超脱语言的，什么语言都能展现。 这个程序其实是不经过思考写出来的程序，当然计算机的运行速度很快我们感觉不到，要让你用笔算估计你就崩溃了。 话说还有没有更省时的算法呢？上过高中的同学都应该学过等差数列吧，这其实就是一个最简单的等差数列求和，当然我们有求和公式啦！一百个加法换成一个乘法，是不是很伟大的转换？节省了大量的时间。 其实我们所要追求的境界就是在能用更好的方法解决问题，而不是仅仅只是解决问题这么简单，这就是算法的魅力。 ### 三、算法特性 算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。 输入输出：算法具有零个或多个输入，有一个或多个输出。（也就是说**可以没有输入但是必有有输出**） 有穷性：指算法在执行**有限个步骤**之后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。 确定性：算法的每一个步骤都有确定的含义，不会出现二义性。 可行性：算法的每一步都必须是可行的，也就是说每一步都能够通过执行有限次数完成。 ### 四、算法设计的要求 1.正确性：算法的正确性是指算法至少应该有输入、输出金额加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。 2.可读性：算法设计的另一个目的是为了便于阅读、理解和交流。 3.健壮性：当输入不合法的数据时，算法也能进行相关处理，而不是产生程序崩溃、异常退出等。 4.时间效率高和存储量低。 ### 五、算法效率的度量方法 凡事讲求证据，你说别人的算法效率低，总的拿出来标准吧，这个标准也就是度量的方法，才能让别人心服口服。 1.事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低。（想法很简单，实施起来不容易，也缺乏公信力，不予采纳） 2.事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。 第二节讨论的问题可以量化优劣了：  第一种算法执行了2n+3次，第二种算法执行了3次。假如n很大的话，这执行时间可就不是一个数量级了吧。所以说研究算法很大程序上是在研究执行效率上面。 ### 六、算法时间复杂度 1.定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 2.推导大O阶方法 推导大O阶： 1.用常数1取代运行时间中的所有加法常数。O（3）=O（1） 2.在修改后的运行次数函数中，只保留最高项。O（n^2+n)=O(n^2) 3.若果最高阶存在且不是1，则除去与这个项相乘的常数。得到的结果就是大O阶。O(2n^2)=O(n^2) 下表介绍常见的时间复杂度： 

本文章作为学习笔记，大量参考了《大话数据结构》这本书，因为没有用于商业活动，而且也算是为作者做了一个小小的宣传，作者应该不会告我侵权，哈。 数据结构的概念：**是相互之间存在的一种或多种特定关系的数据元素的集合。（学了半天这个概念得知道吧！）** ###  开场白 数据结构有什么用？如果你想走程序员的道路，如果你不想一辈子搬砖，如果你想比别人工资高百分之三十，如果你想让家人过上好日子，如果...  够现实了吧！ ### 数据结构的起源 数据结构是程序员的炼狱，你经历了数据结构的“折磨”才能蜕变。数据结构就是大牛们经验的总结，跟着走不会错。 一个经典的公式：程序设计=数据结构+算法。 ### 几个概念 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。（符号--可以输入计算机中并能被计算机程序处理） 数据元素：组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。 数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。 数据对象：是性质相同的数据元素的集合，是数据的子集。 ### 逻辑结构和物理结构 #### 逻辑结构：是指数据对象中数据元素之间的相互关系。 1.集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。 2.线性结构：数据结构中数据元素之间是一对一的关系。 3.树形结构：数据元素之间存在一种一对多的层次关系。 4.图形结构：图形结构的数据元素是多对多的关系。 #### 物理结构：是指数据的逻辑结构在计算机中的存储形式。 1.顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。 2.链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元是连续的，也可以是不连续的。 ### 抽象数据类型 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 抽象数据类型：是指一个数学模型及定义在该模型上的一组操作。（抽象在于数据类型的数学抽象特性） ### 几个图总结一下：  

> 原文出处：[掰扯数据结构](http://blog.csdn.net/column/details/data-structure0516.html) 作者：[张亚运](http://blog.csdn.net/yayun0516) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 掰扯数据结构 > 精简的数据结构教程，由浅入深，帮助初学者快速学习数据结构知识。