一、 概念
1. 概念
存储和组织数据的方式
2. 作用
3. 内存存储结构
二、数据结构
1. 数据结构的分类
1. 线性结构
2. 非线性结构
2.线性表
1. 顺序表
- 定义：将元素顺序地存放在一块连续的存储区间里
-
一体式结构：信息区和数据区在一起
-
分离式结构：信息区和数据区分开
-
数据扩充策略
-
添加元素
- 删除元素
2. 链表
- 存储区非连续的,当前元素保存下一个元素的地址
- 包含两个部分：数据 下一个元素的指向
- 类： 数据data 指向next
-
类结构定义：
# 链表节点类 class LinkNode(): def __init__(self, val): self.val = val self.next = None # 链表类 class LinkList(): def __init__(self, head): self.head = head -
链表的基本操作
# 链表节点类 class LinkNode(): def __init__(self, val): self.val = val self.next = None # 链表类 class LinkList(): def __init__(self, head): self.head = head # 判断是否为空 def is_none(self): if self.head: return False else: return True # 获取长度 def get_len(self): cur = self.head length = 0 while cur: cur = cur.next length = length + 1 return length # 遍历 def travel(self): cur = self.head while cur: print(cur.val) cur = cur.next # 头部增加 def add(self, node): node.next = self.head self.head = node # 尾部增加 def append(self, node): cur = self.head if not cur: self.head = node while cur.next: cur = cur.next cur.next = node # 在指定节点添加 def insert(self, index, node): if self.get_len() <= 0: self.head = node return if index <= 0: self.add(node) elif index >= self.get_len(): self.append(node) else: cur = self.head i = 1 while i < index: cur = cur.next i = i + 1 node.next = cur.next cur.next = node # 删除节点 def delete(self, node): cur = self.head while cur: if cur.val == node.val: if node == self.head: self.head = self.head.next else: p.next = cur.next return p = cur cur = cur.next
4. 链表和顺序表的区别
5. 栈
-
栈的定义？（先进后出）
- 应用
- 寄存器
- 网站页面的前进、后退
-
栈的代码实现
# 顺序表实现 class Stack(): def __init__(self): self.l = [] def push(self, n): self.l.append(n) def pop(self): self.l.pop() def travel(self): for i in range(len(self.l)): print(i) # 链表实现 class Stack(): def __init__(self): self.head = None def push(self, node): node.next = self.head self.head = node def pop(self): if self.head: cur = self.head self.head = self.head.next return cur return None def travel(self): cur = self.head while cur: print(cur.val) cur = cur.next
6. 队列
-
概念： 先进先出
-
作用:保证任务顺序执行
-
代码实现
# 顺序表实现 class Queue(): def __init__(self): self.l = [] def enqueue(self, n): self.l.append(n) def dequeue(self): if len(self.l): return self.l.pop(0) return None def size(self): return len(self.l) def travel(self): for i in range(len(self.l)): print(self.l[i]) # 链表实现 class Node(): def __init__(self, val): self.val = val self.next = None class Queue(): def __init__(self): self.__head = None self.__tail = None def enqueue(self, node): if self.__tail: self.__tail.next = node else: self.__head = node self.__tail = node def dequeue(self): if self.__head: cur = self.__head self.__head = self.__head.next return cur return None def size(self): cur = self.__head i = 0 while cur: i = i + 1 cur = cur.next return i def travel(self): cur = self.__head while cur: print(cur.val) cur = cur.next
7. 双端队列
-
概念
-
代码实现
# 顺序表实现 # 链表实现
