网站设计客户对接流程,xampp安装wordpress说明,关于文化馆网站建设的材料,wordpress ck数据结构与算法1 数据结构基础1.1 数组1.2 链表1.3 队列1.4 栈1.5 二叉树2 排序算法2.1 冒泡排序2.2 快速排序2.3 #xff08;简单#xff09;选择排序2.4 堆排序2.5 #xff08;直接#xff09;插入排序3 查找3.1 二分查找1 数据结构基础 本章所需相关基础知识#xff1a…
数据结构与算法1 数据结构基础1.1 数组1.2 链表1.3 队列1.4 栈1.5 二叉树2 排序算法2.1 冒泡排序2.2 快速排序2.3 简单选择排序2.4 堆排序2.5 直接插入排序3 查找3.1 二分查找1 数据结构基础 本章所需相关基础知识 Python基础学习笔记二—— 数据类型及操作Python基础学习笔记六—— 面向对象编程1 1.1 数组
1. 数组的基本结构
数组是最常见的一种数据结构其由有限个类型相同的变量按照一定的顺序组合构成在Python中常常利用列表list来表示数组。Python定义数组的时候与C/C中定义数组时的区别在于定义时无序指定长度可以动态增长不断向后追加元素一般不会出现数组溢出的状况为编程者带来了极大的自由度。
# 一维数组
arr1 [1, 2, 3, 4]
print(arr1) # [1, 2, 3, 4]
print(arr1[0]) # 1# 二维数组
arr2 [[1, 2, 3, 4], [5, 6, 7, 8]]
print(arr2) # [[1, 2, 3, 4], [5, 6, 7, 8]]
print(arr2[0][3]) # 4
# 一般通过如下方式定义一个二维数组
arr3 [[i for i in range(4)] for j in range(3)]
print(arr3) # [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]2. 数组的基本操作
# 定义
arr [1, 2, 3, 4, 5, 1]# 增加
# arr.append(6)
# print(arr) # [1, 2, 3, 4, 5, 1, 6]# 删除利用pop()remove()del()方法删除元素
# 1. pop([索引]) 删除指定索引对应的元素默认删除数组最后一个元素并返回该值
# arr.pop()
# arr.pop(1)
# 2. remove(元素值) 删除数组里某个值的第一个匹配项
# arr.remove(1)
# 3. del() 按照索引删除元素
# del(arr[2])
# del arr[2]# 插入
# insert(插入的索引位置插入的元素)
# arr.insert(0, 100)# 查找
# 1. 想确定数组中是否含有某一个元素
# if 200 in arr:
# print(True)
# 2. 想确定某个元素的索引index(元素值) 查找数组中该元素第一次出现的索引
# arr.index(1)# 修改
# 通过索引直接访问重新赋值即可
# arr[0] 9# 反转
# reverse()方法反转列表直接对数组进行操作没有产生额外的空间
# arr.reverse()# 排序
# sort(keyNone,reverseFalse)默认升序修改reverseTrue则为降序
# arr.sort()
# arr.sort(reverseTrue)# 清空
# 对数组进行清空输出[]
# arr.clear()# 截取
# 按步长截取顾头不顾尾
# 数组名[起始索引不写则默认包含数组开始的所有元素终止索引不写则默认包含到数组结束的所有元素步长默认为1]
# print(arr[::2]) # [1, 3, 5]
# print(arr[::-1]) # [1, 5, 4, 3, 2, 1]
# print(arr[:-1]) # [1, 2, 3, 4, 5]1.2 链表
1. 链表的基本结构
链表主要包括单向链表和双向链表这是一种无须在内存中顺序存储即可保持数据之间逻辑关系的数据结构。
链表是由一个个节点Node连接而成的每个节点都是包含数据域Data和指针域Next的基本单元。其基本元素如下
链表节点每个节点分为两部分即数据域和指针域 数据域数据域内一般存储的是整型、浮点型等数字类型指针域指针域内一般存储的是下一个节点所在的内存空间地址 头节点指向链表的第一个节点尾节点指向链表的最后一个节点None链表的最后一个节点的指针域为空
单链表
单链表的每个节点的指针域只指向下一个节点整个链表是无环的 双向链表 单向循环链表 相比于数组在链表中执行插入、删除等操作可以使得操作效率大大提高。
以单链表为例在数组内如想要删除或者插入元素到某一位置该位置之后的所有元素都需要象前或者向后移动这样一来时间复杂度就与数组的长度有关为O(n)但是在单链表中仅仅需要通过改变所要删除或者插入位置前后节点的指针域即可时间复杂度为O(1)。
2. 单链表的实现与基本操作
# 链表结点
class Node(object):def __init__(self, item):self.item itemself.next None# 单链表
class SingleLink(object):# 选择该初始化方法调用时使用 SingleLink(node)def __init__(self, nodeNone):self.head node# 选择该初始化方法调用时就不能使用上面的 SingleLink(node)初始化只能通过append添加节点# def __init__(self):# self.head None# 判断单链表是否为空def is_empty(self):if self.head is None:return Trueelse:return False# 获取链表长度def length(self):cur self.headcount 0while cur is not None:cur cur.nextcount 1return count# 遍历链表def travel(self):cur self.headwhile cur is not None:print(cur.item)cur cur.next# 链表头部增加结点def add(self, item):node SingNode(item)node.next self.headself.head node# 链表尾部增加结点注意如果链表为空链表cur是没有next的只需self.headnodedef append(self, item):node SingNode(item)if self.is_empty():self.head nodeelse:cur self.headwhile cur.next is not None:cur cur.nextcur.next node# 链表指定位置增加结点def insert(self, pos, item):if pos 0:self.add(item)elif pos self.length():self.append(item)else:node SingNode(item)cur self.headcount 0while count pos - 1:cur cur.nextcount 1node.next cur.nextcur.next node# 删除结点def remove(self, item):cur self.headpre Nonewhile cur is not None:# 找到了要删除的元素if cur.item item:# 如果要删除的位置在头部if cur self.head:self.head cur.next# 要删除的位置不在头部else:pre.next cur.nextreturn # 删除元素后及时退出循环# 没有找到要删除的元素else:pre curcur cur.next# 查找结点def search(self, item):cur self.headwhile cur is not None:if cur.item item:return Truecur cur.nextreturn False1.3 队列
1. 队列的基本结构
队列最基本的特点就是先进先出在队列尾部加入新元素在队列头部删除元素分为双端队列和一般的单端队列。 队列的作用对于任务处理类的系统即先把用户发起的任务请求接收过来存到队列中然后后端开启多个应用程序从队列中取任务进行处理队列起到了 缓冲压力 的作用 2. 队列的实现与基本操作
利用列表来简单地模拟队列
class Queue(object):def __init__(self):self.items []# 入队def enqueue(self, item):self.items.append(item)# 出队def dequeue(self):self.items.pop(0)# 队列的大小def size(self):return len(self.items)# 判断队列是否为空def is_empty(self):return self.items []对于队列这种数据结构Python的 queue 类模块中提供了一种先进先出的队列模型 Queue可以限制队列的长度也可以不限制在创建队列时利用 Queue(maxsize0)maxsize小于等于0表示不限制否则表示限制。
我们在编程的过程中也可以通过调用现有类来实现队列
from queue import Queue# 队列的定义
q Queue(maxsize0)# put() 在队列尾部添加元素
q.put(1)
q.put(2)
# print(q) # queue.Queue object at 0x0000020095EE82B0
# print(q.queue) # deque([1, 2])# get() 在队列头部取出元素返回队列头部元素
q.get()
print(q.queue) # deque([2])# empty() 判断队列是否为空
print(q.empty()) # False# full(0 判断队列是否达到最大长度限制
print(q.full()) # False# qsize() 队列当前的长度
print(q.qsize()) # 13. 双端队列的实现与基本操作
双端队列deque全名double-ended queue 是一种具有队列和栈的性质的数据结构 双端队列中的元素可以从两端弹出其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
class deque(object):def __init__(self):self.items []# 判断是否为空def is_empty(self):return self.items []# 队列的大小def size(self):return len(self.items)# 头部添加数据def add_front(self, item):self.items.insert(0, item)# 尾部添加数据def add_rear(self, item):self.items.append(item)# 头部删除数据def remove_front(self):self.items.pop(0)# 尾部删除数据def remove(self):self.items.pop()1.4 栈
1. 栈的基本结构
栈最突出的特点是先进后出其插入、删除操作均在栈顶进行。栈一般包括入栈、出栈操作并且有一个顶指针top用于指示栈顶的位置
2. 栈的实现与基本操作
class Stack(object):def __init__(self):self.items [] # 进栈def push(self, item):self.items.append(item)# 出栈def pop(self):self.items.pop()# 遍历def travel(self):for i in self.items:print(i)# 栈的大小def size(self):return len(self.items)# 栈是否为空def is_empty(self):return self.items []# return len(self.items) 0# 返回栈顶元素def peek(self):if self.is_empty():return 栈空return self.items[self.size()-1]# return self.items[-1]1.5 二叉树
1. 树
树是一种数据结构它是由 n 个有限节点组成的一个具有层次关系的集合。
树的基本性质如下 2. 二叉树的基本结构
二叉树则是每个节点最多有两个子树的树结构通常子树被称作“左子树”和“右子树”。
二叉树的一般性质
二叉树是有序的左右子树不能颠倒二叉树的第 k 层上的节点数目最多为 2k−12^{k-1}2k−1深度为 h 的二叉树最多有 2h−12^h-12h−1 个节点设非空二叉树中度为0、1 和 2 的结点个数分别为n0n_0n0 、n1n_1n1 和 n2n_2n2则 n0n21n_0 n_21n0n21 叶子结点比二分支结点多一个
其他常见的二叉树 二叉树通常以链式存储 3. 二叉树的实现与基本操作
# 定义节点类
class Node(object):def __init__(self, item):self.item itemself.lchild Noneself.rchild None# 定义二叉树
class BinaryTree(object):def __init__(self, nodeNone):self.root node思路分析首先在队列中插入根节点取出该节点再判断该节点的左右子树是否为空左子节点不空将其入队右子节点不空将其入队再分别判断左右节点的左右子节点是否为空循环往复直到发现某个子节点为空即把新节点添加进来# 添加节点def add(self, item):node Node(item)# 二叉树为空if self.root is None:self.root nodereturn# 二叉树不空queue []queue.append(self.root)while True:# 从队头取出数据node1 queue.pop(0)# 判断左节点是否为空if node1.lchild is None:node1.lchild nodereturnelse:queue.append(node1.lchild)# 判断右节点是否为空if node1.rchild is None:node1.rchild nodereturnelse:queue.append(node1.rchild)# 广度优先遍历也叫层次遍历def breadth(self):if self.root is None:returnqueue []queue.append(self.root)while len(queue) 0:# 取出数据node queue.pop(0)print(node.item, end )# 判断左右子节点是否为空if node.lchild is not None:queue.append(node.lchild)if node.rchild is not None:queue.append(node.rchild)# 深度优先遍历# 先序遍历根左右def preorder_travel(self, root):if root is not None:print(root.item, end)self.preorder_travel(root.lchild)self.preorder_travel(root.rchild)# 中序遍历左根右def inorder_travel(self, root):if root is not None:self.inorder_travel(root.lchild)print(root.item, end)self.inorder_travel(root.rchild)# 后序遍历左右根def postorder_travel(self, root):if root is not None:self.postorder_travel(root.lchild)self.postorder_travel(root.rchild)print(root.item, end)注意 广度优先遍历基于队列深度优先遍历基于栈 试试 LeetCode 相关题目吧
102. 二叉树的层序遍历144.二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历
4. 由遍历结果反推二叉树结构 2 排序算法
算法的稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变则称这种排序算法是稳定的否则称为不稳定的
不稳定的排序算法选择排序、快速排序、希尔排序、堆排序稳定的排序算法冒泡排序、插入排序、归并排序、基数排序
2.1 冒泡排序
对要进行排序的数据中相邻的数据进行两两比较将较大的数据放在后面依次对所有的数据进行操作直至所有数据按要求完成排序
如果有n个数据进行排序总共需要比较 n-1 次
每一次比较完毕下一次的比较就会少一个数据参与 def bubble_sort(lis):n len(lis)# 控制比较的轮数for j in range(n - 1):count 0# 控制每一轮的比较次数# -1是为了让数组不要越界# -j是每一轮结束之后, 我们就会少比一个数字for i in range(n - 1 - j):if lis[i] lis[i 1]:lis[i], lis[i 1] lis[i 1], lis[i]count 1# 算法优化# 如果遍历一遍发现没有数字交换退出循环说明数列是有序的if count 0:breakif __name__ __main__:lis [2, 7, 3, 6, 9, 4]bubble_sort(lis)print(lis)总结 冒泡排序是稳定的最坏时间复杂度为O(n2)O(n^2)O(n2)最优时间复杂度为O(n)O(n)O(n)遍历一遍发现没有任何元素发生了位置交换终止排序 2.2 快速排序
快速排序算法中每一次递归时以第一个数为基准数 找到数组中所有比基准数小的。再找到所有比基准数大的。小的全部放左边大的全部放右边确定基准数的正确位置。
def quick_sort(lis, left, right):# 递归的结束条件left rightif left right:return# 存储临时变量left0始终为0right0始终为len(lis)-1left0 leftright0 right# 基准值base lis[left0]# left ! rightwhile left ! right:# 从右边开始找寻小于mid的值while lis[right] base and left right:right - 1# 从左边开始找寻大于mid的值while lis[left] base and left right:left 1# 交换两个数的值lis[left], lis[right] lis[right], lis[left]# leftright# 基准数归位lis[left0], lis[left] lis[left], lis[left0]# 递归操作quick_sort(lis, left0, left - 1)quick_sort(lis, left 1, right0) # quick_sort(lis, left 1, right0)if __name__ __main__:lis [1, 2, 100, 50, 1000, 0, 10, 1]quick_sort(lis, 0, len(lis) - 1)print(lis)总结 快速排序算法不稳定最好的时间复杂度O(nlog2n)O(nlog_2n)O(nlog2n)初始序列大小均匀每一次选择的基准值将待排序的序列划分为均匀的两部分递归深度最小算法效率最高最坏的时间复杂度O(n2)O(n^2)O(n2)初始序列有序或逆序每次选择的基准值都是靠边的元素递归深度最大算法效率最低 2.3 简单选择排序
第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾以此类推直到全部待排序的数据元素的个数为零。 def select_sort(lis):n len(lis)# 控制比较的轮数for j in range(n - 1):# 假定最小值的下标min_index j# 控制每一轮的比较次数for i in range(j 1, n):# 进行比较获得最小值下标if lis[min_index] lis[i]:min_index i# 如果假定的最小值下标发生了变化那么就进行交换if min_index ! j:lis[min_index], lis[j] lis[j], lis[min_index]if __name__ __main__:lis [2, 7, 3, 6, 9, 4]select_sort(lis)print(lis)总结 选择排序是不稳定的最坏时间复杂度为O(n^2)最优时间复杂度为O(n^2) 2.4 堆排序 堆排序是不稳定的 2.5 直接插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据算法适用于少量数据的排序
插入算法把要排序的数组分成两部分
第一部分是有序的数字这里可以默认数组第一个数字为有序的第一部分第二部分为无序的数字这里除了第一个数字以外剩余的数字可以认为是无序的第二部分
def insert_sort(lis):n len(lis)# 控制比较的轮数即无序数据的个数一个数肯定是有序的不用比较for j in range(1, n):# 控制每一轮的比较次数# i取值范围[j,j-1,j-2,j-3,,,1]# 取出无序部分的首个在有序部分从后向前比较插入到合适的位置for i in range(j, 0, -1):# 找到合适的位置安放无序数据if lis[i] lis[i - 1]:lis[i], lis[i - 1] lis[i - 1], lis[i]else:breakif __name__ __main__:lis [2, 7, 3, 6, 9, 4]insert_sort(lis)print(lis)总结 直接插入排序是稳定的最坏时间复杂度为O(n^2)本身倒序最优时间复杂度为O(n)本身有序每一轮只需比较一次 3 查找
3.1 二分查找
二分查找的适用前提必须有序
非递归方法
def binary_search(lis, num):left 0right len(arr) - 1while left right:mid (left right) // 2if num lis[mid]:left mid 1elif num lis[mid]:right mid - 1else: # num arr[mid]return midreturn -1if __name__ __main__:lis [1, 3, 5, 7, 9, 10]print(binary_search(lis, 5)) # 2print(binary_search(lis, 8)) # -1递归方法
