目的

之前学过一段时间的python，感觉受益匪浅，个人觉得python语言能火起来也有它一定的道理，所以在这里想总结一下之前所学习的知识，做一篇博客，希望其他人能从中学到知识。

简介

Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。Python 的设计具有很强的可读性，相比其他语言经常使用英文关键字，其他语言的一些标点符号，它具有比其他语言更有特色语法结构，废话不多说，直接开始。

基础知识

序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置，

或索引，第一个索引是0，第二个索引是1，依此类推。（类似数组）Python有6个序列的内置类型，但最常见的是列表和元组。序列都可以进行的操作包括索引，切片，加，乘，检查成员。此外，Python已经内置确定序列的长度以及确定最大和最小的元素的方法。列表是最常用的Python数据类型，它可以作为一个方括号内的逗号分隔值出现。列表的数据项不需要具有相同的类型。

1.列表

下面为定义三个列表L1，L2，L3，然后把L1和L2放到L3里，并且去重

L1 = []
L2 = []
L3 = []
print("请输入两个数分别代表要录入列表L1和列表L2的元素个数")
num1 = int(input())
num2 = int(input())
print("请输入列表L1的数据")
while num1 != 0:
    L1.append(int(input()))
    num1 -= 1
print("请输入列表L2的数据")
while num2 != 0:
    L2.append(int(input()))
    num2 -= 1
print("L1:",L1)
print("L1:",L2)

for i in L1:
    if not i in L3:
        L3.append(i)
for i in L2:
    if not i in L3:
        L3.append(i)

print("L3:",L3)

2.元组

元组操作与列表相似，但元组定义好之后无法修改

3.字典

一个字典变量最好记录一个物品的信息

zidian={"name":小明,
              "age":18,
            "gender":True}

4.字符与ASCII码之间的转化

Python提供了ord和chr两个内置的函数，用于字符与ASCII码之间的转换。

print ord('a')  #97
print chr(97)    #a

面向对象

Python是一门面向对象的语言，所以它有类这个结构，接下来将会介绍一下类的定义格式（对比其他面向对象语言）

1.构造函数

def __init__(self):
    print("这是构造函数")

2.析构函数

def __del__(self):
    print("这是个析构函数")

3.自定义函数

def __del__(self):
    return"这是个自定义函数"

4.对象赋值为空

new_data=None

5.身份运算符

用于判断两个对象的内存地址是否相同

id(x) is id(y)   类似 id(x) == id(y)
id(x) is not id(y)   类似 id(x) != id(y)

is用来判断 两个变量 引用对象是 否为同一个
==用来判断 引用变量的值 是否为同一个

6.定义私有属性

定义私有属性或私有函数时在变量或函数名前面加  两个下划线   __name（但是Python是没有绝对的私有的）

class TreeNode:#树节点
    def __init__(self,data):
        self.__data = data
        self.__lchild = None
        self.__rchild = None

7.类的继承

狗类继承动物类

class Animal:
    pass
class Dog(Animal):
    pass
#pass为占位符

如果子类中重写了父类的方法，在使用子类对象调用方法时调用的是子类重写的方法

8.定义类方法（通过类名调用）

@classmethod
def 类方法名(cls):
    pass

9.定义静态方法（通过类名调用）

@staticmethod
def run():
    pass

数据结构示例

1.约瑟夫环

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

import random
class Node:#定义一个链表节点类
    # __slots__=['__num','__pwd','__next']#在类中定义私有变量

    def __init__(self,num,pwd):
        self.__num = num
        self.__pwd = pwd
        self.__info = True  #用来判断人是否出队
        self.__next = None
    def setInfo(self,info):
        self.__info = info
    def setNext(self,next):
        self.__next = next
    def setNum(self,num):
        self.__num = num
    def setPwd(self,pwd):
        self.__pwd = pwd
    def getInfo(self):
        return self.__info
    def getNext(self):
        return self.__next
    def getNum(self):
        return self.__num
    def getPwd(self):
        return self.__pwd

