数据结构相关知识

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 数据结构相关知识

点击上方”python宝典”,关注获取python全套视频,

技术文章第一时间送达!

一、什么是数据结构?

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。

“程序=数据结构+算法”

二、数据结构的分类

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

  • 线性结构:数据结构中的元素存在一对一的相互关系
  • 树结构:数据结构中的元素存在一对多的相互关系
  • 图结构:数据结构中的元素存在多对多的相互关系
  • 下面就来说说线性结构

    三、线性结构

    (1)栈

    1、定义:栈是一个数据集合,可以理解为只能在一端进行插入或者删除操作的列表。

    2、栈的特点:后进先出(last-in,first-out),简称LTFO表

    3、栈的概念:

  • 栈顶:允许插入和删除的这一端称之为栈顶
  • 栈底:另一固定的一端称为栈底
  • 空栈:不含任何元素的栈称为空栈
  • 4、栈的基本操作:

  • 进栈(压栈):push
  • 出栈:pop
  • 取栈顶:gettop
  • 如图:

    数据结构相关知识数据结构相关知识

    5、栈的Python实现

    不需要自己定义,使用列表结构即可。

  • 进栈函数:append
  • 出栈函数:pop
  • 查看栈顶元素:li[-1]
  • 
    li = []
    li.append(1)
    li.append(2)
    li.append(3)
    print(li)
    print(li.pop())
    print(li.pop())
    print(li.pop())
    # print(li.pop())  #当栈空的时候就会报错
    # print(li[-1]) #查看栈顶元素
    

    6、栈的应用—-括号匹配问题

    问题:给一个字符串,其中包含小括号,中括号,大括号,求该字符串中的括号是否匹配

    例如:

    
    ()()[]{}        匹配
    ([{()}])        匹配
    [](        不匹配
    [(])        不匹配
    

    代码如下:

    
    # 方式一
    def brace_match(s):
        '''括号匹配问题'''
        stack = []
        # {()}[]
        match = {')': '(', '}': '{', ']': '['}
        match2 = {'(': ')', "{": "}", "[": "]"}
        for ch in s:
            # print(i)
            if ch in {'(', '{', '['}:  # 如果左括号在里面就把左括号添加进去,等待和右括号匹配
                stack.append(ch)
            elif len(stack) == 0:  # 如果再次进来括号的时候,这时候发现栈空了,说明缺少了左括号了
                print('缺少了%s' % match[ch])
                return False
            elif stack[-1] == match[ch]:  # 比如栈顶元素是(,ch=')'
                stack.pop()
            else:
                print('括号不匹配')
                return False
    
        if len(stack)  0:  # 如果栈剩余了,说明缺少了右括号
            print('缺少了%s' % match2[stack[-1]])
            return False
        return '匹配成功'
    
    # 方式二
    def check_kuohao(s):
        stack = []
        for char in s:
            if char in {'(', '[', '{'}:
                stack.append(char)
            elif char == ')':
                if len(stack)  0 and stack[-1] == '(':
                    stack.pop()
                else:
                    return False
            elif char == ']':
                if len(stack)  0 and stack[-1] == '[':
                    stack.pop()
                else:
                    return False
            elif char == '}':
                if len(stack)  0 and stack[-1] == '{':
                    stack.pop()
            else:
                return False
        if len(stack) == 0:
            return True
        else:
            return False
    
    ret = brace_match('{()}]')
    print(ret)
    
    print(check_kuohao('{()}]'))
    

    (2)队列

    1、介绍

  • 队列是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除,
  • 进行插入的一端称为队尾(rear),插入动作称之为进队或入队
  • 进行删除的一端称之为对头(front),删除动作称为出队
  • 双向队列:对列的两端都允许进行进队和出队操作

    数据结构相关知识

    2、队列的实现

    队列能否简单用列表实现?为什么?

  • 初步设想:列表+两个下标指针
  • 创建一个列表和两个变量,front变量指向队首,rear变量指向队尾。初始时,front和rear都为0。
  • 进队操作:元素写到li[rear]的位置,rear自增1。
  • 出队操作:返回li[front]的元素,front自减1。
  • 数据结构相关知识

    3、队列的实现原理—–环形对列

    数据结构相关知识 数据结构相关知识

    环形队列:当队尾指针front == Maxsize + 1时,再前进一个位置就自动到0。

  • 实现方式:求余数运算
  • 队首指针前进1:front = (front + 1) % MaxSize
  • 队尾指针前进1:rear = (rear + 1) % MaxSize
  • 队空条件:rear == front
  • 队满条件:(rear + 1) % MaxSize == front
  • 4、对列的内置模块

    使用方法:from collections import deque   #deque是支持双向队列的

  • 创建队列:queue = deque(li)
  • 进队:append
  • 出队:popleft
  • 双向队列队首进队:appendleft
  • 双向队列队尾进队:pop
  • 
    from collections import deque
    queue = deque()#创建队列
    queue.append('first')
    queue.append('second')
    queue.append('third')
    print(queue.popleft())
    print(queue.popleft())
    print(queue.popleft())#出队,,先进先出
    print([i for i in queue])  #查看队列里的元素
    
    queue.appendleft('one')#双向队列队首进队
    queue.appendleft('two')#双向队列队首进队
    queue.appendleft('five')#双向队列队首进队
    print(queue.pop())
    print(queue.pop())#双向队列从队尾出队
    print([i for i in queue])
    
    #单向队列
    from queue import Queue
    q = Queue()
    q.put('a')
    q.put('b')
    q.put('c')
    print(q.get())  #a
    

    (3)单链表

    链表中每一个元素都是一个对象,每一个对象都是一个节点,包含有数据域key和指向下一个节点的指针next。通过各个节点之间的互相连接,最终串联成一个列表

    数据结构相关知识

    1、节点定义:

    
    class Node(object):
        def __init__(self, item):
             self.item = item
             self.next = None
    

    2、建立链表

    头插法

    数据结构相关知识

    尾插法

    数据结构相关知识

    3、链表的遍历

    数据结构相关知识

    4、链表节点的插入和删除

    
    # 插入:
    p.next = curNode.next
    curNode.next = p
    
    #删除:
    p = curNode.next
    curNode.next = p.next  #当前节点的下一个指向就指向他下一个的下一个
    del p
    

    插入:

    数据结构相关知识 数据结构相关知识

    删除:

    数据结构相关知识 数据结构相关知识 数据结构相关知识

    ** (4)双链表**

    双链表中的每个节点有两个指针:一个指向后面节点、一个指向前面节点

    1、节点定义:

    
    class Node(object):
        def __init__(self,item):
            self.item = item  #数据
            self.next = None  #下一个指向 
            self.prior = None #上一个指向
    
    数据结构相关知识

    2、双链表节点的插入和删除

    
    #插入
    p.next = curNode.next
    curNode.next.prior = p 
    p.prior = curNode
    curNode.next = p
    
    #删除
    p = curNode.next
    curNode.next = p.next
    p.next.prior = curNode
    del p
    
    数据结构相关知识 数据结构相关知识 数据结构相关知识 数据结构相关知识 数据结构相关知识

    (5)哈希表

    哈希表(又称为散列表),是一种线性表的存储结构。哈希表由一个顺序表(数组)和一个哈希函数组成。哈希函数h(k)将k作为自变量,返回元素的存储下标。

    1、简单哈希函数

  • 除法哈希:h(k) = k mod m  #mod就是%      #除留余数法
  • 乘法哈希:h(k) = floor(m(kA mod 1))   0A1  #floor是向下取整
  • 假设有一个长度为7的数组,哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图。

    数据结构相关知识 数据结构相关知识

    2、哈希冲突

    由于哈希表的大小是有限的,而要存储的值的总数量是无限的,因此对于任何哈希函数,都会出现两个不同元素映射到同一个位置上的情况 ,

    这种情况叫做哈希冲突。

    比如h(k)=k%7, h(0)=h(7)=h(14)=…

    3、解决哈希冲突的办法

  • a、开放寻址法
  • b、拉链发
  • 开放寻址法:如果哈希函数返回的位置已经有值,则可以向后探查新的位置来存储这个值。

  • 线性探查:如果位置i被占用,则探查i+1, i+2,……
  • 二次探查:如果位置i被占用,则探查i+12,i-12,i+22,i-22,……
  • 二度哈希:有n个哈希函数,当使用第1个哈希函数h1发生冲突时,则尝试使用h2,h3,……
  •  拉链法:哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后。

    数据结构相关知识

    4、哈希表在Python中的应用

    a、字典与集合都是通过哈希表来实现的

    b、 在Python中的字典:a = {‘name’: ‘Alex’, ‘age’: 18, ‘gender’: ‘Man’},使用哈希表存储字典,通过哈希函数将字典的键映射为下标。

    假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4,则哈希表存储为[None, 18, None, ’Alex’, ‘Man’]

    c、在字典键值对数量不多的情况下,几乎不会发生哈希冲突,此时查找一个元素的时间复杂度为O(1)。

    数据结构相关知识

    识别图中二维码,欢迎关注python宝典

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 数据结构相关知识


     上一篇
    算法基础 算法基础
    点击上方”python宝典”,关注获取python全套视频, 技术文章第一时间送达! 一、什么是算法?算法(Algorithm):一个计算过程,解决问题的方法 一个算法应该具有以下七个重要的特征: ①有穷性(Finitene
    2021-04-05
    下一篇 
    树和二叉树简介 树和二叉树简介
    点击上方”python宝典”,关注获取python全套视频, 技术文章第一时间送达! 一、树1、什么是树? 树状图是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它
    2021-04-05