数据结构

1.数据结构

数据结构:互相之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素之间关系的组成.

简单说:数据结构就是设计数据以何种方式组织并存储在计算机中.(列表,字典,集合,都是一种数据结构)

数据结构分类:

①线性结构:

数据结构中的元素存在一对一的相互关系

②树结构:

数据结构中的元素存在一对多的相互关系

③图结构:

数据结构中的元素存在多对多的相互关系

2.列表(python)

注意:32位机器一个整数占4个字节,一个内存地址也是占4个字节

python时间复杂度

pop:O(1)

append:O(1)

indert:O(n)插入一个得把其他的先挪走,再插入

remove:O(n) 删一个得把其他的挪过来

数组与列表的不同:

　　1.一个数组内的元素类型要相同,列表可以不同(数组搜索时时间复杂度是O(1),他要确保每个元素固定长度才能直接取),数组存的是具体的值,列表存的是地址

　　2.数组长度固定,列表长度不固定,python列表长度不够时,他会重新开辟一块内存,比原来的长一些,再把原来的内容复制过来

3.栈

代码:

#用列表实现栈的功能
class Stack:

    def __init__(self):
        self.stack = []

    def push(self, element): #进栈
        self.stack.append(element)

    def pop(self):#出栈
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return None

    def get_top(self):#取栈顶
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None

    def is_empty(self): #判断栈是不是空的
        return len(self.stack) == 0

stack=Stack()
print(stack.push(1))
print(stack.get_top())
print(stack.pop())
print(stack.pop())

栈的应用:

判断括号匹配问题:

给你一些括号(小括号,中括号,大括号),看看格式是不是对的

#栈的应用:
# 思路:遇到左括号就往栈里添加,遇到右括号就取出(但是左右括号要是一对才行)
# 这里只判断字符串里全是括号的情况,如有其他符号或者文字则不适用,需改代码
class Stack:

    def __init__(self):
        self.stack = []

    def push(self, element): #进栈
        self.stack.append(element)

    def pop(self):#出栈
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return None

    def get_top(self):#取栈顶
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None

    def is_empty(self): #判断栈是不是空的
        return len(self.stack) == 0

def brace_match(s):
    match = {'}':'{', ']':"[", ')':'('} #造字典用右括号直接取左括号
    stack = Stack()
    for ch in s:
        if ch in {'(','[','{'}:
            stack.push(ch)
        else:   #ch in {'}',']',')'},此时遇到了右括号
            if stack.is_empty(): #如果栈里为空,直接来个右括号,那就是不对了
                return False
            elif stack.get_top() == match[ch]:#如果当前栈顶存的括号与你遇到的括号匹配,那就把栈顶的括号取出,然后继续匹配下一个
                stack.pop()
            else: # stack.get_top() != match[ch]#如果当前栈顶的括号与你遇到的括号不匹配就报错
                return False
    if stack.is_empty():
        return True
    else:
        return False

print(brace_match('[{()}(){()}[]({}){}]'))
print(brace_match('[]}'))

栏目列表