数据结构入门

目录

1.为什么要学数据结构？

1.1.数据结构在计算机科学中的基础地位

1.2.为什么学习数据结构是编程和算法设计的基石？

1.2.1.数据是编程的核心，而数据结构决定 “怎么存”

1.2.2.数据结构直接决定 “处理效率”

1.2.3.算法依赖数据结构才能落地

1.3.学习目标：培养抽象思维、高效问题解决能力。

2.数据结构的定义

2.1.什么是数据结构

2.2.核心元素

2.3.抽象数据类型（ADT）

3.数据结构类型与实现

3.1.常见数据结构类型

3.2.算法实现与操作

3.3.复杂度分析

本文旨在说明数据结构是什么，以及为什么要学习数据结构，对于数据结构的相关细节，并未过多提及。

1.为什么要学数据结构？

1.1.数据结构在计算机科学中的基础地位

数据结构在计算机科学中就像 “收纳架”—— 计算机处理的所有信息（比如文字、图片、订单记录等）都需要按规则 “摆放”，而数据结构就是这套 “摆放规则”。

它的基础地位体现在：

是所有操作的前提：不管是存数据、查数据还是改数据，先得明确数据怎么组织（比如按顺序排、按层级分、按关联关系连），否则数据就是乱糟糟的一堆，根本没法高效处理。例如：在一堆乱糟糟的衣服和一排用衣架挂着的衣服中选择自己今天要穿的衣服，选择速度是不一样的。决定效率的核心：同样的任务（比如查一个名字），用不同 “架子”（比如数组 vs 哈希表），速度可能差几千倍。例如：在一堆衣服里找自己想要的衣服，一般会一件件翻找；而在一排衣架挂着的衣服中选择自己想要的，一眼就能看到。算法（解决问题的步骤）的好坏，很大程度上依赖于选对数据结构。例如：一堆衣服大概率只能一件件翻，才能找到自己想要的；而一排衣服可以一件件翻，也可以一眼就找到。贯穿所有领域：编程、数据库、操作系统、人工智能等，只要涉及数据处理，就离不开它。比如数据库用 “B 树” 快速查数据，游戏里用 “图” 表示地图关卡，都是数据结构的具体应用。

只要是衣服，你要么就一堆丢在那里，要么就用衣架挂起来，要么就是其它存放方式。总之你只要有一些衣服，你就需要规划如何存放这些衣服。而存放这些衣服的方式，就是数据结构要研究的内容，比如：把衣服乱堆，这是一种数据结构；而把衣服用衣架挂成一排，这也是一种数据结构。

数据结构是计算机处理信息的 “地基”—— 没有它，再复杂的技术都搭不起来。

1.2.为什么学习数据结构是编程和算法设计的基石？

1.2.1.数据是编程的核心，而数据结构决定 “怎么存”

编程的本质是处理数据（比如用户信息、订单记录、图片像素等）。

数据结构就像 “容器”，不同的容器（数组、链表、树等）适合存放不同类型的数据。比如存 100 个固定顺序的成绩，用数组（连续空间）查起来快；但如果要频繁插入 / 删除成绩，链表（每个元素带指针）更灵活。

没有合适的 “容器”，数据就无法被高效管理，后续处理更无从谈起。

你有衣服，你总要选择合适的存放方式（乱堆起来、用衣架挂成一排），不然你要拿出来或者放进去都不方便。

1.2.2.数据结构直接决定 “处理效率”

同样的问题，用不同数据结构，效率天差地别。

比如查一个名字是否在 100 万个名字里：用数组可能要逐个找（最坏查 100 万次）；用哈希表（类似字典，通过 “键” 直接定位）可能 1 次就找到。

算法的好坏很大程度看效率，而效率的根基就是数据结构 —— 选对了结构，才能让算法 “跑起来不费力”。

你把衣服挂起来，一眼就能找到自己想要的；堆成一坨，要找半天。

1.2.3.算法依赖数据结构才能落地

算法是 “解决问题的步骤”，但步骤必须基于具体的数据组织方式。

比如排序算法，对数组排序和对链表排序的步骤完全不同；导航软件找最短路径（用图结构，节点是地点、边是路径），必须依赖 “图” 这种结构才能设计出高效步骤。

没有数据结构，算法就成了 “空中楼阁”，无法转化为可执行的代码。

