python】【Python基础】Python基础数据结构都有哪些

2020-10-19 15:18发布

6条回答
水默
2楼 · 2020-10-19 15:20

python有三种内置的数据结构:

1. list列表[ ] : 处理有序项目的列表,可以改变的,insert(x), append(x), index(x), sort(), reverse(), remove(x), count(x)

2. tuple元组() : 不可修改的列表

3. dictionary字典{} : 一系列未排序的“键值:值”的集合,在同一字典内键值是互不相同的,has_key(k), keys(), get(k)

列表、元组和字符串都是序列,但是序列是什么,它们为什么如此特别呢?序列的两个主要特点是索引操作符和切片操作符。

索引操作符让我们可以从序列中抓取一个特定项目。

切片操作符让我们能够获取序列的一个切片,即一部分序列。


天天
3楼 · 2020-10-19 18:47

Python中的内置数据结构(Built-in Data Structure):列表list、元组tuple、字典dict、集合set。

1)元组:元组是一种静态的数据结构,无法修改,若要修改只能重新生成新的元组;

2)列表:列表是我们常用的;

3)字典:字典很多方法也是跟list是一样的:

4)set集合:set集合里的元素是不能重复的,list里面的元素是可以重复的。


我想吃肉
4楼 · 2020-10-20 08:56

python语法较为简洁,正好最近在复习数据结构,索性就用python去实现吧?
本文实现的有线性表、栈、队列、串、二叉树、图、排序算法。参照教材为数据结构(C语言版)清华大学出版社,还有网上的一些大神的见解。由于包含代码在内,所以内容很多,分了几篇,话不多说,我们直接步入正题?


注:本文实验环境:Anaconda 集成 python 3.6.5 ( 故代码为 python3 )
由于本文代码过多,故每一步不做太详细的介绍,我尽量在代码中解释细节,望体谅


线性表

线性表是最基本、最简单、也是最常用的一种数据结构。它的表示形式有两种,一种为顺序表示,一种为链式表示,我们来看第一种:

线性表的顺序表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,我这里实现了很基础的操作,我们直接看代码?:

#线性表
#线性表的顺序表示
class Lnode(object):
    """节点"""
    
    def __init__(self,last):#线性表定义
        self.data = [None for i in range(100)]
        self.last = last  #线性表长度


# 1.初始化建立空的线性表
def MakeEmpty(num):
  PtrL = Lnode(num)
  return PtrL

# 2.查找给定值的位置
def Find(x, L):
  i =0
  while(i <= L.last and L.data[i] != x):
    i+=1
  if(i> L.last):
    return False  #不符合要求输出False
  else:
    return i


# 3.插入(在第i(0<=i<=n)位置上插入一个值为x的新元素)
def Insert(x,i,L):
  if i<0>L.last:
    print("位置不合理")
    return
  else:
    for j in range(L.last,i-1,-1):
      L.data[j+1] = L.data[j]
    L.data[i] = x
    L.last+=1
  return

# 4.删除第i(0<=i<=n-1)个位置上的元素
def Delete(i,L):
  if i<0>=L.last:
    print("不存在该元素")
    return
  else:
    for j in range(i,L.last-1):
      L.data[j] = L.data[j+1]
    L.last -=1
    return


# 1、测试建立空的线性表
s = MakeEmpty(10)
print(s.data[0:s.last])
print(s.last)

# 2、测试查找函数
num = [0,1,2,3,4,5,6,7,8,9]
L = Lnode(10)
for i in range(10):
  L.data[i] = num[i]
print("建立新的线性表")
print(L.data[0:L.last])
print("查找元素2")
print("下标为:")
print(Find(2,L)) #此2非彼2,这里是第二个数的意思 不是数组下标
print("查找元素12")
print("下标为:")
print(Find(12,L)) 

# 3、测试插入函数
print("在位序3插入元素6")
Insert(6,3,L)
print(L.data[0:L.last])

# 4、测试删除函数
print("删除位序5的元素")
Delete(5,L)
print(L.data[0:L.last])12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879

输出结果为:

