Python学习日志之Python数据结

2023-01-31 03:01:56 数据 学习 日志

python数据结构初识:

一、Python数据结构概述

1.何为数据结构

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

例如:

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


2.数据结构实例

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


#实例:

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

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

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

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


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

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


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

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


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

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


二、Python常见数据结构-栈

1.何为栈

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

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

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


2.栈的图示

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


3.Python中栈的实现

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

#实例:

#栈的实现:

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


 

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中队列的实现

#队列的实现
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.树的基本构造

#树通过逗号,隔开

#树是由列表构成的,实际上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)

'''

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
>>> 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中链表的实现

#链表的实现(单向链表)
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
>>> 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

#(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
>>> =============================== 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中图的实现

#图的实现
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  #找到新结点的时候返回值
>>> =============================== RESTART ===============================
>>> 
>>> path(chart,"A","E")
['A', 'D', 'C', 'E']
>>>

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





相关文章