数据结构学习

一、前言

数据结构是支撑程序表示现实问题的基石，数据结构能让计算机表述许多现实中的问题。数据结构可以让现实问题变得简易。
常见得数据结构有线性数据结构、非线性数据结构。具体为：数组、链表、栈、队列、树、图、散列表、堆。

二、线性数据结构

数组

数组是指存储相同数据类型的数据结构，数组一般是计算机内存连续的存储单元分配的。数组具有这样的特征：一定的长度，具有下标（下标从零开始）
```
//java代码
//初始化一个长度为5的数组
int[] array = new int[5];
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 4;
array[4] = 5;
```

链表

链表相比较数组是一个更复杂的数据结构，链表的物理存储单元并不像数组那样是连续的存储单元。链表的存储单元在物理位置上可以是连续也可以是不连续的，链表每一个节点至少有两个部分，一部分是存储数值的存储单元，另一部分是存储下一个节点地址的存储单元。
（1）链表的定义

//java代码块
//使用Java实现链表的节点
class ListNode{
int val;
ListNode next;
ListNode(int x){
this.val = x
}
}

#python代码块
class ListNote:
def __init__(self,val:int,next:ListNote):
self.val = val
self.next = next

（2）链表的创建
通过定义链表的节点，我们只需要把链表各个节点的存储下一个节点即可

#使用python创建一个链表
class ListNote:
def __init__(self,val):
self.val = val
self.next = None
class LinkList:
def linkcreate(self,n:int):
#创建一个头节点
head = ListNote(0)
temp = head
for i in range(n):
new=ListNote(i)
temp.next = new
temp = new
return head

（3）链表的遍历
链表的遍历通过设置一个指针向下传递直到结束就可以进行遍历整个链表。

def search(self,head):
h = head.next
while h:
print(h.val)
h = h.next

(4)在链表中插入节点
链表的插入,链表插入首先找到要插入的位置，然后将新的节点指针存储后继节点，断开原来的后继节点，在连接新的后继节点。

def linkinsert(self,head:ListNote,val:int)->ListNote:
#创建要插入的一个节点
t = input("请输入插入节点的值:")
va = int(t)
new = ListNote(va)
#寻找插入的位置
h = head.next
while h:
if h.val==val:
new.next = h.next
h.next = new
return head
else:
h = h.next
return None

（5）链表的删除
找到插入节点，将其后继节点设定为后继节点的后继

def delete(self,head:ListNote,val:int)->ListNote:
temp = head
h = head.next
while h:
if h.val == val:
temp.next = h.next
return head
else:
temp = temp.next
h = h.next
return head

栈是一种线性的数据结构，它有一些特殊性，栈中的元素符合后进先出的特性，即先进后出。可以把栈理解为储物的长筒，当放进去两个物体，拿出来的时候必须要先拿出来最后一个放进去的物体才能在拿之前放进去的物体。

栈在各个语言的使用
栈在C语言中没有相应的包，需要自己定义，C语言上定义栈需要用到C语言上的指针和结构体等知识。
在java中有相应的类，java中的栈是一个Vector的一个子类，当想在java中使用栈的时候实现调用该类的子类就行。
```
//java中使用栈
import java.util.*;
public class StackDemo{
 //实现栈的添加元素并输出的类
 static void showpush(Stack<Integer> st,int a){
     st.push(new Integer(a));
 }
 static void showpop(Stack<Integer> st){
     System.out.print("pop->");
     Integer a = (Integer)st.pop();
     System.out.println(a);
 }
 public static void main(String args[]){
     //定义一个栈
     Stack<Integer> st = new Stack<Integer>();
     System.out.println("stack:"+st);
     showpush(st,42);
     showpush(st.99);
     showpop(st);
     showpop(st);
     try{
         showpop(st);
     }catch(EmptyStackException e){
         System.out.println("empty stack!");
     }

 }
}
```
在python中使用栈更加的方便，python有很多的方法可以去模拟栈结构。可以直接使用list去模拟栈，当然也有更方便的包，比如Queue模块有很多方法模拟栈的功能特性。想要了解点击看看

栈的应用

4.队列

(1)简述：队列(FIFO)是一个线性的数据结构，它的特点是先进先出，也就是先进去先处理，后进去后处理

（2）队列的实现，虽然很多的语言都已经实现了自己的队列数据结构，为了实现加深对队列的理解，动手实现一个循环队列。

//java版本
class MyCircularQueue {

    private int[] data;
    private int head;
    private int tail;
    private int size;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return head == -1;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}

