24 篇文档带有标签「数据结构」

寻址方式是指寻找指令或操作数有效地址的方式，即确定本条指令的数据地址及下一条待执行指令的地址的方法。寻址方式分为指令寻址和数据寻址两大类。

基础数据类型 (Primitive Types)

数组（Array）是一种线性数据结构，它由相同类型的元素按顺序排列组成。每个元素在数组中占据一个固定的位置，这些位置由索引（也称为下标）标识。数组的索引通常从零开始，这意味着第一个元素的索引是 $0$，第二个元素的索引是 $1$，以此类推。

单链表结点中只有一个指向其后继的指针，使得单链表只能从头节点依次顺序地向后遍历。要访问某个结点的前驱节点（插入、删除操作时），只能从头开始遍历， 访问后继节点的时间复杂度为 $O(1)$，访问前驱节点的时间复杂度为 $O(n)$。

在循环链表中最后一个节点指向第一个节点，形成一个环。循环链表可以使用单向链表实现也可以使用双向链表实现。

本部分列出一些在学习数据结构之前最好先了解一下的基础知识。包括内存的寻址方式，操作系统中的内存管理等。

在计算机科学中数据结构是很重要的一部分，如果不熟悉数据结构，那么算法的学习也将举步维艰。只有先把数据结构的基础打好，算法学习起来才能得心应手。

动态数组或者叫可变长数组（Variable-Length Array, VLA），有两种解释。

本部分将述数组的基本概念以及数组的使用、数组的内存结构、动态数组的实现等内容。在大部分的数据结构教材中对数组是没有单独章节来讲述的。并且需要注意的是，数组与线性表（也称顺序表或有序表）并不是一回事。我们可以说线性表可以使用数组来实现，但是不能说数组就是线性表。因为有很多线性表的特性，数组是没有的。关于线性表的 ADT 可以在线性表章节中看到。

也称顺序表 (Sequential List)或有序表 (Ordered List)。它是元素的一个有序集合，其长度有限，并且可以根据需要自动伸缩。其形式如下：

链表是一种常见的基础数据结构，是一种线性表。链表中的每个元素都存储有下个元素的指针，通过首尾相接的方式将所有元素有序的串在一起。链表并不要求所有元素在内存中的位置是相邻的，所有元素都可以分散地存储在内存中。

单向链表的特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

跳表（Skip List）是一种随机化的数据结构，它在链表的基础上引入多级索引，从而实现类似于平衡树的对数时间复杂度的搜索、插入和删除操作。跳表由 William Pugh 于1990年发明，用于替代平衡树。跳表主要用于有序数据序列，

算法（英语：algorithm），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。

本部分将介绍一些算法的基本思想，包括递归、分治法、贪心算法等

在算法设计中，常常引入分而治之的策略，称之为分治算法，其本质就是将一个大规模的问题分解为若干规模较小的相同子问题，分而治之。分治算法是一种解题的思想，并不是某种如冒泡排序算法一样的固定的算法。

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。从问题的初始解开始，一步歩地做出当前最好的选择，逐步逼近问题的目标，尽可能得到最优解；即使得不到最优解，也可以得到最优解的近似解。

以下是针对 coding-interview-university 中 「 算法复杂度 / Big-O / 渐进分析法 」 部分知识的学习笔记。

算法（英语：algorithm），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。

多项式求值 $P(x)=ax^{n}+a{n-1}x^{n-1}+a{n-2}x^{n-2}+...+a{3}x^{3}+a{2}x^{2}+a{1}x$，

在阅读本章时，请先抛开算法中关于 大$O$ 的一些定义，先从数学的角度来理解 大$O$。另外这部分是纯数学理论。大部分内容来自《离散数学及其应用》的第三章。

算法的效率如何分析呢？一种度量方式是当输入值具有一定规模时，计算机按此算法解题所花的时间。第二种度量方式是输入值具有一定规模时，实现这一算法计算机需要多大内存。