数据结构——研究数据与数据之间的关系
特点——抽象
运用到数据的操作（指针）
代码的实现上大量的用到指针，所以可以通过画图让抽象关系明确
C语言：
1.语法
2.基本编程思维
3.处理单个或几个变量的数据
处理批量数据（数组+结构体）
数据规模更大（数据结构）
必须理好数据和数据的关系，再结合处理数据的思路（算法）
（好的）程序设计=（好的）算法 + （好的）数据结构
数据:是描述客观事物的符号
数据元素:是组成数据的、有一定意义的基本单位（例如单个学生）
数据项:一个数据元素可以由若干个数据项组成。
（数据项是数据不可分割的最小单位）
数据对象：是性质相同的数据元素的集合，是数据的子集（学生这个身份或者职业的大类）
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
关系：
逻辑结构——反应的是数据与数据之间的相互关系
1.集合：元素与元素之间同属一类
2.线性：元素与元素之间一对一的（排成一个‘链’，有先后次序，每个元素都有自己的前驱节点和后继节点）
3.树形：层次上一对多（1. 有且仅有一个根结点，没有前驱
2. 除根以外，每个结点只有1个前驱（父节点）3. 每个结点可以有0个、1个或多个后继（子节点）4. 结点之间分层，不存在环，不能交叉）
4.图形关系：元素与元素形成多对多（1. 任意两个结点之间都可以相连2. 一个结点可以有多个前驱，也可以有多个后继3. 可以存在环，没有根、没有分层限制4. 边可以有方向（有向图），也可以无方向（无向图）
存储结构（内存本身是线性结构）
顺序存储（数组）：增加和删除元素不方便，要移动大量元素，但是找到（访问）某个数据元素很方便。
链式存储结构：增加和删除元素方便，但是访问要遍历，不方便
所以链式结构每个元素需要自己的数据本身和下一个元素的地址
索引结构：
类似于看书——index（目录或者索引）
- 索引表有序；主文件本身可以无序
- 查找：先查索引，找到地址，再去读真实数据
散列（哈希）结构：
用散列函数直接算出关键字对应的存储地址，不需要挨个比较。
公式： Addr = H(key)
输入关键字 key，经过哈希函数，直接得到存放位置。（即由值通过一个哈希函数得到位置）
同一个逻辑关系的数据可以用不同的存储结构（各有各的优缺点）——根据需求选择
设计算法具有的五个特性（考虑的方面）：输入，输出，有穷性，确定性和可行性
好算法：
1.正确性
2.可读性
3.健壮性（适合更多的不同情况）
4.时间效率（时间复杂度）和存储率（空间复杂度）低
常用的时间复杂度从小到大
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
顺序存储
数组(顺序表)
算法
- 创建 int a[10];
- 增 inputArray insertArray （插入数据）
- 删 deleteArray
- 改 modifyArray //找到 修改
- 查 findArray //
- 销毁
链式: 链表的方式来实现 线性结构
实现: 链表的元素特点描述
包含:
a.数据
b.下一个节点的地址
代码:
typedef int data_t;
struct node
{
data_t data; //数据域
struct node *next； //指针域
};
图示如下
首节点：第一个有效数据节点
尾节点：最后一个有效数据节点，它的指针域为空
定义链表节点类型以及创建头节点代码如下
#include<stdio.h> #include<stdlib.h> typedef int data_t; // 定义链表结点类型，名字别名 node_t typedef struct node { data_t data; // 数据域：存数据 struct node *next; // 指针域：存下一个结点的地址 }node_t; // 创建链表【头结点】 node_t* linklist_create(void) { // 在堆上申请一块node_t大小内存，作为头结点 node_t *head = malloc(sizeof(node_t)); // 判断malloc有没有申请内存失败 if(head == NULL) { printf("linklist_create malloc fail\n"); return NULL; } head->next = NULL; // 空链表：头结点后面暂时没有任何数据结点 return head; // 返回头结点的地址给main函数 } int main(void) { // phead 保存链表头结点的地址，代表整条链表 node_t *phead = linklist_create(); return 0; }以下是给头节点插入新节点的步骤
把新节点插入一个已经存在的头结点后面也是这样，因为这个时候头结点存的已经不是NULL了，而是原本的头结点后一个节点的地址，这个地址被传递给新节点的指针域，头节点再把指针域等于新节点的地址
