数据结构与算法- 第 2 章 常用数据结构

第 2 章 常用数据结构

抽象数据类型（Abstract Data Type，简称 ADT）是计算机科学中一个重要的概念，它是对数据的一种抽象描述，关注数据的逻辑特性和操作，而不涉及具体的实现细节。

抽象数据类型通常由以下两部分组成：

• 数据对象：描述了该数据类型所包含的数据元素以及它们之间的逻辑关系。例如，在一个栈的抽象数据类型中，数据对象是一系列按后进先出（LIFO）原则组织的元素。

• 操作集合：定义了对数据对象可以执行的操作。对于栈来说，常见的操作包括入栈（push）、出栈（pop）、查看栈顶元素（peek）等。

抽象数据类型与数据结构的关系

• 抽象数据类型：强调的是数据的逻辑特性和操作的功能，是一种抽象的概念，不涉及具体的实现细节。它是从用户的角度来描述数据和操作的。

• 数据结构：是抽象数据类型的具体实现，它关注的是数据在计算机内存中的存储方式和操作的具体实现算法。例如，栈这种抽象数据类型可以用数组或链表等数据结构来实现。

2.1 数组

2.1.1 数组的概述

数组是一种线性数据结构，将相同类型的元素顺序地存储在连续的内存空间中，每个元素都有一个索引。

由于数组元素在内存中是连续存储的，所以只要知道数组的起始位置，以及数组元素的类型（单个元素的长度），就可以根据索引计算出任意元素的位置。

数组在创建时需要指定长度，并且数组一旦创建，长度就无法改变，如果需要扩容，只能创建一个更大的数组，再将原数据拷贝到新数组。并且由于数组的连续性，插入和删除数据可能需要移动其他元素。

在 Python 中，并没有像其他一些编程语言（如 C、Java）那样严格意义上的 “数组” 概念，但有多种数据结构可以用来模拟数组的功能，最常用的是列表（list），另外还有 array 模块的数组和 numpy 库的 ndarray。

通过Python 的list列表实现一个动态数组，它内部存储的实际上是对象的引用（指针），而不是对象本身。每个引用指向内存中存储实际对象的位置。

什么是数组

但是 python中没有数组，如果想使用数组，可以使用array.array()或者numpy模块的ndarray,而array.array是支持动态扩容的

下面是一个例子：

import array

list1 = [1,2,3,"hello"]
print(list1)

# 需要是相同数据类型
arr = array.array("i",[1,2,3])
print(arr)

num = 1
print(id(num)) # 140719834157992
print(id(arr[0])) # 140719834157992

这个是list的创建逻辑：

array.array使用数组逻辑：

会发现 和list有区别：

• array.array中因为要求相同数据类型，不能指向 hello的地址

• array.array创建的对象中存储的不是地址，而是具体的值/二进制数

• print(id(num)) 和 print(arr[0])的地址相同

因为如果指定的是 i 的话，如下图,如果存储值只需要2个字节空间大小就可以，但如果是存储地址就需要8个空间，改为存储值 更节省空间。

而在获取地址的时候，它不会直接把值给你，而是需要进行 创建对象，而在创建对象的时候它发现 小整数池中已经存在，因此就不进行创建了，而是直接拿过来使用，所以两个打印的结果一样

2.1.2 顺序表

我们根据数组的概述得知： Python语言中的list、array都是动态，不需要关注扩容的过程，而在一些其他编程语言中，比如C、java中的数组是需要手动扩容的， 它们的底层都是顺序表 ，只不过是不同的存储方式

顺序表包含：

• 一体式存储（如C、java中的数组，Python中的元组）

• 分离式存储 （如Python中的list、array.array，java的ArrayList)

一体式存储：

创建的对象中信息包含：类型、个数、容量、具体元素。 当扩容的时候，会创建新的对象，并指向它的地址

分离式存储：

分离式存储会发现仍旧创建了对象，但list中存储的是数据的地址，当需要扩容的时候，也进行了新的数据对象的创建，但list内部只是更改了存储数据 的地址，list本身并没有扩容

2.1.3 数组的功能定义

2.1.4 数组的创建

实现一个动态数组。

class Array:
def __init__(self):
*"""初始化数组"""*
* *# 数组的初始化容量
self.__capacity = 7
# 数组中元素的个数
self.__size = 0
# 真正存储数据的对象， 创建了一个全是0的数组
self.__items = [0] * 7

def __str__(self):
*"""打印数组"""*
* *arr_str = "["
for i in range(self.__size):
arr_str += str(self.__items[i])
if i < self.__size – 1:
arr_str += ", "
arr_str += "]"
return arr_str

# 方法转为属性
@property
def size(self):
*"""获取数组元素个数"""*
* *return self.__size

def is_empty(self):
*"""判断数组是否为空"""*
* *return self.__size == 0