class LinkList:#循环链表

    def __init__(self):
        self.__head = None
        self.__size = 0
    def __judgeEmpty(self):#判断链表是否存在
        return self.__head == None
    def addNode(self,num,pwd):#向链表中添加数据
        self.__size = self.__size + 1
        temp = Node(num,pwd)
        if self.__judgeEmpty():
            self.__head=temp   #若为空表，将添加的元素设为第一个元素
            self.__head.setNext(self.__head)#循环链表
        else:
            p=self.__head
            while p.getNext()!=self.__head:
                p=p.getNext()   #遍历链表
            temp.setNext(self.__head)
            p.setNext(temp)
    def yueSeFuHuan(self,m ):#约瑟夫环游戏
        p = self.__head
        n = 1
        while  True:
            if n == m and p.getInfo()== True:
                print(p.getNum())
                m = p.getPwd()
                n = 1
                p.setInfo(None)
                self.__size = self.__size - 1
            if self.__size == 0:
                break
            if p.getInfo()== True:
                n = n + 1
            p = p.getNext()   #遍历链表


num_max = int(input("请输入一个正整数代表初始报数上限数值："))
# m = random.randint(1,num_max)
while True:
    m = int(input("m="))
    if m <= 0 or m > num_max:
        print("输入错误请重新输入：")
    else:
        break
# print( m )


people_num = int(input("请输入人数："))
L = LinkList()

num = 1
while num <= people_num:
    password = int(input("请输入第 %d 个人的密码:"% num))
    L.addNode(num ,password)
    num = num + 1

print("出队次序为")
L.yueSeFuHuan(m)
# L.show()

2.数学公式运算

在这里只写了最基本的四则运算，使用栈来实现中缀表达式转后缀表达式

class SNode:    #栈的结点类
    def __init__(self):
        self.__data = None
        self.__next = None
    def set_data(self,data):
        self.__data = data
    def set_next(self,next):
        self.__next = next
    def get_data(self):
        return self.__data
    def get_next(self):
        return  self.__next

class Stack:    #栈类
    def __init__(self):
        self.top = SNode()
        self.base = SNode()
        self.count = 0
    def push(self,data):#入栈
        p = SNode()
        if self.count == 0:
            self.base = p.get_next()
        p.set_data(data)
        p.set_next(self.top)
        self.top = p
        self.count += 1
    def pop(self):
        if not self.Empty():
            print("栈已空")
            return
        temp = SNode()
        temp = self.top
        self.top = self.top.get_next()
        self.count -= 1
        return temp.get_data()
    def Empty(self):#判断栈是否为空
        # if self.top == self.base:
        if self.count == 0:
            return False
        else:
            return True
    def Top(self):  #获得栈顶元素
        p = SNode()
        p = self.top
        return p.get_data()
    def print(self):
        if not self.Empty():
            print("栈已空")
            return
        temp = SNode()
        temp = self.top
        n = 0
        while n < self.count:
            print(self.top.get_data())
            self.top = self.top.get_next()
            n += 1
        self.top = temp

def compare(n,m ):
    return n in ["*", "/"] and m in ["+", "-"]

def getValue(temp1, temp2, operator):
    if operator == "+":
        return temp1 + temp2
    elif operator == "-":
        return temp1 - temp2
    elif operator == "*":
        return temp1 * temp2
    else:
        return temp1 / temp2

def transfersReckon(St1, St2):
    operator = St2.pop()
    temp2 = St1.pop()
    temp1 = St1.pop()
    St1.push(getValue(temp1, temp2, operator))#运算结果存入栈中

def Reckon(arr):
    St1 = Stack()
    St2 = Stack()
    i = 0  # 表达式的索引值
    while i < len(arr):
        if arr[i].isdigit():  # 判断是否是数字字符
            start = i  # 数字字符开始位置
            while i + 1 < len(arr) and arr[i + 1].isdigit():
                i += 1
            St1.push(int(arr[start: i + 1]))# i为最后一个数字字符的位置
        elif arr[i] == ')':  # 右括号，St2出栈同时St1出栈并计算，计算结果入栈St1，直到St2出栈一个左括号
            while St2.Top() != '(':
                transfersReckon(St1, St2)
            St2.pop()  # 出栈"("
        elif not St2.Empty() or St2.Top() == "(":  # 操作符栈为空，或者操作符栈顶为左括号，入栈
            St2.push(arr[i])
        elif arr[i] == "(" or compare(arr[i], St2.Top()):  # 当前操作符为左括号或者比栈顶操作符优先级高，入栈St2
            St2.push(arr[i])
        else:  # 优先级不比栈顶操作符高时，St2出栈同时St1出栈并计算，计算结果如栈St1
            while St2.Empty() and not compare(arr[i], St2.Top()):
                if St2.Top() == "(":  # 若遇到左括号，停止计算
                    break
                transfersReckon(St1, St2)
            St2.push(arr[i])
        i += 1  # 遍历索引后移
    while St2.Empty():
        transfersReckon(St1, St2)
    print(St1.pop())