使用python实现

class NodePoint:
    def __init__(self, val: int, pre, last):
        self.val = val
        self.pre = pre
        self.last = last


class MyCircularQueue:

    def __init__(self, k: int):
        if k == 0:
            return False
        self.list_point = []
        for i in range(k):
            self.list_point.append(NodePoint(0, None, None))
        for i in range(len(self.list_point)):
            if i < len(self.list_point) - 1:
                self.list_point[i].last = self.list_point[i + 1]
            elif i == len(self.list_point) - 1:
                self.list_point[i].last = self.list_point[0]
            if i == 0:
                self.list_point[i].pre = self.list_point[len(self.list_point) - 1]
            else:
                self.list_point[i].pre = self.list_point[i - 1]
        self.headnumber = 0
        self.head = self.list_point[0]
        self.tail = self.list_point[0]

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty():
            self.head.val = value
            self.headnumber += 1
        else:
            self.tail = self.tail.last
            self.tail.val = value
            self.headnumber += 1
        return True

    def deQueue(self) -> bool:

        if self.isEmpty():
            return False
        elif self.headnumber == 1:

            self.headnumber = 0
        else:
            self.head = self.head.last
            self.headnumber -= 1
        return True

    def Front(self) -> int:
        if self.headnumber == 0:
            return -1
        return self.head.val

    def Rear(self) -> int:
        if self.headnumber == 0:
            return -1
        return self.tail.val

    def isEmpty(self) -> bool:
        if self.headnumber == 0:
            return True
        else:
            return False

    def isFull(self) -> bool:

        if self.headnumber == len(self.list_point):
            return True
        else:
            return False

三、非线性数据结构

1.字典树

字典树是方便存储字符串的数据结构，它类似与树结构，字典树又称为单词查找树，tire树。是一种哈希树的变种，典型的应用是用于统计，排序和保存大量的字符串（但也不限于字符串可以是文本等）所以常被应用于文本词频统计。他的优点是：利用字符串的公共前缀来减少查询时间，节省存储空间。
(1)字典树的存储原理
将多个字符串进行存储保存（例如:"abc","bc","abcd","abef","cd"）
存储的时候将字符串进行拆分，存储第一个字符串的时候按照树结构依次存储，并在最后一个字符末尾标记。

当添加字符串利用tire中已有的字符节点来节省存储空间，例如下一个存储字符串为"abcd"。

将所有的字符串进行存储之后就类似于该图。

(2)字典树的实现
设置节点，每个节点都是一个node类节点，该类的属性有判断该点是否为字符串的变量judge,存储该节点的子节点的列表child,存储该节点的值变量s。

class TreeNode:
    def __init__(self, s=''):
        self.s = s
        self.judge = False
        self.child = []

创建Tire树类，该类有三个方法，第一个方法是初始化方法，该方法在Tire创建的时候执行，执行之后为Tire创建一个根节点。

    def __init__(self):
        """
        Initialize your data structure here.
        """
        #初始化成一个根节点
        self.root = TreeNode()

实现添加字符串方法insert方法，此方法是将字符串添加在Tire树并标记最后字符为True表示这是一个字符串。

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        wordlist = list(word)
        #判断节点是否有节点节点
        #如果根节点没有该节点进行创建
        tempnode = self.root
        count = 0
        for i in wordlist:
            templist = []
            for j in tempnode.child:
                templist.append(j.s)
            if i not in templist:
                count += 1
                node = TreeNode(i)
                tempnode.child.append(node)
                tempnode = node
            else:
                count += 1
                tempnode = tempnode.child[templist.index(i)]
        #当到达最后一个节点之后
        tempnode.judge = True

实现查找方法，判断字符串是否存在Tire树中

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tempnode = self.root
        wordlist = list(word)
        count = 0
        for i in wordlist:
            templist = []
            for j in tempnode.child:
                templist.append(j.s)
            if i not in templist:
                return False
            else:
                count += 1
                tempnode = tempnode.child[templist.index(i)]

        if len(wordlist) == count and tempnode.judge:
            return True
        else:
            return False

实现搜寻方法，此方法是查找，Tire树中是否有字串是要搜寻字符串。

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tempnode = self.root
        wordlist = list(prefix)
        count = 0
        for i in wordlist:
            templist = []
            for j in tempnode.child:
                templist.append(j.s)
            if i not in templist:
                return False
            else:
                count += 1
                te = tempnode
                tempnode = tempnode.child[templist.index(i)]
        if len(wordlist) == count:
            return True