Python学习日志之Python数据结构初识

rgewr2

Python数据结构初识：

一、Python数据结构概述

1.何为数据结构

   在程序中，同样的一个或几个数据组织起来，可以有不同的组织方式，也就是不同的存储方式，不同的组织方式就是不同的结构，我们把这些数据组织在一起的结构就叫做数据结构

例如：

   有一串字符串："abc"，我们将它重新组织一下，比如通过list()函数将"abc"变成["a","b","c"]，那么这个时候数据发生了重组，重组之后的结构就发生了变化，我们把["a","b","c"]这种结构叫做列表，也就是说列表是数据结构的一种类型之一。数据结构除了列表之外还有元组()，字典｛""："",｝、队列、栈、树等。

2.数据结构实例

    Python中的数据结构有很多类型。其中，Python中系统自己定义的不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组等，而有一些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义这些数据的组织方式，这些组织方式称为Python的扩展数据结构，比如栈、队列等。

#实例：

#Python内置的数据结构有元组、列表、字典等。

#现在有三个物品，分别是"apple","orange","pear"，需要把这三个物品存储起来

#存储方式1：这三个物品每个物品按顺序分别存储到一个柜子里，这些物品可以取出来，如下：可以修改

1	["apple","orange","pear"]

#存储方式2：这三个物品每个物品按顺序分别存储到一个柜子里，但是物品不可以取出来，也不可以放到其他柜子，如下，其实就是不可修改

1	("apple","orange","pear")

#存储方式3：这三个物品不仅按顺序存储到一个柜子里，而且每个柜子还有一个名词

1	{"sam":"apple","jac":"orange","mating":"pear"}

3.数据结构和算法的关系

    在程序设计中，我们会发现数据结构经常和算法合在一起，这是为什么呢？其实，数据结构是数据的组织方式，就是存储方式，也就是说，数据结构是静态的。算法是指运算方法，通俗的说，就是运算思维，程序是动态的，需要将数据进行计算，运算方法有很多，不同的运算方法叫做不同的算法，所以我们可以这样理解：数据结构是算法的基础，但相同的数据结构运用不同的算法拥有不同的效率

二、Python常见数据结构-栈

1.何为栈

    栈是一种数据结构，这种数据结构不同于系统自带的内置数据结构，属于扩展数据结构，需要自己定义

特点：栈相当于一端开口一端封闭的容器，数据A可以存储在栈里面，把数据A移动到里面这个过程叫做进栈，也叫压栈、入栈

    如果数据A到达栈顶后，同是占了栈的一个位置，当再进入一个数据B的时候，也将到达栈顶，然后使A到栈顶的下一个位置，栈只能对栈顶的数据进行操作，此时就不能对A进行操作，可以将B出栈或删除，等B出栈后，A变成栈顶的时候就可以对A进行操作

2.栈的图示

   只能从开口进开口出，栈顶指向新数据的位置，栈底不变，用过栈顶指针的移动进行数据的进栈出栈。

3.Python中栈的实现

   栈是列表的扩展，只是栈只能从栈顶进行修改，不像列表可以从任意地方

#实例：

#栈的实现：

#栈是列表的扩展，只是栈只能从栈顶进行修改，不像列表可以从任意地方

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Stack():             #定义栈的类      def __init__(st,size): #初始化函数，两个形参，一个代表主体，一个代表容 量          st.stack=[];       #声明了栈          st.size=size;      #声明栈的容量          st.top=-1;         #初始与栈底重合的栈顶      def push(st,content):  #入栈定义          if st.Full():              print"Stack is Full"          else:             st.stack.append(content)  #入栈，数据进入，append增加内容，调用 append方法             st.top=st.top+1           #栈顶指针加1      def out(st):          if st.Empty():              print"Stack is Empty!"          else:              st.top=st.top-1                   def Full(st):          #判断栈是否Full          if st.top==st.size:              return True    #栈满          else:              return False      def Empty(st):          if st.top==-1:              print"Stack is Empty!"