print("请输入表达式：")
formula = input()
Reckon(formula)

3.二叉树排序树

做了一个简单的二叉树排序树，附带前中后三种遍历方式

class TreeNode:#树节点
    def __init__(self,data):
        self.__data = data
        self.__lchild = None
        self.__rchild = None
    def set_data(self,data):
        self.__data = data
    def set_lchild(self,lchild):
        self.__lchild = lchild
    def set_rchild(self,rchild):
        self.__rchild = rchild
    def get_data(self):
        return self.__data
    def get_lchild(self):
        return self.__lchild
    def get_rchild(self):
        return self.__rchild
class BinaryTree:#二叉树

    def __init__(self):     #初始化定义树根
        self.__root = None

    def __judge_tree_root(self):    #判断树根是否存在数据
        return self.__root == None

    def add_tree_node(self,data):   #添加树的结点0
        temp = TreeNode(data)
        if self.__judge_tree_root():
            self.__root = temp
        else:
            p = self.__root
            while True:
                if data <= p.get_data():
                    if p.get_lchild() == None:
                        p.set_lchild(temp)
                        break
                    else:
                        p = p.get_lchild()
                if data > p.get_data():
                    if p.get_rchild() == None:
                        p.set_rchild(temp)
                        break
                    else:
                        p = p.get_rchild()

    def three_trversal(self):
        print("前序遍历")
        self.preorder_traversal(self.__root)
        print("中序遍历")
        self.inorder_traversal(self.__root)
        print("后续遍历")
        self.subsequent_traversal(self.__root)
    def preorder_traversal(self,tree_node):
        if tree_node:
            print(tree_node.get_data())
            self.preorder_traversal(tree_node.get_lchild())
            self.preorder_traversal(tree_node.get_rchild())
    def inorder_traversal(self,tree_node):
        if tree_node:
            self.inorder_traversal(tree_node.get_lchild())
            print(tree_node.get_data())
            self.inorder_traversal(tree_node.get_rchild())
    def subsequent_traversal(self,tree_node):
        if tree_node:
            self.subsequent_traversal(tree_node.get_lchild())
            self.subsequent_traversal(tree_node.get_rchild())
            print(tree_node.get_data())

tree =  BinaryTree()
num = int(input("请输入你要录入的数据个数:"))

while num > 0:
    data = input("请输入数据：")
    tree.add_tree_node(data)
    num -= 1

tree.three_trversal()

4.图的邻接表和深广度遍历

class QNode:
    def __init__(self):
        self.__next = None
        self.__data = None
    def set_next(self,next):
        self.__next = next
    def set_data(self,data):
        self.__data = data
    def get_next(self):
        return self.__next
    def get_data(self):
        return self.__data

class Queue:
    def __init__(self):
        self.__front = None
        self.__rear = None
        self.length = 0
    def InitQueue(self):
        self.__front = QNode()
        self.__rear = QNode()
        self.__front = self.__rear
        self.__front.set_next(None)
    def EnQueue(self,elem):#入队
        p = QNode()
        if p == None:
            exit(0)
        p.set_data(elem)
        p.set_next(None)
        self.__rear.set_next(p)
        self.__rear = p
        self.length += 1

    def DeQueue(self):#出队
        self.length -= 1
        if self.__front == self.__rear:
            return False
        #p = QNode()
        p = self.__front.get_next()
        e = p.get_data()
        self.__front.set_next(p.get_next())
        if self.__rear == p:
            self.__rear = self.__front
        return e

    def JudgeEmpty(self):#判断队列是否为空
        if self.length == 0:
            return True
        else:
            return False
