数据结构——数组和链表（数组 结构体 链表）
off999 2024-10-01 13:48 33 浏览 0 评论
数组和链表
Created: Apr 04, 2020 2:49 PM
01 集合
数据结构是以不同方式将数据组织和分组在一起的容器。 当你编写代码来解决问题时，总会涉及到数据-以及如何在计算机内存中存储或构造数据会对你可以执行哪些操作以及执行这些操作的效率产生巨大影响。
在本节中，我们将首先回顾一些您可能至少已经部分熟悉的基本数据结构。然后，随着课程的进行，在解决不同类型的问题时，我们将考虑使用不同结构的利弊。我们将从讨论非常通用的结构（集合）开始。
集合的特性
- 没有特定的顺序
- 具有相同类型的对象
02 列表
列表特性
- 有顺序
- 没有固定的长度
03 数组
Python中数组和list的区别
数组和列表有一些共同点：
- 是一些单元的集合
- 他们是一个顺序的集合
主要区别之一是数组具有索引
要了解这一点，有助于了解如何将数组存储在内存中。 创建数组时，始终会为其指定一些初始大小，即它应该能够容纳的元素数量（以及每个元素的大小）。 然后，计算机会找到一块内存，并为阵列留出空间。
重要的是，预留的空间是一个连续的块。 也就是说，数组的所有元素都是连续的，这意味着它们在内存中都彼此相邻。
数组的另一个关键特性是所有元素的大小都相同。
当我们直观地表示一个数组时，我们通常将其绘制为一系列大小相同且彼此相邻的盒子：
因为所有元素彼此相邻且大小相同，所以这意味着如果我们知道第一个元素的位置，就可以计算任何其他元素的位置。
例如，如果数组中的第一个元素位于内存位置00且元素为24个字节，则下一个元素将位于位置00 + 24 =24。其后的一个元素将位于24 + 24 = 48， 等等。
由于我们可以轻松计算数组中任何项目的位置，因此我们可以为每个项目分配一个索引，并使用该索引快速而直接地访问该项目
相反，列表中的元素在内存中可能相邻，也可能不相邻！ 例如，在本课程的稍后部分，我们将查看链接列表，其中每个列表项都指向下一个列表项，但是这些项本身可能分散在内存的不同位置。 在这种情况下，知道列表中第一个项目的位置并不意味着您可以简单地计算其他项目的位置。 这意味着我们不能像使用数组那样使用索引直接访问列表项。 我们将在短期内更详细地探讨链接列表。
在python中我们可以使用[]创建一个列表
>>> my_list = ['a', 'b', 'c']
>>> my_list
['a', 'b', 'c']然后我们可以通过索引访问列表中的元素：
>>> my_list[0]
'a'
>>> my_list[1]
'b'
>>> my_list[2]
'c'我们将不会涉及所有细节，但是您需要在此课程中了解的重要事项如下：如果深入研究，您会发现Python列表实际上是像数组一样实现的（特别是，如果您感到好奇，它的行为就像一个动态数组）。特别是，Python列表的元素在内存中是连续的，可以使用索引对其进行访问。
除了基础数组之外，Python列表还包含一些其他行为。例如，您可以在Python列表上使用pop和append方法之类的东西来添加或删除项。使用这些方法，您实际上可以利用Python列表（例如堆栈）（这是我们稍后将讨论的另一种数据结构）
通常，我们将尽量避免使用pop和append之类的东西，因为这些是高级语言功能，您可能无法使用其他语言来使用。在大多数情况下，我们将忽略Python列表附带的额外功能，而是像使用简单数组一样使用它们。这将使您看到底层数据结构如何工作，而与实现这些结构所使用的语言无关。
这是底线：
- - Python list本质上是数组，但还包含其他高级功能
- - 在本课程中，我们通常将忽略此高级功能，并将Python列表视为简单数组
这种方法将使您对底层数据结构有更好的了解。
初始化列表
"""An Element has some value associated with it (which could be anything a€”
a number, a string, a character, et cetera), and it has a variable that
points to the next element in the linked list. """
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
"""This code is very similar a€” we're just establishing that a LinkedList is
something that has a head Element, which is the first element in the list.
If we establish a new LinkedList without a head, it will default to None."""
class LinkedList(object):
def __init__(self, head=None):
self.head = head添加节点
def append(self, value):
"""adds a new Element to the end of our LinkedList"""
cur = self.head
if self.head:
while (cur.next):
cur = cur.next
cur.next = Element(value)
else:
self.head = Element(value)弹出节点
def pop(self):
cur = self.head
if cur == None:
return None
if cur.next == None:
val = cur.value
self.head = None
#pdb.set_trace()
return val
while cur.next:
if (cur.next.next == None):
val = cur.next.value
cur.next = None
return val
cur = cur.next获取对应位置的节点
def get_position(self, position):
"""Get an Element from a particular position. Assume the first position is "1".
Return "None" if position is not in the list."""
if position > 0:
current = self.head
counter = 1
while current:
if counter == position:
return current
current = current.next
counter += 1
# position too large
return None
else:
# position too small
return None插入节点
def insert(self, value, position):
"""Insert a new node at the given position. Assume the first position is "1".
Inserting at position 3 means between the 2nd and 3rd elements."""
i = position - 1
cur = self.head
new_element = Element(value)
if position > 0:
if i == 0:
new_element.next = cur
self.head = new_element
else:
while(i == 2):
#pdb.set_trace()
cur = cur.next
i -= 1
new_element.next = cur.next
cur.next = new_element删除节点
def delete(self, value):
"""Delete the first node with a given value."""
cur = self.head
if cur.value == value:
self.head = cur.next
else:
while cur.next:
if cur.next.value == value:
cur.next = cur.next.next
break列表逆序
def reverse(self):
cur = self.head
new_list = LinkedList()
prev_node = None
while cur:
new_node = Element(cur.value)
new_node.next = prev_node
prev_node = new_node
cur = cur.next
new_list.head = prev_node
return new_list递归实现
递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决
- - 1、明确递归终止条件；
- - 2、给出递归终止时的处理办法；
- - 3、提取重复的逻辑，缩小问题规模。
"""在递去过程中解决问题"""
function recursion(大规模){
if (end_condition){ // 明确的递归终止条件
end; // 简单情景
}else{ // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题
solve; // 递去
recursion(小规模); // 递到最深处后，不断地归来
}
}
"""在归来过程中解决问题"""
function recursion(大规模){
if (end_condition){ // 明确的递归终止条件
end; // 简单情景
}else{ // 先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题
recursion(小规模); // 递去
solve; // 归来
}
}
原始序列： A-->B-->None
head.next.next = head
A-->B-->None
↑___|
head.next = None
A-->B-->None
|________↑
B->A->None
"""def reverse_recursion(head):
if head is None or head.next is None:
return head
new_head = reverse_recursion(head.next)
pdb.set_trace()
head.next.next = head
head.next = None
return new_head合并两个列表
def merge(list1, list2):
merged = LinkedList(None)
if list1 is None:
return list2
if list2 is None:
return list1
list1_elt = list1.head
list2_elt = list2.head
while list1_elt is not None or list2_elt is not None:
if list1_elt is None:
merged.append(list2_elt)
list2_elt = list2_elt.next
elif list2_elt is None:
merged.append(list1_elt)
list1_elt = list1_elt.next
elif list1_elt.value <= list2_elt.value:
merged.append(list1_elt)
list1_elt = list1_elt.next
else:
merged.append(list2_elt)
list2_elt = list2_elt.next
return merged
class NestedLinkedList(LinkedList):
def flatten(self):
return self._flatten(self.head)
def _flatten(self, node):
if node.next is None:
return merge(node.value, None)
return merge(node.value, self._flatten(node.next))
linked_list = LinkedList(Node(1))
linked_list.append(3)
linked_list.append(5)
second_linked_list = LinkedList(Node(2))
second_linked_list.append(4)
nested_linked_list = NestedLinkedList(Node(linked_list))
nested_linked_list.append(second_linked_list)
flattened = nested_linked_list.flatten()
node = flattened.head
while node is not None:
#This will print 1 2 3 4 5
print(node.value)
node = node.nextAdd one
```python
'''
Add-One:
Problem Statement:
You are given a non-negative number in the form of a list elements.
For example, the number 123 would be provided as arr = [1, 2, 3]
Add one to the number and return the output in the form of a new list.
Example 1:
input = [1, 2, 3]
output = [1, 2, 4]
Example 2:
input = [9, 9, 9]
output = [1, 0, 0, 0]
Challenge:
One way to solve this problem is to convert the input array into a
number and then add one to it. For example, if we have
input = [1, 2, 3], you could solve this problem by creating the
number 123 and then separating the digits of the output number 124.
But can you solve it in some other way?
'''
import pdb
def add_one(arr):
'''
:param: arr - list of digits representing some number x
return a list with digits representing int (x + 1)
'''
output = 1;
for i in range(len(arr), 0, -1):
output = output + arr[i -1]
borrow = output // 10
pdb.set_trace()
if borrow == 0:
arr[i - 1] = output
break
else:
arr[i - 1] = output % 10
output = borrow
arr = [borrow] + arr
index = 0
while arr[index] == 0:
index += 1
return arr[index:]
def test_function(test_case):
arr = test_case[0]
solution = test_case[1]
output = add_one(arr)
for index, element in enumerate(output):
if element != solution[index]:
print("Fail")
return
print("Pass")
arr = [0]
solution = [1]
test_case = [arr, solution]
test_function(test_case)
arr = [1, 2, 3]
solution = [1, 2, 4]
test_case = [arr, solution]
test_function(test_case)
arr = [9, 9, 9]
solution = [1, 0, 0, 0]
test_case = [arr, solution]
test_function(test_case)查找并返回输入数组中连续子数组中的最大和。
"""
Problem Statement
You have been given an array containg numbers. Find and return the largest sum in a contiguous subarray within the input array.
Example 1:
arr= [1, 2, 3, -4, 6]
The largest sum is 8, which is the sum of all elements of the array.
Example 2:
arr = [1, 2, -5, -4, 1, 6]
The largest sum is 7, which is the sum of the last two elements of the array.
"""
def max_sum_subarray(arr):
"""
:param - arr - input array
return - number - largest sum in contiguous subarry within arr
Author: Zhijin Li (lizhijin1993@gmail.com)
"""
current_sum = arr[0]
max_sum = arr[0]
for num in arr[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(current_sum, max_sum)
return max_sum
def test_function(test_case):
arr = test_case[0]
solution = test_case[1]
output = max_sum_subarray(arr)
if output == solution:
print("Pass")
else:
print("Fail")
# Test Case 1
arr= [1, 2, 3, -4, 6]
solution= 8 # sum of array
test_case = [arr, solution]
test_function(test_case)
# Test Case 2
arr = [1, 2, -5, -4, 1, 6]
solution = 7 # sum of last two elements
test_case = [arr, solution]
test_function(test_case)
# Test Case 3
arr = [-12, 15, -13, 14, -1, 2, 1, -5, 4]
solution = 18 # sum of subarray = [15, -13, 14, -1, 2, 1]
test_case = [arr, solution]
test_function(test_case)
? 2020 GitHub, Inc.
Terms
Privacy
Security
Status
Help
Contact GitHub
Pricing
API
Training
Blog
AboutPascal's triangle
'''
问题陈述：
查找并返回列表形式的Pascal三角形的第n行。
n从0开始
例如，如果n = 4，则输出= [1、4、6、4、1]
Pascal的Triangle参考：
https://www.mathsisfun.com/pascals-triangle.html
任何帕斯卡三角形的公式：
[（n）/（k）]
---------------------
[（n！）/（k！（n-k）！）]
参数：-n-索引（从0开始）
return-list（）代表Pascal三角形的第n行
'''
def nth_row_pascal(n):
if n == 0:
return [1]
current_row = [1]
for i in range(1, n + 1):
previous_row = current_row
current_row = [1]
for j in range(1, i):
next_number = previous_row[j] + previous_row[j-1]
current_row.append(next_number)
current_row.append(1)
return current_row
def test_function(test_case):
n = test_case[0]
solution = test_case[1]
output = nth_row_pascal(n)
if solution == output:
print("Pass")
else:
print("Fail")
n = 0
solution = [1]
test_case = [n, solution]
test_function(test_case)
n = 1
solution = [1, 1]
test_case = [n, solution]
test_function(test_case)
n = 2
solution = [1, 2, 1]
test_case = [n, solution]
test_function(test_case)
n = 3
solution = [1, 3, 3, 1]
test_case = [n, solution]
test_function(test_case)
n = 4
solution = [1, 4, 6, 4, 1]
test_case = [n, solution]
test_function(test_case)
```
### 偶数排在奇数后
```python
'''
问题陈述：
给定具有整数数据的链表，请以以下方式排列元素：将所有具有偶数的节点放在奇数之后。 不要创建任何新节点，并避免使用任何其他数据结构。 偶数和奇数元素的相对顺序不得更改。
例：
链表= 1 2 3 4 5 6
输出= 1 3 5 2 4 6
'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Solution
def even_after_odd(head):
if head is None:
return head
even = None
odd = None
even_tail = None
head_tail = None
while head:
next_node = head.next
if head.data % 2 == 0:
if even is None:
even = head
even_tail = even
else:
even_tail.next = head
even_tail = even_tail.next
else:
if odd is None:
odd = head
odd_tail = odd
else:
odd_tail.next = head
odd_tail = odd_tail.next
head.next = None
head = next_node
if odd is None:
return even
odd_tail.next = even
return odd
def create_linked_list(arr):
if len(arr) == 0:
return None
head = Node(arr[0])
tail = head
for data in arr[1:]:
tail.next = Node(data)
tail = tail.next
return head
def print_linked_list(head):
while head:
print(head.data, end=' ')
head = head.next
print()
def test_function(test_case):
head = test_case[0]
solution = test_case[1]
node_tracker = dict({})
node_tracker['nodes'] = list()
temp = head
while temp:
node_tracker['nodes'].append(temp)
temp = temp.next
head = even_after_odd(head)
temp = head
index = 0
try:
while temp:
if temp.data != solution[index] or temp not in node_tracker['nodes']:
print("Fail")
return
temp = temp.next
index += 1
print("Pass")
except Excemption as e:
print("Fail")
arr = [1, 2, 3, 4, 5, 6]
solution = [1, 3, 5, 2, 4, 6]
head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)
arr = [1, 3, 5, 7]
solution = [1, 3, 5, 7]
head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)
arr = [2, 4, 6, 8]
solution = [2, 4, 6, 8]
head = create_linked_list(arr)
test_case = [head, solution]
test_function(test_case)交换节点
'''
问题陈述：
给定一个链表，交换位置i和j处的两个节点。
这些位置基于从0开始的索引。
注意：您必须交换节点，而不仅仅是交换值。
例：
linked_list = 3 4 5 2 6 1 9
位置= 3 4
输出= 3 4 5 6 2 1 9
说明：
位置3上的节点的值为2
位置4上的节点的值为6
交换这些节点将导致最终节点顺序为3 4 5 6 2 1 9
'''
class Node:
def __init__(self, data):
self.data = data
self.next = None
def swap_nodes(head, left_index, right_index):
# if both the indices are same
if left_index == right_index:
return head
left_previous = None
left_current = None
right_previous = None
right_current = None
count = 0
temp = head
new_head = None
# find out previous and current node at both the indices
while temp is not None:
if count == left_index:
left_current = temp
elif count == right_index:
right_current = temp
break
if left_current is None:
left_previous = temp
right_previous = temp
temp = temp.next
count += 1
right_previous.next = left_current
temp = left_current.next
left_current.next = right_current.next
# if both the indices are next to each other
if left_index != right_index:
right_current.next = temp
# if the node at first index is head of the original linked list
if left_previous is None:
new_head = right_current
else:
left_previous.next = right_current
new_head = head
return new_head
def test_function(test_case):
head = test_case[0]
left_index = test_case[1]
right_index = test_case[2]
left_node = None
right_node = None
temp = head
index = 0
try:
while temp is not None:
if index == left_index:
left_node = temp
if index == right_index:
right_node = temp
break
index += 1
temp = temp.next
updated_head = swap_nodes(head, left_index, right_index)
temp = updated_head
index = 0
pass_status = [False, False]
while temp is not None:
if index == left_index:
pass_status[0] = temp is right_node
if index == right_index:
pass_status[1] = temp is left_node
index += 1
temp = temp.next
if pass_status[0] and pass_status[1]:
print("Pass")
else:
print("Fail")
return updated_head
except Exception as e:
print("Fail")
def create_linked_list(arr):
if len(arr) == 0:
return None
head = Node(arr[0])
tail = head
for data in arr[1:]:
tail.next = Node(data)
tail = tail.next
return head
def print_linked_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
arr = [3, 4, 5, 2, 6, 1, 9]
head = create_linked_list(arr)
left_index = 3
right_index = 4
test_case = [head, left_index, right_index]
updated_head = test_function(test_case)
arr = [3, 4, 5, 2, 6, 1, 9]
left_index = 2
right_index = 4
head = create_linked_list(arr)
test_case = [head, left_index, right_index]
updated_head = test_function(test_case)
arr = [3, 4, 5, 2, 6, 1, 9]
left_index = 0
right_index = 1
head = create_linked_list(arr)
test_case = [head, left_index, right_index]
updated_head = test_function(test_case)相关推荐
- 笔记本电脑系统修复软件（笔记本电脑程序修复）
-
1、超级兔子2013系统修复软件超级兔子是一款完整的系统维护工具。拥有电脑系统评测、垃圾清理和注册表清理、可疑文件和插件检测、网页防护等功能，同时自带一些实用的系统工具，可清理你大多数的文件、注册表里...
- 联想保修服务包括哪些（联想保修都保修什么）
-
1、保修36个月的硬件包括：CPU、内存。2、保修24个月的硬件包括：主板、显卡、LCD屏、硬盘、电源适配器、键盘、鼠标模块。3、保修12个月的硬件包括：LCD之附件、光驱、DVD、CDR/W、软驱...
- 系统科学大会（中国系统科学学会）
-
2021年各种科学大会的召开时间取决于疫情的发展和国家政策的调整。一些大型的国际科学会议可能会推迟或者采用线上形式进行，以保障参会人员的安全和健康。同时，一些国内的学术会议也会受到疫情的影响，需要推迟...
- win10系统下载的内容在哪（win10下载的软件在哪个文件夹）
-
进入C:\Windows\SoftwareDistribution\Download目录下，通过win10应用商店中下载的安装包都放在此目录下。进入C:\Windows\SoftwareDistrib...
- 下载原版xp系统光盘（xp光盘系统安装教程怎么安装）
-
方法步骤步骤如下：1、首先打开计算机，在电脑光驱上放入XP光盘，启动电脑后不停按F12、F11、Esc等启动热键，在弹出的启动菜单中选择DVD选项，回车。2、进入光盘主菜单，按数字2或点击选项2运行w...
- windows7中文版下载安装（windows7安装包下载）
-
谢邀，如果你戳设置-时间和语言-区域和语言，右边的语言提示“只允许使用一种语言包”，那么你的系统就是家庭中文版。家庭中文版限定系统界面只能使用简体中文显示，其他功能则与普通家庭版没有区别，也可以使用其...
- win7开机按f2怎么重装系统（win7开机按f12怎么重装系统）
-
开机或重启时，在进入Windows前按F2进入BIOS。 ←→移动到第三个好像是BOOT。 然后将EXTENELBOOT选项设置为ENABLE 最后按F5将第一启动项目设置为EXTENEL...
-
- win10驱动管理（win10驱动程序）
-
win10由于联网后会自动安装驱动，如果自动安装驱动没出现问题，即可视为最佳驱动，若出现问题，卸载出问题的驱动，然后去查自己主板型号，在主板供应商官网下载对应驱动即是最佳01Windows10驱动更新调整当前当你插入连接即插即用（Pn...
-
2025-12-29 05:51 off999
- 手机上怎么找qq邮箱登录（用手机怎么找到qq邮箱）
-
入口是“联系人”选项卡。qq邮箱手机在QQ主菜单中选择下方的“联系人”选项卡；3、在“联系人”中选取“公众号”选项卡；4、在公众号中菜单中找到或搜索“QQ邮箱提醒”，点击进入；5、点击“进入邮箱”；6...
- amd显卡控制面板
-
AMD显卡控制面板是用来管理你的AMD显卡的,可以在控制面板中进行设置一些简单的调整,来提升显卡性能和效果。1、先打开AMD控制面板。2、打开“垂直同步(V-SYNC)”功能，可调整细节，改善影像流畅...
- win10老是未响应卡死（window10总是未响应）
-
具体方法：1、如果win10中的应用程序出现不响应的情况，应该是应用程序加载失败了。可以通过重置方法来解决win10应用程序无响应。2、登录win10系统，用管理员身份运行Powershell（可在C...
- usb安装系统步骤（USB安装系统步骤）
-
1.准备一张U盘，将联想官网下载的系统镜像文件复制到U盘中；2.将U盘插入联想S41U电脑，重启电脑，按F12进入BIOS设置，将U盘设置为启动项；3.重启电脑，进入U盘安装界面，按提示操作，完成系统...
- win98安装教程（win98iso怎么安装）
-
如何安装windows98 一、具体安装步骤 备份好重要文件之后，就可以安装windows98了。 第一步：启动安装程序。 用户如果原来已安装了windows95/97/98，现在拟对其进行升...
- 雨林木风win7安装（雨林木风win732位安装教程）
-
安装步骤如下： 1、光盘放入光驱，复制光盘上的win7.gho和安装系统.exe到硬盘非C盘的文件夹；（gho文件名可以是其他名字，后缀为gho，体积最大的就是。） 2、双击安装系统.exe;...
- win10解绑管理员账户（win10管理员账户怎么取消开机密码）
-
要解除Windows10电脑上的管理员权限，您需要进行以下操作：1.打开“控制面板”：右键单击“开始”按钮，然后选择“控制面板”。2.进入“用户账户”：在控制面板中，选择“用户账户”。3.点击...
欢迎 你 发表评论:
- 一周热门
-
-
抖音上好看的小姐姐，Python给你都下载了
-
全网最简单易懂!495页Python漫画教程，高清PDF版免费下载
-
Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!
-
飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx
-
python入门到脱坑 输入与输出—str()函数
-
宝塔面板如何添加免费waf防火墙?（宝塔面板开启https）
-
Python三目运算基础与进阶_python三目运算符判断三个变量
-
(新版)Python 分布式爬虫与 JS 逆向进阶实战吾爱分享
-
失业程序员复习python笔记——条件与循环
-
系统u盘安装（win11系统u盘安装）
-
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (77)
- python封装 (57)
- python写入txt (66)
- python读取文件夹下所有文件 (59)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)