有口碑的番禺网站建设,ui设计职业培训机构,wap网站建设多少钱,服务好的专业建站公司目录 1 数组
1.1 数组常用操作
1. 初始化数组
2. 访问元素
3. 插入元素
4. 删除元素
5. 遍历数组
6. 查找元素
7. 扩容数组
1.2 数组优点与局限性
1.3 数组典型应用
2 链表
2.1 链表常用操作
1. 初始化链表
2. 插入节点
3. 删除…目录 1 数组
1.1 数组常用操作
1. 初始化数组
2. 访问元素
3. 插入元素
4. 删除元素
5. 遍历数组
6. 查找元素
7. 扩容数组
1.2 数组优点与局限性
1.3 数组典型应用
2 链表
2.1 链表常用操作
1. 初始化链表
2. 插入节点
3. 删除节点
4. 访问节点
5. 查找节点
2.2 数组 VS 链表
2.3 常见链表类型
2.4 链表典型应用
3 列表
3.1 列表常用操作
1. 初始化列表
2. 访问元素
3. 插入与删除元素
4. 遍历列表
5. 拼接列表
6. 排序列表
3.2 列表实现
4 小结
1. 重点回顾
2. Q A 1 数组
「数组 array」是一种线性数据结构其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的「索引 index」。图 4-1 展示了数组的主要术语和概念。 图 4-1 数组定义与存储方式
1.1 数组常用操作
1. 初始化数组
我们可以根据需求选用数组的两种初始化方式无初始值、给定初始值。在未指定初始值的情况下大多数编程语言会将数组元素初始化为 0 。 int arr[5] { 0 }; // { 0, 0, 0, 0, 0 }
int nums[5] { 1, 3, 2, 5, 4 };2. 访问元素
数组元素被存储在连续的内存空间中这意味着计算数组元素的内存地址非常容易。给定数组内存地址即首元素内存地址和某个元素的索引我们可以使用图 4-2 所示的公式计算得到该元素的内存地址从而直接访问此元素。 图 4-2 数组元素的内存地址计算
观察图 4-2 我们发现数组首个元素的索引为 0 这似乎有些反直觉因为从 1 开始计数会更自然。但从地址计算公式的角度看索引的含义本质上是内存地址的偏移量。首个元素的地址偏移量是 0 因此它的索引为 0 也是合理的。
在数组中访问元素是非常高效的我们可以在 O(1)内随机访问数组中的任意一个元素。 /* 随机访问元素 */
int randomAccess(int *nums, int size) {// 在区间 [0, size) 中随机抽取一个数字int randomIndex rand() % size;// 获取并返回随机元素int randomNum nums[randomIndex];return randomNum;
}3. 插入元素
数组元素在内存中是“紧挨着的”它们之间没有空间再存放任何数据。如图 4-3 所示如果想要在数组中间插入一个元素则需要将该元素之后的所有元素都向后移动一位之后再把元素赋值给该索引。 图 4-3 数组插入元素示例
值得注意的是由于数组的长度是固定的因此插入一个元素必定会导致数组尾部元素的“丢失”。我们将这个问题的解决方案留在列表章节中讨论。 /* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {// 把索引 index 以及之后的所有元素向后移动一位for (int i size - 1; i index; i--) {nums[i] nums[i - 1];}// 将 num 赋给 index 处元素nums[index] num;
}4. 删除元素
同理如图 4-4 所示若想要删除索引 i 处的元素则需要把索引 i 之后的元素都向前移动一位。 图 4-4 数组删除元素示例
请注意删除元素完成后原先末尾的元素变得“无意义”了所以我们无须特意去修改它。 /* 删除索引 index 处元素 */
// 注意stdio.h 占用了 remove 关键词
void removeItem(int *nums, int size, int index) {// 把索引 index 之后的所有元素向前移动一位for (int i index; i size - 1; i) {nums[i] nums[i 1];}
}总的来看数组的插入与删除操作有以下缺点。
时间复杂度高数组的插入和删除的平均时间复杂度均为 O(n) 其中 n 为数组长度。丢失元素由于数组的长度不可变因此在插入元素后超出数组长度范围的元素会丢失。内存浪费我们可以初始化一个比较长的数组只用前面一部分这样在插入数据时丢失的末尾元素都是“无意义”的但这样做也会造成部分内存空间的浪费。
5. 遍历数组
在大多数编程语言中我们既可以通过索引遍历数组也可以直接遍历获取数组中的每个元素。 /* 遍历数组 */
void traverse(int *nums, int size) {int count 0;// 通过索引遍历数组for (int i 0; i size; i) {count;}
}6. 查找元素
在数组中查找指定元素需要遍历数组每轮判断元素值是否匹配若匹配则输出对应索引。
因为数组是线性数据结构所以上述查找操作被称为“线性查找”。 /* 在数组中查找指定元素 */
int find(int *nums, int size, int target) {for (int i 0; i size; i) {if (nums[i] target)return i;}return -1;
}7. 扩容数组
在复杂的系统环境中程序难以保证数组之后的内存空间是可用的从而无法安全地扩展数组容量。因此在大多数编程语言中数组的长度是不可变的。
如果我们希望扩容数组则需重新建立一个更大的数组然后把原数组元素依次拷贝到新数组。这是一个 O(n) 的操作在数组很大的情况下是非常耗时的。 /* 扩展数组长度 */
int *extend(int *nums, int size, int enlarge) {// 初始化一个扩展长度后的数组int *res (int *)malloc(sizeof(int) * (size enlarge));// 将原数组中的所有元素复制到新数组for (int i 0; i size; i) {res[i] nums[i];}// 初始化扩展后的空间for (int i size; i size enlarge; i) {res[i] 0;}// 返回扩展后的新数组return res;
}1.2 数组优点与局限性
数组存储在连续的内存空间内且元素类型相同。这种做法包含丰富的先验信息系统可以利用这些信息来优化数据结构的操作效率。
空间效率高: 数组为数据分配了连续的内存块无须额外的结构开销。支持随机访问: 数组允许在 O(1) 时间内访问任何元素。缓存局部性: 当访问数组元素时计算机不仅会加载它还会缓存其周围的其他数据从而借助高速缓存来提升后续操作的执行速度。
连续空间存储是一把双刃剑其存在以下缺点。
插入与删除效率低:当数组中元素较多时插入与删除操作需要移动大量的元素。长度不可变: 数组在初始化后长度就固定了扩容数组需要将所有数据复制到新数组开销很大。空间浪费: 如果数组分配的大小超过了实际所需那么多余的空间就被浪费了。
1.3 数组典型应用
数组是一种基础且常见的数据结构既频繁应用在各类算法之中也可用于实现各种复杂数据结构。
随机访问如果我们想要随机抽取一些样本那么可以用数组存储并生成一个随机序列根据索引实现样本的随机抽取。排序和搜索数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。查找表当我们需要快速查找一个元素或者需要查找一个元素的对应关系时可以使用数组作为查找表。假如我们想要实现字符到 ASCII 码的映射则可以将字符的 ASCII 码值作为索引对应的元素存放在数组中的对应位置。机器学习神经网络中大量使用了向量、矩阵、张量之间的线性代数运算这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。数据结构实现数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如图的邻接矩阵表示实际上是一个二维数组。
2 链表
内存空间是所有程序的公共资源在一个复杂的系统运行环境下空闲的内存空间可能散落在内存各处。我们知道存储数组的内存空间必须是连续的而当数组非常大时内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
「链表 linked list」是一种线性数据结构其中的每个元素都是一个节点对象各个节点通过“引用”相连接。引用记录了下一个节点的内存地址通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以被分散存储在内存各处它们的内存地址是无须连续的。 图 4-5 链表定义与存储方式
观察图 4-5 链表的组成单位是「节点 node」对象。每个节点都包含两项数据节点的“值”和指向下一节点的“引用”。
链表的首个节点被称为“头节点”最后一个节点被称为“尾节点”。尾节点指向的是“空”它在 Java、C 和 Python 中分别被记为 null、nullptr 和 None 。在 C、C、Go 和 Rust 等支持指针的语言中上述的“引用”应被替换为“指针”。
如以下代码所示链表节点 ListNode 除了包含值还需额外保存一个引用指针。因此在相同数据量下链表比数组占用更多的内存空间。 /* 链表节点结构体 */
struct ListNode {int val; // 节点值struct ListNode *next; // 指向下一节点的指针
};typedef struct ListNode ListNode;/* 构造函数 */
ListNode *newListNode(int val) {ListNode *node, *next;node (ListNode *) malloc(sizeof(ListNode));node-val val;node-next NULL;return node;
}2.1 链表常用操作
1. 初始化链表
建立链表分为两步第一步是初始化各个节点对象第二步是构建引用指向关系。初始化完成后我们就可以从链表的头节点出发通过引用指向 next 依次访问所有节点。 /* 初始化链表 1 - 3 - 2 - 5 - 4 */
// 初始化各个节点
ListNode* n0 newListNode(1);
ListNode* n1 newListNode(3);
ListNode* n2 newListNode(2);
ListNode* n3 newListNode(5);
ListNode* n4 newListNode(4);
// 构建引用指向
n0-next n1;
n1-next n2;
n2-next n3;
n3-next n4;数组整体是一个变量比如数组 nums 包含元素 nums[0] 和 nums[1] 等而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称比如以上代码中的链表可被记做链表 n0 。
2. 插入节点
在链表中插入节点非常容易。如图 4-6 所示假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P 则只需要改变两个节点引用指针即可时间复杂度为 O(1) 。
相比之下在数组中插入元素的时间复杂度为 O(n) 在大数据量下的效率较低。 图 4-6 链表插入节点示例 /* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {ListNode *n1 n0-next;P-next n1;n0-next P;
}3. 删除节点
如图 4-7 所示在链表中删除节点也非常方便只需改变一个节点的引用指针即可。
请注意尽管在删除操作完成后节点 P 仍然指向 n1 但实际上遍历此链表已经无法访问到 P 这意味着 P 已经不再属于该链表了。 图 4-7 链表删除节点 /* 删除链表的节点 n0 之后的首个节点 */
// 注意stdio.h 占用了 remove 关键词
void removeNode(ListNode *n0) {if (!n0-next)return;// n0 - P - n1ListNode *P n0-next;ListNode *n1 P-next;n0-next n1;// 释放内存free(P);
}4. 访问节点
在链表访问节点的效率较低。如上节所述我们可以在 O(1) 时间下访问数组中的任意元素。链表则不然程序需要从头节点出发逐个向后遍历直至找到目标节点。也就是说访问链表的第 i 个节点需要循环 i−1 轮时间复杂度为 O(n) 。 /* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {while (head head-next index) {head head-next;index--;}return head;
}5. 查找节点
遍历链表查找链表内值为 target 的节点输出节点在链表中的索引。此过程也属于线性查找。 /* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {int index 0;while (head) {if (head-val target)return index;head head-next;index;}return -1;
}2.2 数组 VS 链表
表 4-1 总结对比了数组和链表的各项特点与操作效率。由于它们采用两种相反的存储策略因此各种性质和操作效率也呈现对立的特点。
表 4-1 数组与链表的效率对比
数组链表存储方式连续内存空间分散内存空间缓存局部性友好不友好容量扩展长度不可变可灵活扩展内存效率占用内存少、浪费部分空间占用内存多访问元素O(1)O(n)添加元素O(n)O(1)删除元素O(n)O(1)
2.3 常见链表类型
如图 4-8 所示常见的链表类型包括三种。
单向链表即上述介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点将最后一个节点称为尾节点尾节点指向空 None 。环形链表如果我们令单向链表的尾节点指向头节点即首尾相接则得到一个环形链表。在环形链表中任意节点都可以视作头节点。双向链表与单向链表相比双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点下一个节点和前驱节点上一个节点的引用指针。相较于单向链表双向链表更具灵活性可以朝两个方向遍历链表但相应地也需要占用更多的内存空间。 /* 双向链表节点结构体 */
struct ListNode {int val; // 节点值struct ListNode *next; // 指向后继节点的指针struct ListNode *prev; // 指向前驱节点的指针
};typedef struct ListNode ListNode;/* 构造函数 */
ListNode *newListNode(int val) {ListNode *node, *next;node (ListNode *) malloc(sizeof(ListNode));node-val val;node-next NULL;node-prev NULL;return node;
}图 4-8 常见链表种类
2.4 链表典型应用
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
栈与队列当插入和删除操作都在链表的一端进行时它表现出先进后出的的特性对应栈当插入操作在链表的一端进行删除操作在链表的另一端进行它表现出先进先出的特性对应队列。哈希表链地址法是解决哈希冲突的主流方案之一在该方案中所有冲突的元素都会被放到一个链表中。图邻接表是表示图的一种常用方式在其中图的每个顶点都与一个链表相关联链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表常被用于需要快速查找前一个和下一个元素的场景。
高级数据结构比如在红黑树、B 树中我们需要访问节点的父节点这可以通过在节点中保存一个指向父节点的引用来实现类似于双向链表。浏览器历史在网页浏览器中当用户点击前进或后退按钮时浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。LRU 算法在缓存淘汰算法LRU中我们需要快速找到最近最少使用的数据以及支持快速地添加和删除节点。这时候使用双向链表就非常合适。
循环链表常被用于需要周期性操作的场景比如操作系统的资源调度。
时间片轮转调度算法在操作系统中时间片轮转调度算法是一种常见的 CPU 调度算法它需要对一组进程进行循环。每个进程被赋予一个时间片当时间片用完时CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现。数据缓冲区在某些数据缓冲区的实现中也可能会使用到循环链表。比如在音频、视频播放器中数据流可能会被分成多个缓冲块并放入一个循环链表以便实现无缝播放。 3 列表
数组长度不可变导致实用性降低。在实际中我们可能事先无法确定需要存储多少数据这使数组长度的选择变得困难。若长度过小需要在持续添加数据时频繁扩容数组若长度过大则会造成内存空间的浪费。
为解决此问题出现了一种被称为「动态数组 dynamic array」的数据结构即长度可变的数组也常被称为「列表 list」。列表基于数组实现继承了数组的优点并且可以在程序运行过程中动态扩容。我们可以在列表中自由地添加元素而无须担心超过容量限制。
3.1 列表常用操作
1. 初始化列表
我们通常使用“无初始值”和“有初始值”这两种初始化方法。 // C 未提供内置动态数组2. 访问元素
列表本质上是数组因此可以在 O(1) 时间内访问和更新元素效率很高。 // C 未提供内置动态数组3. 插入与删除元素
相较于数组列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 (1) 但插入和删除元素的效率仍与数组相同时间复杂度为 O(n) 。 // C 未提供内置动态数组4. 遍历列表
与数组一样列表可以根据索引遍历也可以直接遍历各元素。
// C 未提供内置动态数组5. 拼接列表
给定一个新列表 list1 我们可以将该列表拼接到原列表的尾部。 // C 未提供内置动态数组6. 排序列表
完成列表排序后我们便可以使用在数组类算法题中经常考察的“二分查找”和“双指针”算法。 // C 未提供内置动态数组3.2 列表实现
许多编程语言都提供内置的列表例如 Java、C、Python 等。它们的实现比较复杂各个参数的设定也非常有考究例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。
为了加深对列表工作原理的理解我们尝试实现一个简易版列表包括以下三个重点设计。
初始容量选取一个合理的数组初始容量。在本示例中我们选择 10 作为初始容量。数量记录声明一个变量 size 用于记录列表当前元素数量并随着元素插入和删除实时更新。根据此变量我们可以定位列表尾部以及判断是否需要扩容。扩容机制若插入元素时列表容量已满则需要进行扩容。首先根据扩容倍数创建一个更大的数组再将当前数组的所有元素依次移动至新数组。在本示例中我们规定每次将数组扩容至之前的 2 倍。 /* 列表类简易实现 */
struct myList {int *nums; // 数组存储列表元素int capacity; // 列表容量int size; // 列表大小int extendRatio; // 列表每次扩容的倍数
};typedef struct myList myList;/* 构造函数 */
myList *newMyList() {myList *list malloc(sizeof(myList));list-capacity 10;list-nums malloc(sizeof(int) * list-capacity);list-size 0;list-extendRatio 2;return list;
}/* 析构函数 */
void delMyList(myList *list) {free(list-nums);free(list);
}/* 获取列表长度 */
int size(myList *list) {return list-size;
}/* 获取列表容量 */
int capacity(myList *list) {return list-capacity;
}/* 访问元素 */
int get(myList *list, int index) {assert(index 0 index list-size);return list-nums[index];
}/* 更新元素 */
void set(myList *list, int index, int num) {assert(index 0 index list-size);list-nums[index] num;
}/* 尾部添加元素 */
void add(myList *list, int num) {if (size(list) capacity(list)) {extendCapacity(list); // 扩容}list-nums[size(list)] num;list-size;
}/* 中间插入元素 */
void insert(myList *list, int index, int num) {assert(index 0 index size(list));// 元素数量超出容量时触发扩容机制if (size(list) capacity(list)) {extendCapacity(list); // 扩容}for (int i size(list); i index; --i) {list-nums[i] list-nums[i - 1];}list-nums[index] num;list-size;
}/* 删除元素 */
// 注意stdio.h 占用了 remove 关键词
int removeNum(myList *list, int index) {assert(index 0 index size(list));int num list-nums[index];for (int i index; i size(list) - 1; i) {list-nums[i] list-nums[i 1];}list-size--;return num;
}/* 列表扩容 */
void extendCapacity(myList *list) {// 先分配空间int newCapacity capacity(list) * list-extendRatio;int *extend (int *)malloc(sizeof(int) * newCapacity);int *temp list-nums;// 拷贝旧数据到新数据for (int i 0; i size(list); i)extend[i] list-nums[i];// 释放旧数据free(temp);// 更新新数据list-nums extend;list-capacity newCapacity;
}/* 将列表转换为 Array 用于打印 */
int *toArray(myList *list) {return list-nums;
}4 小结
1. 重点回顾
数组和链表是两种基本的数据结构分别代表数据在计算机内存中的两种存储方式连续空间存储和分散空间存储。两者的特点呈现出互补的特性。数组支持随机访问、占用内存较少但插入和删除元素效率低且初始化后长度不可变。链表通过更改引用指针实现高效的节点插入与删除且可以灵活调整长度但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、循环链表、双向链表。动态数组又称列表是基于数组实现的一种数据结构。它保留了数组的优势同时可以灵活调整长度。列表的出现极大地提高了数组的易用性但可能导致部分内存空间浪费。
2. Q A
数组存储在栈上和存储在堆上对时间效率和空间效率是否有影响
存储在栈上和堆上的数组都被存储在连续内存空间内数据操作效率是基本一致的。然而栈和堆具有各自的特点从而导致以下不同点。
分配和释放效率栈是一块较小的内存分配由编译器自动完成而堆内存相对更大可以在代码中动态分配更容易碎片化。因此堆上的分配和释放操作通常比栈上的慢。大小限制栈内存相对较小堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。灵活性栈上的数组的大小需要在编译时确定而堆上的数组的大小可以在运行时动态确定。
为什么数组要求相同类型的元素而在链表中却没有强调同类型呢
链表由结点组成结点之间通过引用指针连接各个结点可以存储不同类型的数据例如 int、double、string、object 等。
相对地数组元素则必须是相同类型的这样才能通过计算偏移量来获取对应元素位置。例如如果数组同时包含 int 和 long 两种类型单个元素分别占用 4 bytes 和 8 bytes 那么此时就不能用以下公式计算偏移量了因为数组中包含了两种长度的元素。
# 元素内存地址 数组内存地址 元素长度 * 元素索引删除节点后是否需要把 P.next 设为 None 呢
不修改 P.next 也可以。从该链表的角度看从头结点遍历到尾结点已经遇不到 P 了。这意味着结点 P 已经从链表中删除了此时结点 P 指向哪里都不会对这条链表产生影响了。
从垃圾回收的角度看对于 Java、Python、Go 等拥有自动垃圾回收的语言来说节点 P 是否被回收取决于是否有仍存在指向它的引用而不是 P.next 的值。在 C 和 C 等语言中我们需要手动释放节点内存。
在链表中插入和删除操作的时间复杂度是 O(1) 。但是增删之前都需要 O(n) 查找元素那为什么时间复杂度不是 O(n) 呢
如果是先查找元素、再删除元素确实是 O(n) 。然而链表的 O(1) 增删的优势可以在其他应用上得到体现。例如双向队列适合使用链表实现我们维护一个指针变量始终指向头结点、尾结点每次插入与删除操作都是 O(1) 。
图片“链表定义与存储方式”中浅蓝色的存储结点指针是占用一块内存地址吗还是和结点值各占一半呢
文中的示意图只是定性表示定量表示需要根据具体情况进行分析。
不同类型的结点值占用的空间是不同的比如 int、long、double 和实例对象等。指针变量占用的内存空间大小根据所使用的操作系统及编译环境而定大多为 8 字节或 4 字节。
在列表末尾添加元素是否时时刻刻都为 O(1)
如果添加元素时超出列表长度则需要先扩容列表再添加。系统会申请一块新的内存并将原列表的所有元素搬运过去这时候时间复杂度就会是 O(n) 。
“列表的出现大大提升了数组的实用性但副作用是会造成部分内存空间浪费”这里的空间浪费是指额外增加的变量如容量、长度、扩容倍数所占的内存吗
这里的空间浪费主要有两方面含义一方面列表都会设定一个初始长度我们不一定需要用这么多。另一方面为了防止频繁扩容扩容一般都会乘以一个系数比如 ×1.5 。这样一来也会出现很多空位我们通常不能完全填满它们。
在 Python 中初始化 n [1, 2, 3] 后这 3 个元素的地址是相连的但是初始化 m [2, 1, 3] 会发现它们每个元素的 id 并不是连续的而是分别跟 n 中的相同。这些元素地址不连续那么 m 还是数组吗
假如把列表元素换成链表节点 n [n1, n2, n3, n4, n5] 通常情况下这五个节点对象也是被分散存储在内存各处的。然而给定一个列表索引我们仍然可以在 O(1) 时间内获取到节点内存地址从而访问到对应的节点。这是因为数组中存储的是节点的引用而非节点本身。
与许多语言不同的是在 Python 中数字也被包装为对象列表中存储的不是数字本身而是对数字的引用。因此我们会发现两个数组中的相同数字拥有同一个 id 并且这些数字的内存地址是无须连续的。
C STL 里面的 std::list 已经实现了双向链表但好像一些算法的书上都不怎么直接用这个是不是有什么局限性呢?
一方面我们往往更青睐使用数组实现算法而只有在必要时才使用链表主要有两个原因。
空间开销由于每个元素需要两个额外的指针一个用于前一个元素一个用于后一个元素所以 std::list 通常比 std::vector 更占用空间。缓存不友好由于数据不是连续存放的std::list 对缓存的利用率较低。一般情况下std::vector 的性能会更好。
另一方面必要使用链表的情况主要是二叉树和图。栈和队列往往会使用编程语言提供的 stack 和 queue 而非链表。
