Python实现数据结构

àì夳堔傛蜴生んèń 2023-08-17 15:15 71阅读 0赞

### 1.栈 ###

#### 特性：先进后出的数据结构 ####

#### 栈顶，栈尾 ####

*  Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
 *  push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
 *  pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
 *  peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
 *  isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
 *  size() 返回栈中的 item 数量。不需要参数，并返回一个整数。
    
        1 class Stack():
         2     def __init__(self):
         3         self.items = []
         4     def push(self,item):
         5         self.items.append(item)
         6     def pop(self):
         7         if self.isEmpty():
         8             return None
         9         else:
        10             return self.items.pop()
        11     def isEmpty(self):
        12         #空=》True
        13         return self.items == []
        14     def peek(self):
        15         return self.items[len(self.items) - 1]
        16     def size(self):
        17         return len(self.items)

### 2.队列 ###

#### 特性：先进先出 ####

*  Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
 *  enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
 *  dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
 *  isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。

size() 返回队列中的项数。它不需要参数，并返回一个整数。

1 class Queue():
     2     def __init__(self):
     3         self.items = []
     4     def enqueue(self,item):
     5         self.items.insert(0,item)
     6     def isEmpty(self):
     7         return self.items == []
     8     def dequeue(self):
     9         if self.isEmpty():
    10             return None
    11         else:
    12             return self.items.pop()
    13     def size(self):
    14         return len(self.items)
    15     def travel(self):
    16         print(self.items)

### 3.顺序表 ###

*  集合中存储的元素是有顺序的，顺序表的结构可以分为两种形式：单数据类型和多数据类型。
 *  python中的列表和元组就属于多数据类型的顺序表
 *  单数据类型顺序表的内存图（内存连续开启）
    
     *  对应的内存空间是连续开辟的
     *  顺序表的变量/引用存的的（指向的）是内存空间的首地址

*  多数据类型顺序表的内存图（内存非连续开辟）

#### 重点： ####

\- 想把数据存储到内存中，必须先在内存中开辟指定大小的内存空间（大小，地址：定位）  
\- 如果一个引用指向了某一块内存空间，则表示该引用存储了该内存空间的地址

\- 顺序表的弊端：顺序表的结构需要预先知道数据大小来申请连续的存储空间，而在进行扩充时 又需要进行数据的搬迁。

### 4.链表 ###

#### 特性： ####

#### 相对于顺序表，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。[   ][Link 1] ####

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个结点（数据存储单元）里存放下一个结点的信息（即地址）

*  is\_empty()：链表是否为空
 *  length()：链表长度
 *  travel()：遍历整个链表
 *  add(item)：链表头部添加元素
 *  append(item)：链表尾部添加元素
 *  insert(pos, item)：指定位置添加元素
 *  remove(item)：删除节点

search(item)：查找节点是否存在

1 #封装节点数据结构
     2 class Node():
     3     def __init__(self,item):
     4         self.item = item
     5         self.next = None
     6     def __str__(self):
     7         return self.item
     8 #封装链表数据结构
     9 class Link():
    10     #初始化一个空链表
    11     def __init__(self):
    12         #该属性永远指向第一个节点
    13         self._head = None
    14     def isEmpty(self):
    15         return self._head == None
    16     def add(self,item):
    17         #创建一个新的节点对象
    18         node = Node(item)
    19         #将节点插入到链表的头部
    20         node.next = self._head
    21         self._head = node
    22     def travel(self):
    23         cur = self._head
    24         while cur:
    25             print(cur.item)
    26             cur = cur.next
    27     def length(self):
    28         count = 0
    29         cur = self._head
    30         while cur:
    31             count += 1
    32             cur = cur.next
    33         return count
    34     def append(self,item):
    35         cur = self._head
    36         pre = None #cur前面节点的地址
    37         
    38         node = Node(item)
    39         #如果链表为空则新节点作为链表中的第一个节点
    40         if self._head is None:
    41             self._head = node
    42             return
    43         #链表非空对应的插入情况    
    44         while cur:
    45             pre = cur
    46             cur = cur.next
    47         pre.next = node
    48       
    49     def insert(self,pos,item):
    50         cur = self._head
    51         pre = None
    52         node = Node(item)
    53         length = self.length()
    54         #对特殊情况的处理
    55         if pos > length:
    56             self.append(item)
    57             return
    58         if pos <= 0:
    59             self.add(item)
    60             return
    61         #正常处理
    62         for i in range(pos):
    63             pre = cur
    64             cur = cur.next
    65         pre.next = node
    66         node.next = cur
    67     def remove(self,item):
    68         cur = self._head
    69         pre = None
    70         #如果删除的是第一个节点
    71         if item == cur.item:
    72             self._head = cur.next
    73             return
    74         while cur:
    75             if cur.item == item:
    76                 pre.next = cur.next
    77                 return
    78             else:
    79                 pre = cur
    80                 cur = cur.next
    81         
    82         
    83     def search(self,item):
    84         find = False
    85         cur = self._head
    86         while cur:
    87             if cur.item == item:
    88                 find = True
    89                 break
    90             cur = cur.next
    91         return find

