大家好，我是讯享网，很高兴认识大家。



目录

概念

一、时间复杂度

二、算法度量工具

数组（Array）

一、概念

1.静态初始化

2.动态初始化

二、基本操作

1、遍历

2、添加

3、删除

4、更改

5、查询

6、扩容

链表（List）

一、概念

二、单向链表

1、遍历链表

2、添加节点

3、修改数据

4、删除节点

5、查找数据

6、翻转链表

三、单向循环链表

1、判断是否循环

2、遍历

3、添加

4、删除

5、更改

6、查询

四、双向链表

1、遍历

2、添加

3、删除

4、查询

5、更改

五、双向循环链表

1、判断是否循环

2、遍历

3、添加

4、删除

5、查询

6、修改

栈（Stack）

一、概念

二、数组实现栈

三、链表实现栈

1、单向链表实现

2、双向链表实现

队列（Queue）

一、用数组实现队列

二、用链表实现队列

1、单向链表实现

2、双向链表实现

三、循环队列

1、数组实现循环队列

2、双向链表实现循环队列

树（Tree）

一、概念

二、实现二叉树

1、节点：

2、二叉树：

排序

一、冒泡排序

二、选择排序

三、插入排序

JAVA数据基础数据结构算法

四、快速排序

五、归并排序

六、希尔排序

七、二分查找

特别感谢

---

概念

        数据结构（data structure）：数据在计算机中的存储与组织形式；其主要目的是为了对数据进行高效地访问和修改；数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。

        算法（algorithm）：在特定的计算模型下，旨在解决特定问题的一系列指令。

        程序 = 数据结构 + 算法

一、时间复杂度

        时间复杂度是对一个算法运行时间长短的量度，用大O表示，记作T(n) =O(f(n))

                若T(n) = Cn(C为常数)，则执行次数是线性的

                若T(n) = Clogn，则执行次数是用对数计算的

                若T(n) = C，则执行次数是常量

                若T(n) = C1n^2+C2n，则执行次数是用多项式计算

        为了解决时间分析的难题，有了渐进时间复杂度的概念，也就是大O表示法；大O表示法简化了时间函数T(n)，让其简化到一个数量级，这个数量级可以n，n²，n³，也就是T(n) =O(n)

        大O表示法有以下几个原则：

                如果运行时间是常数量级，则用常数1表示

                只保留时间函数中的最高阶项

                如果最高阶项存在，则会省去最高阶项前面的系数

        常见的时间复杂度按照从低到高的顺序：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等

二、算法度量工具

        𝑂(𝑛) 表达算法最坏情况的度量

        𝜃(𝑛) 表达算法最好情况的度量

        Ω(𝑛) 表达了一个算法的平均值

数组（Array）

一、概念

        数组是一种物理上连续，逻辑上也连续的数据结构；是有限个相同数据类型变量所组成的有序集合，数组中的每一个变量或其他类型被称为元素

        数组的特点是在内存中顺序存储，可以很好的实现逻辑上的顺序表，但数组的空间大小一旦创建了就不能被改变；正因为是顺序存储所以数组有了下标，这使得查询或更改速度得到了很大的提升，数组按照地址访问，可以在O(1)时间复杂度内完成高校访问

1.静态初始化

       静态初始化有两种方式

       第一种：数据类型[ ] 数组名 = new 数据类型[ ]{value1,value2,value3, ......}

       第二种：数据类型[ ] 数组名 = {value1,value2,value3, ......};

2.动态初始化

       数据类型[ ] 变量名 = new 数据类型[长度];

二、基本操作

1、遍历

讯享网

2、添加

讯享网

3、删除

4、更改

讯享网

5、查询

6、扩容

链表（List）

一、概念

        链表和数组同属于线性结构，他与数组是互补的。数组属于静态存储结构，而链表属于动态存储结构

        链表是逻辑上连续的存储单元，但物理上不连续。链表的基本存储单元是节点（node),存储单元之间使用引用或指针相互链接。同一个数组只能存储同种数据类型的元素，链表也一样，同一个链表只能存储同种数据类型，链表可以为空。链表的第一个节点称为头节点，最后一个节点称为尾节点，当链表为空时，头节点和尾节点相同，都指向null

        相邻节点彼此称为前驱或后继，一个节点的前驱或后继必须唯一，没有前驱的节点称为首节点，没有后继的称为末节点，链表按照关系访问，最坏情况的时间复杂度是O(n)

        链表分类：单向链表、双向链表、循环链表

二、单向链表

        单向链表的每一个节点Node包含两个部分，一部分是存放数据的变量data，另一部分是引用next，指向下一个节点，节点结构如下：

1、遍历链表

2、添加节点

3、修改数据

4、删除节点

5、查找数据

6、翻转链表

三、单向循环链表

        单向链表中，当尾节点的next指向了头结点，就形成了单向循环链表，循环链表中大部分代码都不用更改，基本与单向链表一致，为了大家阅读方便我就全部写上了

1、判断是否循环

2、遍历

3、添加

4、删除

5、更改

6、查询

四、双向链表

        链表按照关系访问，最坏情况的时间复杂度是O(n)，与单向链表不同的是双向链表中的节点有前驱与后驱的引用，这样可以使得链表相对于单向链表更易于访问，节点结构：

1、遍历

2、添加

3、删除

4、查询

5、更改

五、双向循环链表

1、判断是否循环

2、遍历

3、添加

4、删除

5、查询

6、修改

栈（Stack）

一、概念

        栈（stack）是一种操作受限的线性序列，只能在栈的顶部插入和删除数据，底部为盲端，栈是一种后进先出（LIFO）或先进后出（FILO）的数据结构

二、数组实现栈

三、链表实现栈

1、单向链表实现

        在单向链表中，那些用不到的方法我就不加上去了，其中为了便于栈的实现，我做了一些修改，代码如下：

节点：

单向链表：

栈：

2、双向链表实现

       与单链表一样，我对双链表也进行了一定的修改，代码如下：

节点：

双链表：

栈（与单链表的相同，为了方便阅读我也把代码粘出来）：

队列（Queue）

        队列也是一种操作受限制的线性序列，链表有队头与队尾，队列只能在队尾插入数据，在队头删除数据

一、用数组实现队列

二、用链表实现队列

1、单向链表实现

2、双向链表实现

三、循环队列

        因为单向链表实现流程基本相同，这里就用数组与双向链表来实现

1、数组实现循环队列

2、双向链表实现循环队列

树（Tree）

一、概念

       树中任意一个顶点，都有深度和高度，跟节点是所有节点的公共祖先且深度为0，没有后代的节点称作叶子，所有叶子深度中最大者称为树的高度，空树的高度为-1

        节点度不超过2的树称为二叉树，同一个节点的孩子和子树均分左右，深度为m的树，最多有2^m-1个节点，含有n个节点、高度为h的二叉树中h<n<2^h+1，当n=h+1时退化为链表，二叉树还分为满二叉树与真二叉树，满二叉树满足条件：n = 2^h-1，真二叉树是二叉树通过引入外部节点，使得原有的节点度数统一为2

二、实现二叉树

1、节点：

2、二叉树：

排序

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、归并排序

六、希尔排序

七、二分查找

特别感谢