数据结构入门

        从来不写笔记的我为什么突然想写笔记？最近不知道是怎么回事？感觉自己的记性非常不好，比如接触了一个新东西，就算了解了其实现原理，能跟着思路自己手动完成，但是不过一个星期又忘了？难道是自己老了？从前找东西都是找的度娘，就算是使用过的东西也是同样的找度娘？记性是真的很差。所以现在想把最近所学的东西归纳总结一下，就算忘记了也能不断的通过笔记来复习，都说好记性不如好键盘，最近在学习数据结构，想把数据结构做一个总结，这个只是个人的总结，大牛路过的路望指点其中的不足，作为一名小白我只想把所学的东西做一个记录。

一、为什么要学习数据结构？

        举个例子来说，在古代为什么我们看的武侠电视剧里面的人在修炼武功的时候都要先练习基本功？就像少林寺和尚为什么进门之前要先挑水劈柴念经，为的就是修炼内功，只有修炼好了内功才能在高阶武功上进行深造，一步一步的达到上层。这就是为什么一天屠龙记的周芷若在内功不扎实的情况下修炼九阴真经达不到上层的原因。作为一个程序员，我们学习数据结构的目的就是为了打好基本功，只有这样一步一个脚印的走下去才能达到高级工程师的水平。而且在大型公司面试的时候基本都要求会数据结构，因为我们的程序就是数据结构和算法组成的，所以其研究价值比较高。

二、什么是数据结构？

        数据结构是对在计算机内存中的数据的一种安排。也可以理解为对计算机运算的数据单元的一个抽象。很抽象对不对，反正当初我在学习的时候是没听懂这个是什么意思，但是如果我自己来理解的话，我觉得就是数据与数据之间存在的一种关系，是我们的数据在计算机中的模型。

三、数据结构研究的内容

（一）数据的逻辑结构

            1. 集合结构

                    数据结构中的元素之间除了"同属一个集合" 的相互关系外，别无其他关系。

            2. 线性结构

                    数据结构中的元素存在一对一的相互关系;

            3. 树形结构

                    数据结构中的元素存在一对多的相互关系;

            4. 图形结构

                数据结构中的元素存在多对多的相互关系。

    光看这几个名词我们是不太明白它是什么东西的，接下来上图就好理解了。

    根据我们的理解和认知我们大概可以从上图了解到数据结构是个什么东西了。

（二）数据结构的存储结构（物理结构）

            1. 表    

            2.堆栈

            3.队列

            4.数组

            5.树

            6.图

四、线性表

对于表我们重点来研究线性表，什么是线性表？

由零个或多个数据元素组成的有限序列。线性表属于数据结构中逻辑结构中的线性结构。

注意：

（1）线性表是一个序列。

（2）0个元素构成的线性表是空表。

（3）线性表中的第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。

（4）线性表是有长度的，其长度就是元素个数，且线性表的元素个数是有限的，也就是说，线性表的长度是有限的。

线性表是线性结构的一种，那么线性表当然也有物理结构，也就是说，线性表有两种，分别是顺序结构的线性表（叫做顺序表）和链式结构的线性表（叫做链表）。

（一）顺序存储方式的线性表——顺序表

顺序表是指顺序存储结构的线性表，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序表表现在物理内存中，也就是物理上的存储方式，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。注意，这块物理内存的地址空间是连续的。举个例子来说就是“一个萝卜一个坑”、“排队”等表现形式。如下图：


知道了表现形式后，我们可以对着顺序表进行分析。如下图：


我们对线性表上的元素是这样定义的，其中a1是a2的前驱，ai+1是ai的后继，an没有后继，a1没有前驱。n为顺序表中元素的个数，当n==0时，线性表为空表。

顺序表的数据结构的代码表现形式为：

class Student{

Student[] data;

int size;

}

顺序表的应用：

ArrayList，Vector，ArrayQueue，ArrayDeque，PriorityQueue。

并发包：CopyOnWriteArrayList、ArrayBlockingQueue、PriorityBlockingQueue等。

（一）链式存储方式的线性表——链表

链表的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。如下图：


链表的分类：

1.单向链表


2.单向循环链表

将单链表中的终端结点的指针由空指针指向头结点，这样一来就使整个单链表形成了一个环，这种头尾相连的单链表称为单向循环链表，简称循环链表。


3.双向链表


4.双向循环链表

双向循环列表是单向循环链表的每个结点中，在设置一个指向其前驱结点的指针域，这样两个单向循环链表就构成了双向循环链表。


单向链表的数据结构的代码表现形式为：

class Node{

Object data;    //元素  数据域

Node next;      //指向当前节点的下一个元素结点

}

双向链表的数据结构的代码表现形式为：

class Node{

Object data;    //元素  数据域

Node prev;      //指向当前节点的上一个节点

Node next;      //指向当前节点的下一个节点

}

单链表的应用：MessageQueue、LinkedBlockingQueue（并发包）。

双链表的应用：LinkedList、LinkedBlockingDeque（并发包）。