时间复杂度
- 用来评估算法运行时间的一个式子(单位)
- 一般来说，时间复杂度高的算法比复杂度低的算法慢
- 常见的时间复杂度(按效率排序)
- O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2logn) < O(n^3)
- 复杂问题的时间复杂度
- O(n!) O(2^n) O(n^n)
- 快速判断算法复杂度
- 确定问题规模n
- 循环减半过程 --> logn
- k层关于n的循环 --> n^k
空间复杂度
- 用来评估算法内存占用大小的式子
- 空间复杂度的表示方式与时间复杂度完全一样
- 算法使用了几个变量：O(1)
- 算法使用了长度为n的一维列表：O(n)
- 算法使用了m行n列的二维列表：O(mn)
- "空间换时间"
递归
-
特点：
- 调用自身
- 结束条件
# 下面这个函数不符合递归的特性，因为它在调用自身的时候传入的参数始终满足判断条件，所以这是一个死循环 def func1(x): if x > 0: print(x) func1(x+1) # 正确示例： def func1(x): if x > 0: print(0) func1(x-1)
查找
- 在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程
- 列表查找（线性表查找）：从列表中查找指定元素
- 输入：列表、待查找元素
- 输出：元素下标（未找到元素时一般返回None或者-1）
顺序查找(线性查找)
-
从列表的第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表的最后一个元素为止
-
时间复杂度：O(n)
# li:列表 val:需要查找的元素 def linear_search(li,val): for ind,v in enumerate(li): if v == val: return ind else: return None
二分查找(折半查找)
-
从==有序==列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半
-
时间复杂度：O(logn)
def binary_search(li,val): left = 0 right = len(li) - 1 while left <= right: mid = (left + right) // 2 # 候选区有值 if li[mid] == val: return mid elif li[mid] > val: # 待查找的值在mid左侧 right = mid - 1 else: # li[mid] < val 待查找的值在mid右侧 left = mid + 1 else: return None
排序
- 将一组==无序==的记录序列调整为==有序==的记录序列
- 列表排序：将无序列表变为有序列表
- 输入：列表
- 输出：有序列表
- 升序与降序
冒泡排序
-
列表每两个相邻的数，如果前面比后面大，则交换这两个数
-
一趟排序完成后，则无序区减少一个数，有序区增加一个数
-
时间复杂度：O(n^2)
def bubble_sort(li): for i in range(len(li) - 1): # 第i趟 for j in range(len(li) - i - 1): # 下标 if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] -
如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法
def bubble_sort(li): for i in range(len(li) - 1): # 第i趟 exchange = False for j in range(len(li) - i - 1): # 下标 if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] exchange = True if not exchange: return
选择排序
-
一趟排序记录最小的数，放到第一个位置
-
再一趟排序记录记录列表无序区最小的数，放到第二个位置
-
......
-
算法关键点：有序区和无序区、无序区最小数的位置
def select_sort(li): li_new = [] for i in range(len(li)): min_val = min(li) li_new.append(min_val) li.remove(min_val) return li_new上述选择排序不足：
1、需要新建列表作为有序区，消耗内存空间
2、
min()和remove()函数都会遍历列表，降低效率3、时间复杂度：O(n^3)
def select_sort(li): for i in range(len(li)-1): # 第i趟 min_loc = i for j in range(i+1,len(li)): if li[j] < li[min_loc]: min_loc = j if min_loc != i: li[i],li[min_loc] = li[min_loc],li[i]在之前选择排序的基础上优化：
1、没有新建列表，直接在原列表上进行数据交换
2、没有使用复杂度较高的函数
3、时间复杂度：O(n^2)
和冒泡排序有点类似，每次要遍历无序区，不同的是选择排序每趟选出最大值或最小值放在有序区内，冒泡排序是和相邻的数做比较，然后交换
插入排序
-
初始时手里（有序区）只有一张牌
-
每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
-
时间复杂度：O(n^2)
def insert_sort(li): for i in range(1,len(li)): # i表示摸到的牌的下标 tmp = li[i] j = i - 1 # j指的是手里的牌的下标 while j >= 0 and li[j] > tmp: li[j+1] = li[j] j -= 1 li[j+1] = tmp
快速排序
-
取一个元素p（第一个元素），使元素p归位
-
列表被p分成两部分，左边都比p小，右边都比p大
-
递归完成排序
-
时间复杂度：O(nlogn)
def partition(li,left,right): tmp = li[left] while left < right: # 从右边找比tmp小的数 while left < right and li[right] >= tmp: right -= 1 # 往左走一步 li[left] = li[right] # 把右边的值写到左边空位上 while left < right and li[left] <= tmp: left += 1 li[right] = li[left] # 把左边的值写到右边空位上 li[lift] = tmp # 把tmp归位 return left def quick_sort(li,left,right): if left < right: mid = partition(li,left,right) quick_sort(li,left,mid-1) quick_sort(li,mid+1,right) -
最坏情况：
- 如果列表是倒序的，移动元素的次数n会达到最大值，这时的时间复杂度为：O(n^2)
- 解决方案：先选择列表的第一个元素p，然后在列表中随机选择一个元素和元素p的位置交换，虽然也会有最坏情况出现，但是属于不可控（可控：自定义倒序列表），遇到的几率很小。
-
递归：
-
递归会开辟新的内存空间，所以存在递归最大深度的问题，根据电脑的配置来决定的，可以进行修改，但是不是绝对的，比如电脑内存大小只能递归999次，你修改成10000也没用
import sys # 递归最大深度修改为10000 sys.setrecursionlimit(10000)
-
堆排序及应用
-
堆：一种特殊的完全二叉树，父节点的值比每个子节点的值都要大（大根堆）或者父节点的值比每个子节点的值都要小（小根堆）
-
堆排序过程：
- 建立堆
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
- 堆顶元素为第二大元素
- 重复步骤3，直到堆变空
-
时间复杂度：O(nlogn)
# 向下调整函数(大根堆) def sift(li,low,high): ''' li:列表 low:堆的根节点位置 high:堆的最后一个元素的位置 ''' i = low # i最开始指向根节点 j = 2 * i + 1 # j开始是左孩子 tmp = li[low] # 把堆顶存起来 while j <= high: # 只要j位置有数 if j +1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大 j = j + 1 # j 指向右孩子 if li[j] > tmp: li[i] = li[j] i = j # 往下看一层 j = 2 * i +1 else: # tmp更大，把tmp放到i的位置上 li[i] = tmp # 把tmp放到某一级领导位置上 break else: li[i] = tmp # 把tmp放到叶子节点上 # 堆排序 def heap_sort(li): n = len(li) for i in rang((n-2)//2,-1,-1): # i表示建堆的时候调整的部分的根的下标 sift(li,i,n-1) # 建堆完成了 for i in rang(n-1,-1,-1): # i指向当前堆的最后一个元素 li[0],li[i] = li,li[0] sift(li,0,i-1) # i-1是新的high -
Python内置函数（heapq）可以完成堆排序
import heapq # q -> queue 优先队列 heapq.heapify(li) # 建堆 heapq.heappop(li) # 每次输出当前堆中最小的元素 -
topk问题
-
现在有n个数，设计算法得到前k大的数。(k<n)
-
解决思路：
- 排序后切片 O(nlogn)
- 使用冒泡/选择/插入排序 O(kn)
- 堆排序 O(nlogk)
-
堆排序解决思路：
- 取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则堆顶更换为该元素，并且对堆进行一次调整；
- 遍历列表所有元素后，倒序弹出堆顶。
# 向下调整函数(小根堆) def sift(li,low,high): i = low j = 2 * i + 1 tmp = li[low] while j <= high: if j +1 <= high and li[j+1] < li[j]: j = j + 1 if li[j] < tmp: li[i] = li[j] i = j j = 2 * i +1 else: li[i] = tmp break else: li[i] = tmp def topk(li,k): # 1.建堆 heap = li[0:k] for i in range((k-2)//2,-1,-1): sift(heap,i,k-1) # 2.遍历 for i in range(k,len(li)-1): if li[i] > li[i]: heap[0] = li[i] sift(heap,0,k-1) # 3.出数 for i in range(k-1,-1,-1): heap[0],heap[i] = heap[i],heap[0] sift(heap,0,i-1) return heap
-
归并排序
-
归并
- 假设现在的列表分两段有序，将其合成为一个有序列表的操作
-
归并排序步骤
- 分解：将列表越分越小，直至分成一个元素
- 终止条件：一个元素是有序的
- 合并：将两个有序列表归并，列表越来越大
-
时间复杂度：O(nlogn)
-
空间复杂度：O(n) 归并的过程中新建了一个列表
# 归并 def merge(li,low,mid,high): ''' li:列表 low:前段有序列表的第一个数的下标 mid:前段有序列表的最后一个数的下标 high:后段有序列表的最后一个数的下标 ''' i = low j = mid + 1 ltmp = [] while i <= mid and j <= high: # 只要左右两边都有数 if li[i] < li[j]: ltmp.append(li[i]) i += 1 else: ltmp.append(li[j]) j += 1 # while执行完，肯定有一部分没数了 while i <= mid: ltmp.append(li[i]) i += 1 while j <= mid: ltmp.append(li[j]) j += 1 li[low:high+1] = ltmp def merge_sort(li,low,high): if low < high: # 至少有两个元素，递归 mid = (low + high) // 2 merge_sort(li,low,mid) merge_sort(li,mid+1,high) merge(li,low,mid,high)
总结
- 三种排序算法的时间复杂度都是O(nlogn)
- 一般情况下，就运行时间而言：快速排序 < 归并排序 < 堆排序
- 三种排序算法的缺点：
- 快速排序：极端情况下排序效率低
- 归并排序：需要额外的内存开销
- 堆排序：在快的排序算法中相对较慢
希尔排序
-
希尔排序(Shell Sort)是一种分组插入排序算法
-
首先取一个整数d
1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序 -
去第二个整数d
2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序 -
希尔排序每趟并不使某些元素有序，而是是整体数据越来越接近有序，最后一趟排序使得所有数据有序
-
时间复杂度：
希尔排序有很多实现方法，k(组数)的获取方式不同，时间复杂度也不同，比如下面的\lfloor\frac {n}{2^k}\rfloor，最坏时间复杂度为O(n^2)，k还有很多获取方式：
2\lfloor\frac {n}{2^{k+1}}\rfloor+1：O(n^\frac32)(1960年)
Successive numbers of the form 2^p3^q：O(nlog^2n)(1971年)
\lceil\frac15(9·(\frac94)^{k-1}-4)\rceil：时间复杂度未知(2001年)
希尔排序不管怎么实现，时间复杂度都是介于冒泡/选择/插入排序和快速/堆/归并之间
def insert_sort_gap(li,gap): # gap参数:组数 for i in range(gap,len(li)): # i表示摸到的牌的下标 tmp = li[i] j = i - gap # j指的是手里的牌的下标 while j >= 0 and li[j] > tmp: li[j+gap] = li[j] j -= gap li[j+1] = tmp def shell_sort(li): d = len(li) // 2 while d >= 1: insert_cort_gap(li,d) d // 2
计数排序
-
对列表进行排序，已知列表中的数范围都在0到100之间
-
时间复杂度：O(n)
def count_sort(li,max_count=100): count = [0 for _ in range(max_count+1)] for val in li: count[val] += 1 li.clear() for ind,val in enumerate(count): for i in range(val): li.append(ind)优点：速度很快，比快速/堆/归并/默认排序都要快
缺点：需要事先知道列表中的数据范围，比如0-100；需要消耗很多内存空间
如果元素的范围比较大（比如在1到1亿之间），如何改造算法？于是出现了桶排序
桶排序
-
首先将元素分在不同的桶中，再对每个桶中的元素排序
-
复杂度：
- 桶排序的表现取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略
- 平均情况时间复杂度：O(n+k)
- 最坏情况时间复杂度：O(n^2k)
- 空间复杂度：O(nk)
def bucket_sort(li,n=100,max_count=10000): buckets = [[] for _ in range(n)] # 创建桶 for var in li: i = min(var // (max_num // n),n-1) # i表示var放到几号桶里 buckets[i].append(var) # 把var加到桶里边 # 保持桶内的顺序 for j in range(len(buckets[i])-1,0,-1): if buckets[i][j] < buckets[i][j-1]: buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j] else: break sorted_li = [] for buc in buckets: sorted_li.extend(buc) return sorted_li
基数排序
-
多关键字排序：假如现在有一个员工表，要求按照薪资排序，年龄相同的员工按照年龄排序
-
先按照年龄进行排序，再按照薪资进行稳定的排序
-
对32,13,94,52,17,54,93排序，是否可以看做多关键字排序？
基数排序实现思路：
1、先取列表中最大数的位数，比如9的位数为1,999的位数为3
2、分10个桶，根据元素的个位数，依次放入桶中
3、按照桶的顺序，把桶中的元素依次拿出来
4、重复2、3过程，根据列表最大数的位数(个十百千万)
-
-
复杂度：
- 时间复杂度：O(kn)
- 空间复杂度：O(k+n)
- k表示数字位数
def radix_sort(li): max_num = max(li) # 最大值 9->1,99->2,888->3,10000->5 it = 0 while 10 ** it <= max_num: # 分桶 buckets = [[] for _ in range(10)] for var in li: # 987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10=9 digit = (var // 10 ** it) % 10 buckets[digit].append(var) # 把数重新写回li li.clear() for buc in buckets: li.extend(buc) i += 1
附：算法面试题
-
1.给两个字符串s和t，判断t是否为s的重新排列后组成的单词
- s = "anagram"，t = "nagaram"，return true
- s = "rat"，t = "car"，retrun false
# 解法1：把s和t转换为列表，然后排序，判断 def isAnagram(s,t): ss = list(s) tt = list(t) ss.sort() tt.sort() return ss == tt # 解法2：计算s和t中英文字母出现的次数，保存在字典中，然后判断 def isAnagram(s,t): dict1 = {} # {'a':1,'b':2} dict2 = {} for ch in s: dict1[ch] = dict1.get(ch,0) + 1 for ch in t: dict2[ch] = dict2.get(ch,0) + 1 return dict1 == dict2 # 总结：解法1和解法2都能完成需求，但是时间复杂度：解法2<解法1. -
2.给定一个m*n的二维列表，查找一个数是否存在。列表有一下特性：
- 每一行的列表从左到右已经排序好
- 每一行第一个数比上一行最后一个数大
''' [ [1,3,5,7], [10,11,16,20], [23,30,34,50] ] ''' # 解法1：遍历 def searchMatrix(matrix,target): for line in matrix: if target in line: return True return False # 解法2：二分查找 def searchMatrix(matrix,target): h = len(matrix) if h == 0: return False # [] w = len(matrix[0]) if w == 0: return False # [[],[],[]] left = 0 right = w * h - 1 while left <= right: mid = (left + right) // 2 i = mid // w j = mid % w if matrix[i][j] == target: return True elif matrix[i][j] > target: right = mid - 1 else: left = mid + 1 else: return False # 总结:时间复杂度：解法2<解法1，在写算法的时候，要考虑到边界条件，比如给的条件为空 -
3.给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数。保证肯定仅有一个结果
- 例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1)
# 解法1：遍历 def twoSum(nums,target): for i in range(len(nums)): for j in range(i): if nums[i] + nums[j] == target: return [i,j] # 解法2：二分查找 def binary_search(li,left,right,val): while left <= right: mid = (left + right) // 2 if li[mid][0] == val: return mid elif li[mid][0] > val: right = mid - 1 else: left = mid + 1 else: return None def twoSum(nums,target): new_nums = [[num,i] for i,num in enumerate(nums)] new_nums.sort(key=lambda x:x[0]) for i in range(len(new_nums)): a = new_nums[i][0] b = target - a if b >= a: j = binary_search(new_nums,i+1,len(new_nums)-1,b) else: j = binary_search(new_nums,0,i-1,b) if j: break return sorted([new_nums[i][1],new_nums[j][1]]) # 总结:时间复杂度：解法2<解法1
数据结构
- 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和改集合中数据元素之间的关系组成
- 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中
- 比如：列表、集合与字典等都是一种数据结构
- N.Wirth：“程序=数据结构+算法”
- 数据结构按照其逻辑结构可分为线性结构、树结构、图结构
- 线性结构：数据结构中的元素存在一对一的相互关系
- 树结构：数据结构中的元素存在一对多的相互关系
- 图结构：数据结构中的元素存在多对多的相互关系
列表/数组
-
列表（其他语言称数组）是一种基本数据类型
-
关于列表的问题：
-
列表中的元素是如何存储的？
列表里的每个格子存的是元素对应的内存地址，每次访问元素的时候，其实是访问该元素的内存地址，然后指向元素具体的值
-
列表的基本操作：按下标查找（O(1)）、插入元素（O(n)）、删除元素(O(n))......
-
这些操作的时间复杂度是多少？
-
-
扩展：Python的列表是如何实现的？
栈
-
栈(Stack)是一个数据集合，可以理解为只能再一段进行插入或删除操作的列表
-
栈的特点：后进先出LIFO（last-in，first-out）
-
栈的概念：栈顶、栈底
-
栈的基本操作：
- 进栈（压栈）：push
- 出栈：pop
- 取栈顶：gettop
-
使用一般的列表结构即可实现栈
- 进栈：li.append
- 出栈：li.pop
- 取栈顶：li[-1]
-
括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配
-
例如：
- ()()[]{} 匹配
- ([{()}]) 匹配
- []( 不匹配
- [(]) 不匹配
# 自定义栈 class Stack: def __init__(self): self.stack = [] # 进栈 def push(self,element): self.stack.append(element) # 出栈 def pop(self): return self.stack.pop() # 取栈顶 def get_top(self): if len(self.stack) > 0: return self.stack[-1] else: return None # 判断栈是否为空 def is_empty(self): return len(self.stack) == 0 def brace_match(s): match = {'}':'{',']':'[',')':'('} stack = Stack() for ch in s: if ch in {'(','[','{'}: stack.push(ch) else: # ch in {'}',']',')'} if stack.is_empty(): return False elif stack.get_top() == match[ch]: stack.pop() else: # stack.get_top() != match[ch] return False if stack.is_empty(): return True else: return False
队列
-
队列(Queue)是一个数据集合，仅允许在列表的一段进行插入，另一端进行删除
-
进行插入的一段成为队尾(rear)，插入动作称为进队或入队
-
进行删除的一端称为队头(front)，删除动作称为出队
-
队列的性质：先进先出FIFO (First-in，First-out)
-
环形队列：当队尾指针front == Maxsize - 1时，再前进一个位置就自动到0
- 队首指针前进1：front = (front + 1) % Maxsize
- 队尾指针前进1：rear = (rear + 1) % Maxsize
- 队空条件：rear == front
- 队满条件：(rear + 1) % Maxsize == front
class Queue: def __init__(self,size=100): self.queue = [0 for _ in range(size)] self.size = size self.rear = 0 # 队尾指针 self.front = 0 # 队首指针 # 进队 def push(self,element): if not self.is_filled(): self.rear = (self.rear + 1) % self.size self.queue[self.rear] = element else: raise IndexError('Queue is filled.') # 出队 def pop(self): if not self.is_empty(): self.front = (self.front + 1) % self.size return self.queue[self.front] else: raise IndexError('Queue is empty.') # 判断队空 def is_empty(self): return self.rear == self.front # 判断队满 def is_filled(self): return (self.rear + 1) % self.size == self.front -
双向队列的两端都支持进队和出队操作
-
双向队列的基本操作：
- 队首进队
- 队首出队
- 队尾进队
- 队尾出队
-
Python内置模块使用方法：
from collections import deque- 创建队列：
queue = deque(list,maxsize)，maxsize为队列最大长度，当队满有元素进队时，队首元素会自动出队 - 进队：
append() - 出队：
popleft() - 双向队列队首进队：
appendleft() - 双向队列队尾出队：
pop()
# 使用双向队列实现类似Linux系统tail命令，查看文件最后n行的数据 from collections import deque def tail(n): with open('test.txt','r') as f: q = deque(f,n) return q for line in tail(5): print(line,end='') - 创建队列：
栈和队列的应用:迷宫问题
-
给一个二维列表，表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径
maze = [ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,0,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,0,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1] ]
栈：深度优先搜索
-
回溯法
-
思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找有其他方向的点
-
使用栈存储当前路径
dirs = [ lambda x,y:(x+1,y), lambda x,y:(x-1,y), lambda x,y:(x,y-1), lambda x,y:(x,y+1), ] def maze_path(x1,y1,x2,y2): #x1,y1:起点坐标 x2,y2:终点坐标 stack = [] stack.append((x1,y1)) while len(stack) > 0: curNode = stack[-1] # 当前节点 # 走到终点了 if curNode[0] == x2 and curNode[1] == y2: for p in stack: print(p) return True # x,y四个方向 x+1,y; x-1,y; x,y-1; x,y+1 for dir in dirs: nextNode = dir(curNode[0],curNode[1]) # 如果下一个节点能走 if maze[nextNode[0]][nextNode[1]] == 0: stack.append(nextNode) maze[nextNode[0]][nextNode[1]] = 2 # 2表示为已经走过 break else: maze[nextNode[0]][nextNode[1]] = 2 stack.pop() else: print('没有路') return False
队列：广度优先搜索
-
思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口
-
使用队列存储当前正在考虑的节点
from collections import deque dirs = [ lambda x,y:(x+1,y), lambda x,y:(x-1,y), lambda x,y:(x,y-1), lambda x,y:(x,y+1), ] def print_r(path): curNode = path[-1] realpath = [] while curNode[2] == -1: realpath.append(curNode[0:2]) curNode = path[curNode[2]] realpath.append(curNode[0:2]) # 起点 realpath.reverse() for node in realpath: print(node) def maze_path_queue(x1,y1,x2,y2): queue = deque() queue.append((x1,y1,-1)) path = [] while len(queue) > 0: curNode = queue.pop() path.append(curNode) if curNode[0] == x2 and curNode[1] == y2: # 终点 print_r(path) return True for dir in dirs: nextNode = dir(curNode[0],curNode[1]) if maze[nextNode[0]][nextNode[1]] == 0: # 后续节点进队，记录哪个节点带他来的 queue.append((nextNode[0],nextNode[1],len(path) -1)) maze[nextNode[0]][nextNode[1]] = 2 # 标记为已经走过 else: print('没有路') return False
链表
-
链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表
# 自定义链表 class Node: def __init__(self,item): self.item = item self.next = None # 头插法 def create_linklist_head(li): head = Node(li[0]) for element in li[1:]: node = Node(element) node.next = head head = node return head # 尾插法 def ceate_linklist_tail(li): head = Node(li[0]) tail = head for element in li[1:]: node = Node(element) tail.next = node tail = node return head # 遍历链表 def print_linklist(lk): while lk: print(lk.item,end=',') lk = lk.next -
链表节点的插入
- p.next = curNode.next
- curNode.next = p
-
链表节点的删除
- p = curNode.next
- curNode.next = curNode.next.next
- del p
双链表
-
双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点
class Node: def __init__(self,item): self.item = item self.next = None self.piror = None -
双链表节点的插入
- p.next = curNode.next
- curNode.next,prior = p
- p.prior = curNode
- curNode.next = p
-
双链表节点的删除
- p = curNode.next
- curNode.next = p.next
- p.next.piror = curNode
- del p
总结：链表与顺序表
- 链表在插入和删除的操作上明显快于顺序表
- 链表的内存可以更灵活的分配
- 试利用链表重新实现栈和队列
- 链表这种链式存储的数据结构对树和图的结构有很大的启发性
哈希表
- 哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
- insert(key,value)：插入键值对(key,value)
- get(key)：如果存在键为key的键值对则返回其value，否则返回空值
- delete(key)：删除键为key的键值对