文章目录 2. 顺序表 顺序表 2. 顺序表 顺序表 在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。 对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。 这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中...

文章目录 2.1. 顺序表的形式 顺序表的基本形式 2.1. 顺序表的形式 顺序表的基本形式 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直 图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即： Loc(ei) = Loc(e0) + c*i 故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。 如果元素的...

文章目录 2.3. 顺序表的操作 顺序表的操作 增加元素 删除元素 2.3. 顺序表的操作 顺序表的操作 增加元素 如图所示，为顺序表增加新元素111的三种方式 a. 尾端加入元素，时间复杂度为O(1) b. 非保序的加入元素（不常见），时间复杂度为O(1) c. 保序的元素加入，时间复杂度为O(n) 删除元素 a. 删除表尾元素，时间复杂度为O(1) b. 非保序的元素删除（不常见），时间复杂度为O(1) c. 保序的元素删除，时间复杂度为O(n)

文章目录 2.2. 顺序表的结构与实现 顺序表的结构与实现 顺序表的结构 顺序表的两种基本实现方式 元素存储区替换 元素存储区扩充 2.2. 顺序表的结构与实现 顺序表的结构与实现 顺序表的结构 一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。 顺序表的两种基本实现方式 图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分...

文章目录 2.4. Python中的顺序表 Python中的顺序表 list的基本实现技术 2.4. Python中的顺序表 Python中的顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。 tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。 list的基本实现技术 Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持...

文章目录 3. 链表 链表 为什么需要链表 链表的定义 3. 链表 链表 为什么需要链表 顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。 链表的定义 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

文章目录 3.1. 单向链表 单向链表 节点实现 单链表的操作 单链表的实现 链表与顺序表的对比 3.1. 单向链表 单向链表 单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放具体的数据。 链接域next用来存放下一个节点的位置（python中的标识） 变量p指向链表的头节点（首节点）的位...

文章目录 3.2. 单项循环链表 单向循环链表 操作 实现 3.2. 单项循环链表 单向循环链表 单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 rem...

文章目录 3.3. 双向链表 双向链表 操作 实现 3.3. 双向链表 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。 操作 is_empty() 链表是否为空 length() 链表长度 travel() 遍历链表 add(item) 链表头部添加 append(item) 链表尾部添加 insert(pos, item) 指定位置添加 remove(...

文章目录 4. 栈 栈 4. 栈 栈 栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。 由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

文章目录 4.1. 栈结构实现 栈结构实现 栈的操作 4.1. 栈结构实现 栈结构实现 栈可以用顺序表实现，也可以用链表实现。 栈的操作 Stack() 创建一个新的空栈 push(item) 添加一个新的元素item到栈顶 pop() 弹出栈顶元素 peek() 返回栈顶元素 is_empty() 判断栈是否为空 size() 返回栈的元素个数 class Stack(object): """栈""&quo...

文章目录 5. 队列 队列 5. 队列 队列 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

文章目录 5.1. 队列的实现 队列的实现 操作 5.1. 队列的实现 队列的实现 同栈一样，队列也可以用顺序表或者链表实现。 操作 Queue() 创建一个空的队列 enqueue(item) 往队列中添加一个item元素 dequeue() 从队列头部删除一个元素 is_empty() 判断一个队列是否为空 size() 返回队列的大小 class Queue(object): """队列""" ...

文章目录 5.2. 双端队列 双端队列 操作 实现 5.2. 双端队列 双端队列 双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。 操作 Deque() 创建一个空的双端队列 add_front(item) 从队头加入一个item元素 add_rear(item) 从队尾加入一个item元素 re...