数据结构与算法5—栈
栈（stack）是一种遵循先入后出逻辑的线性数据结构。 如图所示，我们将堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫做“入栈”，删除栈顶元素的操作叫做“出栈”。 1. 栈的常用操作栈的常用操作如下表所示： 方法 描述 时间复杂度 push() 元素入栈（添加至栈顶） $O(1)$ pop() 栈顶元素出栈 $O(1)$ peek() 访问栈顶元素 $O(1)$ 通常情况下，一些编程语言内置了栈类。当没有提供栈类时，可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。C++具有栈类stack可以直接使用，而Python的列表也有能轻易实现栈操作的方法，因此下面以C为例实现栈。 2. 栈的实现栈可以视为一种受限制的数组或链表，因为它只能在栈顶添加或删除元素。换句话说，我们可以通过屏蔽数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。 2.1...
数据结构与算法4—列表
列表（list）是一个抽象的数据结构概念，表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无需使用者考虑容量限制的问题。列表可以基于链表或数组实现。 链表天然可以看作一个列表，其支持元素增删改查操作，并且可以灵活动态扩容。 数组也支持元素增删改查，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 由于数组不具备扩展长度的能力，因此可以使用动态数组来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。 许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等。通常，将列表和动态数组视为等同的概念。 1. 列表常用操作1.1 初始化列表列表的初始化可以采用“无初始值”和“有初始值”这两种初始化方法： 12345/* 初始化列表 */// 无初始值vector<int> nums1;// 有初始值vector<int> nums = { 1, 3, 2, 5, 4 }; 1.2...
数据结构与算法3—链表
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。 链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”或“指针”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。 链表节点ListNode除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。 1. 链表结构体不同编程语言中的链表结构体如下所示： 12345/* 链表节点结构体 */typedef struct ListNode { int val; // 节点值 struct ListNode *next; // 指向下一节点的引用} ListNode; 1234567/* 链表节点 */struct ListNode { ...
数据结构与算法2—数组
数组是一种常见的线性数据结构，其将相同类型的元素存储在连续的内存空间中，我们将元素在数组中的位置称为该元素的索引。 1. 数组的常用操作1.1 初始化数组初始化数组时，我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0，但是经过实测，C++和C在数组为初始化时，大多数情况下不会将数组初始化为0，特别是使用new或malloc创建动态数组时数组元素都是随机值，因此在C++和C中建议创建完数组后就立刻将其初始化： 123456789101112/* 初始化数组arr */// 将数组存储在栈上int size = 5;int arr[5] = {0};printf("数组 arr = ");printArray(arr, 5);/* 初始化数组nums */// 将数组存储在栈上int nums[5] = {1, 2, 3, 4, 5};printf("数组 nums = ");printArray(nums,...
数据结构与算法1—基本概念与复杂度
1. 算法的定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 2. 算法的特性算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。 2.1 输入输出算法通常具有零个或多个输入，但至少有一个或多个输出。输出的形式可以是打印输出，也可以是返回一个或多个值。 2.2 有穷性有穷性指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。 2.3 确定性确定性指算法的每一步骤都具有确定的含义，不会出现二义性。 2.4 可行性可行性指算法的每一步都必须是可行的，也就是说每一步都能够执行有限次数完成。可行性意味着算法可以转化为程序上机运行，并得到正确的结果。 3. 算法设计的要求算法设计的要求包括正确性、可读性、健壮性、高效率和低内存需求。 3.1...
Python格式规范
1. Python命名规范1.1 文件名、包名、模块名、变量名、函数名、实例名全部采用小写的形式，并使用下划线连接，如下所示： 12my_car.pymy_car 1.2 类名采用驼峰命名法，即将类中的每个单词的首字母都大写，且不使用下划线，如下所示： 1ElectricCar 1.3 常量名所有字母大写，单词之间采用下划线连接，如下所示： 1MAX_NUM = 100 2. Google Python命名规范 模块名写法: module_name ;包名写法: package_name ;类名: ClassName ;方法名: method_name ;异常名: ExceptionName ;函数名: function_name ;全局常量名: GLOBAL_CONSTANT_NAME ;全局变量名: global_var_name ;实例名: instance_var_name ;函数参数名: function_parameter_name ;局部变量名: local_var_name . 3....
Python学习笔记6—类
1. 创建和使用类1.1 创建Dog类下面将创建一个表示小狗的Dog类，根据Dog类创建的每个示例都将存储名字和年龄，并且赋予每条小狗蹲下（sit()）和打滚（roll_over()）的能力： dog.py 123456789101112131415class Dog(): """ 创建一个表示小狗的类 """ def __init__(self, name, age): """ 初始化属性name和age """ self.name = name self.age = age def sit(self): """ 模拟小狗被命令时蹲下 """ print(self.name.title() + " is now sitting.") def roll_over(self): ...
Python学习笔记5—函数
1. 函数的定义在Python中，函数可按下面这种方式定义： 12345def greet_user(username): """ 显示简单的问候语 """ print("Hello, " + username.title() + "!") greet_user('jesse') 上面这段代码演示了最简单的函数结构，第一行代码使用关键字def来定义一个函数，def后面的greet_user(username)为函数名，username叫做函数的形参，而’jesse’叫做实参。紧跟在def greet_user(username):后面的所有缩进行构成了函数体。””” 显示简单的问候语 “””叫做文档字符串，描述的函数是做什么的，文档字符串用三引号括起，Python使用它们来生成有关程序中函数的文档。要使用这个函数，可调用它，依次指定函数名以及要传入括号中的参数。上面这段代码的输出为： 1Hello, Jesse! 2....
Python学习笔记4—字典
1. 字典的创建和访问字典中的值在Pyhton中，字典是一系列键值对，每个键都与一个值相关联，可以使用键来访问与之相关联的值。与键相关联的值可以是数字、字符串、列表乃至字典。在Python中，字典用放在花括号{}中的一系列键值对表示，如下面就是一个字典： 1alien_0 = {'color': 'green', 'points': 5} 键值对是两个相关联的值，指定键时，Python将返回与之相关联的值。键和值之间用冒号分隔，而键值对之间用逗号分隔。 要获取与键相关联的值，可依次指定字典名和放在方括号内的键，如下所示： 12alien_0 = {'color': 'green'} print(alien_0['color']) 这将返回字典中alien_0中与键’color’相关联的值： 1green 2....
Python学习笔记3—元组
1. 元组的创建在Python中元组的定义和用法与列表相似，列表用方括号[]表示，而元组用圆括号()表示，与列表不同的是元组中的元素不可修改，除此之外，Python的列表长度是可变的，而元组长度不可变，元组的定义如下所示： 123dimensions = (200, 50)print(dimensions[0])print(dimensions[1]) 在上面的代码中，先定义了元组dimensions，然后输出索引为0和1的两个元素，其输出结果为： 1220050 如果尝试修改该元组中某个元素的值，则会导致Python报错，如： 12dimensions = (200, 50) dimensions[0] = 250 此时会返回如下错误： 1234Traceback (most recent call last): File "<pyshell#1>", line 1, in <module> dimensions[0] = 250TypeError: 'tuple' object does not...