2.1.5 数组扩容

当数组容量占满后，我们可以创建一个新的数组，容量为之前数组的2倍，并将之前数组的元素拷贝到新数组中。

def __grow(self):
*"""数组扩容"""*
* *# 创建新的数据 容量是原来的2倍
self.__capacity *= 8
new___items = [0] * self.__capacity

# 将老数组数据 复制到新的数组中
for i in range(self.__size):
new___items[i] = self.__items[i]

# 将数组存储数据的对象地址 指向新的数组
self.__items = new___items

2.1.6 添加/插入元素

在中间插入元素时，将指定位置及其之后的元素全部向后移动一个位置，并将指定位置改为新的元素。

如果直接从前边向后移动,索引会混乱,因此**从后边向前边遍历, **以上述 数组创建为例,那么应该从索引5的位置遍历,到索引3

#添加元素
def insert(self,index,item):
if index < 0 or index > self.__size:
raise IndexError("index out of range")

# 判断是否需要扩容
if self.__size == self.__capacity:
self.__grow()

for i in range(self.__size,index,-1):
self.__items[i] = self.__items[i-1]

self.__items[index] = item

self.__size += 1

# 向数组中追加元素
def append(self,item):
self.insert(self.__size,item)

2.1.7 删除元素

删除数组中指定位置的元素时，将该位置之后的所有元素向前移动一个位置。

把索引为3的值赋值到索引为2的位置,索引为4的位置赋值到索引为3的位置,

# 向数组中追加元素
def append(self,item):
self.insert(self.__size,item)

# 从数组指定的位置删除元素
def remove(self,index):
if index < 0 or index >= self.__size:
raise IndexError("index out of range")

for i in range(index, self.__size-1):
self.__items[i] = self.__items[i+1]

self.__size -= 1

for i in range(index, self.__size):这样写也不会报错,但上相比于上面代码,多执行了一步

因为不管是size还是size-1如何处理,最后一个索引会被删掉

2.1.8修改元素

# 修改元素
def set(self,index,item):
if index < 0 or index >= self.__size:
raise IndexError("index out of range")

self.__items[index] = item

2.1.9访问元素

def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
return self.__items[index]

2.1.10查询元素

def find(self, item):
"""查找元素"""
for i in range(self.__size):
if self.__items[i] == item:
return i
return -1

2.1.11遍历元素

def for_each(self, func):
"""遍历数组"""
for i in range(self.__size):
func(self.__items[i])

2.1.12 完整代码

class Array:
def __init__(self):
"""初始化数组"""
self.__capacity = 8
self.__size = 0
self.__items = [0] * 8

def __str__(self):
"""打印数组"""
arr_str = "["
for i in range(self.__size):
arr_str += str(self.__items[i])
if i < self.__size – 1:
arr_str += ", "
arr_str += "]"
return arr_str

@property
def size(self):
"""获取数组元素个数"""
return self.__size

def is_empty(self):
"""判断数组是否为空"""
return self.__size == 0

def __grow(self):
"""数组扩容"""
self.new___items = [0] * self.__capacity * 2
for i in range(self.__size):
self.new___items[i] = self.__items[i]
self.__items = self.new___items
self.__capacity *= 2

def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if self.__size == self.__capacity:
self.__grow()
for i in range(self.__size, index, -1):
self.__items[i] = self.__items[i – 1]
self.__items[index] = item
self.__size += 1

def append(self, item):
"""末尾插入元素"""
self.insert(self.__size, item)

def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
for i in range(index, self.__size – 1):
self.__items[i] = self.__items[i + 1]
self.__size -= 1

def set(self, index, item):
"""修改元素"""
if index < 0 or index >= self.__size:
raise IndexError
self.__items[index] = item

def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
return self.__items[index]

def find(self, item):
"""查找元素"""
for i in range(self.__size):
if self.__items[i] == item:
return i
return -1

def for_each(self, func):
"""遍历数组"""
for i in range(self.__size):
func(self.__items[i])

2.2 链表

2.2.1 链表的概述

链表（Linked List）是一个线性结构，由一系列**节点（Node）**组成，每个节点包含一个数据元素和一个指向下一节点的指针（Pointer）。所有节点通过指针相连，形成一个链式结构。通常我们将链表中的第一个节点称为头结点，并将头结点的位置作为整个链表的位置标识。与数组不同，链表中每个节点分散的存储在内存中，每个节点都保存了当前节点的数据和下一节点的地址（指针）。

由于链表中节点通过指针相连，插入和删除节点只需要修改指针的指向即可，而不需要像数组那样移动数据。且链表不需要像数组那样预先指定大小，而是可以随时动态的增长或缩小。由于链表使用分散存储的方式，因而无需使用大段连续的内存空间。