class VertexNode:   #顶点结点类
    def __init__(self):
        self.__data = None
        self.__firstarc = None
    def set_data(self,data):
        self.__data = data
    def set_firstarc(self,firstarc):
        self.__firstarc = firstarc
    def get_data(self):
        return self.__data
    def get_firstarc(self):
        return self.__firstarc

class ArcNode:      #边结点类
    def __init__(self):
        self.__adjvex = None
        self.__weight = None
        self.__next = None
    def set_adjvex(self,node_data):
        self.__adjvex = node_data
    def set_weight(self,arc_weight):
        self.__weight = arc_weight
    def set_next(self,next):
        self.__next = next
    def get_adjvex(self):
        return self.__adjvex
    def get_weight(self):
        return self.__weight
    def get_next(self):
        return self.__next

class GraphAdjacencyList:        #图的邻接表类
    def __init__(self):
        self.__vertex_node = []
        self.visted = []

    def addVertexNode(self,ver_node_data):  #添加顶点
        temp = VertexNode()
        temp.set_data(ver_node_data)
        for i in self.__vertex_node:
            if i.get_data() == ver_node_data:
                return False
        self.__vertex_node.append(temp)
        self.visted.append(False)
        return True

    def addArcNode(self,ver_node1,ver_node2,arc_weight):    #添加边
        index1 = self.verNodeIndex(ver_node1)
        index2 = self.verNodeIndex(ver_node2)
        if index1 == -1 or index2 == -1 or index1 == index2:
            return False
        temp = ArcNode()
        temp.set_adjvex(index2)
        temp.set_next(self.__vertex_node[index1].get_firstarc())
        self.__vertex_node[index1].set_firstarc(temp)

        temp = ArcNode()
        temp.set_adjvex(index1)
        temp.set_next(self.__vertex_node[index2].get_firstarc())
        self.__vertex_node[index2].set_firstarc(temp)
        return True

    def verNodeIndex(self,data): #获得顶点在列表中的索引值
        num = 0
        for i in self.__vertex_node:
            if i.get_data() == data:
                return num
            num += 1
        return -1

    def travelBFS(self,data):
        length = len(self.__vertex_node)
        while length != 0:
            self.visted[length-1] = False
            length -= 1
        self.BFS(self.verNodeIndex(star_data))
        for i in self.__vertex_node:
            if self.visted[self.verNodeIndex(i.get_data())] == False:
                self.BFS(self.verNodeIndex(i.get_data()))

    def BFS(self,v):
        queue = Queue()
        queue.InitQueue()
        print(self.__vertex_node[v].get_data())
        self.visted[v] = True
        queue.EnQueue(v)
        while not queue.JudgeEmpty() :
            v = queue.DeQueue()
            p = self.__vertex_node[v].get_firstarc()
            while p:
                if not self.visted[p.get_adjvex()]:
                    print(self.__vertex_node[p.get_adjvex()].get_data())
                    self.visted[p.get_adjvex()] = True
                    queue.EnQueue(p.get_adjvex())
                p = p.get_next()

    def travelDFS(self,data):
        self.DFS(self.verNodeIndex(star_data))
        for i in self.__vertex_node:
            if self.visted[self.verNodeIndex(i.get_data())] == False:
                self.DFS(self.verNodeIndex(i.get_data()))
    def DFS(self,v):
        print(self.__vertex_node[v].get_data())
        self.visted[v] = True
        p = self.__vertex_node[v].get_firstarc()
        while p:
            u = p.get_adjvex()
            if not self.visted[u]:
                self.DFS(u)
            p = p.get_next()

    # def show_ver_node(self):
    #     for i in self.__vertex_node:
    #         print(i.get_data())


g_a_l = GraphAdjacencyList()

ver_node_num = int(input("请输入你要创建的顶点数："))
while ver_node_num > 0:
    while True:
        node_data = input("请输入顶点数据：")
        if g_a_l.addVertexNode(node_data) == True:
            break
        else:
            print("该顶点已存在请重新输入")
    ver_node_num -= 1


