数据结构与算法
数据结构（英语：data structure）是计算机中存储、组织数据的方式。
数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。
不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。
为什么要学习数据结构和算法？
随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，
而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。
常见的10种数据结构
1、数组
数组：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
定义结构体数组的方法很简单，同定义结构体变量是一样的，只不过将变量改成数组。
或者说同普通数组的定义是一模一样的，如：
structSTUDENT stu[10];
这就定义了一个结构体数组，共有 10 个元素，每个元素都是一个结构体变量，都包含所有的结构体成员。
结构体数组的引用与引用一个结构体变量在原理上是一样的。只不过结构体数组中有多个结构体变量，我们只需利用 for 循 环一个一个地使用结构体数组中的元素。
下面编写一个程序，编程要求：从键盘输入 5 个学生的基本信息，如姓名、年龄、性别、学号，然后将学号最大的学生的基本信息输出到屏幕（如果相同则输出最后一个）。
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 # include <stdio.h> # include <string.h> /* 编程要求： 从键盘输入 5 个学生的基本信息，如姓名、年龄、性别、学号，然后将学号最大的学生的基本信息输出到屏幕（如果相同则输出最后一个）。 */ struct STU { char name[20]; int age; char sex; char num[20]; }; void OutputSTU(struct STU stu[5]); //函数声明, 该函数的功能是输出学号最大的学生信息 int main(void) { int i; struct STU stu[5]; for (i = 0; i<5; ++i) { printf("请输入第%d个学生的信息:", i + 1); scanf("%s%d %c%s", stu[i].name, &stu[i].age, &stu[i].sex, stu[i].num);/*%c前面要加空格, 不然输入时会将空格赋给%c*/ } OutputSTU(stu); system("PAUSE");//结束不退出 } void OutputSTU(struct STU stu[5]) { struct STU stumax = stu[0]; int j; for (j = 1; j<5; ++j) { if (strcmp(stumax.num, stu[j].num) < 0) //strcmp函数的使用 { stumax = stu[j]; } } printf("学生姓名：%s 学生年龄：%d 学生性别：%c 学生学号：%s\n", stumax.name, stumax.age, stumax.sex, stumax.num); }
2、链表
链表：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
例如，使用链表存储 {1,2,3}，数据的物理存储状态如图 1 所示：
我们看到，图 1 根本无法体现出各数据之间的逻辑关系。
对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图 2 所示：
像图 2 这样，数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。
链表有 单链表、双向链表、静态链表，展开说的话比较多，这里就演示单链表，想要学习更多链表直接点击链接进入学习。
链表的节点
从图 2 可以看到，链表中每个数据的存储都由以下两部分组成：
- 数据元素本身，其所在的区域称为数据域；
- 指向直接后继元素的指针，所在的区域称为指针域；
即链表中存储各数据元素的结构如图 3 所示：
图 3 所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如图 4 所示：
因此，链表中每个节点的具体实现，需要使用 C 语言中的结构体，具体实现代码为：
typedef struct Link{ char elem; //代表数据域 struct Link * next; //代表指针域，指向直接后继元素 }link; //link为节点名，每个节点都是一个 link 结构体
提示，由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型（这里要写成 struct Link* 的形式）。
头节点，头指针和首元节点
其实，图 4 所示的链表结构并不完整。一个完整的链表需要由以下几部分构成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
- 其他节点：链表中其他的节点；
因此，一个存储 {1,2,3} 的完整链表结构如图 5 所示：
注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
明白了链表的基本结构，下面我们来学习如何创建一个链表。
链表的创建（初始化）
创建一个链表需要做如下工作：
- 声明一个头指针（如果有必要，可以声明一个头节点）；
- 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；
例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码如下：
link * initLink(){ link * p=NULL;//创建头指针 link * temp = (link*)malloc(sizeof(link));//创建首元节点 //首元节点先初始化 temp->elem = 1; temp->next = NULL; p = temp;//头指针指向首元节点 //从第二个节点开始创建 for (int i=2; i<5; i++) { //创建一个新节点并初始化 link *a=(link*)malloc(sizeof(link)); a->elem=i; a->next=NULL; //将temp节点与新建立的a节点建立逻辑关系 temp->next=a; //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对 temp=temp->next; } //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表 return p; }
3、堆
堆：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
最小堆：父结点的键值总是小于或等于任何一个子节点的键值。示意图如下：
假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85，需要执行的步骤如下：
如上图所示，当向最大堆中添加数据时：先将数据加入到最大堆的最后，然后尽可能把这个元素往上挪，直到挪不动为止！
将85添加到[90,80,70,60,40,30,20,10,50]中后，最大堆变成了[90,85,70,60,80,30,20,10,50,40]。
/* * 最大堆的向上调整算法(从start开始向上直到0，调整堆) * * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。 * * 参数说明： * start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引) */ static void maxheap_filterup(int start) { int c = start; // 当前节点(current)的位置 int p = (c-1)/2; // 父(parent)结点的位置 int tmp = m_heap[c]; // 当前节点(current)的大小 while(c > 0) { if(m_heap[p] >= tmp) break; else { m_heap[c] = m_heap[p]; c = p; p = (p-1)/2; } } m_heap[c] = tmp; } /* * 将data插入到二叉堆中 * * 返回值： * 0，表示成功 * -1，表示失败 */ int maxheap_insert(int data) { // 如果"堆"已满，则返回 if(m_size == m_capacity) return -1; m_heap[m_size] = data; // 将"数组"插在表尾 maxheap_filterup(m_size); // 向上调整堆 m_size++; // 堆的实际容量+1 return 0; }
更多详情请点击：二叉堆(一)之 图文解析 和 C语言的实现 ：https://www.cnblogs.com/skywang12345/p/3610187.html
4、栈
栈：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
栈是限制插入和删除只能在一个位置上进行的线性表。其中，允许插入和删除的一端位于表的末端，叫做栈顶（top），不允许插入和删除的另一端叫做栈底（bottom）。
对栈的基本操作有 PUSH（压栈）和 POP （出栈），前者相当于表的插入操作（向栈顶插入一个元素），后者则是删除操作（删除一个栈顶元素）。
栈是一种后进先出（LIFO）的数据结构，最先被删除的是最近压栈的元素。
栈就像是一个箱子，往里面放入一个小盒子就相当于压栈操作，往里面取出一个小盒子就是出栈操作，取盒子的时候，最后放进去的盒子会最先被取出来，最先放进去的盒子会最后被取出来，这即是后入先出。
下面是一个栈的示意图：
如下入栈出栈示例：
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> //元素elem进栈 int push(int* a, int top, int elem){ a[++top] = elem; return top; } //数据元素出栈 int pop(int * a, int top){ if (top == -1) { printf("空栈"); return -1; } printf("弹栈元素：%d\n", a[top]); top--; return top; } int main() { int a[100]; int top = -1; top = push(a, top, 1); top = push(a, top, 2); top = push(a, top, 3); top = push(a, top, 4); top = pop(a, top); top = pop(a, top); top = pop(a, top); top = pop(a, top); top = pop(a, top); system("PAUSE");//结束不退出 }
