Python数据结构

数据结构

线性数据结构

Array

• 概念
  Element+Index
  
• 表示

from array import *
arrayName = array(typecode, [Initializers])

ASCII码：英文字母一个字节，中文两个字节，八位二进制数
UTF-8：英文字符（含标点）一个字节，中文字符（含标点）三个字节。
Unicode：中英文及其标点均是两个字符。

• 基本方法
  遍历：

for i in array:
    print(i)

插入

array.insert(index_num,content)

删除

array.remove(content)

搜索

array.index(content)

更新

array[index_num]=content

二维数组

数组嵌套实现。
[array1,array2.....]

• 访问数组
  多次索引
  要打印完整的二维数组值可使用for循环

for i in T:
    for j in i:
        print(c,end = " ")
    print()

• 更新/删除
  方法同普通list操作

Node

节点，类似于指针的作用，数据和数据元素的下一个位置的地址也会被存储，内存分配到非连续块中，是链表和树的基础。
创建实现一个保存指针和数据元素的类来实现的。
创建和遍历：

#定义和初始化类
class mint:
    def __init__(self,deta=None):
        self.data = data
        self.next = None
#创建数据
e1 = mint('Mon')
e2 = mint('Tue')
e3 = mint('wed')
#创建指针
e1.next = e3
e3.next = e2
#遍历元素
this = e1
while this:
    print(this.data)
    this = this.next

Linked List

• 概念
  一系列数据元素，通过链接连接在一起，每个数据元素以指针的形式包含到另一个元素的连接。实现方法为通过节点实现

单链表

• 基本操作
  创建链表：

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
class SLinkedList:
    def __init__(self):
        self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3

或者

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
class SLinkedList:
    def __init__(self):
        self.head = None
    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.LListprint()

遍历：

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next

插入：

def AtBegining(self,newdata):
        NewNode = Node(newdata)
# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return
        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

删除：

def RemoveNode(self, Removekey):
        HeadVal = self.head
        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return
        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next
        if (HeadVal == None):
            return
        prev.next = HeadVal.next
        HeadVal = None

双链表

双链表：第一个和最后一个的链接元素，每个链表有一个数据字段和两个被称为next和prev的链接字段。每个链接可与上一个链接和下一个链接链接，最后一个链表使用空来标记列表的结尾。
在单链表的基础上添加prev标记
插入、附加

Stack

堆栈，后进先出
添加和删除元素的操作称为PUSH和POP操作

class Stack:
    def __init__(self):
        self.stack = []
    def add(self, dataval):
        if dataval not in self.stack:
            self.stack.append(dataval)
            return True
        else:
            return False
    def peek(self):     
        return self.stack[-1]
    def remove(self):
        if len(self.stack) <= 0:
            return ("No element in the Stack")
        else:
            return self.stack.pop()

Queue

队列

先进先出
insert()添加pop()删除移除元素

双端队列

双端队列可从任一端添加和删除元素
collections模块

import collections

创建双端队列：collections.deque(list)
append()
appendleft()
clear() copy()
count() extend() extendleft()
insert() pop() popleft()
remove() reverse()

Matrix

使用numply进行矩阵数据管理。

from numpy import *
a =array([['wen',1,2,3,1],['hai',4,5,6,4],['ping',7,8,9,7]]) #多中括号

• 矩阵格式转换
  reshape(array,(n,m)) n行m列
• 矩阵值访问
  参照list
• 末尾追加添加行
  append(array,[[]],0) 0表示行，中间矩阵行表示需要使用双中括号，只能添加到最后一行。
• 插入
  insert(array,[n],[[]],1)
  insert(array,[m],[[]],0)
  0表示行，1表示列，n、m表示选取的位置
• 删除
  detele(array,[q],1)
  delete(array,[p],0)
  0表示行，1表示列，p,q表示选取的位置
• 更新
  array[n]=[] 更新时需使用序列。