你要找衣服，必须得先有衣服（数据）。有了衣服，就一定会有衣服的存放方式（你哪怕是空想出来的衣服，它也会有一个存放方式），要么堆起来放，要么挂着放，而这种存放方式，就叫数据结构。

1.3.学习目标：培养抽象思维、高效问题解决能力。

学习数据结构的核心目标，简单说就是：

学会 “合理收纳数据”—— 知道用什么方式（比如数组、链表、树等）存储数据最合适，让后续操作（增删改查）更方便；（怎么存放衣服比较合适）提升效率 —— 让处理数据时少花时间、少占空间，尤其面对海量数据时，好的结构能避免程序 “卡壳”；（怎么存放衣服，找起来的时候才方便）解决复杂问题更轻松 —— 很多难题（比如排序、找最优解）靠合适的数据结构能简化逻辑，让问题变 “好下手”；（把衣服从大到小排，堆成一坨的衣服不好排；用衣架挂着的一眼就能看到谁大谁小，就很好排）打牢基础 —— 它是学算法、编程深入、数据库等知识的 “地基”，不懂数据结构，后面很多内容学不透；（你不学基础的衣服存放方式，你连怎么快速拿到自己想要的衣服都不知道。举个简单例子，当你用衣架挂了一排非常长的衣服时，你要怎么才能找到自己需要的衣服？你一眼看不出来的吧，数据结构这门课就是教你如何快速地找到自己想要的衣服）培养结构化思维 —— 遇到问题时，先想清楚 “数据怎么放”，再想 “怎么处理”，让解决问题更有条理。（衣服要怎么放，怎么才能快速拿到想要的衣服）

说到底，就是让我们跟数据 “打交道” 时更聪明、更高效。

2.数据结构的定义

2.1.什么是数据结构

数据结构简单说就是 “组织和存储数据的方式”。

打个比方：你家里的书，是按类别放书架（像数组）、还是按借阅顺序堆成一摞（像栈）、还是排成一队等着登记（像队列）？不同的摆法，找书、添书、挪书的方便程度不一样 —— 这就是数据结构的核心：通过特定的规则把数据 “排好队、放到位”，让数据之间的关系更清晰，后续对数据的增删改查等操作更高效。

它不只是 “存数据”，更关注数据之间的关系（比如谁挨着谁、谁包含谁），以及怎么用最高效的方式处理这些数据。常见的像列表、字典、树、图等，都是具体的数据结构。

2.2.核心元素

数据结构的核心元素可以概括为以下四点，用通俗的方式理解：

数据元素：就是 “要处理的数据本身”，比如数字、文字、对象等，是最基本的单位（比如通讯录里的 “某个人的信息”）。

逻辑结构：指 “数据元素之间的关系”，比如：

线性关系（像排队，一个接一个，如数组、链表）；层次关系（像家谱，有父有子，如树）；网状关系（像社交网络，任意两人可能相连，如图）。 这是 “抽象层面” 的关系，不关心具体存在哪里。 物理结构（存储结构）：指 “这些关系在计算机里怎么存”，即数据实际的存储方式：

顺序存储（挤在连续的内存空间里，比如数组）；链式存储（分散存在内存各处，用 “指针” 串起来，比如链表）。 这决定了数据操作的效率（比如查数据快不快、增删方便不方便）。 基本操作：指 “对数据能做的事”，比如增删数据、查找数据、修改数据等。不同的结构，这些操作的效率天差地别（比如数组查得快，链表删得快）。

简单说，数据结构就是：用什么方式（逻辑 / 物理结构）组织数据（元素），以及怎么高效地操作它们。

2.3.抽象数据类型（ADT）

抽象数据类型可以简单理解为：对一类数据的 “抽象描述”。

它包含两部分：一是这类数据里有哪些信息（比如 “学生” 包含姓名、学号等）；二是能对这些信息做哪些操作（比如查询、修改学生信息等）。

关键是，它只说 “有什么” 和 “能做什么”，不说 “具体怎么做”（比如不用管这些信息存在电脑内存的哪个位置）。——接口与实现的分离

比如 “手机通讯录” 就是一种抽象数据类型：数据是联系人（姓名、电话），操作是添加、删除、查找联系人，而具体是存在手机内存还是 SIM 卡，用户不用关心。

简单来说就是能挂在衣架上的不只是衣服，被子、丝绸等物都可以挂在衣架上。

