# dataStructure

**Repository Path**: nebneb/data-structure

## Basic Information

- **Project Name**: dataStructure
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-03-24
- **Last Updated**: 2022-04-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# dataStructure

## 一、线性表

### 1、顺序表

### 2、链表

#### 2.1 单链表

#### 2.2 双链表

#### 2.3 循环链表

## 二、栈

### 1、顺序栈

### 2、链栈

## 三、队列

### 1、顺序队列

### 2、链队列

## 四、串

### 1、BF暴力匹配算法

### 2、BM

### 3、KMP

暴力匹配

```java

public static int Index(String s, String pattern) {// 主串顺序匹配
        int i = 0; //s
        int j = 0; //pattern
        while (i < s.length() && j < pattern.length()) {
            if (s.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            } else {
                i = i - j + 1;  //j表示 pattern前进的步数  因为i和j是一起加的，i-j表示减去j的部分回到上一次的地方 +1表下一个位置
                j = 0;
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }
```

next数组

```java
    public static int[] getNext(String pattern) {
        int i = 0;
        int j = -1;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while (i < pattern.length() - 1) {  //  pattern.length()的话  如果i = pattern.length()-1  那么i++后就是pattern.length()了
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
            System.out.println(i);
        }
        return next;
    }
```

nextval数组

```java
public static int[] getNextVal(String pattern) {
        int i = 0;
        int j = -1;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;

                if (pattern.charAt(i) != pattern.charAt(j)) {  //这里属于  j = -1的情况
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }

            } else {
                j = next[j];
            }
        }
        return next;
    }
```

KMP算法

```java
 public static int KMP_test(String s, String pattern) {// 主串顺序匹配
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < s.length() && j < next.length) {
            if (j == -1 || s.charAt(i) == pattern.charAt(j)) {  //与朴素的相比较 加了 j == -1
                ++i;
                ++j;
            } else {
                j = next[j];     //与朴素的相比较 替换成 j = next[j]
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

```



## 五、树

### 1、树

### 2、二叉树

### 2、线索二叉树

### 3、顺序存储二叉树

## 六、图

### 1、邻接表

边

```java

```

顶点

```java


```



### 2、邻接矩阵

```java


```



### 3、深度优先搜索

### 4、广度优先搜索

### 5、Prim最小生成树

### 6、KrusKal最小生成树

## 七、查找

### 1、折半查找

### 2、二叉排序树

### 3、散列表

## 八、排序

### 1、冒泡排序
### 2、选择排序

```java

    public int[] selectSort(int[] table1) {
        int[] table = table1.clone();
        int min;
        for (int i = 0; i < table.length; i++) {
            min = i;
            for (int j = i + 1; j < table.length; j++) {
                if (table[min] > table[j]) {
                    min = j;
                }
            }
            if (i != min) {
                swap(table, i, min);
            }
        }
        return table;
    }
```



### 3、插入排序
### 4、希尔排序
### 5、堆排序

https://www.cnblogs.com/chengxiao/p/6129630.html

```java
    public int[] heapSort(int[] table1) {
        int[] table = table1.clone();
        // 构建最大顶栈  非叶节点进行 循环
        // 首尾互换 再次构建大顶栈  将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
        for (int i = table.length / 2 - 1; i >= 0; i--) {
            heapAdjust(table, i, table.length);
        }
        for (int j = table.length - 1; j > 0; j--) {
            swap(table, 0, j);
            heapAdjust(table, 0, j - 1);  //第j已经换到底部 0到j-1
        }
        return table;
    }
 public static void heapAdjust(int[] table, int begin, int end) {
        // begin 到 end 的循环
        //先比较 左孩子 和 右孩子 的大小
        int temp = table[begin];
        for (int i = begin * 2 + 1; i < end; i = i * 2 + 1) {
            if (table[i] < table[i + 1] && begin < end) { //找出左右中最大的
                i++;
            }
            if (temp >= table[i]) {  //双亲大于 左和右中最大的 则不需要 交换位置
                break; // 跳出循环    无需交换 函数结束
            }
            //交换位置    双亲交换左右中最大值的位置
            table[begin] = table[i];  //begin 改变
            begin = i;  //赋予新的 左子树 或者新的右子树  交换后 子树也混乱所以得继续循环交换
        }
        table[begin] = temp;
    }
```



### 6、归并排序





### 7、快速排序

```java
    public int[] quickSort(int[] table1) {
        int [] table = table1.clone();
        qsort(table,0,table.length-1);
        return table;
    }

    //   https://blog.csdn.net/shujuelin/article/details/82423852
    public static void qsort(int[] table, int begin, int end) {
        if (begin < end) {
            int i = begin; //从左到右边的指针
            int j = end; //从右到左的指针
            int vot = table[i]; //第一个值作为基准值
            while (i != j) {  //两个指针相遇结束
                while (i < j && vot <= table[j]) {
                    j--; //从后往前寻找小于vot的值
                }
                while (i < j && vot >= table[i]) {
                    i++; //从前往后寻找大于vot的值
                }
                if(i < j){
                    swap(table,i,j);  //交换 i j的值
                }
            }
            //最后将基准为与i和j相等位置的数字交换
            table[begin] = table[i];
            table[i] = vot;
            //递归调用左边数组
            qsort(table,begin,j-1);
            //递归调用右边数组
            qsort(table,j+1,end);

        }
    }
```