[None, None, None, None, None, None, None, None, None, None]
10
建立新的线性表
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
查找元素2
下标为:
2
查找元素12
下标为:
False
在位序3插入元素6
[0, 1, 2, 6, 3, 4, 5, 6, 7, 8, 9]
删除位序5的元素
[0, 1, 2, 6, 3, 5, 6, 7, 8, 9]123456789101112131415

线性表的链式表示

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。(这些存储单元可以是连续的,也可以是不连续的)。对于每一个数据元素来说(这里先忽略首尾)都包含两个域,一个是存储数据元素信息的域,叫数据域,另一个是存储直接后继存储位置的域,叫做指针域,我们来看代码:

#线性表
#线性表的链式表示
class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空

# 下面创建单链表,并实现其应有的功能
class SingleLinkList(object):
    """单链表"""
    
    def __init__(self, node=None):  # 使用一个默认参数,在传入头结点时则接收,在没有传入时,就默认头结点为空
        self.__head = node
        
    def init_list(self, data):  # 按列表给出 data,初始化列表
        self.__head = Node(data[0])
        p = self.__head  # 指针指向头结点
        for i in data[1:]:
            p.next = Node(i)  # 确定指针指向下一个结点
            p = p.next  # 指针滑动向下一个位置
        
    def is_empty(self):
        '''判断链表是否为空'''
        return self.__head == None

    def length(self):
        '''链表长度'''
        cur = self.__head   # 遍历节点
        count =  0            #记录数量
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print("\n")

    def addhead(self, item):
        '''链表头部添加元素'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''链表尾部添加元素'''
        node = Node(item)
        # 由于特殊情况当链表为空时没有next,所以在前面要做个判断
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        '''指定位置添加元素'''
        if pos <= 0:
                # 如果pos位置在0或者以前,那么都当做头插法来做
            self.addhead(item)
        elif pos > self.length() - 1:
            # 如果pos位置比原链表长,那么都当做尾插法来做
            self.append(item)
        else:
            per = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                per = per.next
            # 当循环退出后,pre指向pos-1位置
            node = Node(item)
            node.next = per.next
            per.next = node

    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断该节点是否是头结点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
                
    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False
        
if __name__ == "__main__":
    #测试案例
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())
   
    ll.init_list([1,5,6,65])#传入数组
    ll.travel()         #遍历输出
    ll.append(2)        #插入尾部
    ll.travel()
    ll.addhead(999)     #插入头部
    ll.travel()
    ll.insert(-3, 110)  #如果位置比0小插入头部,比len大插入尾部
    ll.travel()
    ll.insert(99, 111)
    ll.travel()
    print(ll.is_empty())
    print(ll.length())
    ll.remove(111)
    ll.travel()
    print(ll.search(22))
    print(ll.search(65))123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128

输出结果为:

True
0
1 5 6 65 

1 5 6 65 2 

999 1 5 6 65 2 

110 999 1 5 6 65 2 

110 999 1 5 6 65 2 111 

False
8
110 999 1 5 6 65 2 

False
True123456789101112131415161718

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。栈是一种后进先出的数据结构(LIFO结构),表尾称为栈顶,表头称为栈底。最典型的例子就是你桌上的一摞书。栈有一个重要应用是在程序设计中实现递归操作,这里不详细讲述。由于python的列表操作过于强大,所以实现这个栈不是什么难事,代码如下?:

#栈

class Stack(object):
    """栈"""
    
    # 初始化栈为空列表
    def __init__(self):
        self.items = []
        
    def clearstack(self):
        self.items.clear()
        
    # 判断栈是否为空,返回布尔值
    def is_empty(self):
        return self.items == []

    # 返回栈顶元素 
    def gettop(self):
        if self.is_empty():  #一定要进行此步骤,否则会出现数组越界报错,下Pop同
            return '栈为空,无法进行你的操作'
        else:
            return self.items[-1]

    # 返回栈的大小
    def size(self):
        return len(self.items)

    # 把新的元素堆进栈里面
    def push(self, item):
        self.items.append(item)

    # 把栈顶元素丢出去,并且返回丢掉的数值
    def Pop(self):     #大写Pop防止与python中list的pop操作混淆,这里换个函数名也可以
        if self.is_empty():
            return '栈为空,无法进行你的操作'
        else:
            return self.items.pop()