arc_node_num = int(input("请输入你要创建边的个数："))
while arc_node_num > 0:
    while True:
        node_data1 = input("请输入第一个结点的数据：")
        node_data2 = input("请输入第二个结点的数据：")
        arc_weight = int(input("请输入该边的权值："))
        if g_a_l.addArcNode(node_data1,node_data2,arc_weight) == True:
            break
        else:
            print("输入错误请重新输入")
    arc_node_num -= 1

print("深度优先遍历")
star_data = input("请输入一个顶点数据：")
g_a_l.travelDFS(star_data)

print("广度优先遍历")
star_data = input("请输入一个顶点数据：")
g_a_l.travelBFS(star_data)
# g_a_l.DFS(g_a_l.verNodeIndex(star_data))
# g_a_l.show_ver_node()

5.哈夫曼树

此代码使用哈夫曼树实现了简单的压缩解压

#实验五哈夫曼树

class QNode:
    def __init__(self):
        self.__next = None
        self.__trNode = None
        self.__weight = 0
    def set_weight(self,weight):
        self.__weight = weight
    def set_next(self,next):
        self.__next = next
    def set_trNode(self,trNode):
        self.__trNode = trNode
    def get_weight(self):
        return self.__weight
    def get_next(self):
        return self.__next
    def get_trNode(self):
        return self.__trNode
class Queue:
    def __init__(self):
        self.__first = QNode()
        self.__size = 0
    def set_first(self,first):
        self.__first=first
    def set_size(self,size):
        self.__size=size
    def get_first(self):
        return self.__first
    def get_size(self):
        return self.__size

    def createQueue(self,list):
        for i in list:
            aux = htNode()          #创建一个树结点对象
            aux.set_lchild(None)
            aux.set_rchild(None)
            aux.set_data(i.get_data())#赋值
            self.EnQueue(aux,i.get_weight())#插入队列
            #aux待插入的结点，i.get_weight()代表字符的权值
    def EnQueue(self,aux,weight):#入队
        temp = QNode()
        temp.set_weight(weight)
        temp.set_trNode(aux)
        if self.__size==0:
            temp.set_next(None)
            self.__first = temp
            self.__size += 1
            return
        else:
            if weight <= self.__first.get_weight():
                temp.set_next(self.__first)
                self.__first = temp
                self.__size += 1
                return
            else:
                iterator = QNode()
                iterator = self.__first
                while iterator.get_next()!=None:
                    if weight<=iterator.get_next().get_weight():
                        temp.set_next(iterator.get_next())
                        iterator.set_next(temp)
                        self.__size += 1
                    iterator = iterator.get_next()
                if iterator.get_next() == None:
                    temp.set_next(None)
                    iterator.set_next(temp)
                    self.__size += 1
                    return
    def getQueue(self):
        returnValue = htNode()
        if self.__size>0:
            returnValue = self.__first.get_trNode()
            self.__first = self.__first.get_next()
            self.__size -= 1
        else:
            print("空队列")
        return returnValue

class htNode:   #哈夫曼树节点类
    def __init__(self):
        self.__data = None
        self.__lchild = None
        self.__rchild = None
    def set_data(self,data):
        self.__data = data
    def set_lchild(self,lchild):
        self.__lchild = lchild
    def set_rchild(self,rchild):
        self.__rchild = rchild
    def get_data(self):
        return self.__data
    def get_lchild(self):
        return self.__lchild
    def get_rchild(self):
        return self.__rchild
class htTree:   #哈夫曼树
    def __init__(self):
        self.__root = htNode()
    def get_root(self):
        return self.__root
    def three_trversal(self):
        print("中序遍历")
        self.inorder_traversal(self.__root)
    def inorder_traversal(self,tree_node):
        if tree_node:
            self.inorder_traversal(tree_node.get_lchild())
            print(tree_node.get_data())
            self.inorder_traversal(tree_node.get_rchild())

    def BuildTree(self,list):
        huffmanQueue = Queue()#创建初始化队列
        huffmanQueue.createQueue(list)

        while huffmanQueue.get_size()!=1:
            weigth = huffmanQueue.get_first().get_weight()#新节点的权值
            weigth += huffmanQueue.get_first().get_next().get_weight()
            lchild = htNode()
            rchild = htNode()
            lchild = huffmanQueue.getQueue()
            rchild = huffmanQueue.getQueue()
            newNode = htNode()
            newNode.set_lchild(lchild)
            newNode.set_rchild(rchild)
            huffmanQueue.EnQueue(newNode,weigth)
        self.__root = huffmanQueue.getQueue()

