秀网站,无锡制作网站公司简介,域名解析记录值填什么,企业建设网站的主要作用数据结构
“” 基础概念: 程序 数据结构 算法 数据结构 存储和组织数据的方式. 算法 解决问题的思维, 思路, 方式.
算法的特性:独立性: 算法 思维, 是解决问题的思路和方式, 不依赖语言.5大特性: 有输入, 有输出, 有穷性, 确定性, 可行性.问: 如何衡量算法的优劣?…数据结构
“” 基础概念: 程序 数据结构 算法 数据结构 存储和组织数据的方式. 算法 解决问题的思维, 思路, 方式.
算法的特性:独立性: 算法 思维, 是解决问题的思路和方式, 不依赖语言.5大特性: 有输入, 有输出, 有穷性, 确定性, 可行性.问: 如何衡量算法的优劣?
答: 时间复杂度.
例如: 下述的两个代码, 执行时长为: 代码的总步骤 * 每步的基本时间方式1: 1001³ * 9 * 每步的基本时间方式2: 1001² * 9 * 每步的基本时间虽然上述的方式可以计算代码执行时间, 但是我们在考虑算法的时间复杂度的时候, 只考虑 主要条件, 而会忽略次要条件.时间复杂度介绍:它适用于衡量算法的优劣的, 一般采用大O标记法, 把次要条件都忽略, 最终形成的表达式就叫: 大O标记法.名词解释:问题规模: 程序(算法)的计算量, 计算范围...主要条件: 随着问题规模变化而变化的代码.次要条件: 随着问题规模变化而不变的代码.计算方式:常数项: O(1)顺序结构: 加法分支结构: 最高次项循环结构: 乘法分析的时候, 只参考 主要条件, 忽略 次要条件 和 常数项.如果没有特殊说明的情况下, 我们分析时间复杂度, 指的都是: 最坏时间复杂度.最优时间复杂度: 最理想, 最乐观的状态, 算法需要的最少步骤.最坏时间复杂度: 算法的保证, 最多需要多少步能计算出结果.常用的时间复杂度介绍:从低到高分别是:常数阶 对数阶 线性阶 常数对数阶 平方阶 立方阶O(1) O(logn) O(n) O(nlogn) O(n²) O(n³)空间复杂度(了解):概述: 算法执行过程中, 临时占用的内存空间大小.分类:O(1) O(logn) O(n) O(n²) O(n³)细节:内存是通过 字节 的形式来存储数据的, 每块空间都有自己的地址值. “”
import time# 需求: 演示算法 - 穷举法. 已知: a² b² c², 且 a b c 1000, 问: a,b,c可以是哪些组合.
start time.time()
# 方式1: 穷举法, 3层循环嵌套.
for a in range(0, 1001):for b in range(0, 1001):for c in range(0, 1001):# if a b c 1000 and a ** 2 b ** 2 c ** 2: # 122秒if a ** 2 b ** 2 c ** 2 and a b c 1000: # 235秒print(a, b, c)
end time.time()
print(f程序共执行了: {(end - start):.2f} 秒) # 122.01秒# 方式2: 穷举法 代入法, 2层循环嵌套.
start time.time()
# 方式1: 穷举法, 3层循环嵌套.
for a in range(0, 1001):for b in range(0, 1001):c 1000 - a - bif a ** 2 b ** 2 c ** 2:print(a, b, c)
end time.time()
print(f程序共执行了: {(end - start):.2f} 秒) # 0.34s“” 数据结构介绍: 概述: 数据结构 存储,组织属于的方式, 也是算法解决问题时的载体. 分类: 线性结构 非线性结构
线性结构:特点:每个节点有且只能有1个前驱节点(父节点) 和 1个后继节点(子节点)举例:栈, 队列, 链表...分类:顺序表:概述:采用 连续 的内存空间来存储.根据存储方式不同, 又分为:一体式存储: 信息区 和 数据区在一起.分离式存储: 信息区 和 数据区分开存储.扩容策略:一体式: 扩容时, 信息区和数据区整体搬迁.分离式: 只搬迁数据区, 然后用信息区重新关联即可.思路:方式1: 每次增加固定的容量, 假设: 每次扩容增加100个字节. 拿时间换空间.方式2: 每次扩容容量翻倍. 拿空间换时间(推荐做法).链表:概述:采用 非连续 的内存空间来存储.非线性结构:特点:每个节点都可以有多个前驱节点(父节点) 和 多个后继节点(子节点)举例:树图...“” 链表介绍:概述:它属于数据结构的一种, 属于: 线性结构(每个节点都只能有1个前驱节点 和 1个后继节点)回顾: 顺序表的弊端扩容时要求有足够的连续的内存空间, 否则扩容失败.链表扩容:比较简单, 有地儿就行, 可以不连续, 最后通过链条连接起来.链表 通过 一条线把各个节点链接起来, 形成一个 链条就叫: 链表.组成:元素域(数值域) 链接域(地址域)分类:单向链表:每个节点由 元素域(数值域) 链接域(地址域), 前边节点的链接域指向后1个节点的地址, 最后1个节点的链接域为: None.单向循环链表:每个节点由 元素域(数值域) 链接域(地址域), 前边节点的链接域指向后1个节点的地址, 最后1个节点的链接域为: 第1个节点的地址.双向链表:每个节点由 链接域(地址域) 元素域(数值域) 链接域(地址域),每个节点的链接域会分别指向: 前, 后节点的地址.第1个节点的: 前链接域(地址域) 和 最后1个节点的 后链接域(地址域)为 None双向循环链表:每个节点由 链接域(地址域) 元素域(数值域) 链接域(地址域),每个节点的链接域会分别指向: 前, 后节点的地址.第1个节点的: 前链接域(地址域) 指向最后1个节点的 地址.最后1个节点的 后链接域(地址域)指向第1个节点的 地址.需求:自定义代码, 采用面向对象思维, 模拟链表.“” 案例: 自定义代码, 采用面向对象思维, 模拟: (单向)链表.
回顾: 链表 由节点组成, 节点 数值域(元素域) 地址域(链接域)
分析: 节点类: SingleNode 属性: item: 数值域(元素域) next: 地址域(链接域)
链表类: SingleLinkedList属性:head: 指向头结点“”
# 定义节点类
class SingleNode(object):def __init__(self, item):self.item itemself.next None#定义链表类
class SingleLinkedList(object):def __init__(self, headNone):self.head head# 判断链表为空def is_Empty(self):return self.head None# 返回链表长度def length(self):cur self.headcount 0while cur is not None:count 1cur cur.nextreturn count# 遍历打印链表def travel(self):cur self.headcount 0while cur is not None:print(cur.item)cur cur.next# 链表头部增加元素def add(self, item):new_node SingleNode(item)new_node.next self.headself.head new_node# 链表尾部添加元素def append(self, item):new_node SingleNode(item)if self.is_Empty():self.head new_nodeelse:cur self.headwhile cur.next is not None:cur cur.nextcur.next new_nodeif __name__ __main__:# 创建对象s1 SingleLinkedList()# 测试判空函数print(s1.is_Empty())# 测试添加元素s1.add(坤坤)# 测试遍历元素s1.travel()# 测试在尾部添加数据s1.append(鸡叫)# 测试遍历元素s1.travel()