抽象数据类型，就是有一类物品（一类数据），这类物品有衣服、被子和丝绸等（这类数据拥有的信息），可以挂在衣架上，也可以从衣架上拿下来（对这些信息的操作），你怎么挂衣服和怎么把衣服从衣架上拿下来，我管不着，只要能挂上去和拿下来就行。

3.数据结构类型与实现

3.1.常见数据结构类型

线性结构：数组、链表、栈、队列。

// 数组

#define MAX_SIZE 100

typedef int ElementType;

ElementType array[MAX_SIZE];

// 链表

typedef struct Node {

ElementType data;

struct Node* next;

} Node;

typedef struct {

Node* head;

int size;

} LinkedList;

// 栈（链式实现）

typedef struct StackNode {

ElementType data;

struct StackNode* next;

} StackNode;

typedef struct {

StackNode* top;

} Stack;

// 队列（链式实现）

typedef struct QueueNode {

ElementType data;

struct QueueNode* next;

} QueueNode;

typedef struct {

QueueNode* front;

QueueNode* rear;

int size;

} Queue;

非线性结构：树（二叉树、堆、二叉搜索树）、图（有向图、无向图）。

// 二叉树

typedef struct TreeNode {

ElementType data;

struct TreeNode* left;

struct TreeNode* right;

} TreeNode;

// 最大堆

#define MAX_HEAP_SIZE 100

typedef struct {

ElementType* data;

int size;

int capacity;

} MaxHeap;

// 二叉搜索树

typedef struct BSTNode {

ElementType data;

struct BSTNode* left;

struct BSTNode* right;

} BSTNode;

// 有向图（邻接表实现）

typedef struct AdjListNode {

int vertex;

struct AdjListNode* next;

} AdjListNode;

typedef struct {

AdjListNode** adjList;

int numVertices;

} DirectedGraph;

// 无向图（邻接表实现）

typedef struct UndirectedGraph {

AdjListNode** adjList;

int numVertices;

} UndirectedGraph;

散列结构：哈希表。

// 哈希表（链地址法处理冲突）

typedef struct HashNode {

ElementType key;

ElementType value;

struct HashNode* next;

} HashNode;

typedef struct {

HashNode** table;

int size;

int capacity;

} HashTable;

3.2.算法实现与操作

基本操作：如何实现插入、删除、遍历等。

// 定义单链表节点结构

typedef struct Node {

int data; // 数据域

struct Node* next; // 指向下一个节点的指针

} Node;

// 创建新节点

Node* createNode(int data);

// 插入操作：在链表头部插入节点

void insertAtHead(Node** head_ref, int data);

// 删除操作：删除指定值的第一个节点

void deleteNode(Node** head_ref, int key);

// 遍历操作：打印链表中的所有元素

void traverseList(Node* head);

// 其它操作

···

3.3.复杂度分析

时间复杂度和空间复杂度是衡量算法效率的两个核心指标，都描述了算法随输入数据规模（比如 n 个元素）增长时的变化趋势，而非具体数值。

时间复杂度：算法 “算得快不快”

指算法执行时所需步骤（或操作次数）随输入规模 n 增长的趋势。

比如：

逐个检查 n 个元素（遍历），需要 n 步，趋势是 “随 n 线性增长”，记为 O (n)；两层循环逐个比较 n 个元素（比如冒泡排序），需要 n×n 步，趋势是 “随 n 平方增长”，记为 O (n²)；二分查找（每次排除一半元素），需要 步，趋势是 “随 n 对数增长”，记为 O ()。

核心：数值越小（比如 O () < O (n) < O (n²)），算法越 “快”。

空间复杂度：算法 “用得省不省”

指算法执行时所需额外空间（除输入数据外的临时空间）随输入规模 n 增长的趋势。 比如：

只用到几个临时变量（比如交换两个数），不管 n 多大，空间都不变，趋势是 “固定空间”，记为 O (1)；用一个长度为 n 的数组存中间结果，空间随 n 线性增长，记为 O (n)；递归调用 n 次（每次递归存一个变量），栈空间随 n 增长，记为 O (n)。

核心：数值越小（比如 O (1) < O (n)），算法越 “省空间”。

简单说：时间复杂度看 “步骤增长快慢”，空间复杂度看 “额外空间增长快慢”，都是为了判断算法在数据量变大时的效率。