由于链表中的节点不是连续存储的，无法像数组一样根据索引直接计算出每个节点的地址。必须从头节点开始遍历链表，直到找到目标节点，这导致了链表的随机访问效率较低。链表的每个节点都需要存储指向下一个节点的指针，这会占用额外的存储空间。相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。

常见的链表包括三种：

• 单向链表：单向链表的节点包含值和指向下一节点的引用。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。

• 环形链表：将单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

• 双向链表：双向链表记录了两个方向的引用，同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用。

单向链表:

双向链表:

环形链表

2.2.2 链表的功能定义

2.2.3 链表的创建

实现一个单向链表。

class Node:
*"""链表上的节点类"""*
* *def __init__(self, data,next=None):
self.data = data
self.next = next

class MyLinkedList:
def __init__(self):
# 链表上的元素个数
self.__size = 0
self.__head = None

@property
def size(self):
return self.__size

def is_empty(self):
return self.__size == 0

def __str__(self):
res_list = []

# 怎么取出链表上的元素
node = self.__head
while node:
res_list.append(str(node.data))
node = node.next

return "->".join(res_list)

2.2.4 添加/插入元素

def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if index == 0:
# 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
self.__head = Node(item, self.__head)
else:
# 插入到中间，先找到index-1位置的节点
node = self.__head
for i in range(**index – 1**):
node = node.next
# 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
#(新节点指向后一个节点）
node.next = Node(item, node.next)
self.__size += 1

链表中没有索引可以理解为索引，链表中想拿到元素只能从头开始做循环。如果插入到头部，重新指向一下新的头部节点，如果插入到中间，按索引算 比如在1和2中间插入（新索引2的位置），就是在索引为1的后边插入，就需要先找到1（index-1）的位置，从而拿到1的数据，而拿到1的数据只需要获取1前边的索引位置的信息.next就可以拿到了，就是索引为0的位置，相当于实际拿到的是index-2的位置，但因为range左开右闭，因此实际写为index-1

在末尾插入元素时，使用insert()并将index设置为链表长度。

def append(self, item):
"""末尾插入元素"""
self.insert(self.__size, item)

2.2.5 删除元素

def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
if index == 0:
# 下一个节点改为头节点
self.__head = self.__head.next
else:
# 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
node = self.__head
for i in range(index – 1):
node = node.next
node.next = node.next.next
self.__size -= 1

2.2.6 修改元素

def set(self, index, item):
"""修改元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
#比如索引为3，node就是第二个索引位置，node.next就是第三个索引节点
node = node.next
node.data = item

2.2.7 访问元素

def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
return node.data

2.2.8 查找元素

def find(self, item):
"""查找元素"""
node = self.__head
while node:
if node.data == item:
return True
node = node.next
return False

获取元素第一次的索引

def find(self,item):
node = self.__head
for i in range(self.__size):
if node.data == item:
return i
node = node.next

return -1

2.2.9 遍历链表

def for_each(self, func):
"""遍历链表"""
node = self.__head
while node:
func(node)
node = node.next

2.2.10 完整代码

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

class LinkedList:
def __init__(self):
"""初始化链表"""
self.__head = None
self.__size = 0

def __str__(self):
"""打印链表"""
result = []
current = self.__head
while current:
result.append(str(current.data))
current = current.next
return " -> ".join(result)

@property
def size(self):
"""获取链表元素个数"""
return self.__size

def is_empty(self):
"""判断链表是否为空"""
return self.__size == 0

def insert(self, index, item):
"""插入元素"""
if index < 0 or index > self.__size:
raise IndexError
if index == 0:
# 插入到头部，需要新建一个节点，然后让新节点的next指向原来的head，然后让head指向新节点
self.__head = Node(item, self.__head)
else:
# 插入到中间，先找到index-1位置的节点
node = self.__head
for i in range(index – 1):
node = node.next
# 新节点的next指向index位置的节点，然后让index-1位置的节点的next指向新节点
node.next = Node(item, node.next)
self.__size += 1

def append(self, item):
"""末尾插入元素"""
self.insert(self.__size, item)

def remove(self, index):
"""删除元素"""
if index < 0 or index >= self.__size:
raise IndexError
if index == 0:
self.__head = self.__head.next
else:
# 找到index-1位置的节点，然后让index-1位置的节点的next指向index位置的节点的next
node = self.__head
for i in range(index – 1):
node = node.next
node.next = node.next.next
self.__size -= 1

def set(self, index, item):
"""修改元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
node.data = item

def get(self, index):
"""访问元素"""
if index < 0 or index >= self.__size:
raise IndexError
node = self.__head
for i in range(index):
node = node.next
return node.data

def find(self, item):
"""查找元素"""
node = self.__head
while node:
if node.data == item:
return True
node = node.next
return False

def for_each(self, func):
"""遍历链表"""
node = self.__head
while node:
func(node)
node = node.next