三、Python常见数据结构-队列

1.何为队列

    队列也是一种扩展的数据结构

特点：两端开的开口容器，但是只能在一端进行删除操作，不能进行插入操作，而另一端只能进行插入操作而不能进行删除操作，进行插入的这端叫做队尾，进行删除操作的这端叫做队首

    数据是队尾进队首出，类似于排队

    队首队尾不是根据位置来区别的，是根据功能来区分的

2.队列的图示

    队尾进队首出

    进队：qu.tail=qu.tail+1

    出队：qu.head=qu.head+1

3.Python中队列的实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#队列的实现 class Queue():                  #队列类     def __init__(qu,size):      #初始化信息，队列主体qu，队列容量size         qu.queue=[];            #用列表声明         qu.size=size;           #传递进来的参数信息         qu.head=-1;             #刚开始的队首队尾都在输出方         qu.tail=-1;     def Empty(qu):              #先判断是否为空         if qu.head==qu.tail:    #空的时候队首队尾指针参数             return True         else:             return False     def Full(qu):               #判断队列是否已满         if qu.tail-qu.head+1==qu.size:             return True         else:             return False     def enQueue(qu,content):    #进队         if qu.Full():             print "Queue is Full!"         else:             qu.queue.append(content)             qu.tail=qu.tail+1   #进队只和队尾相关，队尾指针加1     def outQueue(qu):           #出队         if qu.Empty():             print "Queue is Empty!"         else:             qu.head=qu.head+1   #出队指针只和队首相关，队首加1

四、Python常见数据结构-树

1.何为树:

    树是一种非线性的数据结构，树具有非常高的层次性。利用树来存储数据，能够是用公有元素进行存储，能够很大程度上节约空间。

定义：有且只有一个根节点，其次有N个不相交的子集，每个子集为一颗子树

2.树的图示：

3.什么是二叉树：

    二叉树市一中特殊的树，二叉树要么是空树，要么是左、右两个不相交的子树组成，二叉树是有序树，即使只有一个子树，也需要区分该子树是左子树还是右子树。二叉树每个节点的度不可能大于2，可以取0,1,2。二叉树的存储方式有两种，一种是顺序方式，一种是链式存储。

顺序存储采用一维数组的存储方式

链式存储中，采用表的存储方式，通常分为三部分：数据域，左孩子链域和右孩子链域

4.二叉树的图示：

有5种情况，加上空树

5.Python中树以及二叉树的实现：通过列表表示

#1.树的基本构造

#树通过逗号，隔开

1 2 3 4 5 6 7 8 9 10 11 12 13

#树是由列表构成的，实际上Tree2=[58,6,[5]],Tree3=[5] Tree=[2,3,[58,6,[5]]] print Tree[0] print Tree[1] print Tree[2] Tree2=Tree[2] print Tree2[0] >>> 2 3 [58, 6, [5]] 58#实现了树的嵌套，子树 >>>

#2.二叉树的构造

'''

比如要构造一个二叉树：

      7

  8       9

   23       36

57   58

可以这样分析：

节点（左节点，右节点，当前节点数据）

根节点base=(-->8也就是jd2,-->9也就是jd3,base)

jd2=(no,-->23也就是jd4,8)

jd3=(no,-->36也就是jd5,9)

jd4=(-->57也就是jd6,-->58也就是jd7,23)

jd5=(no,no,36)

jd6=(no,no,57)

jd7=(no,no,58)

但是要注意，写的时候倒过来写，就是从右叶子开始写，直到根节点

jd7=(no,no,58)

jd6=(no,no,57)

'''

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class TRee():    #树的初始化     def __init__(self,leftjd=0,rightjd=0,data=0):         self.leftjd=leftjd;         self.rightjd=rightjd;         self.data=data; class Btree():  #二叉树的初始化     def __init__(self,base=0):         self.base=base     def empty(self):         if self.base is 0:             return True         else:             return False     def qout(self,jd):         """前序遍历，NLR，根左右"""         if jd==0:             return   #没有节点的话，原样返回         print jd.data  #先返回根节点的值         self.qout(jd.leftjd)  #访问左节点         self.qout(jd.rightjd) #访问右节点     def mout(self,jd):         """中序遍历，LNR，左根右"""         if jd==0:             return         self.mout(jd.leftjd)         print jd.data         self.mout(jd.rightjd)     def hout(self,jd):         """后序遍历，LRN，左右根"""         if jd==0:             return         self.hout(jd.leftjd)         self.hout(jd.rightjd)         print jd.data

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

