数据结构与算法教程，数据结构C语言版教程！（第一部分、数据结构快速入门，数据结构基础详解）一

本套数据结构与算法教程，不仅讲解了基本的数据存储结构，还讲解了经典的算法，并把它们付诸实践，解决生活中的实际问题，例如停车场管理系统、迷宫游戏、字符过滤系统等。

这套数据结构教程，最大的特点是通俗易懂，深入浅出，摒弃教条主义，不做“学院派”，以“生动有趣”的笔风来讲解每个知识点，更配有完整的 C 语言实现代码供初学者参考。

数据结构是程序设计的重要理论基础，不管你从事什么方向的软件开发，一定会用到它。

第一部分、数据结构快速入门，数据结构基础详解

数据结构基础，主要研究数据存储的方式。

本章作为数据结构的入门课程，主要让读者明白，数据结构到底是什么，常用的数据存储结构有哪些，数据结构和算法之间到底有怎样的关系等等。

深度剖析数据结构的本质，同时以通俗易懂的语言描述出来，致力于让读者快速入门数据结构。

?一、什么是数据结构

当你决定看这篇文章，就意味着系统学习数据结构的开始。本节，我们先来讲什么是数据结构。

数据结构，直白地理解，就是研究数据的存储方式。

我们知道，数据存储只有一个目的，即为了方便后期对数据的再利用，就如同我们使用数组存储?{1,2,3,4,5}?是为了后期取得它们的加和值，无缘由的数据存储行为是对存储空间的不负责任。

因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容。

例如，一直以来大家面对的数据存储，都是类似存储 1、2、{a,b,c}、"http://data.biancheng.net" 这样的问题，解决方式无疑是用变量或者数组对数据进行存储，即：

int a=1;
int b=2;
char str[3]={'a','b','c'};
char *data="http://data.biancheng.net";

但是，如果要存储这样一组数据：{张亮，张平，张华，张群，张晶，张磊}，数据之间具有这样的关系：张亮是张平、张华和张群的父亲，同时张平还是张晶和张磊的父亲，数据之间的关系如图 1 所示：

图 1 数据及数据之间的关系

对于存储之间具有复杂关系的数据，如果还是用变量或数组来存储（比如用数组存储 {“张亮”,"张平",“张华”,"张群","张晶","张磊"} ），数据存储是没有问题，但是无法体现数据之间的逻辑关系，后期根本无法使用，显然不明智。

针对此类数据，数据结构中提供有专门的树结构来存储这类数据。

再比如，导航无疑是出游旅行的必备神器，在我们程序员眼中，无论是哪款导航软件，其导航功能的实现都需要大量地图数据的支持。很明显，这些数据绝不是使用变量或数组进行存储的，那样对于数据的使用简直是个悲剧。

针对此类数据，数据结构提供了《第七部分：一、数据结构的图存储结构》专门用于存储这类数据。

通过以上两个示例可以体会出，数据结构教会我们的绝不仅仅是如何存储 1、2、{a,b,c} 这样简单的数据，而是解决具有复杂关系的大量数据的存储问题。

因此，数据结构是什么??我认为，数据结构是一门学科，它教会我们“如何存储具有复杂关系的数据更有助于后期对数据的再利用”。

（1）如何存储具有复杂关系的数据

（2）便于后续对数据进行再利用

二、数据结构有哪些，常用数据结构详解

通过上节我们知道，数据结构是学习数据存储方式的一门学科，那么，数据存储方式有哪几种呢？本节将对数据结构的学习内容做一个简要的总结。

数据结构大致包含以下几种存储结构：

• 线性表（见《第二部分：一、什么是线性表（线性存储结构）》），还可细分为顺序表（见《第二部分：二、顺序表（顺序存储结构）及初始化详解》）、链表（见《第二部分：四、什么是单链表，链式存储结构详解》）、栈（见《第三部分：一、什么是栈，栈存储结构详解》）和队列（见《第三部分：七、什么是队列（队列存储结构）》）；
• 树结构，包括普通树，二叉树（见《第六部分：二、什么是二叉树（包含满二叉树和完全二叉树）》），线性二叉树（见《第六部分：十、线索二叉树（C语言详解）》）等；
• 图存储结构（见《第七部分：一、数据结构的图存储结构》）；

下面对各种数据结构做详细讲解。

1、线性表

线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。

例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。

线性表并不是一种具体的存储结构，它包含顺序存储结构（见《第二部分：二、顺序表（顺序存储结构）及初始化详解》）和链式存储结构（见《第二部分：四、什么是单链表，链式存储结构详解》），是顺序表和链表的统称。

（1）顺序表

顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}，如图 1 所示：

图 1 顺序表结构

由于顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。

（2）链表

我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，如图 1 所示。

链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。

为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），就如同一个个小学生都伸手去拉住下一个小学生的手，这样，看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表，如图 2 所示：

图 2 链表结构

（3）栈和队列

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。

图 3 栈结构示意图

栈结构如图 3 所示，像一个木桶，栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。

队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。

图 4 队列结构示意图

队列结构如图 4 所示，队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。

2、树存储结构

树存储结构适合存储具有“一对多”关系的数据。

图 5 树存储结构示意图

如图 5 所示，其中张平只有一个父亲，但他却有两（多）个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。

3、图存储结构

图存储结构适合存储具有“多对多”关系的数据。

图 6 图存储结构示意图

如图 6 所示，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。

?本节只是对数据结构中包含的各种存储结构做一个简要的介绍，各存储结构具体的实现会在后续文章中作详解介绍。