神出鬼没的Enderman

数据结构

什么是数据结构

数据结构是计算机存储、组织数据的方式。主要描述数据元素和元素之前的逻辑关系以及在计算机中的存储形式。数据结构指的是数据元素及数据元素之间的相互关系，或组织数据的形式。

• 数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称
• 数据元素是数据的基本单位，又称之为记录（Record）。一般，数据元素由若干基本项（如姓名、年龄等）组成

数据之间的结构关系

逻辑结构

• 表示数据之间的抽象关系（如邻接关系、从属关系等），按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。如: 栈、队列、二叉查找树、B+树、红黑树、图等

物理结构(存储结构)

• 逻辑结构在计算机中的具体实现方法，分为顺序存储方法、链接存储方法、散列存储、树状存储等方法。如: 顺序表、链表等

逻辑结构和物理结构的关系

• 每种逻辑结构采用何种特理结构来实现并没有明确的规定，甚至某些特殊情况下，同一种逻辑结构可能需要多种物理结构配合实现

逻辑结构

• 只是描述数据结构中数据元素之间的联系规律
• 是从具体问题中抽象出来的数学模型，是独立于计算机存储器的（与机器无关）
• 逻辑结构分为四种类型：线性结构，树形结构，图形结构，集合结构

逻辑结构分类

• 线性结构,对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合

• 树形结构（层次结构）,树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构，是一类重要的非线性数据结构。在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个

• 图状结构（网状结构）,图是一种比较复杂的数据结构。在图结构中任意两个元素之间都可能有关系，也就是说这是一种多对多的关系

• 集合结构,除了以上几种常见的逻辑结构外，数据结构中还包含其他的结构，比如集合等。有时根据实际情况抽象的模型不止是简单的某一种，也可能拥有更多的特征

物理结构（存储结构）

物理结构又叫存储结构，分为四种：顺序存储结构、链式存储结构、索引结构、散列结构

• 是数据的逻辑结构在计算机存储器中的映象（或表示）
• 存储结构是通过计算机程序来实现的，因而是依赖于具体的计算机语言的

常用的存储结构

• 顺序存储（Sequential Storage）：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。
• 链式存储（Linked Storage）：将数据结构中各元素分布到存储器的不同点，用记录下一个结点位置的方式建立它们之间的联系，由此得到的存储结构为链式存储结构。

线性结构的物理存储

顺序存储结构

若将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间，这种机制表示为线性表的顺序存储结构

优点

• 逻辑上数据元素都是相邻的，请宽度相等，可以用索引随机访问
• 存储密度高，方便对数据的遍历查找

缺点

• 对表的插入和删除等运算的效率较差

在Python中，list存放于一片单一连续的内存块，故可借助于列表类型来描述线性表的顺序存储结构，而且列表本身就提供了丰富的接口满足这种数据结构的运算

>>>L = [1,2,3,4]
>>>L.append(10)      #尾部增加元素
L
[1, 2, 3, 4, 10]

>>>L.insert(1,20)    #插入元素
L
[1, 20, 2, 3, 4, 10]

>>>L.remove(3)       # 删除元素
L
[1, 20, 2, 4, 10]     

>>>L[4] = 30         # 修改
L
[1, 20, 2, 4, 30]

>>>L.index(2)        # 查找
2
>>> del L[1]        # 删除指定位置的数据元素

链式存储结构

链式存储结构是指使用一组不连续的存储单元依次存储各个元素，在每个元素的存储空间内部用额外的空间(指针或引用)来存储各个元素之间的关系。也就是物理上不要求连续，逻辑上连续。链式存储结构中将每个元素存放在彼此独立的存储单元中，该存储单元称为节点，通常这些节点中增加一个或多个指针来记录前趋或后继节点的地址，以此保证逻辑上的连续

• 旧金山大学数据结构可视化网站

优点

1. 大小动态扩展，存储稀疏，不必开辟整块存储空间。
2. 插入删除效率高

缺点

1. 不能随机访问。
2. 查找元素速度慢。

链表的分类

• 单向线性链表
• 双向线性链表
• 双向环型链表

链表的基本操作

class LinkList:
    def __init__(self, iterable=None):
        self.__head = None

    def __str__(self):
        '''转为字符串'''

    def append(self, val):
        '''末尾追加'''

    def insert(self, index, val):
        '''在index位置插入'''

    def __len__(self):
        '''返回数据个数'''

    def is_empty(self):
        '判断是否为空'

    def clear(self):
        '''清空数据'''

    def head_insert(self, val):
        '''头部插入'''

    def remove(self, val):
        '''删除指定内容'''

    def __getitem__(self, index):
        '''获某个位置的数据'''

    def index(self, val):
        '根据val找到索引'