### 5.二叉树 ###

#### 构成：根节点，左叶子结点，右叶子结点，子树 ####

#### 广度遍历：层级 ####

#### 深度遍历：前序（跟左右），中序（左根右），后序（左右根） ####

1 class Node():
     2     def __init__(self,item):
     3         self.item = item
     4         self.left = None
     5         self.right = None
     6 class Tree():
     7     def __init__(self):
     8         self.root = None
     9     def add(self,item):
    10         node = Node(item)
    11         
    12         if self.root is None:
    13             self.root = node
    14             return       
    15         queue = [self.root]
    16         while queue:
    17             cur = queue.pop(0)
    18             if cur.left is None:
    19                 cur.left = node
    20                 return
    21             else:
    22                 queue.append(cur.left)
    23             if cur.right is None:
    24                 cur.right = node
    25                 return
    26             else:
    27                 queue.append(cur.right)
    28     def travel(self):
    29         if self.root is None:
    30             return
    31         queue = [self.root]
    32         
    33         while queue:
    34             cur = queue.pop(0)
    35             print(cur.item)
    36             if cur.left is not None:
    37                 queue.append(cur.left)
    38             if cur.right is not None:
    39                 queue.append(cur.right)
    40

### 排序二叉树 ###

1 class Node():
     2     def __init__(self,item):
     3         self.item = item
     4         self.left = None
     5         self.right = None
     6 class Tree():
     7     def __init__(self):
     8         self.root = None
     9         
    10     def insertByOder(self,item):
    11         
    12         node = Node(item)
    13         if self.root is None:
    14             self.root = node
    15             return
    16         
    17         cur = self.root
    18         while True:
    19             if item < cur.item:
    20                 if cur.left is None:
    21                     cur.left = node
    22                     return
    23                 else:
    24                     cur = cur.left
    25             else:
    26                 if cur.right is None:
    27                     cur.right = node
    28                     return
    29                 else:
    30                     cur = cur.right
    31             
    32     def forward(self,root):
    33         if root is None:
    34             return
    35         # 根 左 右
    36         print(root.item,end=' ')
    37         self.forward(root.left)
    38         self.forward(root.right)
    39     def mid(self,root):
    40         if root is None:
    41             return
    42         #左根右
    43         self.mid(root.left)
    44         print(root.item,end=' ')
    45         self.mid(root.right)
    46     def back(self,root):
    47         if root is None:
    48             return
    49         #左右根
    50         self.back(root.left)
    51         self.back(root.right)
    52         print(root.item,end=' ')
    53

### 6.个数据结构与其时间复杂度 ###

![1492569-20190714174244182-1164885193.png][]

转载于:https://www.cnblogs.com/ppf3678/p/11123015.html

[Link 1]: http://localhost:8888/notebooks/%E8%AF%BE%E4%BB%B6/5.%E9%A1%BA%E5%BA%8F%E8%A1%A8%E5%92%8C%E9%93%BE%E8%A1%A8.ipynb#%E9%93%BE%E8%A1%A8%EF%BC%9A%E7%9B%B8%E5%AF%B9%E4%BA%8E%E9%A1%BA%E5%BA%8F%E8%A1%A8%EF%BC%8C%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84%E5%8F%AF%E4%BB%A5%E5%85%85%E5%88%86%E5%88%A9%E7%94%A8%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%86%85%E5%AD%98%E7%A9%BA%E9%97%B4%EF%BC%8C%E5%AE%9E%E7%8E%B0%E7%81%B5%E6%B4%BB%E7%9A%84%E5%86%85%E5%AD%98%E5%8A%A8%E6%80%81%E7%AE%A1%E7%90%86%E4%B8%94%E8%BF%9B%E8%A1%8C%E6%89%A9%E5%85%85%E6%97%B6%E4%B8%8D%E9%9C%80%E8%A6%81%E8%BF%9B%E8%A1%8C%E6%95%B0%E6%8D%AE%E6%90%AC%E8%BF%81%E3%80%82
[1492569-20190714174244182-1164885193.png]: /images/20230810/a4b4f63ef8cb4ebb8ddaab0dc6926c04.png