Python学习-数据结构与算法01

基础概念

算法 + 数据结构 = 程序。

数据结构

是指数据之间的关系和相应的存储方法。即 = 数据的存储方式 + 组织方式；

算法

是指对数据的操作方法的描述，即 = 解决问题的一系列步骤 / 方法。
算法的五大特性：

1. 有输入：具有 0 个或多个输入的参数。
2. 有输出：算法执行要有输出结果，不同的输入通常对应不同的输出。
3. 有穷性
   算法中每条指令的执行次数必须是有限的，即算法必须在执行了有穷步后结束，不能无限运行下去。
4. 确定性
   每条指令都必须有确切的含义、无二义性。同样的输入，无论执行多少次，结果一定相同；步骤不能模糊、不能含糊不清。
5. 可行性
   算法中的每一步操作都必须是基本可执行、可实现的。可以通过有限次基础运算完成，不能出现逻辑上无法实现、超出计算机能力的步骤。

时间、空间复杂度

时间复杂度

随着数据规模 n 增大，算法执行时间的增长趋势。不看具体运行了多少毫秒，只看增长量级。
——通常用来衡量一个算法的优劣，用T(n)表示。
大 O 表示法：
T(n) = O(f(n))，表示算法执行时间与 f(n) 成正比，即算法效率的增长量级。
只关注最高次项（即增长最快的项）忽略常数系数和低次项。
例如：T(n) = 3n² + 5n + 100→ 只保留最高次项 n²→ 时间复杂度为 O(n²)

计算规则：

1. 基本（固定）操作：时间复杂度为O(1)
2. 加法规则（顺序执行、分支结构）：总复杂度 = 复杂度最大的那一段。例：O(n) + O(n²) = O(n²)
3. 乘法规则（嵌套循环）：内外循环复杂度相乘。例：O(n) * O(n) = O(n²)
4. 忽略常数，保留最高次项。例：O(10n) = O(n)，O(n³ + n² + n) = O(n³)

最好、最坏、平均复杂度：

1. 最好时间复杂度：最理想情况，如在数组第一个位置找到目标，O(1)
2. 最坏时间复杂度：最糟糕情况，遍历到最后才找到，O(n)
3. 平均时间复杂度：综合所有情况的期望。

注意：没有特殊情况下，大O标记法默认最坏时间复杂度。
常见时间复杂度：

