数据结构(一) 1. 概述
数据结构定义:
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(如元素的CURD、排序等)而执行的相应操作，这个相应的操作也叫算法。
数据结构 = 元素 + 元素的关系
算法 = 对数据结构的操作
算法:
算法就是：解决问题的方法和步骤
衡量算法有如下标准:
时间复杂度
程序要执行的次数，并非执行时间
空间复杂度
算法执行过程中大概要占用的最大内存
难易程度(可读性)
健壮性
2. 数据结构的特点和地位地位:
数据结构处于软件中核心的地位。
如计算机内存中栈和堆的区别，不懂数据结构的人可能会认为内存就是分两大部分，一块叫栈，一块叫堆，显然这是非常肤浅且不正确的结论。
实际上如果一块内存是以压栈出栈的方式分配的内存，那么这块内存就叫栈内存，如果是以堆排序的方式分配的内存，那么这块内存就叫堆内存，其最根本的区别还是其内存分配算法的不同。
例如，函数的调用方式也是通过压栈出栈的方式来调用的，或者操作系统中多线程操作有队列的概念，队列用于保证多线程的操作顺序，这也是数据结构里面的内容、或者计算机编译原理里面有语法树的概念，这实际上就是数据结构里面的树，比如软件工程、数据库之类都有数据结构的影子。
特点:
数据结构修炼的是内功，并不能直接立竿见影的可以解决现实问题，但是有了这门内功会在其他方面的学习中对你大有益处。
3. 预备知识（C语言）学习数据结构应该具备如下知识：
指针
结构体
动态内存的分配和释放
跨函数使用内存
本小节主要介绍学习数据结构应该有的基础，并对相关知识稍作讲解。
指针指针是 C语言 的灵魂，重要性不需多言。
指针定义
地址：
地址是内存单元的编号
其编号是从 0 开始的非负整数
范围： 0 -- 0xFFFFFFFF (232 - 1) 注：此指x86平台，x64平台下最大内存地址为 (264 - 1)
指针：
指针就是地址，地址就是指针。
指针变量是存放内存单元地址的变量,它内部保存的值是对应的地址,地址就是内存单元的编号(如内存地址值：0xffc0)。
指针的本质是一个操作受限的非负整数
在计算机系统中，CPU 可以直接操作内存，关于 CPU 对内存的操作与控制原理可以简单理解如下图
地址线 ： 确定操作哪个地址单元
控制线 ： 控制该数据单元的读写属性
数据线 ： 传输 CPU 和内存之间的数据
指针的分类
基本类型的指针
int i = 10; // 定义一个 整形变量 i 初始值 10 int *p = i; // 定义一个 整形的指针变量 p , 变量 p 指向 i 的地址 int *p; // 这两行等价于上面一行 p = &i; 1. p 存放了 i 的地址，我们就可以说“ p 指向了 i” ，但 p 和 i 是两个不同的变量，修改一方不会影响另一个的值。 2. *p 等价于 i ，i 等价于 *p;两者是一块内存空间，里面的值一变具变。
指针和函数
// 修改外部实参的值 void func(int * p) { *p = 100; // 函数内修改外部变量的值 } // 修改外部实参的值，二级指针的值 void func2(int ** p) { *p = 100; // 函数内修改外部变量的值 ，这里实际修改的是指针的内部的地址，这里直接自己修改并不严谨也不安全，只是为了表达意思 } int main(void) { // 修改外部实参 int i = 10; func(&i); printf("i = %d",i); // 修改外部二级指针 int *p = i; // 等价于 int *p; p = &i; func(&p); printf("i = %d",i); return 0; } // 通过函数调用，改变函数外部变量（实参）的值
指针和数组
【指针】 和 【一维数组】
int a[5] = {1,2,3,4,5 }; a[3] == *(a + 3) // 等价于 a[3] == *(3 + a) == 3[a]; // 3[a] 这种写法只是不常用，从原理上来说是正确的 a 等价于 a[0]; // a 是数组中第一个元素，每个元素占用内存单位长度相同， // a[i] 中的 i 实际代表的是单位长度的倍数数组名:
一维数组名是个指针常量(它的值不可变)
它存放的是该一维数组的第一个元素的地址(一维数组名指向其第一个元素)
下标和指针的关系:
(1)、 a[i] 等价于 *(a + i)
(2)、假设指针变量的名字为 p,
则 p + i 的值为 p + i * (p 所指向的变量所占字节数)
(3)、每个下标表示的是第 i+1 个元素，根据元素类型分配的字节长度不同(int 类型4个字节)，每个字节都有对应的内存地址编号，指针变量 p 保存的是该元素首字节的地址。