非线性数据结构

Binary Tree

二叉树
树结构：仅有一个父节点
定义左节点和右节点，插入树中

二叉搜索树：
BST：Binary Search Tree
节点的左子树小于等于其父节点的值，节点的右子树大于其父节点的值

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

搜索的基本过程是按大小左右搜索

Heap

堆：
每个父节点小于或等于其子节点，最小堆；每个父节点大于或等于子节点，最大堆。
创建堆：
heapq库：heapify常规列表转换为堆，最小元素索引0；heappush堆在最后的索引处添加一个元素而不改变当前堆；heappop返回堆中最小的数据元素，索引为0；heapreplace用新值替换最小的数据元素，在未被修复的地方插入新值。

Hash Table

散列表
数据元素的地址或索引值是由散列函数生成的，哈希表存储键值对，密钥通过哈希函数生成。
通过字典类型实现哈希表（密钥）：
字典键可散列，具备唯一值生成结果，字典数据元素顺序不固定。

Graph

一组对象通过链接连接的一组对象的图形表示。互连对象为顶点，连接顶点的链接为边。
基本操作：
显示图形顶点：直接获取图形字典的关键字
显示图形边缘：遍历顶点关系，获取图形关系集合列表
添加顶点：新定义一个键
添加边缘：添加顶点
创建图

Python特征数据结构

list

• 概念
  通用，不限于元素数据类型
• 表示
  [initializers]

• 基本操作
  取值
  list[index_num]
  更新
  list[index_num]=content
  删除
  del list[index_num] or list.remove(content)

• 函数方法
  分片
  [a:b:c]：a起始值，b终止值，c分片间隔
  列表嵌套
  函数：len() max() min() list(seq)#整数、浮点树、布尔值不能转换为list。
  方法：
  list.append() 末尾追加
  list.count(content) 统计元素出现次数
  list.extend(list)末尾追加列表
  list.index()寻找索引
  list.insert(index,obj)
  list.pop(index) 移除列表中的元素，默认移除最后一个，并返回该元素的值
  list.remove(obj) 移除第一个匹配项
  list.reverse() 元素反向
  list.sort(key = None，reverse = False)#key为函数、reverse反序与否
  list.copy()复制列表
  list.clear()清空列表
  

  

tuple

• 概念
  不可变元素序列。
• 表示
  (n,m,q....)
  使用,创建元组。
• 基本操作
  除不变性（删除单一元素，更新元素）外，其它性质与list一致。
  len(tuple)
  max(tuple)
  min(tuple)
  tuple(seq)

Dictionary

• 概念
  键值对，键唯一，键为不可变数据类型，值可以是任意类型。

• 表示
  {key1:value1,key2:value2,key3:value3}
  字典key属性值无限制，但需要保证不重复key（重复会选取最后一个），key值使用不可变类型。

• 基本操作
  访问
  dict[key1]、dict.get(key，default=None)
  更新（修改或添加）
  dict[key]=value
  删除
  del dict[key] 、del dict、dict.clear()

• 函数方法
  len()、str()、type()
  dict.clear() 删除字典里所有元素
  dict.copy() 浅复制
  dict.fromkeys() 创建新字典，以序列中元素做字典的键，val为键对应的初始值
  key in dict 返回布尔值
  dict.items() 以列表返回键值元组
  dict.keys() 返回字典的键；dict.values() 返回字典的所有值。
  dict.setdefalut(key,default) 取键，键不在字典里设置为default值。
  dict.update(dict2) 以dict2的值来更新dict中的值
  pop(key[,default]) 删除字典key所对应的值，返回被删除的值。
  popitem()
  随机返回并删除键值对（一般删除末尾对）。

Set

set([])创建集合
访问集合值=循环打印
添加：add()
删除：discard()
集合运算：并| 交& 差- 比较<=>

Reference

URL

https://www.tutorialspoint.com/python/python_data_structure_introduction.htm