单向线性链表的程序实现

class Node:
    """
    思路：　将自定义的类视为节点的生成类，实例对象中
    　　　　包含数据部分和指向下一个节点的next
    """
    def __init__(self,value,next=None):
        self.value = value
        self.next = next

class LinkList:
    """
    思路：　单链表类，生成对象可以进行增删改查操作
    　　　　具体操作通过调用具体方法完成
    """
    def __init__(self):
        self.head = None # 指向第一个节点

    def __str__(self):
        '''转为字符串'''
        res_str = 'head->'
        next = self.head
        while next:
            res_str += '('+str(next.value)+')->'
            next = next.next
        return res_str+'None'

    def append(self,value):
        '''末尾追加'''
        temp = Node(value) # 追加一个数据
        if self.head == None:
            self.head = temp
            return
        # 将新增的数据 存入最后一个数据的next
        last = self.head
        # 如果next有值 就循环到下一个
        # 直到没有结果为None时 停止循环
        while last.next:
            last = last.next
        # 将新增的数据写入next
        last.next = temp

    def insert(self,index,value):
        '''在index位置插入'''
        temp = Node(value)
        # 如果index是0 直接添加到开头
        if index == 0:
            temp.next = self.head
            # temp = Node(value,self.head)
            self.head = temp
        # 如果index在中间
        else:
            p = self.head
            for i in range(index-1):
                p = p.next
                if p.next == None:
                    break
            temp.next = p.next
            p.next = temp

    def remove(self,value):
        '''删除指定内容'''
        # 判断是否为第一个
        if self.head.value == value:
            value = self.head.next
            self.head = value
            return
        # 判断是否为之后的结果
        p = self.head
        while p.next:
            if p.next.value == value:
                p.next = p.next.next
                return
            p = p.next
        raise ValueError('error')

    def __len__(self):
        '''返回数据个数'''
        count = 0
        p = self.head
        while p:
            p = p.next
            count += 1
        return count

    def __getitem__(self, item):
        count = 0
        p = self.head
        while p:
            if item == count:
                return p.value
            p = p.next
            count += 1
        raise IndexError('error')





L= LinkList()
# L= []
L.append(3)
L.append(5)
L.append(7)
# L.append(9)
L.insert(1,2)
L.insert(3,4)
# L.insert(5,6)
L.insert(799,8)
print(L)

# L.remove(1)
# L.remove(5)
# L.remove(8)
# L.remove(111)

# print(len(L))
print(L[2])
print(L[0])
print(L[21])
# print(L)

双向线性链表的程序实现

class Node:
    def __init__(self,value,next=None,prev=None):
    """
    思路：　将自定义的类视为节点的生成类，实例对象中
    　　　　包含数据部分和指向下一个节点的next
    """
        self.value = value
        self.next = next
        self.prev = prev

class DoubleLinkList:
    """
    思路：　单链表类，生成对象可以进行增删改查操作
    　　　　具体操作通过调用具体方法完成
    """
    def __init__(self):
        self.head = None # 指向第一个节点
        self.tail = None # 指向最后一个节点

    def __str__(self):
        '''转为字符串'''
        res_str = '['
        next = self.head
        while next:
            res_str += str(next.value)
            if next.next:
                res_str += ','
            next = next.next
        return res_str+']'

    def append(self,value):
        '''末尾追加'''
        temp = Node(value)
        # 判断是否为空列表
        if self.head == None:
            self.head = temp
            self.tail = temp
            return
        # 正常追加
        p = self.tail
        # 提取
        temp.prev = p
        p.next = temp
        self.tail = temp

    def insert(self,index,value):
        '''头部插入'''
        temp = Node(value)
        # 如果index是0 直接添加到开头
        p = self.head
        if index == 0:
            temp.next = p
            if self.head:
                p.prev = temp
            self.head = temp
            return

        # 正常插入
        for _ in range(index):
            if p.next == None:
                self.tail = temp
                break
            p = p.next

        # 插入数据并且维护上下关系
        temp.prev = p
        temp.next = p.next
        if p.next:
            p.next.prev = temp
        p.next = temp

    def remove(self,value):
        '''删除指定内容'''
        pass

    def __len__(self):
        '''返回数据个数'''
        count = 0
        p = self.head
        while p:
            p = p.next
            count += 1
        return count

    def __getitem__(self, item):
        '''获某个位置的数据'''
        count = 0
        p = self.head
        while p:
            if item == count:
                return p.value
            p = p.next
            count += 1
        raise IndexError('error')