class hlNode:       #编码链表的的节点类
    def __init__(self):
        self.__data = None
        self.__code = []
        self.__next = None
    def set_data(self,data):
        self.__data = data
    def set_code(self,code,k):
        n = 0
        while n<k:
            self.__code.append(code[n])
            n += 1
    def set_next(self,next):
        self.__next = next
    def get_data(self):
        return self.__data
    def get_next(self):
        return self.__next
    def get_code(self):
        return self.__code
class hlEncode:     #编码类

    def __init__(self):
        self.__first = None
        self.__last = None
    def BuildList(self,huffmanTree):
        code = []
        k = 0
        self.traverseTree(huffmanTree.get_root(),k,code)
    def traverseTree(self,treeNode,k,code):
        if treeNode.get_lchild() == None and treeNode.get_rchild() == None:
            aux = hlNode()
            aux.set_code(code,k)
            aux.set_data(treeNode.get_data())
            aux.set_next(None)
            # print(code)
            # print(treeNode.get_data())
            if self.__first == None:
                self.__first = aux
                self.__last = aux
            else:
                self.__last.set_next(aux)
                self.__last = aux
        #左0   右1
        if treeNode.get_lchild() != None:
            code.append('0')
            if k <len(code):
                code[k] = '0'
            self.traverseTree(treeNode.get_lchild(),k+1,code)
        if treeNode.get_rchild() !=None:
            code.append('1')
            if k <len(code):
                code[k] = '1'
            self.traverseTree(treeNode.get_rchild(),k+1,code)
    def encode(self,list):
        if self.__first == None:
            return False

        traversal = hlNode()
        traversal = self.__first
        for i in list:
            traversal = self.__first
            while traversal.get_data()!=i.get_data():
                traversal = traversal.get_next()
            print(traversal.get_data(),":",traversal.get_code())
        return True
    def decode(self,tree,list):
        if tree.get_root()==None:
            print("1")
            return False
        traversal = tree.get_root()#临时根
        for i in list:
            if traversal.get_lchild()==None and traversal.get_rchild()==None:
                print(traversal.get_data())
                traversal = tree.get_root()
            if i == '0':
                traversal = traversal.get_lchild()
            if i == '1':
                traversal = traversal.get_rchild()
            if i!='0'and i!='1':
                print("2")
                return False

            #防止编码最后一次不输出
            if traversal.get_lchild() == None and traversal.get_rchild() == None:
                print(traversal.get_data())
                traversal = tree.get_root()
        print()
        return True
class Elem:
    def __init__(self,data,weight):
        self.__data = data
        self.__weight = weight
    def set_data(self,data):
        self.__data = data
    def set_weight(self,weight):
        self.__weight = weight
    def get_data(self):
        return self.__data
    def get_weight(self):
        return self.__weight


tree = htTree()#哈夫曼树
encoding = hlEncode()#编码
while True:
    print()
    print("创建编码表输入1")
    print("显示编码表输入2")
    print("显示哈夫曼树输入3")
    print("解码输入4")
    n = int(input("请输入你的选择："))
    if n==1:
        num = int(input("请输入字符集大小："))
        list = []
        while num>0:
            elem = Elem(input("请输入字符："),int(input("请输入字符代表的权值：")))
            list.append(elem)
            num -= 1
        tree.BuildTree(list)
        encoding.BuildList(tree)
    elif n==2:
        if encoding.encode(list):
            print("显示成功")
        else:
            print("操作失败")
    elif n==3:
        tree.three_trversal()
    elif n==4:
        coding = str(input("请输入编码："))
        if encoding.decode(tree,coding):
            print("解码成功")
        else:
            print("解码失败")
    else:
        break