# go-data-structure

**Repository Path**: liuqi2018/go-data-structure

## Basic Information

- **Project Name**: go-data-structure
- **Description**: golang数据结构和算法总结
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-08-10
- **Last Updated**: 2021-09-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构和算法（Golang实现）笔记

1. [算法](https://goa.lenggirl.com/#/basic/rescuvie?id=%e4%ba%8c%e3%80%81%e4%be%8b%e5%ad%90%ef%bc%9a%e6%96%90%e6%b3%a2%e9%82%a3%e5%a5%91%e6%95%b0%e5%88%97)含义：算法是一种有限，确定，有效的并适合用计算机程序来实现的，用来解决问题的方法。首先，有一个问题，然后有一个方法去解决它，这个方法叫算法
2. 数据结构:链表、栈、队列、树、图
3. 分治法和递归,在计算机科学中，分治法是一种很重要的算法。字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题。直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。分治法一般使用递归来求问题的解（汉塔诺递归）
4. 基本的数据结构有：链表，栈和队列，树和图
   > 链表，就是把数据链接起来，关联起来，一个数据节点指向另外一个数据节点，像自然界的一条条铁链，大部分*数据>结构，都是由链表的若干变种来表示

   >栈和队列，主要用来存储多个数据，只不过一个是先进后出，一个先进先出。比如下压栈，先入栈的数据是最后才能出来，而我们熟知的队列，先排队的人肯定先获得服务。

   >其次是树和图，树就是有一个树根节点，存放着数据，下面有很多子节点，也存放着数据，类比自然界的树。图则可以类比自然界的地图，多个点指向多个点，点和点之间有一条或多条边，而这些点存放着数据，边也可以存放着数据，比如距离等
5. 什么叫好的数据结构和好的算法
   > 计算机资源是有限 的，所以占用计算机资源越少的数据结构和算法越好。  
    人的生命是有限的 的，等待时间是有忍耐度的，所以能辅助程序越快完成工作的数据结构和算法越好。  
    所以出了个理论：时间和空间算法复杂度理论。  
    程序执行过程中，要么空间换时间，要么时间换空间，空间可以认为是一种计算机资源如内存使用情况，而时间是人类感知的第四个维度，就是慢还是快，两者一般不能兼得，如果发现居然兼得了，那就是发明了一种更好的算法。
## 分治法和递归
> 字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题。 
  直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。  
  分治法一般使用递归来求问题的解。  
  [阶乘算法](./01递归算法_test.go "递归算法") 比如我们求阶乘 1 * 2 * 3 * 4 * 5 *...* N:  
  [斐波那契数](./01递归算法_test.go "递归算法") 是指，后一个数是前两个数的和的一种数列。 1 1 2 3 5 8 13 21 ... N-1 N 2N-1  
  [二分查找](./01递归算法_test.go "递归算法") 在一个已经排好序的数列，找出某个数，如。1 5 9 15 81 89 123 189 333 从上面排好序的数列中找出数字 189

## 算法复杂度
> o(n) n表示循环执行次数
算法的优先级排列如下，一般排在上面的要优于排在下面的：  
常数复杂度：O(1)  
对数复杂度：O(logn)  
一次方复杂度：O(n)  
一次方乘对数复杂度：O(nlogn)  
乘方复杂度：O(n^2)，O(n^3)  
指数复杂度：O(2^n)  
阶乘复杂度：O(n!)  
无限大指数复杂度：O(n^n)  

##常见的数据结构及算法

>常见的典型数据结构有：
链表
栈和队列
树
图
上述可以延伸出各种各样的术语和结构，如列表，集合，哈希表，堆，优先队列，二叉树，红黑树，B+树以及各种变种等。
我们区别开数据结构和算法，是因为算法是更高层次的一种智慧结晶，目的就是为了解决问题，基本的算法分类有：
排序算法
查找算法
图相关的算法
其他的算法
计算机科学作为数学的一个分支，大部分的数学知识都是离散数学。我们学习微积分，都是连续的量，可是计算机处理的都是离散的量，数据不存在渐变，都是一个个离散数据。
所以针对离散的计算机科学来说，很多算法都是很简单，也是富含哲学的。 也就是说，现在已知的所有算法，都是严格定义的，是死的，是千篇一律的。作为解决日常生活的一种思路，不需要纠结算法是什么分类，只要知道有这种方法，在什么时候需要使用它就行了。
一般在日常工程开发中，也就是做软件，做网站，基本只使用到排序和查找算法，甚至有些情况下不需要使用。100%的日常开发场景是，我拿到一个数据存在数据库，你需要这个数据，我再帮你找出来。



## 链表

> 链表由一个个数据节点组成的，它是一个递归结构，要么它是空的，要么它存在一个指向另外一个数据节点的引用  
结构体 LinkNode 有两个字段，一个字段存放数据 Data，另一个字典指向下一个节点 NextNode 。这种从一个数据节点指向下一个数据节点的结构，都可以叫做链表。  
有些书籍，把链表做了很细的划分，比如单链表，双链表，循环单链表，循环双链表，其实没有必要强行分类，链表就是从一个数据指向另外一个数据，一种将数据和数据关联起来的结构而已。  
好吧，我们还是要知道是什么。 
>>单链表，就是链表是单向的，像我们上面这个结构一样，可以一直往下找到下一个数据节点，它只有一个方向，它不能往回找。   
>>双链表，每个节点既可以找到它之前的节点，也可以找到之后的节点，是双向的。  
>>循环链表，就是它一直往下找数据节点，最后回到了自己那个节点，形成了一个回路。循环单链表和循环双链表的区 别就是，一个只能一个方向走，一个两个方向都可以走。