精华内容
下载资源
问答
  • 数据结构学习笔记:利用Python列表实现栈结构利用Python列表实现栈结构。有两种实现方式:1、将列表的末尾(rear)作为栈顶(top)2、将列表的前端(front)作为栈顶(top)一、将列表的末尾(rear)作为栈顶(top)来实现栈结构...

    数据结构学习笔记:利用Python列表实现栈结构

    利用Python列表实现栈结构。有两种实现方式:

    1、将列表的末尾(rear)作为栈顶(top)

    2、将列表的前端(front)作为栈顶(top)

    一、将列表的末尾(rear)作为栈顶(top)来实现栈结构

    1、编写源代码:利用列表创建栈01.py

    07c0418aa90d820f47e6815b38bd2709.png

    """

    利用列表创建栈01

    在列表末尾作为栈顶

    """

    class Stack:

    def __init__(self):

    self.items = []

    def isEmpty(self):

    return self.items == []

    def push(self, item):

    self.items.append(item)

    def pop(self):

    return self.items.pop()

    def peek(self):

    return self.items[len(self.items)-1]

    def size(self):

    return len(self.items)

    def __str__(self):

    return str(self.items)

    s = Stack()

    print(s)

    print("isEmpty:", s.isEmpty())

    s.push('dog')

    s.push('cat')

    s.push('tiger')

    print(s)

    print("isEmpty:", s.isEmpty())

    print("size:", s.size())

    print("pop:", s.pop())

    print(s)

    print("size:", s.size())

    s.push(100)

    s.push(True)

    print(s)

    print("peek:", s.peek())

    print(s)

    print("size:", s.size())

    2、查看程序运行结果

    22e72e31930258b315eef483b5296e6d.png

    二、将列表的前端(front)作为栈顶(top)来实现栈结构

    1、编写源代码:利用列表创建栈02.py

    9927bfb0dbe92924e2764efb840cbcac.png

    2、查看程序运行结果

    e51652ab2760d29d7a7d7a67e62fe621.png

    三、栈结构的特点:LIFO(后进先出)

    e2d7fe324920ca5c1b24f2892d2c7b33.png

    本文分享 CSDN - howard2005。

    如有侵权,请联系 support@oschina.cn 删除。

    本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

    展开全文
  • Python列表实现

    2020-05-08 16:41:15
    # Python列表实现栈 class Stack(): def __init__(self): self.items = [] # 用于print def __str__(self): return str(self.items) # 入栈 def push(self,item): ...
    # Python列表实现栈
    class Stack():
        def __init__(self):
            self.items = []
            
        # 用于print    
        def __str__(self): 
            return str(self.items)
        # 入栈    
        def push(self,item):
            self.items.append(item)
        # 出栈    
        def pop(self):
            return self.items.pop()
            
        # 查看栈顶    
        def peek(self):
            return self.items[len(self.items)-1]
    	# 是否为空        
        def isEmpty(self):
            return self.items==[]
        # 栈的大小
        def size(self):
            return len(self.items)
            
    if __name__=="__main__":
        s = Stack()
        print("s",s)
        print(s.isEmpty())
        s.push(4)
        print("s",s)
        s.push('dog')
        print("s",s)
        print("peek",s.peek())
        s.push(True)
        print(str(s),"size",s.size())
        print('isEmoty',s.isEmpty())
        s.push(8.4)
        print("pop",s.pop())
        print("pop",s.pop())
        print(s,"size",s.size())
    
    

    输出:

    s []
    True
    s [4]
    s [4, 'dog']
    peek dog
    [4, 'dog', True] size 3
    isEmoty False
    pop 8.4
    pop True
    [4, 'dog'] size 2
    
    展开全文
  • 本文将介绍列表在 CPython中的实现,因为毕竟Cpython 又是 Python 最为常用的实现Python 中的列表非常强大,看看它的内部实现机制是怎么样的,一定非常有趣。下面是一段 Python 脚本,在列表中添加几个整数,然后...

    本文将介绍列表在 CPython中的实现,因为毕竟Cpython 又是 Python 最为常用的实现。

    Python 中的列表非常强大,看看它的内部实现机制是怎么样的,一定非常有趣。

    下面是一段 Python 脚本,在列表中添加几个整数,然后打印列表。

    Python

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    >>>l=[]

    >>>l.append(1)

    >>>l.append(2)

    >>>l.append(3)

    >>>l

    [1,2,3]

    >>>foreinl:

    ...printe

    ...

    1

    2

    3

    可以发现,列表是一个迭代器。

    列表对象的 C 语言结构体

    Cpython 中的列表实现类似于下面的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

    Python

    1

    2

    3

    4

    5

    typedefstruct{

    PyObject_VAR_HEAD

    PyObject**ob_item;

    Py_ssize_t allocated;

    }PyListObject;

    列表初始化

    看看初始化一个空列表的时候发生了什么,例如:l = []。

    Python

    1

    2

    3

    4

    5

    6

    7

    8

    9

    arguments:size of the list=0

    returns:listobject=[]

    PyListNew:

    nbytes=size*size of globalPython object=0

    allocate newlistobject

    allocate listof pointers(ob_item)of size nbytes=0

    clear ob_item

    setlist‘sallocated var to0=0slots

    returnlistobject

    要分清列表大小和分配的槽大小,这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小,这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。

    Append 操作

    向列表添加一个整数:l.append(1) 时发生了什么?调用了底层的 C 函数 app1()。

    Python

    1

    2

    3

    4

    5

    6

    7

    arguments:listobject,newelement

    returns:0ifOK,-1ifnot

    app1:

    n=size of list

    call list_resize()to resize the listto sizen+1=0+1=1

    list[n]=list[0]=newelement

    return0

    下面是 list_resize() 函数。它会多申请一些内存,避免频繁调用 list_resize() 函数。列表的增长模式为:0,4,8,16,25,35,46,58,72,88……

    Python

    1

    2

    3

    4

    5

    6

    7

    arguments:listobject,newsize

    returns:0ifOK,-1ifnot

    list_resize:

    new_allocated=(newsize>>3)+(newsize<9?3:6)=3

    new_allocated+=newsize=3+1=4

    resize ob_item(listof pointers)to size new_allocated

    return0

    现在分配了 4 个用来装列表元素的槽空间,并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。

    列表追加元素操作的平均复杂度为 O(1)。

    9be6105e06faf46655d6e330828b70fc.png

    继续添加新的元素:l.append(2)。调用 list_resize 函数,参数为 n+1 = 2, 但是因为已经申请了 4 个槽空间,所以不需要再申请内存空间。再添加两个整数的情况也是一样的:l.append(3),l.append(4)。下图显示了我们现在的情况。

    28f06c9d44c355031a6d5254318a8374.png

    Insert 操作

    在列表偏移量 1 的位置插入新元素,整数 5:l.insert(1,5),内部调用ins1() 函数。

    Python

    1

    2

    3

    4

    5

    6

    7

    arguments:listobject,where,newelement

    returns:0ifOK,-1ifnot

    ins1:

    resize listto sizen+1=5->4more slots will be allocated

    starting at the last element up to the offset where,right shift each element

    setnewelement at offset where

    return0

    e2eb7999988c7c363cddcc78ebae99a6.png

    虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间,但是列表的大小却只是 5。

    列表插入操作的平均复杂度为 O(n)。

    Pop 操作

    取出列表最后一个元素 即l.pop(),调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数,如果取出元素后列表的大小小于分配的槽空间数的一半,将会缩减列表的大小。

    Python

    1

    2

    3

    4

    5

    6

    7

    8

    arguments:listobject

    returns:element popped

    listpop:

    iflistempty:

    returnnull

    resize listwithsize5-1=4.4isnotless than8/2so no shrinkage

    setlistobjectsize to4

    returnlast element

    列表 pop 操作的平均复杂度为 O(1)。

    83a66122a9f6afb1addee684888bfaed.png

    可以看到 pop 操作后槽空间 4 依然指向原先的整数对象,但是最为关键的是现在列表的大小已经变为 4。

    继续 pop 一个元素。在 list_resize() 函数中,size – 1 = 4 – 1 = 3 已经小于所分配的槽空间大小的一半,所以缩减分配的槽空间为 6,同时现在列表的大小为 3。

    可以看到槽空间 3 和 4 依然指向原先的整数,但是现在列表的大小已经变为 3。

    657c86484b2acd23d9113f673cdb9f23.png

    Remove 操作

    Python 的列表对象有个方法,删除指定的元素: l.remove(5)。底层调用 listremove() 函数。

    Python

    1

    2

    3

    4

    5

    6

    7

    8

    arguments:listobject,element to remove

    returns noneifOK,null ifnot

    listremove:

    loop through each listelement:

    ifcorrect element:

    slicelistbetween element‘s slot and element‘sslot+1

    returnnone

    returnnull

    为了做列表的切片并且删除元素,调用了 list_ass_slice() 函数,它的实现方法比较有趣。我们在删除列表位置 1 的元素 5 的时候,低位的偏移量为 1 同时高位的偏移量为 2.

    Python

    1

    2

    3

    4

    5

    6

    7

    arguments:listobject,low offset,high offset

    returns:0ifOK

    list_ass_slice:

    copyinteger5to recycle listto dereference it

    shift elements fromslot2to slot1

    resize listto5slots

    return0

    列表 remove 操作的复杂度为 O(n)。

    0052a4e909ac7f02caa390d750cbaa35.png

    全能程序员交流QQ群290551701,群内程序员都是来自,百度、阿里、京东、小米、去哪儿、饿了吗、蓝港等高级程序员 ,拥有丰富的经验。加入我们,直线沟通技术大牛,最佳的学习环境,了解业内的一手的资讯。如果你想结实大牛,那 就加入进来,让大牛带你超神!

    原文:http://www.cnblogs.com/fengliucaizi/p/4914277.html

    展开全文
  • 利用python列表实现单链表

    千次阅读 2014-10-31 10:42:46
    利用python列表实现单链表

        利用python列表实现单链表

        C语言中单链表是了;利用结构体和指针操作实现的,python是面向对象编程,我们可以创建一个Node类来实现链表,利用类的属性引用来代替指针操作。

            下面的代码创建了一个节点类,然后编写了几个链表创建,插入,删除,输出的函数方法:

                 

                下面代码编写了测试的部分,手工输入要插入的位置和值以及删除的位置

               

              运行结果如下:

             

    展开全文
  • 在开发中对列表去重是非常常见的需求,列表去重也是Python...那么Python列表去重要怎么做呢?列表去重的方式有很多,下面介绍4种方式,并对其进行性能比较。让我们先制造一些简单的数据,生成0到99的100万个随机数:...
  • 使用LINQ功能扩展python列表实现干净,快速的编码
  • 数据结构学习笔记:利用Python列表实现栈结构 利用Python列表实现栈结构。有两种实现方式: 1、将列表的末尾(rear)作为栈顶(top) 2、将列表的前端(front)作为栈顶(top) 一、将列表的末尾(rear)作为...
  • Python列表实现斐波那契数列

    千次阅读 2020-02-10 00:00:00
    i = eval(input("请输入第几项:")) list1 = [0,1] n = 2 while True: list.append(list1[-1]+list1[-2]) n = n+1 if n == i: print(list1[-1]) break 运行效果 结语 对于python中的编程题,我们可已用多种方法解决...
  • 原文标题和地址:python实现堆栈、队列 https://www.cnblogs.com/shenbuer/p/7841626.html
  • python3列表 python中,列表是一种使用频率很高的数据结构,有点类似于C++的数组,但是功能似乎又比数组更加强大,用法更加灵活,可能是我C++没有学到位吧!在这里就不介绍数组了,因为列表本身就是一个加强版的数组...
  • 方法一: 通过切片来实现列表倒序 list =[1,2,3,4,5,6] list1=list[::-1] print (list1) 方法二: 通过reverse() 函数用于反向列表中元素 aList = [123, 'xyz', 'zara', 'abc', 'xyz'] aList.reverse() ...
  • 斐波那契数列(fibonacci) 题目:有个人想知道,一年之内一对兔子能繁殖多少对?于是就筑了一道围墙把一对兔子关在里面。已知一对兔子每个月可以生一对小兔子,而一对兔子从出生后第3个月起每月生一对小兔子。...
  • S.is_empty():判断栈是否为空 len(S):返回栈中元素的数量 1.3 栈的 Python List 实现: class Error(Exception): pass class ArrayStack: def __init__(self): self.__data = [] def __len__(self): return len...
  • # 自己实现了之后,发现有现成的方法可以调用。 # 以下将自己写的与网上百度到的都放到这里。 # PART1 自己写的 # 思路:每次弹出(pop)序列中的一个元素,让其依次(遍历)与余下的元素组合 def comb(a, seq): """ ...
  • python 列表实现字典的get功能

    千次阅读 2019-06-13 10:35:53
    有时候用列表时也想有类似的操作,则可以将列表转为字典就可以进行类似操作。 list_a = [0, 1] d = dict(enumerate(list_a)) print d.get(3, 3) # 获取索引为3的值,如果不存在则默认为3 ...
  • python列表实现斐波那契数列的计算

    千次阅读 2020-02-10 09:48:30
    我们可以使用列表来作为存储数列的数据结构,每增加一个数列项,就在数列的后面使用append增加一项。然后用最后一项除以倒数第二项获得比值。 对于求和,土方法是设计一个变量,每生成一个新的比例值,就把这个值...
  • python列表实现括号匹配

    千次阅读 2016-01-27 14:19:17
    假设我们有一些复杂的表达式,里边包含了多种括号的嵌套,这个时候去肉眼判断括号匹配是一件非常令人蛋疼的事情,那么,怎么用python来进行基本的判断呢,答案很简单,就是用python中的list来模拟栈结构进行判断。
  • class PyQueue: def __init__(self, size=20): self.queue = [] self.size = size self.end = -1 def SetSize(self, size): self.size = size def In(self, element): ...
  • " + self.name) print("学号:" + self.ID) print("成绩:" + self.score) 存储信息的数据结构设计好了,接下来实现管理系统的基本功能,我们将这些部分封装为不同的函数,函数的参数为可变类型的列表: 增 #向列表...
  • 字典有一个很好用的方法,就是get,既可以预防KeyError异常,也可以为不存在的key设置一个默认的value ...如果想在列表实现字典的get方法的功能,可以这样: l = [0, 1] d = dict(enumerate(l)) print d.ge...
  • def list_sort(list): for i in range(len(list)-1): for j in range(len(list)-1-i): if list[j] < list[j+1]: num = list[j] list[j] = list[j+1] ...
  • 书上说的是:列表实现可以是数组和链表。顺序表是怎么回事?顺序表一般是数组。列表是一个线性的集合,它允许用户在任何位置插入、删除、访问和替换元素。列表实现是基于数组或基于链表结构的。当使用列表迭代器的...
  • 请问一个python 列表逆序打印的问题。今天在python教程上看到一个列表逆序输出的列子: lists = [1,2,3] prinprint li[1:] #输出[2,3,4,5,6,7],省略终止索引,表示取起始索引之后的所有值,等效于li[1:len(li)] ...
  • 本身排序可以用python的内置函数sort和sorted,但题目的要求是手动实现。看起来很简单,实现的发现并不容易,花了半个小时才调试好。解题思路:1.将列表中的第1个元素放入新列表,然后将元素的索引存入索引列表,...
  • python列表实现

    2018-10-11 12:02:11
    从数据结构的角度来看,python列表是通过线性表来实现的,进一步来讲,是 动态的顺序表来实现list的。 那我们就应该首先讲一下什么是动态的顺序表? 顺序表分为两类-----一体式顺序表和动态的顺序表, 动态的顺序表...
  • class Loop_Queue2(object):'''实现循环列表'''def __init__(self,maxsize):'''初始化,命令头部元素的序号,尾部元素的序号,定义序列列表:param maxsize: 传入列表的最大长度'''self.queue=[None]*maxsizeself....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,766
精华内容 6,706
关键字:

python列表实现

python 订阅