>>> jd1=TRee(data=8) >>> jd2=TRee(data=9) >>> base=TRee(jd1,jd2,7) >>> x=Btree(base)  #调用Btree >>> x.qout (x.base) #前序遍历NLR根左右 7 8 9 >>> x.mout (x.base) #中序遍历LNR左根右 8 7 9 >>> x.hout (x.base) #后序遍历LRN左右根 8 9 7 >>>

五、Python常见数据结构-链表

1.何为链表

    链表也是一种数据结构，链表是一种非连续，非顺序的存储方式，链表由一系列节点组成，每个节点包括两个部分，一部分是数据域，另一个部分是指向下一节点的指针域，链表可以分为单向链表,单向循环链表，双向链表，双向循环链表。

单向链表：a可以指向b，但是b不能指向a

单向循环链表：表头和表尾首尾相连，仍是单项

双向链表：a可以指向b，b也可以指向a

双向循环链表：首尾相连，可以顺时针，也可以逆时针

2.链表的图示

指针域：指向下一个节点的位置

节点之间是不相连的

3.Python中链表的实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#链表的实现（单向链表） class jd():   #节点类，存储数据     def __init__(self,data):  #初始化         self.data=data         self.next=None  #最初的时候不指向       class Linklist():  #链表类，实现链表作用     def __init__(self,jd2):  #初始化         self.head=jd2        #把jd2传到表头         self.head.next=None  #下一个位置         self.tail=self.head  #初始化表头表尾重合     def add(self,jd2):       #增加链表节点         self.tail.next=jd2   #将节点2赋值到链表尾         self.tail=self.tail.next     def view(self):          #查看链表的所有情况         jd2=self.head        #表头         linkstr=""           #节点的数据，转化成字符串，然后不断累加         while jd2 is not None:  #节点2不为空，开始             if jd2.next is not None: #节点2下一个节点不为空，开始遍历                 linkstr=linkstr+str(jd2.data)+"-->"  #开始遍历节点             else:                 linkstr+=str(jd2.data)             jd2=jd2.next         print linkstr    #打印出链表linkstr

1 2 3 4 5 6 7 8 9

>>> jd1=jd(7) >>> jd2=jd("hello") >>> jd3=jd(8) >>> x=Linklist(jd1) >>> x.add (jd3) >>> x.add (jd2) >>> x.view () 7-->8-->hello >>>

六、Python常见数据结构-bitmap：通过数组表示

1.何为bitmap

    同样，bitmap也是一种数据结构。bit指的是位，map指的是图，bitmap也叫是位图。这种数据结构的存储简单来说就是把原来的数转化成二进制来存储，每个位占一个存储单元。我们对bitmap进行数据操作时，也就相当于操作一个位。bitmap的数据结构的优点是可以实现很好的排序

2.bitmap的图示

最高位为符号位，Python中一个数是32位，最右边为最低位，位图上存在数就变成1，不存在就是0

00000000 00000000 00000000 00000101

2^2+2^0=5，上面是数字5的二进制形式，实际上bitmap和二进制数值是有差异的

def bitIndex(self, num): #位索引，算出数值所在单元

        return num % 31   

3.Python中bitmap的实现

（1）.bitmap排序原理：

例如：请比较1，2，34的大小（出去符号位最高位在左边）