if __name__ == "__main__":
    
    # 初始化一个栈对象
    my_stack = Stack()
    my_stack.push('p')
    my_stack.push('y')
    
    print (my_stack.size())
    print (my_stack.gettop())
    print (my_stack.Pop())
    my_stack.clearstack()  
    print (my_stack.gettop())
    print (my_stack.is_empty())
    my_stack.push('p')
    my_stack.push('y')
    my_stack.push('t')
    my_stack.push('h')
    my_stack.push('o')
    my_stack.push('n')
    print (my_stack.size())
    print (my_stack.Pop())
    print (my_stack.size())
    print (my_stack.is_empty())1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162

输出结果为:

2
y
y
栈为空,无法进行你的操作
True
6
n
5
False123456789

队列

队列正好和栈是相反的,它是一种先进先出的线性表(FIFO),它只允许在表的一端进行插入,在另一端删除元素,也是一种受限制的线性表,所以进行队列操作时不能删除和插入中间元素,和我们日常排队是一致的(不考虑有人插队?),最早进入的元素最先离开,允许插入的一段叫做队尾,删除的一端叫做队头,代码如下(这里实现的是链式队列):

#链式队列

class Node(object):
    def __init__(self,value):
        self.data = value
        self.next = None
 
class Queue(object):
    def __init__(self):
        self.front = Node(None)
        self.rear = self.front

    #将新元素插入队尾
    def enQueue(self,element):
        n = Node(element)
        self.rear.next = n
        self.rear = n

    #删除队头元素
    #此处注意“队列”这种数据结构不能删除中间元素
    def deQueue(self):
        if self.is_empty():
            print('队空')
            return
        temp = self.front.next
        self.front.next = self.front.next.next
        if self.rear == temp:
            self.rear = self.front
        del temp
 
    def getHead(self):
        if self.is_empty():
            return '队空,无值输出'
        return self.front.next.data
 
    def is_empty(self):
        return self.rear == self.front

    #输出列
   def printQueue(self):
        cur = self.front.next
        tmp = ''
        while cur != None:
            tmp += cur.data
            cur = cur.next
        print(tmp)

    #清空列
    def clear(self):
        while self.front.next != None:
            temp = self.front.next
            self.front.next = temp.next
        self.rear = self.front

    #列长
    def length(self):
        cur = self.front.next
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
 
if __name__ == '__main__':

    queue = Queue()
    
    queue.enQueue('p')
    queue.enQueue('y')
    queue.enQueue('t')
    queue.enQueue('h')
    queue.enQueue('o')
    queue.enQueue('n')
    
    queue.printQueue()
    print()
    print(queue.is_empty())
    print(queue.length())
    print(queue.getHead())
    
    queue.deQueue()  
    print()
    queue.printQueue()
    print()
    print(queue.getHead())
    print()
    
    queue.clear()
    print(queue.length())
    print(queue.is_empty())
    print(queue.getHead())1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192

输出结果为:

p
y
t
h
o
n

False
6
p

y
t
h
o
n

y

0
True
队空,无值输出


茄子酱
5楼 · 2020-10-20 10:23

数据结构分类

  1. 列表(list)

  2. 元组(tuple)

  3. 字典(dict)

  4. 集合(set)


有点好奇
6楼 · 2020-10-20 16:16

Python自带的数据结构可分为可变和不可变的。
可变的有:数组、集合、字典;
不可变的有:字符串、元组、数。

征戰撩四汸
7楼 · 2022-04-08 17:19

Python的数据结构:

image.png

