“指针”是编程语言中的一个对象，它存储着一个内存空间的地址，计算机可以通过这个地址找到变量的值。
指针最大的优点在于它可以有效利用零碎的内存空间。
- 数组合并
- 二分查找
- 链表
数组合并
问题：用指针合并两个有序数组
合并有序数组
通过一个数组中每个元素的下标，找出对应的值，可以将存储这个元素位置的下标值的变量看作一个指针。
代码实现: 使用模拟指针完成两个有序数组的合并
list1 = [1,4,6,8,9]
list2 = [3,7,10,11]
index_ = 0
res = list1.copy()
# print(id(list1))
# print(id(res))
len_1 = len(list1)
len_2 = len(list2)
for i in range(len_2):
while index_ < len_1:
# index_ 的范围不能超过数组元素下标的最大值
if list2[i] <= list1[index_]:
res.insert(index_ + i, list2[i])
break
else:
index_ += 1
else:
res = res + list2[i:]
break
print(res)
二分查找
问题: 如何快速在一个有序数组中准确找到一个元素的位置
什么是二分查找
二分查找又叫做折半查找，顾名思义，就是每次查找后，查找的范围都折半，查到最后只剩一个数时，判断是否为要查找的数。
二分查找思维解析
二分查找需要两个指针，一个指向数组的第一个元素，叫做头指针，另一个指向数组最后一个元素的后方，叫作尾指针。要查找的范围就是头指针和尾指针之间的所有元素。
初始化之后，需要找到范围中的中间数，可以通过把头指针和尾指针的值相加再除以2来得到中间数的下标值。然后将得到下标值的元素与查找元素对比，缩小范围，重复操作，最终得出结论
代码实现: 用指针实现有序数组中的二分查找
# 定义有序数组
val = [1,3,4,6,7,8,11,13,14,15,18,23,25,26,28,36,38,45,47,52]
# 获取头指针与尾指针
head, tail = 0, len(val)
# 输入查找的数
search_num = int(input("Enter a number to search:>>>"))
#
res = None
# 当 （尾指针 - 头指针）= 1时，查找范围内 只有head指向的数
while tail - head > 1:
mid = (head + tail) // 2
# 若小于 mid指向的元素
if search_num < val[mid]:
tail = mid
# 若大于 mid指向的元素
if search_num > val[mid]:
head = mid + 1
# 找到元素直接结束
if search_num == val[mid]:
res = mid
break
else:
search_num == val[head]
res = head
# res, mid为伪指针，要做判断输出结果
if search_num == val[res]:
print(val[res])
else:
print('Not found.')
链表
链表是用指针连接的用于存储数据的数组，其最大的优点在于: 可以有效利用零碎的内存空间。
在很多语言中，数组的大小要提前定义，定义后不能更改，且数组中只能存储同一类型的变量。
若使用了链表，则可以改变数组的长度，且可以在同一个数组中存储不同类型的元素
Python语言没又指针，可使用模拟指针的方法实现链表
单链表
链表的每个元素不仅存储该元素的值，还要存储与它相连的元素的指针的值，这样链表才能被连接起来。
什么是单链表
单链表 的每个元素包含一个本身的值和一个指向下一个数的指针。
链表的最后一个数没有下一个数，所以它的指针为空指针。
建立单链表
方法1. 把链表中的每一个元素存储在一个列表中，再将它们的指针存储在另一个列表里
#
list_val = [1, 5, 6, 2, 4, 3]
list_pointer = [3, 2, -1, 5, 1, 4]
'''
在两个数组中，相同下标的元素组成了链表中的一个元素
如: 链表中第一个元素的值为1， 在list_val数组中的下标为0，则list_pointer[0] = 3, 它是链表中这个元素存储的指针，
也就是list_val中下标为3的数值为2。依次类推，直到有个一指针的值为-1，代表后面没有其他元素了。
这样两个数组list_val, list_pointer 合起来建立了一个链表
'''
输出一个由两个列表组成的单链表
list_val = [1, 5, 6, 2, 4, 3]
list_pointer = [3, 2, -1, 5, 1, 4]
# head 是指向链表第一个元素的指针，需要定义
head = 0
print(list_val[head])
#给next赋初始值
next = list_pointer[head]
while next != -1:
print(list_val[next])
next = list_pointer[next]
方法2. 数组中套数组
linked_list = [[1, 3], [5, 2], [6, -1], [2, 5], [4, 1], [3, 4]]
'''
大数组中的每个小数组都是链表中的一个元素。
小数组的第一个数是这个元素存储的值， 第二个数是指向下一个元素的指针。
调用大数组中的第m个小数组中的第n个元素可以 linked_list[m-1][n-1](下标为0)
'''
输出一个列表套列表组成的单链表
pointer = 1
linked_list = [[1, 3], [5, 2], [6, -1], [2, 5], [4, 1], [3, 4]]
head = 1
print(linked_list[head - 1][pointer - 1])
next = linked_list[head - 1][pointer]
while next != -1:
print(linked_list[next][pointer - 1])
next = linked_list[next][pointer]
向单链表中添加元素
首先，把新元素的指针指向它将要插入的位置后方的元素，
随后，把新元素前面的元素的指针指向这个元素，
最后，形成一个更长的链表
思考: 为什么要把新元素的指针指向它后面的元素，再让它前面的元素指向它？而不是反过来
注意: 指针是存储下一个元素位置的变量
向单链表中插入元素
def out_put(list_val, list_pointer, head):
# 定义一个用于输出链表的函数
print(list_val[head])
next = list_pointer[head]
while next != -1:
print(list_val[next])
next = list_pointer[next]
list_val = [1, 5, 6, 2, 7, 3]
list_pointer = [3, 2, 4, 5, -1, 1]
head = 0
# 已知要插入的位置的上一个元素的位置
prepos = 5
print("输出未插入元素的链表:")
out_put(list_val, list_pointer, head)
list_val.append(4)
list_pointer.append(list_pointer[prepos])
list_pointer[prepos] = len(list_val) - 1
print('输出已插入元素的链表:')
out_put(list_val, list_pointer, head)
双链表
什么是双链表
双链表中的每个元素由它的值和两个指针组成，一个指针指向下一个元素，一个指针指向上一个元素
建立双链表
方法1. 用三个数组分别存储值，左指针，右指针
list_val = [1, 5, 6, 2, 7, 3]
list_right = [3, 2, 4, 5, -1, 1]
list_left = [-1, 5, 1, 0, 2, 3]
方法2. 一个大数组中的小数组
linked_list = [[1, 3, -1], [5, 2, -5], [6, 4, 1], [2, 5, 0], [7, -1, 2], [3, 1, 3]]
正序输出双链表
# 1
list_val = [1, 5, 6, 2, 7, 3]
list_rigth = [3, 2, 4, 5, -1, 1]
list_left = [-1, 5, 1, 0, 2, 3]
head = list_left.index(-1)
print(list_val[head])
next = list_rigth[head]
while next > -1:
print(list_val[next])
next = list_rigth[next]
#2
right = 1
val = 0
linked_list = [[1, 3, -1], [5, 2, 5], [6, 4, 1], [2, 5, 0], [7, -1, 2], [3, 1, 3]]
head = 0
print(linked_list[head][val])
next = linked_list[head][right]
while next > -1:
print(linked_list[next][val])
next = linked_list[next][right]
双向输出双链表
list_val = [1, 5, 6, 2, 7, 3]
list_rigth = [3, 2, 4, 5, -1, 1]
list_left = [-1, 5, 1, 0, 2, 3]
print('Is the output:')
head = list_left.index(-1)
print(list_val[head])
next = list_rigth[head]
while next > -1:
print(list_val[next])
next = list_rigth[next]
print('Reverse output:')
head = list_rigth.index(-1)
print(list_val[head])
next = list_left[head]
while next > -1:
print(list_val[next])
next = list_left[next]
向双链表中添加元素
一个未插入新元素的双链表， 一个要被插入的元素
首先，给新元素指前后元素的指针赋值，
随后，给前后两个元素指向新元素的指针赋值，
最后，组成一个新的双链表
向双链表中插入元素
def out_put(list_val, list_right, list_left):
head = list_left.index(-1)
print(list_val[head])
next = list_right[head]
while next > -1:
print(list_val[next])
next = list_right[next]
# 双向链表
list_val = [1, 5, 6, 2, 7, 3]
list_right = [3, 2, 4, 5, -1, 1]
list_left = [-1, 5, 1, 0, 2, 3]
# head = 0
prepos = 5
print('输出未插入元素的链表: ')
out_put(list_val, list_right, list_left)
list_val.append(4)
list_right.append(list_right[prepos])
list_left.append(prepos)
list_left[list_right[prepos]] = len(list_val) - 1
list_right[prepos] = len(list_val) - 1
print('输出已插入元素的链表:')
out_put(list_val, list_right, list_left)