线性结构：顺序表和链表

# 线性结构

0x00 什么是线性结构

0x01 线性结构有什么特点



# 顺序表

0x00 什么是顺序表
     将元素存储在一片连续的内存空间当中。

0x01 顺序表的结构种类
     一体式结构：存储的数据类型是一样的。比如int型，就只有int型的数据放在那一片内存空间当中。
     分离式结构：存储的数据类型不止一种。可能先存int型，然后再存一个str类型。
     
     当一体式结构的时候，可以通过  首数据 的地址，加上偏移量直接进行寻址来找到数据。
     当分离式结构的时候，不能直接通过偏移进行寻址，要通过具体地址来寻找数据。
     

0x02 顺序表的组成
     表头信息+数据。
     
     一体式结构：（地址）+数据；
     分离式结构：（地址+数据）+（地址+数据）。

0x03 顺序表的特点
     在内存当中的存储是连续的。

0x04 顺序表的操作
     顺序表添加元素；
     顺序表删除元素。
     
0x05 顺序表的作用
     用于数据存储。

0x06 代码实现


# 链表

0x00 什么是链表
     将元素存储在非连续的内存空间中。

0x01 链表的类型
     a.单链表
     记得之所以叫做单链表，就是因为方向是不可改变的，但是其中的值确是可以被改变的，记得这是单链表的灵魂。
     
0x02 链表的组成
     a.单链表的组成：
     头结点=值+指向下一个结点的指针
     中间若干节点
     尾结点=值+指向一个空值的指针

0x05 单链表的操作
     增删改查

0x04 链表的作用
     a.单链表的作用
       将数据存储在一段不连续的内存空间当中。

0x03 链表的实现
     a.单链表的实现
     
     先实现一个节点的创建
     
     # 节点

     # 节点包含：当前节点的数据内容
     #           和指向下一个节点的指针
     # 链表中节点的实现
     class SingleNode(object):
         def __init__(self, item):
             # 当前节点的内容
             self.item = item
             # 指向下一个节点的指针
             self.next = None

     node_one = SingleNode(1)
     print(node_one)
     print(f'内容为{node_one.item}')
     print(f'下一节点的指针为{node_one.next}')

     <__main__.SingleNode object at 0x00000281DF3628C8>
     内容为1
     下一节点的指针为None
     >>> 
     
     然后实现单链表的创建：
     
     # 单链表
     # 首先要给单链表一个默认的属性：头节点,如果没有传入头节点，默认头节点为空。
     class SingleLinkList(object):
         def __init__(self, node=None):
             self.head = node

         # 然后判断单链表是否为空
         # 因为目前单链表中还未添加任何节点，所以仅需要判断是否传入头节点即可
         def is_empty(self):
             # 如果没有传入头节点，单链表为空，self.head为None，not None就为True
             print(not self.head)
             return not self.head

     '''
     a = SingleLinkList()
     a.is_empty()
     
     >>> True
     '''
     
         # 获取链表长度
         # 这时引入了一个当前指针对象的概念，写做cur
         # 先将cur指向头节点，然后遍历链表，直到cur指向后继节点为None停止遍历。
         def get_length(self):
             cur = self.head
             count = 0

             while cur is not None:
                 count += 1
                 cur = cur.next
             print(count)
             return count
     '''
     a.get_length()
     
     >>> 0
     '''
     
         # 遍历链表
         # 先将cur指向头节点，然后遍历，用cur = cur.next()往下走，直到cur指向None，结束遍历
         def travel(self):
             cur = self.head

             while cur is not None:
                 print(cur.item)
                 cur = cur.next
     '''
     a.travel()
     
     >>>
     '''
         # 头部增加节点
         # 为了不丢失头部的指针，需要先将新增节点的next指针域指向当前单链表的头节点（无论有没有头节点），
         # 然后将当前单链表的头节点指向新增节点
         def add(self):
             node = SingleNode(10)
             if self.head is None:
                 self.head = node
                 return

             node.next = self.head
             self.head = node

     '''
     a.add()
     a.add()
     a.add()
     a.add()
     a.travel()
     
     >>> 
     10
     10
     10
     10
     '''
     
         # 在尾部增加节点
         # 当节点的next指针指向None的时候，先不指向None，而是指向新添加的节点
         def append(self, item):
             node = SingleNode(item)

             # 当是空链表的时候，尾部增加的节点也是头节点
             if self.is_empty():
                 self.head = node
                 return

             # 如果单链表不为空，当节点的next指针指向None的时候，先不指向None，而是指向新添加的节点
             else:
                 cur = self.head
                 while cur.next is not None:
                     cur = cur.next

                 cur.next = node
     '''
     a = SingleLinkList()
     # a.is_empty()
     # a.get_length()
     # a.travel()
     a.add()
     a.add()
     a.add()
     a.add()
     a.travel()

     a.append(500)
     a.travel()
     
     >>>
     10
     10
     10
     10
     False
     10
     10
     10
     10
     500
     '''
     
         # 指定位置增加节点
         # 先找到需要插入位置的前一个节点，然后插入目标节点
         def insert(self, pos, item):
             if pos <= 0:
                 self.add(item)
                 return
             if pos > self.get_length():
                 self.append(item)
                 return
             else:
                 cur = self.head
                 count = 0
                 node = SingleNode(item)
                 
                 # 找到目标位置的前一个节点cur
                 while count < pos-1:
                     cur = cur.next
                     count += 1

                 # 先将cur的指针域和新增节点的指针域都指向 下一个节点
                 node.next = cur.next
                 # 然后将cur的指针域指向新增节点
                 cur.next = node

         # 删除元素
         # 删除元素的思想在于，将想要删除对象的前一个对象的指针直接指向删除对象的下一个指针。
         def remove(self, item):
             # 游标指向头节点
             cur = self.head
             # 辅助游标
             pre = None

             while cur is not None:
                 # 找到了要删除的元素：
                 if cur.item == item:
                     # 要删除的元素在头部
                     if cur == self.head:
                         self.head = cur.next
                     # 不是头部找到要删除的元素
                     else:
                         pre.next = cur.next
                     return
                 # 没找到要删除的元素：
                 else:
                     pre = cur
                     cur = cur.next
             print(f"没有{item}")


     '''
     a = SingleLinkList()
     # a.is_empty()
     # a.get_length()
     # a.travel()
     a.add(10)
     # a.add()
     # a.add()
     # a.add()
     # a.travel()

     a.append(500)
     # a.travel()
     #
     a.insert(1, 2333)
     a.remove(23334)
     a.travel()

     >>>
     没有23334这个元素
     10
     2333
     500

     item要是2333结果为：
     10
     500
     '''
         
         # 搜索元素是否存在
         # 搜索元素的思路在于遍历单链表，如果存在就返回True，不存在就返回False
         def search(self, item):
             cur = self.head

             while cur.next is not None:
                 if item != cur.item:
                     cur = cur.next
                 else:
                     print(f"找到了{item}")
                     return True
             else:
                 if item != cur.item:
                     cur = None
                 else:
                     print(f"找到了{item}")
                     return True

             print(f"没有找到{item}")
             return False

     '''
     print("--------搜索--------")
     a.search(2333)
     
     >>>
     --------搜索--------
     找到了2333
     '''