相关问题推荐

  • 回答 1

    可以试下在cmd命令行执行,编辑器中对turtle的支持度不是很好。

  • 回答 6

    人工智能是一门起步晚却发展快速的科学。20 世纪以来科学工作者们不断寻求着赋予机器人类智慧的方法。现代人工智能这一概念是从英国科学家图灵的寻求智能机发展而来,直到1937年图灵发表的论文《理想自动机》给人工智能下了严格的数学定义,现实世界中实际要...

  • 回答 7

    代理ip网址http://www.goubanjia.com/http://www.ip181.com/https://www.kuaidaili.com/python 环境安装requests库安装bs4库proxies设置代理服务器地址proxies = {&#39;http&#39;:  &#39;http://61.155.164.110:3128&#39;}http://www.goub......

  • 回答 2

    要求:用户正确输入用户名和密码便成功登陆,分别有三次机会输入用户名和密码,超过3次便锁定分析:用两个while循环即可,代码如下:user_name = Brettpassword = 1314i = 0n = 0Is_exit = False  #进入循环标志while not Is_exit:User_name = input(please ...

  • 回答 2

    MacOS设置环境变量path的完全总结  一、MacOS加载bash shell 环境变量的加载顺序   mac 一般使用bash作为默认shell,Mac系统的环境变量,加载顺序为:1、系统级别的/etc/profile                                              ...

  • 回答 4

    当你运行代码的时候,需要你指定闹钟的时间,然后闹钟就会在指定的时间想起来。电脑pytho加载time模块,获取此时此刻的时间:import timet = time.localtime()print(t)时间是以字典的形式出现的。从字典里面提取时间信息:now = time.strftime(%H %M, t).spli...

  • 回答 5

    在几千条数据中有正负数,筛选出同一供应商下正负数相加为零的数据,正负数相加有可能为一正一负相加为零,也有可能是一正多负,也有可能一负多正,总体是将可以所有正负数相加为零的数据标注颜色出来。excel论坛上说计算量太 ...可以用pandas来处理...

  • 回答 2
    已采纳

    import sqlite3p = sqlite3.connect(file:memDB1?mode=memory&cache=shared, uri=True)p.execute('CREATE TABLE tbTest (fld1, fld2)')p.execute(INSERT INTO tbTest VALUES ('fld1', 'fld2'...

  • 回答 8

    Python虽然是解释型语言,但从设计之初就已经是一门面向对象的语言,对于Python来说一切皆为对象。正因为如此,在Python中创建一个类和对象是很容易的,当然如果习惯面向过程或者函数的写法也是可以的,Python并不做硬性的限制。...

  • 回答 4

    什么是任务         一个电脑运行这的软件     什么是多任务         电脑同时运行着的多个软件     多任务原理         时间片的轮转     并行与并发         并发:假的多任务,多个任务共用一个核       ...

  • 回答 4

    Try...except... 假如,我们已经知道这种类型的错误,那么就可以通过一个异常扑捉来扑捉这个错误。我们可以通过try...except 来接收这个错误。打开文件写入:try:     open(abc.txt,&#39;r&#39;)except IOError:    pass再来运行程序就会看不到任...

  • 回答 10

    Python用异常对象 (exception object)来表示异常情况。遇到错误后,会引发异常。如果异常对象并未被处理或捕捉,程序就会用所谓的 回溯 (traceback, 一种错误信息)终止执行。

  • 回答 5

    1.try…except…结构在Python异常处理结构中try…except…结构使用最为频繁,其中try子句中代码块为可能引发异常的语句,except子句用来捕获相应的异常。也可以解释为,当try子句代码块执行异常并且被except子句捕获,则执行except子句的代码块2.try…excep…...

  • 回答 8

    面向对象和面向过程的区别:a.面向过程:  1)根据业务逻辑从上到下写代码  2)开发思路是将数据和函数按照执行的逻辑顺序组织在一起  3)分开考虑数据与函数  定义性文字:  面向对象编程(Object Oriented Programming-OOP) 是一种解决软件复用的...

  • 回答 7

    NameVersionDescriptionPython3.3.3Python programming language with standard libraryPython 标准库astroid1.0.1Rebuild a new abstract syntax tree from Python's ast (required for pylint)colorama0.2.7Cross...

  • 回答 7

    java.lang.*java.util.*java.io.*java.net.*java.sql.*

没有解决我的问题,去提问