合肥义城建设集团有限公司网站,网上做平面设计的网站,企业信息系统公示,wordpress 帮助手册算法其他篇 目录#xff1a; 1.1 数据结构中的一些概念1.2 栈#xff08;stack#xff09;1.3 队列1.4 链表1.5 python中字典对象实现原理1.6 数组1.1 数据结构中的一些概念 返回顶部 1、数据结构是什么 1、简单来说#xff0c;数据结果就是设计数据以何种方式存储在计…算法其他篇 目录 1.1 数据结构中的一些概念1.2 栈stack1.3 队列1.4 链表1.5 python中字典对象实现原理1.6 数组1.1 数据结构中的一些概念 返回顶部 1、数据结构是什么 1、简单来说数据结果就是设计数据以何种方式存储在计算机中 2、比如列表集合与字典等都是一种数据结构 3、程序 数据结构 算法 1.2 栈stack 返回顶部 1、栈的定义 栈是一种数据集合可以理解为只能在一端进行插入或删除操作的列表 2、栈的特点 后进先出last-in, first-out 3、栈的概念 栈顶栈底 4、栈的基本操作 进栈压栈push 出栈pop 取栈顶gettop 5、栈的使用匹配括号是否成对出现 def check_kuohao(s):stack []for char in s:if char in [(,[,{]:stack.append(char)elif char ):if len(stack)0 and stack[-1] (:stack.pop()else:return Falseelif char ]:if len(stack) 0 and stack[-1] [:stack.pop()else:return Falseelif char }:if len(stack) 0 and stack[-1] {:stack.pop()else:return Falseif len(stack) 0:return Trueelse:return False
print(check_kuohao((){}{}[])) #True 匹配括号是否成对出现 1.3 队列 返回顶部 1、队列定义 1、队列是一个数据集合仅允许在列表的一端进行插入另一端进行删除 2、插入的一端称为队尾rear插入动作叫进队或入队 3、进行删除的一端称为对头front删除动作称为出队 4、队列性质先进先出First-in, First-out 5、双向队列队列的两端都允许进行进队和出队操作 2、对列使用方法 1、导入 from collectios import deque 2、创建队列queue deque(li) 3、进队 append 4、出队 popleft 5、双向队列队首进队appendleft 6、双向队列队尾出队pop 3、双向对列原理图 1、 环形对列当对位指针front Maxsize 1 时再进一个位置就自动到0 2、 实现方法求余数运算 3、 队首指针前进1 front (front 1)%MaxSize 4、 队尾指针前进1rear (rear1)%MaxSize 5、 队空条件rear front 6、 队满条件rear1%MaxSize front 1.4 链表 返回顶部 1、单链表 注链表中每个元素都是一个对象每个对象称为一个节点包含有数据域key和指向下一节点的指针next通过各个节点间的相互连接最终串联成一个链表 #! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):def __init__(self, item):self.item itemself.next Noneclass DLinkList(object):def __init__(self):self._head Nonedef is_empty(self):return self._head Nonedef append(self, item):尾部追加元素node Node(item)if self.is_empty():self._head nodeelse:cur self._headwhile cur.next ! None:cur cur.nextcur.next nodedef add(self, item):头部插入元素node Node(item)if self.is_empty():self._head node # 如果是空链表将_head指向nodeelse:node.next self._head # 将node的next指向_head的头节点self._head node # 将_head 指向nodedef travel(self):cur self._headwhile cur ! None:print cur.item,cur cur.nextprint def remove(self, item):删除元素if self.is_empty():returnelse:cur self._headif cur.item item:# 如果首节点的元素即是要删除的元素if cur.next None: # 如果链表只有这一个节点self._head Noneelse: # 将_head指向第二个节点self._head cur.nextreturnwhile cur ! None:if cur.next.item item:cur.next cur.next.nextbreakcur cur.nextdef insert(self, pos, item):在指定位置添加节点if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:node Node(item)cur self._headcount 0# 移动到指定位置的前一个位置while count (pos - 1):count 1cur_next cur.next# 将node的next指向cur的下一个节点cur.next nodenode.next cur_nextdef length(self):返回链表的长度cur self._headcount 0while cur ! None:count 1cur cur.nextreturn countif __name__ __main__:ll DLinkList()# 1、将链表后面追加三个元素1,2,3ll.append(1)ll.append(2)ll.append(3)ll.travel() # 1 2 3# 2、将链表头部插入一个元素0ll.add(0)ll.travel() # 1 2 3 0 1 2 3# 3、删除链表中的元素3ll.remove(3)ll.travel() # 0 1 2 3 0 1 2# 4、在链表的第2号位置插入元素8ll.insert(2,8)ll.travel() # 0 1 2 0 8 1 2 单链表增删改查 #! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):def __init__(self, val):self.val valself.next Nonedef list_reverse(head):if head None:return NoneL, R, cur None, None, head # 左指针、有指针、游标while cur.next ! None:L R # 左侧指针指向以前右侧指针位置R cur # 右侧指针前进一位指向当前游标位置cur cur.next # 游标每次向前进一位R.next L # 右侧指针指向左侧实现反转cur.next R # 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)return curif __name__ __main__:原始链表1 - 2 - 3 - 4反转链表4 - 3 - 2 - 1l1 Node(1)l1.next Node(2)l1.next.next Node(3)l1.next.next.next Node(4)l list_reverse(l1)print l.val # 4 反转后链表第一个值4print l.next.val # 3 第二个值3 链表反转 #! /usr/bin/env python
# -*- coding: utf-8 -*-
class ListNode(object):def __init__(self, val, nextNone):self.val valself.next next# 归并法: 对链表排序
class Solution:def sortList(self, head):if head is None or head.next is None:return headpre headslow head # 使用快慢指针来确定中点fast headwhile fast and fast.next:pre slowslow slow.nextfast fast.next.nextleft headright pre.nextpre.next None # 从中间打断链表left self.sortList(left)right self.sortList(right)return self.merge(left, right)def merge(self, left, right):pre ListNode(-1)first prewhile left and right:if left.val right.val:pre.next leftpre leftleft left.nextelse:pre.next rightpre rightright right.nextif left:pre.next leftelse:pre.next rightreturn first.nextnode1 ListNode(4)
node2 ListNode(3)
node3 ListNode(2)
node4 ListNode(1)node1.next node2
node2.next node3
node3.next node4s Solution()
result s.sortList(node1)while (result ! None):print result.val, # 1 2 3 4result result.next 链表排序归并排序算法实现 #!/usr/bin/env python
# -*- coding:utf-8 -*-
def mergesort(seq):if len(seq) 1:return seqmid int(len(seq) / 2)left mergesort(seq[:mid])right mergesort(seq[mid:])return merge(left, right)def merge(left, right):result []i, j 0, 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result left[i:]result right[j:]return resultif __name__ __main__:seq [10,4,6,3,8,2,5,7]print mergesort(seq) # [2, 3, 4, 5, 6, 7, 8, 10] 对python列表排序归并排序 对比 2、双链表 注双链表中每个节点有两个指针一个指针指向后面节点、一个指向前面节点 #! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):双向链表节点def __init__(self, item):self.item itemself.next Noneself.prev Noneclass DLinkList(object):双向链表def __init__(self):self._head Nonedef is_empty(self):判断链表是否为空return self._head Nonedef length(self):返回链表的长度cur self._headcount 0while cur ! None:count 1cur cur.nextreturn countdef travel(self):遍历链表cur self._headwhile cur ! None:print cur.item,cur cur.nextprint def add(self, item):头部插入元素node Node(item)if self.is_empty():# 如果是空链表将_head指向nodeself._head nodeelse:# 将node的next指向_head的头节点node.next self._head# 将_head的头节点的prev指向nodeself._head.prev node# 将_head 指向nodeself._head nodedef append(self, item):尾部插入元素node Node(item)if self.is_empty():# 如果是空链表将_head指向nodeself._head nodeelse:# 移动到链表尾部cur self._headwhile cur.next ! None:cur cur.next# 将尾节点cur的next指向nodecur.next node# 将node的prev指向curnode.prev curdef search(self, item):查找元素是否存在cur self._headwhile cur ! None:if cur.item item:return Truecur cur.nextreturn Falsedef insert(self, pos, item):在指定位置添加节点if pos 0:self.add(item)elif pos (self.length() - 1):self.append(item)else:node Node(item)cur self._headcount 0# 移动到指定位置的前一个位置while count (pos - 1):count 1cur cur.next# 将node的prev指向curnode.prev cur# 将node的next指向cur的下一个节点node.next cur.next# 将cur的下一个节点的prev指向nodecur.next.prev node# 将cur的next指向nodecur.next nodedef remove(self, item):删除元素if self.is_empty():returnelse:cur self._headif cur.item item:# 如果首节点的元素即是要删除的元素if cur.next None:# 如果链表只有这一个节点self._head Noneelse:# 将第二个节点的prev设置为Nonecur.next.prev None# 将_head指向第二个节点self._head cur.nextreturnwhile cur ! None:if cur.item item:# 将cur的前一个节点的next指向cur的后一个节点cur.prev.next cur.next# 将cur的后一个节点的prev指向cur的前一个节点cur.next.prev cur.prevbreakcur cur.nextif __name__ __main__:ll DLinkList()ll.add(1)ll.add(2)# ll.append(3)# ll.insert(2, 4)# ll.insert(4, 5)# ll.insert(0, 6)# print length:,ll.length()# ll.travel()# print ll.search(3)# print ll.search(4)# ll.remove(1)print length:,ll.length()ll.travel() 双链表增删改查 #! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):def __init__(self, item):self.item itemself.next Noneself.prev Noneclass DLinkList(object):def __init__(self):self._head Nonedef is_empty(self):return self._head Nonedef append(self, item):node Node(item)if self.is_empty():self._head nodeelse:cur self._headwhile cur.next ! None:cur cur.nextcur.next nodenode.prev curdef travel(self):cur self._headwhile cur ! None:print cur.item,cur cur.nextif __name__ __main__:ll DLinkList()ll.append(1)ll.append(2)ll.append(3)# print ll._head.item # 打印第一个元素1# print ll._head.next.item # 打印第二个元素2# print ll._head.next.next.item # 打印第三个元素3ll.travel() # 1 2 3 双链表追加和遍历 1.5 python中字典对象实现原理 返回顶部 注字典类型是Python中最常用的数据类型之一它是一个键值对的集合字典通过键来索引关联到相对的值理论上它的查询复杂度是 O(1) 1、哈希表 (hash tables) 1. 哈希表也叫散列表根据关键值对(Key-value)而直接进行访问的数据结构。 2. 它通过把key和value映射到表中一个位置来访问记录这种查询速度非常快更新也快。 3. 而这个映射函数叫做哈希函数存放值的数组叫做哈希表。 4. 通过把每个对象的关键字k作为自变量通过一个哈希函数h(k)将k映射到下标h(k)处并将此对象存储在这个位置。 2、具体操作过程 1. 数据添加把key通过哈希函数转换成一个整型数字然后就将该数字对数组长度进行取余取余结果就当作数组的下标 将value存储在以该数字为下标的数组空间里。 2. 数据查询再次使用哈希函数将key转换为对应的数组下标并定位到数组的位置获取value。 3、{“name”:”zhangsan”,”age”:26} 字典如何存储的呢? 1. 比如字典{“name”:”zhangsan”,”age”:26}那么他们的字典key为name、age假如哈希函数h(“name”) 1、h(“age”)3, 2. 那么对应字典的key就会存储在列表对应下标的位置[None, “zhangsan”, None, 26 ] 4、解决hash冲突 5、python字典操作时间复杂度 1.6 数组 返回顶部 1、数组定义 1. 所谓数组就是相同数据类型的元素按一定顺序排列的集合 2. 在Java等其他语言中并不是所有的数据都能存储到数组中只有相同类型的数据才可以一起存储到数组中。 3. 因为数组在存储数据时是按顺序存储的存储数据的内存也是连续的所以他的特点就是寻址读取数据比较容易插入和删除比较困难。 2、python中list与数组比较 1. python中的list是python的内置数据类型list中的数据类不必相同的而array的中的类型必须全部相同。 2. 在list中的数据类型保存的是数据的存放的地址简单的说就是指针并非数据 3. 这样保存一个list就太麻烦了例如list1[1,2,3,a]需要4个指针和四个数据增加了存储和消耗cpu。 转载于:https://www.cnblogs.com/xiaonq/p/8574655.html
