数据结构

物理结构

又称存储结构

逻辑结构

集合结构：(同属一个整体，但是每个元素之间没有关系)
​ 线性结构：队尾元素没有直接后继，队头元素没有直接前驱,其他元素有唯一的直接前驱和后继（一对一）
​ 树形结构：除了根元素，其他元素都有一个前驱和多个后继（一对多）
​ 图形结构：每个元素都有多个前驱和后继（多对多）

重点:线性结构

  • 如果既是线性结构，又是链式结构，这种结构成为链表
  • 如果既是线性结构，又是顺序结构，这种结构成为顺序表

链表又分为：单向链表 双向链表 单向循环链表

单向链表:当连接表中的每个节点只包含一个指针时，他只能指向下一个节点地址，这种只含有一个指针域的链表，称为单向链表

双向链表：它的连接表中，每个节点，都有两个指针，指向了直接前驱和直接后继，从双向链表中的任意一个节点开始访问，都能很方便的访问到它的前驱节点和后继节点，这种结构，称为双向链表

单向循环链表：普通的单向链表，末尾节点(也叫叶子节点)的指针，不再指向NULL，而是指向第一个节点，即开始节点

为什么要用单向循环链表，打个比方，我们要对单向链表中的某个节点进行访问，只能从头开始访问，而单向循环链表，可以从任意一个节点开始，因为它末尾的的指针指向了第一个节点，极大的增加了其灵活性

接下来，我们用代码来展示一下

'''
单向链表：指向空的节点为尾结点
单向循环链表：指向头结点的节点为尾结点
'''
# 创建节点类
class Node:
    def __init__(self, data):
        """节点类"""
        self.data = data
        self.pointer = None
        
# 创建链表类       
class SCLL:
    def __init__(self):
        """ 初始化函数"""
        self.head = Node(None)
        self.head.pointer = self.head
        
	# 判断是否位空
    '''需要判断头结点是否指向自身，从而确定是否为空'''
	def is_empty(self):
        if self.head.pointer == self.head:
        return True
    
    # 针对空链表可返回None；针对非空链表即采用循环操作，结束条件当前位置是尾结点
    def traversal(self):
    """ 遍历链表"""
    if self.is_empty():
        return False
    else:
        counter = 1
        current =self.head.pointer
        # 当前指针不指向头结点时进行循环
        while(current != self.head):
            print(" Element {{ is {{ ".format(counter, current.data))
            counter += 1
            current = current.pointer
        return True

链表和顺序表的区别：
链表插入删除方便，修改查找不方便
顺序表修改和查找方便，插入删除不方便

顺序结构：逻辑结构相邻，物理结构也相邻
​链式结构：逻辑相邻，物理不一定相邻

算法

官方说法为：解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制

通俗的讲：

算法是特定解决问题的方法步骤

算法特性

  • 输入：有零个或多个输入
  • 输出：有一个或多个输出
  • 有穷性：有限的时间或有限的步骤可以结束算法
  • 确定性：每个步骤只有唯一的意思，不会产生歧义
  • 可行性：可用现有的条件可以实现

算法复杂度

  • 时间复杂度:算法运行所需要的时间

用大O表示法
list：pop()删除末尾元素：O(1)
pop(0)删除第一个元素：O(n)
sort()排序：O(nlogn)
insert()插入元素 O(n)
append()末尾添加元素:O(1)
字典：
除了循环 复制 O(n)
删除、添加、修改、查询元素O(1)

  • 空间复杂度：算法运行所需要的空间