L= DoubleLinkList()
# L= []
# L.append(1)
# L.append(3)
L.append(5)
# L.append(7)
# L.insert(1,2)
# print(L.tail.value)
L.insert(0,4)
L.insert(0,3)
L.insert(0,2)
L.insert(0,1)
L.insert(5,6)
# L.insert(799,8)
# print(L)

# L.remove(1)
# L.remove(5)
# L.remove(8)
# L.remove(7)
# L.remove(6)
# L.remove(111)
# L.append(9)

# print(len(L))
# print(L[2])
# print(L[0])
print(L)

双向循环链表的程序实现

# 此示例示意双向循环链表的使用

# 定义一个节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.next = self  # 右手，指向后一个人(数据节点)
        self.prev = self  # 左手，指向前一个人(数据节点)
    def __str__(self):
        return str(self.value)

class DoubleCircleLinkList:
    def __init__(self):
        '''初始化链表'''
        # self 是链表的主节点, 初始是,next和 prev都指向自己
        self.next = self  # self.next, 人的右手,指向链表的头
        self.prev = self  # self.prev, 人的左手,指向链表的尾

    def __str__(self):
        '''返回链表对应的字符串'''
        res_str = '['
        next = self.next
        while next:
            res_str += str(next.value)
            if next.next == self:
                break
            res_str += ','
            next = next.next
        return res_str+']'

    def append(self, value):
        '''追加数据到链表的末尾'''
        new = Node(value)
        # 1. 将new的new.prev指向最后一个节点 通过self.prev获取到当前的最后节点
        new.prev = self.prev
        # 2. 将new的new.next指向主节点
        new.next = self
        # 3.将当前最后一个节点的next指向新节点
        self.prev.next = new
        # 4. 将主节点的 prev 指向new
        self.prev = new

    def insert(self, index, value):
        '''插入数据到index位置之前'''
        new = Node(value)
        # 初始next在索引为0 即从self开始循环
        next = self
        for i in range(index):
            #　将指针指向下一个节点
            next = next.next
            # 循环到末尾时退出循环
            if next.next == self:
                break
        # 1. 将new的new.prev指向当前节点
        new.prev = next
        # 2. 将new的new.next指向下一个节点
        new.next = next.next
        # 3.将当前节点的next节点的prev指向new
        next.next.prev = new
        # 4. 将当前节点的next指向new
        next.next = new


        # # 初始next在索引为1  即从self.next开始循环
        # next = self.next
        # for i in range(index):
        #     # 循环到末尾时退出循环
        #     if next == self:
        #         break
        #     #　将指针指向下一个节点
        #     next = next.next
        # # 1. 将new的new.next指向当前节点
        # new.next = next
        # # 2. 将new的new.prev指向上一个节点
        # new.prev = next.prev
        # # 3.将当前最后一个节点的next指向新节点
        # next.prev.next = new
        # # 4. 将当前节点的 prev 指向new
        # next.prev = new

    def remove(self, value):
        '''删除值为value的数据'''
        next = self.next
        while next:
            if next.value == value:
                # 发现相同值操作删除
                next.prev.next = next.next
                next.next.prev = next.prev
                return
            # 判断循环到头就跳出循环
            if next.next == self:
                break
            next = next.next
        raise ValueError('error')

    def __len__(self):
        '''返回元素个数'''
        count = 0
        next = self.next
        while next != self:
            count += 1
            if next.next == self:
                break
            next = next.next
        return count

    def __getitem__(self, item):
        '''返回item位置的数据元素'''
        count = 0
        p = self.next
        while p:
            if item == count:
                if p == self:
                    break
                return p.value
            if p.next == self:
                break
            p = p.next
            count += 1
        raise IndexError('error')


L= DoubleCircleLinkList()
# L= []
# L.append(1)
# L.append(3)
# L.append(5)
# L.append(7)
# L.insert(1,2)
# print(L.tail.value)
# L.insert(0,4)
# L.insert(0,3)
# L.insert(0,2)
# L.insert(0,1)
# L.insert(5,6)
# L.insert(799,8)
# print(L)
print(len(L))
# print(L[0])
# print(L[2])
# print(L[22])
# print(L[0])
# print(L)

# L.remove(2)
# L.remove(8)
# L.remove(8)
# L.remove(7)
# L.remove(6)
# L.remove(111)
# L.append(9)
# print(L)
# print(len(L))
# print(L[2])
# print(L[22])
# print(L[0])
# print(L)