营销型网站建设总结,织梦怎么做的网站,室内设计培训课程,wordpress 显示小工具*说明 如果需要用到这些知识却没有掌握#xff0c;则会让人感到沮丧#xff0c;也可能导致面试被拒。无论是花几天时间“突击”#xff0c;还是利用零碎的时间持续学习#xff0c;在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢#xff1f;列表、字典、集… *说明 如果需要用到这些知识却没有掌握则会让人感到沮丧也可能导致面试被拒。无论是花几天时间“突击”还是利用零碎的时间持续学习在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢列表、字典、集合还有……栈Python 有栈吗本系列文章将给出详细拼图。
第5章Searching 和 Sorting 排序和查找是最基础和频繁的操作python内置了in操作符和bisect二分操作模块实现查找内置了sorted方法来实现排序操作。二分和快排也是面试中经常考到的本章讲的是基本的排序和查找。
def binary_search(sorted_seq, val): 实现标准库中的bisect.bisect_left low 0high len(sorted_seq) - 1while low high:mid (high low) // 2if sorted_seq[mid] val:return midelif val sorted_seq[mid]:high mid - 1else:low mid 1return lowdef bubble_sort(seq): # O(n^2), n(n-1)/2 1/2(n^2 n)n len(seq)for i in range(n-1):for j in range(n-1-i): # 这里之所以 n-1 还需要 减去 i 是因为每一轮冒泡最大的元素都会冒泡到最后无需再比较if seq[j] seq[j1]:seq[j], seq[j1] seq[j1], seq[j]def select_sort(seq):可以看作是冒泡的改进每次找一个最小的元素交换每一轮只需要交换一次n len(seq)for i in range(n-1):min_idx i # assume the ith element is the smallestfor j in range(i1, n):if seq[j] seq[min_idx]: # find the minist element indexmin_idx jif min_idx ! i: # swapseq[i], seq[min_idx] seq[min_idx], seq[i]def insertion_sort(seq): 每次挑选下一个元素插入已经排序的数组中,初始时已排序数组只有一个元素n len(seq)for i in range(1, n):value seq[i] # save the value to be positioned# find the position where value fits in the ordered part of the listpos iwhile pos 0 and value seq[pos-1]:# Shift the items to the right during the searchseq[pos] seq[pos-1]pos - 1seq[pos] valuedef merge_sorted_list(listA, listB): 归并两个有序数组 new_list list()a b 0while a len(listA) and b len(listB):if listA[a] listB[b]:new_list.append(listA[a])a 1else:new_list.append(listB[b])b 1while a len(listA):new_list.append(listA[a])a 1while b len(listB):new_list.append(listB[b])b 1return new_list第6章: Linked Structure list是最常用的数据结构但是list在中间增减元素的时候效率会很低这时候linked list会更适合缺点就是获取元素的平均时间复杂度变成了O(n)
# 单链表实现
class ListNode:def __init__(self, data):self.data dataself.next Nonedef travsersal(head, callback):curNode headwhile curNode is not None:callback(curNode.data)curNode curNode.nextdef unorderdSearch(head, target):curNode headwhile curNode is not None and curNode.data ! target:curNode curNode.nextreturn curNode is not None# Given the head pointer, prepend an item to an unsorted linked list.
def prepend(head, item):newNode ListNode(item)newNode.next headhead newNode# Given the head reference, remove a target from a linked list
def remove(head, target):predNode NonecurNode headwhile curNode is not None and curNode.data ! target:# 寻找目标predNode curNodecurNode curNode.dataif curNode is not None:if curNode is head:head curNode.nextelse:predNode.next curNode.next第7章Stacks 栈也是计算机里用得比较多的数据结构栈是一种后进先出的数据结构可以理解为往一个桶里放盘子先放进去的会被压在地下拿盘子的时候后放的会被先拿出来。
class Stack: Stack ADT, using a python listStack()isEmpty()length()pop(): assert not emptypeek(): assert not empty, return top of non-empty stack without removing itpush(item)def __init__(self):self._items list()def isEmpty(self):return len(self) 0def __len__(self):return len(self._items)def peek(self):assert not self.isEmpty()return self._items[-1]def pop(self):assert not self.isEmpty()return self._items.pop()def push(self, item):self._items.append(item)class Stack: Stack ADT, use linked list使用list实现很简单但是如果涉及大量push操作list的空间不够时复杂度退化到O(n)而linked list可以保证最坏情况下仍是O(1)def __init__(self):self._top None # top节点, _StackNode or Noneself._size 0 # intdef isEmpty(self):return self._top is Nonedef __len__(self):return self._sizedef peek(self):assert not self.isEmpty()return self._top.itemdef pop(self):assert not self.isEmpty()node self._topself.top self._top.nextself._size - 1return node.itemdef _push(self, item):self._top _StackNode(item, self._top)self._size 1class _StackNode:def __init__(self, item, link):self.item itemself.next link第8章Queues
队列也是经常使用的数据结构比如发送消息等celery可以使用redis提供的list实现消息队列。 本章我们用list和linked list来实现队列和优先级队列。
class Queue: Queue ADT, use list。list实现简单但是push和pop效率最差是O(n)Queue()isEmpty()length()enqueue(item)dequeue()def __init__(self):self._qList list()def isEmpty(self):return len(self) 0def __len__(self):return len(self._qList)def enquue(self, item):self._qList.append(item)def dequeue(self):assert not self.isEmpty()return self._qList.pop(0)from array import Array # Array那一章实现的Array ADT
class Queue:circular Array 通过头尾指针实现。list内置append和pop复杂度会退化使用环数组实现可以使得入队出队操作时间复杂度为O(1)缺点是数组长度需要固定。def __init__(self, maxSize):self._count 0self._front 0self._back maxSize - 1self._qArray Array(maxSize)def isEmpty(self):return self._count 0def isFull(self):return self._count len(self._qArray)def __len__(self):return len(self._count)def enqueue(self, item):assert not self.isFull()maxSize len(self._qArray)self._back (self._back 1) % maxSize # 移动尾指针self._qArray[self._back] itemself._count 1def dequeue(self):assert not self.isFull()item self._qArray[self._front]maxSize len(self._qArray)self._front (self._front 1) % maxSizeself._count - 1return itemclass _QueueNode:def __init__(self, item):self.item itemclass Queue: Queue ADT, linked list 实现。为了改进环型数组有最大数量的限制改用带有头尾节点的linked list实现。def __init__(self):self._qhead Noneself._qtail Noneself._qsize 0def isEmpty(self):return self._qhead is Nonedef __len__(self):return self._countdef enqueue(self, item):node _QueueNode(item) # 创建新的节点并用尾节点指向他if self.isEmpty():self._qhead nodeelse:self._qtail.next nodeself._qtail nodeself._qcount 1def dequeue(self):assert not self.isEmpty(), Can not dequeue from an empty queuenode self._qheadif self._qhead is self._qtail:self._qtail Noneself._qhead self._qhead.next # 前移头节点self._count - 1return node.itemclass UnboundedPriorityQueue: PriorityQueue ADT: 给每个item加上优先级p高优先级先dequeue分为两种- bounded PriorityQueue: 限制优先级在一个区间[0...p)- unbounded PriorityQueue: 不限制优先级PriorityQueue()BPriorityQueue(numLevels): create a bounded PriorityQueue with priority in range[0, numLevels-1]isEmpty()length()enqueue(item, priority): 如果是bounded PriorityQueue, priority必须在区间内dequeue(): 最高优先级的出队同优先级的按照FIFO顺序- 两种实现方式1.入队的时候都是到队尾出队操作找到最高优先级的出队出队操作O(n)2.始终维持队列有序每次入队都找到该插入的位置出队操作是O(1)(注意如果用list实现list.append和pop操作复杂度会因内存分配退化)from collections import namedtuple_PriorityQEntry namedtuple(_PriorityQEntry, item, priority)# 采用方式1用内置list实现unbounded PriorityQueuedef __init__(self):self._qlist list()def isEmpty(self):return len(self) 0def __len__(self):return len(self._qlist)def enqueue(self, item, priority):entry UnboundedPriorityQueue._PriorityQEntry(item, priority)self._qlist.append(entry)def deque(self):assert not self.isEmpty(), can not deque from an empty queuehighest self._qlist[0].priorityfor i in range(len(self)): # 出队操作O(n)遍历找到最高优先级if self._qlist[i].priority highest:highest self._qlist[i].priorityentry self._qlist.pop(highest)return entry.itemclass BoundedPriorityQueue: BoundedPriorityQueue ADT用linked list实现。上一个地方提到了 BoundedPriorityQueue但是为什么需要 BoundedPriorityQueue呢 BoundedPriorityQueue 的优先级限制在[0, maxPriority-1]对于 UnboundedPriorityQueue,出队操作由于要遍历寻找优先级最高的item所以平均是O(n)的操作但是对于 BoundedPriorityQueue用队列数组实现可以达到常量时间用空间换时间。比如要弹出一个元素直接找到第一个非空队列弹出 元素就可以了。(小数字代表高优先级先出队)qlist[0] - [white][1][2] - [black, green][3] - [purple, yellow]# Implementation of the bounded Priority Queue ADT using an array of ## queues in which the queues are implemented using a linked list.from array import Array # 第二章定义的ADTdef __init__(self, numLevels):self._qSize 0self._qLevels Array(numLevels)for i in range(numLevels):self._qLevels[i] Queue() # 上一节讲到用linked list实现的Queuedef isEmpty(self):return len(self) 0def __len__(self):return len(self._qSize)def enqueue(self, item, priority):assert priority 0 and priority len(self._qLevels), invalid priorityself._qLevel[priority].enquue(item) # 直接找到 priority 对应的槽入队def deque(self):assert not self.isEmpty(), can not deque from an empty queuei 0p len(self._qLevels)while i p and not self._qLevels[i].isEmpty(): # 找到第一个非空队列i 1return self._qLevels[i].dequeue()