增长速度排序：O(1) < O(log n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。
时间复杂度越低，效率越高。

空间复杂度

用来衡量算法在运行过程中临时占用存储空间的增长趋势，同样使用大O记法表示。只算额外占用，不算输入数据本身占用的空间；关注增长量级，不关心具体字节数。
——用S(n)表示。
常见空间复杂度：

数据结构分类

按逻辑结构分类

常见的逻辑结构有4种，即集合、线性结构、树和图。树结构和图结构统称为非线性结构。

1. 集合：其数据元素之间的逻辑特点是满足“共同属于一个集合”的关系。
2. 线性结构：其数据元素之间的逻辑特点是一对一关系，有唯一前驱、唯一后继。
   例如：线性表、栈、队列、串、多维数组等。
3. 非线性结构
   3.1 树结构：其数据元素之间存在着一对多的层次关系。
   例如：二叉树、哈夫曼树等。
   3.2 图结构：数据元素之间存在着多对多的关系。

按存储结构分类

基本的存储结构通常有两大类：顺序存储结构和链式存储结构。
内存中的存储结构：
内存是以字节为基本存储单位，每个基本存储空间都有自己的地址，一个内存地址代表一个字节（8bit）的存储空间。
整型（int）：4个字节；
字符（char）：1个字节，单个字符占1个字节，字符串"abcd"占4个字节。
分类：

1. 顺序存储结构：用一组连续的存储单元依次存储各个数据元素，例如：数组。
   优点：随机访问快，查找O(1)；缺点：插入删除慢，浪费空间
2. 链式存储结构：用一组任意的存储单位存储各个数据元素，数据元素间关系通常用指针来表示。例如，后一个元素的地址存储在前一个元素的某个特定数据项中。
   优点：插入删除方便；缺点：不能随机访问，查找慢

线性表

简称表，是一种最简单、最常用的数据结构，也是典型的线性结构。通常是由零个或多个具有相同类型的数据元素构成的有限序列，相邻元素之间具有单一的前驱和后继的关系。
线性表的常用存储结构：包括顺序存储结构（顺序表）和链式存储结构（如单链表、循环链表、双向链表等）。

顺序表

——只需知道第一个元素的存储地址及每个元素占用的存储空间，就可直接计算出任意元素的存储地址。
顺序表的基本运算：

1. 构造顺序表
   创建一个顺序表，其数据元素来自数组a的各个元素。

def__init__(self,a,n,max_size):''' 初始化参数 :param a: 传入的数组 :param n: 数组的长度 :param max_size: 顺序表的容量 '''self.a=a self.n=n self.max_size=max_size# 顺序表self.data=[None]*self.max_size# 若数组长度超出最大容量，则抛出异常ifself.n>self.max_size:raiseException('数组长度超过顺序表的最大长度')else:foriinrange(self.n):self.data[i]=a[i]# 定义表此时的长度self.length=n

2. 遍历顺序表

deftraverse(self):foriinrange(self.length):print(self.data[i],end=' ')print()

3. 插入操作

definsert(self,x,num):# 判断位置合法性ifx<0orx>self.length:raiseIndexError('插入位置非法！')ifself.length>=self.max_size:raiseException('表容量已满，无法插入！')foriinrange(self.length,x,-1):self.data[i]=self.data[i-1]self.data[x]=num self.length+=1self.traverse()

4. 删除操作

# 删除defdel_element(self,x):ifx<0orx>self.length:raiseIndexError('删除位置非法！')print('被删除的元素为：',self.data[x-1])foriinrange(x-1,self.length-1):self.data[i]=self.data[i+1]self.length-=1self.traverse()

5. 修改操作

# 修改defupdate(self,x,num):ifx<0orx>self.length:raiseIndexError('修改位置非法！')print('被修改的元素为：',self.data[x-1])self.data[x-1]=num self.traverse()

6. 查找操作

# 按位查找defget_element(self,x):ifx<0orx>=self.length:raiseIndexError("查找位置非法")print(f'第{x}位为：{self.data[x-1]}')# 按值查找deflocate_element(self,num):index=-1foriinrange(self.length):ifself.data[i]==num:index=ibreakifindex!=-1:print(f'{num}位于第{index+1}位')else:print('该元素不存在')

顺序表的优缺点：
优点：

1. 利用物理位置上的相邻关系来表示数据元素之间的逻辑关系，因此不需要为表示元素之间的逻辑关系而增加额外的存储空间；
2. 可以方便地随机访问和修改顺序表中任意位置的元素。
   缺点：
3. 插入和删除操作需移动大量的数据元素，效率较低；
4. 顺序表要求占用连续的存储空间，存储分配只能预先进行，属于静态存储分配方式，因此难以选择合适的存储容量。

链表

——在存储每个元素值的同时，还需存储该元素的直接后继元素的位置信息（称为指针/链），这两部分构成实际的存储结构，称为结点。
——采用动态存储方式，即程序在运行时根据实际需要随时申请内存，在不需要时将申请的内存释放。

1. 单链表
   链表中的每个结点只包含一个指向直接后继的指针。
   因此，每个结点均有数据域和指针域两部分构成，数据域用于存储元素的值，指针域用来存储直接后继的地址。
   
   单链表的基本运算：
   1.1 构造单链表

# 定义结点类classSingleNode:def__init__(self,data):''' 初始化属性，包括数值域，指针域(初始为空) '''self.data=data self.next=None# 定义链表类classSingle_LinkList:''' 定义单链表类 属性：头结点 方法： 1. 判断链表是否为空 is_empty() 2. 求链表长度 length() 3. 遍历输出 traverse() 4. 查找操作 locate() 5. 插入操作 insert() 6. 删除操作 del_e() '''def__init__(self,node=None):self.head=node

1.2 判断链表是否为空

# 1. 判断链表是否为空defis_empty(self):ifself.headisNone:returnTrueelse:returnFalse

1.3 求链表长度

# 2. 求链表长度deflength(self):cur=self.head count=0whilecurisnotNone:count+=1cur=cur.nextreturncount

1.3 遍历输出

# 3. 遍历输出deftraverse(self):cur=self.headwhilecurisnotNone:print(cur.data,end=' ')cur=cur.nextprint()

1.3 查找操作

# 4. 查找操作deflocate(self,data):cur=self.headwhilecurisnotNone:ifcur.data==data:returnTrueelse:cur=cur.nextreturnFalse

1.4 插入操作

# 5. 插入操作# 5.1 头部插入元素definsert_head(self,data):# 创建新结点new_node=SingleNode(data)# 新结点的指针域指向原来的头结点new_node.next=self.head# 新的头结点指向新结点self.head=new_node# 5.2 尾部插入元素definsert_tail(self,data):# 创建新结点new_node=SingleNode(data)# 判断链表是否为空，若为空，头结点直接指向新结点即可ifself.is_empty():self.head=new_node# 链表非空，即为None的地址域指向新结点else:cur=self.headwhilecur.nextisnotNone:cur=cur.nextcur.next=new_node# 5.3 中间指定位置插入元素definsert(self,index,data):# 创建新结点new_node=SingleNode(data)# 索引小于等于0，即在头部插入ifindex<=0:self.insert_head(data)# 索引超出链表长度，即在尾部插入elifindex>=self.length():self.insert_tail(data)else:cur=self.head count=0# 找到插入位置的前一个结点的地址域whilecount<index-1:cur=cur.nextcount+=1new_node.next=cur.nextcur.next=new_node

1.3 删除操作

# 6. 删除操作defdel_e(self,data):cur=self.head# 记录需要删除节点的前一个结点pre=NonewhilecurisnotNone:ifcur.data==data:# 判断要删除的结点是否是头结点ifcur==self.head:self.head=cur.nextelse:pre.next=cur.nextreturnelse:pre=cur cur=cur.next

2. 循环链表
   单链表最后一个结点的指针域指向头结点，整个链表构成一个环，即首尾相接的单链表称为单循环链表。
   

3. 双链表
   在每个节点中再加入一个用于存储前一个元素的地址的指针域，称为双链表。