网站营销软件,烟台企业网站开发,wordpress flickr相册,wordpress建站腾讯云说明 如果需要用到这些知识却没有掌握#xff0c;则会让人感到沮丧#xff0c;也可能导致面试被拒。无论是花几天时间“突击”#xff0c;还是利用零碎的时间持续学习#xff0c;在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢#xff1f;列表、字典、集…
说明 如果需要用到这些知识却没有掌握则会让人感到沮丧也可能导致面试被拒。无论是花几天时间“突击”还是利用零碎的时间持续学习在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢列表、字典、集合还有……栈Python 有栈吗本系列文章将给出详细拼图。
第1章ADT抽象数据类型定义数据和其操作
什么是ADT: 抽象数据类型Abstract Data Type学过数据结构的应该都知道。
如何为 ADT 选择数据结构
数据结构是否满足 ADT 域指定的存储要求数据结构是否提供数据访问和操作功能来完全实现 ADT高效执行基于复杂性分析。 下边代码是个简单的示例比如实现一个简单的Bag类先定义其具有的操作然后我们再用类的magic method来实现这些方法
class Bag:constructor: 构造函数sizecontainsappendremoveiterdef __init__(self):self._items list()def __len__(self):return len(self._items)def __contains__(self, item):return item in self._itemsdef add(self, item):self._items.append(item)def remove(self, item):assert item in self._items, item must in the bagreturn self._items.remove(item)def __iter__(self):return _BagIterator(self._items)class _BagIterator: 注意这里实现了迭代器类 def __init__(self, seq):self._bag_items seqself._cur_item 0def __iter__(self):return selfdef __next__(self):if self._cur_item len(self._bag_items):item self._bag_items[self._cur_item]self._cur_item 1return itemelse:raise StopIterationb Bag()
b.add(1)
b.add(2)
for i in b: # for使用__iter__构建用__next__迭代print(i)
# for 语句等价于
i b.__iter__()
while True:try:item i.__next__()print(item)except StopIteration:break第2章array 和 list array: 定长操作有限但是节省内存貌似我的生涯中还没用过不过python3.5中我试了确实有array类可以用import array直接导入 list: 会预先分配内存操作丰富但是耗费内存。我用sys.getsizeof做了实验。我个人理解很类似C STL里的vector是使用最频繁的数据结构。
list.append: 如果之前没有分配够内存会重新开辟新区域然后复制之前的数据复杂度退化list.insert: 会移动被插入区域后所有元素,O(n)list.pop: pop不同位置需要的复杂度不同pop(0)是O(1)复杂度,pop()首位O(n)复杂度list[]: slice操作copy数据预留空间到另一个list
来实现一个array的ADT:
import ctypesclass Array:def __init__(self, size):assert size 0, array size must be 0self._size sizePyArrayType ctypes.py_object * sizeself._elements PyArrayType()self.clear(None)def __len__(self):return self._sizedef __getitem__(self, index):assert index 0 and index len(self), out of rangereturn self._elements[index]def __setitem__(self, index, value):assert index 0 and index len(self), out of rangeself._elements[index] valuedef clear(self, value): 设置每个元素为value for i in range(len(self)):self._elements[i] valuedef __iter__(self):return _ArrayIterator(self._elements)class _ArrayIterator:def __init__(self, items):self._items itemsself._idx 0def __iter__(self):return selfdef __next__(self):if self._idex len(self._items):val self._items[self._idx]self._idex 1return valelse:raise StopIteration2.1 二维数组Two-Demensional Arrays
class Array2D: 要实现的方法Array2D(nrows, ncols): constructornumRows()numCols()clear(value)getitem(i, j)setitem(i, j, val)def __init__(self, numrows, numcols):self._the_rows Array(numrows) # 数组的数组for i in range(numrows):self._the_rows[i] Array(numcols)propertydef numRows(self):return len(self._the_rows)propertydef NumCols(self):return len(self._the_rows[0])def clear(self, value):for row in self._the_rows:row.clear(value)def __getitem__(self, ndx_tuple): # ndx_tuple: (x, y)assert len(ndx_tuple) 2row, col ndx_tuple[0], ndx_tuple[1]assert (row 0 and row self.numRows andcol 0 and col self.NumCols)the_1d_array self._the_rows[row]return the_1d_array[col]def __setitem__(self, ndx_tuple, value):assert len(ndx_tuple) 2row, col ndx_tuple[0], ndx_tuple[1]assert (row 0 and row self.numRows andcol 0 and col self.NumCols)the_1d_array self._the_rows[row]the_1d_array[col] value2.2 The Matrix ADT, m行n列。这个最好用还是用pandas处理矩阵自己实现比较*疼
class Matrix: 最好用pandas的DataFrameMatrix(rows, ncols): constructornumCols()getitem(row, col)setitem(row, col, val)scaleBy(scalar): 每个元素乘scalartranspose(): 返回transpose转置add(rhsMatrix): size must be the samesubtract(rhsMatrix)multiply(rhsMatrix)def __init__(self, numRows, numCols):self._theGrid Array2D(numRows, numCols)self._theGrid.clear(0)propertydef numRows(self):return self._theGrid.numRowspropertydef NumCols(self):return self._theGrid.numColsdef __getitem__(self, ndxTuple):return self._theGrid[ndxTuple[0], ndxTuple[1]]def __setitem__(self, ndxTuple, scalar):self._theGrid[ndxTuple[0], ndxTuple[1]] scalardef scaleBy(self, scalar):for r in range(self.numRows):for c in range(self.numCols):self[r, c] * scalardef __add__(self, rhsMatrix):assert (rhsMatrix.numRows self.numRows andrhsMatrix.numCols self.numCols)newMartrix Matrix(self.numRows, self.numCols)for r in range(self.numRows):for c in range(self.numCols):newMartrix[r, c] self[r, c] rhsMatrix[r, c]第3章Sets 和 Maps
除了list之外最常用的应该就是python内置的set和dict了。
3.1 sets ADT
集合是一个容器它存储给定可比域中唯一值的集合其中存储的值没有特定的顺序。
class Set: 使用list实现set ADTSet()length()contains(element)add(element)remove(element)equals(element)isSubsetOf(setB)union(setB)intersect(setB)difference(setB)iterator()def __init__(self):self._theElements list()def __len__(self):return len(self._theElements)def __contains__(self, element):return element in self._theElementsdef add(self, element):if element not in self:self._theElements.append(element)def remove(self, element):assert element in self, The element must be setself._theElements.remove(element)def __eq__(self, setB):if len(self) ! len(setB):return Falseelse:return self.isSubsetOf(setB)def isSubsetOf(self, setB):for element in self:if element not in setB:return Falsereturn Truedef union(self, setB):newSet Set()newSet._theElements.extend(self._theElements)for element in setB:if element not in self:newSet._theElements.append(element)return newSet3.2 Maps or Dict: 键值对,python内部采用hash实现。
class Map: Map ADT list implementionMap()length()contains(key)add(key, value)remove(key)valudOf(key)iterator()def __init__(self):self._entryList list()def __len__(self):return len(self._entryList)def __contains__(self, key):ndx self._findPosition(key)return ndx is not Nonedef add(self, key, value):ndx self._findPosition(key)if ndx is not None:self._entryList[ndx].value valuereturn Falseelse:entry _MapEntry(key, value)self._entryList.append(entry)return Truedef valueOf(self, key):ndx self._findPosition(key)assert ndx is not None, Invalid map keyreturn self._entryList[ndx].valuedef remove(self, key):ndx self._findPosition(key)assert ndx is not None, Invalid map keyself._entryList.pop(ndx)def __iter__(self):return _MapIterator(self._entryList)def _findPosition(self, key):for i in range(len(self)):if self._entryList[i].key key:return ireturn Noneclass _MapEntry: # or use collections.namedtuple(_MapEntry, key,value)def __init__(self, key, value):self.key keyself.value value3.3 The multiArray ADT, 多维数组一般是使用一个一维数组模拟然后通过计算下标获取元素
class MultiArray: row-major or column-marjor ordering, this is row-major orderingMultiArray(d1, d2, ...dn)dims(): the number of dimensionslength(dim): the length of given array dimensionclear(value)getitem(i1, i2, ... in), index(i1,i2,i3) i1*(d2*d3) i2*d3 i3setitem(i1, i2, ... in)计算下标index(i1,i2,...in) i1*f1 i2*f2 ... i(n-1)*f(n-1) in*1def __init__(self, *dimensions):# Implementation of MultiArray ADT using a 1-D # array,数组的数组的数组。。。assert len(dimensions) 1, The array must have 2 or more dimensionsself._dims dimensions# Compute to total number of elements in the arraysize 1for d in dimensions:assert d 0, Dimensions must be 0size * d# Create the 1-D array to store the elementsself._elements Array(size)# Create a 1-D array to store the equation factorsself._factors Array(len(dimensions))self._computeFactors()propertydef numDims(self):return len(self._dims)def length(self, dim):assert dim 0 and dim len(self._dims), Dimension component out of rangereturn self._dims[dim-1]def clear(self, value):self._elements.clear(value)def __getitem__(self, ndxTuple):assert len(ndxTuple) self.numDims, Invalid # of array subscriptsindex self._computeIndex(ndxTuple)assert index is not None, Array subscript out of rangereturn self._elements[index]def __setitem__(self, ndxTuple, value):assert len(ndxTuple) self.numDims, Invalid # of array subscriptsindex self._computeIndex(ndxTuple)assert index is not None, Array subscript out of rangeself._elements[index] valuedef _computeIndex(self, ndxTuple):# using the equation: i1*f1 i2*f2 ... in*fnoffset 0for j in range(len(ndxTuple)):if ndxTuple[j] 0 or ndxTuple[j] self._dims[j]:return Noneelse:offset ndexTuple[j] * self._factors[j]return offset第4章Algorithm Analysis
一般使用大O标记法来衡量算法的平均时间复杂度, 1 log(n) n nlog(n) n^2 n^3 a^n。 了解常用数据结构操作的平均时间复杂度有利于使用更高效的数据结构当然有时候需要在时间和空间上进行衡量有些操作甚至还会退化比如list的append操作如果list空间不够会去开辟新的空间操作复杂度退化到O(n)有时候还需要使用均摊分析(amortized)