数组1：可以存储31个数，除去符号位，范围1-31

数组2：可以存储31个数，除去符号位，范围32-62

1：存储到数组1，2^0

2：存储到数组1，2^1

34：存储到数组2，34-32=2，再加1，就是数组2第三位

首先：数组2的大于数组1，从右往左依次增大

开始时bitmap为0，当所对应的位置存在数据时，就开始映射到bitmap对应位置，位置

上的0变成1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#（2）.bitmap的实现 class Bitmap():     def __init__(self, max): #最大的数         self.size  = int((max+31 - 1) / 31) #计算所需要的数组个数         self.array = [0 for i in range(self.size)]  #从数组中开始生成单元， 每个单元存储的值都是0               def bitIndex(self, num): #位索引，算出数值所在单元         return num % 31              def set(self, num):      #置1         elemIndex =num / 31  #判断所在数组         byteIndex = self.bitIndex(num)   #计算位索引         elem= self.array[elemIndex]      #对应选择的数组         self.array[elemIndex] = elem |(1 << byteIndex)  #置1，向左移动的次数     def test(self, i):         elemIndex = i / 31   #判断在第几个数组         byteIndex = self.bitIndex(i)         if self.array[elemIndex] & (1 << byteIndex): #判断是否在bitmap，不应 该超出范围             return True         return False    if __name__ == '__main__':     MAX = ord('z')  #设置最大数为‘z’使用ord转化成ansll     suffle_array = [x for x in 'coledraw'] #将单词拆分     result       = []     bitmap = Bitmap(MAX) #将MAX传递到Bitmap     for c in suffle_array:  #从c开始调用到set         bitmap.set(ord(c))     for i in range(MAX + 1):           if bitmap.test(i):    #如果存在i中存在数值，进行依次调用到test             result.append(chr(i))        print '原始数组为:    %s' % suffle_array #拆分后的数组     print '排序后的数组为: %s' % result

1 2 3 4 5 6

>>> =============================== RESTART =============================== >>> >>> 原始数组为:    ['c', 'o', 'l', 'e', 'd', 'r', 'a', 'w'] 排序后的数组为: ['a', 'c', 'd', 'e', 'l', 'o', 'r', 'w'] >>>

七、Python常见数据结构-图

1.何为图

    图仍是一种数据结构，我们可以简单的理解成一个关系网络，该网络中有N多结点，每个结点都存储着一个数据，数据之间的关联我们可以用线把关联的结点连起来的方式进行表示。

    其中，有的数据关系是有方向的，比如数据A-->数据B，其关系只能从A到B，而不能从B到A，如果数据之间的关系是有方向，我们在图里面用带箭头弧线表示。有的数据关系是没有方向的，A--B表示既可以从A关联到B，也可以B关联A，这种没有方向的关系用线段表示。

2.图的图示

    不同的结点之间有的有直接联系，有的通过中间结点有间接联系  

3.Python中图的实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#图的实现 chart={"A":["B","D"],"C":["E"],"D":["C","E"]}#图通过字典表示 #"A"：["B","D"]:A-->B,A-->D #"C":["E"]:C-->E #"D":["C","E"]:D-->C,D-->E def path(chart,x,y,pathd=[]): #chart:图 #x:起始结点 #y:指向结点 #pathd=[]:走过的路径     pathd=pathd+[x]  #初始结点     if x==y:         return pathd  #返回pathd     if not chart.has_key(x):  #判断是否存在结点         return None           for jd in chart[x]:   #结点在chart所直接对应的结点         if jd not in pathd:             newjd=path(chart,jd,y,pathd) #初始结点变成jd，寻找路径             if newjd:                 return newjd  #找到新结点的时候返回值

1 2 3 4 5

>>> =============================== RESTART =============================== >>> >>> path(chart,"A","E") ['A', 'D', 'C', 'E'] >>>

与之共勉，入门学习，需要持之以恒。