什么是数据结构

数据结构： 数据结构就是计算机存储，组织，管理数据的方式方法；

数据结构的类型

① 根据数据的逻辑结构划分 (数据间关系)
集合：数据结构中的元素之间除了"同属一个组织"之外，别无其他关系；
线性数据结构： 数据之间 "一对一"的关系，数据具有唯一的前驱和后继，典型代表是链表
非线性数据结构：数据之间不具有唯一的前驱和后继。例如： 二维数组，二叉树...，典型代表
是二叉树。

② 根据数据在内存中的存储方式划分
顺序结构：各个元素存储在连续的内存空间 ，典型代表是数组
链式结构：各个元素存储在不连续的内存空间 ，典型代表是链表
索引结构：元素在存储时，不仅存储元素数据，还建立元素附加的索引表来标识元素的地址

哈希(散列)结构：元素在存储时，为元素提供关键字，在元素访问时，可根据关键字来访问数 据。

常见的数据结构 链表 顺序表 树 图 映射 栈 队列...

线性表

概念

对于一组拥有n个数据元素的线性表，其严格数学定义是：其中任何一个数据元素 ，有且仅有一 个直接前驱 ，有且仅有一个直接后继 。首元素 无直接前驱，尾元素 无直接后继。 满足这种数学关系的一组数据，当中的数据是一个挨着一个的，常被称为一对一关系。反之，如果 数据之间的关系不是一对一的，就是非线性的。

举例

生活中的线性表例子非常多，比如一个班级中的以学号编排的学生，一座图书馆中的以序号编排的 图书、一条正常排队等候的队列、一摞从上到下堆叠的餐盘，这些都是线性表。他们的特点都是： 除了首尾两个元素，其余任何一个元素前后都对应相邻的另一个元素。

注意：

线性表是一种数据内部的逻辑关系，与存储形式无关

线性表既可以采用连续的顺序存储（顺序表），也可以采用离散的链式存储（链表）

顺序表

基本概念

顺序表：顺序存储的线性表。
链式表：链式存储的线性表，简称链表。
顺序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，或者是匿
名的堆数组。
存储方式不仅仅只是提供数据的存储空间，而是必须要能体现数据之间的逻辑关系。当采用顺序存
储的方式来存放数据时，唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两
个人，小明和小花，如果小明在逻辑上排在相邻的小花的前面，那么在存储位置上也必须把小明存
放在相邻的小花的前面。

基本操作

顺序表设计
一般而言，为了方便操作顺序表，需要一个专门管理顺序表的”管理结构体“，管理结构体中一般
会包含：
1. 顺序表总容量
2. 顺序表当前最末元素下标位置
3. 顺序表指针

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
typedef struct
{
    int   capacity; // 顺序表容量
    int   last;     // 最末元素下标
    int * data;     // 顺序表，以整型数据为例
}sequenceList;

初始化

所谓初始化就是建立一个不包含任何元素的顺序表，设置好管理结构体中的表的总容量、末元
素下标，申请好顺序表内存空间等系列准备工作。
下面是初始化顺序表的示例代码：

sequenceList  *init_list(int cap)
{
    sequenceList *list = malloc(sizeof(sequenceList));
    if(list != NULL)
   {
        list -> data = malloc(sizeof(int) *cap);
        if(list -> data == NULL)
       {
            free(list);
            return NULL;
       }
        list -> capacity = cap;
        list -> last = -1;
   }
    return list;
}

测试

int main()
{
    sequenceList *list = init_list(10);
    if(list == NULL)
   {
        perror("初始化顺序表失败!");
        exit(0);
   }
    else
   {
        printf("初始化顺序表成功！\n");
   }
}

增删节点

在顺序表中增加一个数据，可以有多种方式，比如在原数组的末尾增加，或者在原数组的头部
增加，或者在数组中间任意一个位置增加。根据实际需要来定。
下面以在顺序表头部增删数据为例，示例代码如下：

// 判定顺序表是否为空
bool isEmpty(sequenceList *s)
{
    return s->last == -1;
}
// 判定顺序表是否已满
bool isFull(sequenceList *s)
{
    return s->last == s->capacity-1;
}
// 在顺序表表头插入一个新数据
bool insert(sequenceList *s, int data)
{
    if(isFull(s))
        return false;
    // 将原有数据全部往后挪一位
    for(int i=s->last; i>=0; i--)
        s->data[i+1] = s->data[i];
    
    // 将新数据置入表头
    s->data[0] = data;
    s->last++;
    return true;
}
// 将顺序表表头的数据删除掉
bool removeNode(sequenceList *s)
{
    if(isEmpty(s))
        return false;
    // 将所有数据全部往前挪一位
    for(int i=0; i<s->last; i++)
        s->data[i] = s->data[i+1];
    
    s->last--;
    return true;
}

销毁顺序表

一个顺序表最后不再需要，应当要释放其所占用的内存空间，这被称为顺序表的销毁。
下面是销毁操作的示例代码：

void destroy(sequenceList *s)
{
    if(s == NULL)
        return;
    free(s->data);
    free(s);
}

顺序表优缺点总结

顺序存储中，由于逻辑关系是用物理位置来表达的，因此从上述示例代码可以很清楚看到，增删数
据都非常困难，需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。
总结其特点如下：
优点

1. 不需要多余的信息来记录数据间的关系，存储密度高
2. 所有数据顺序存储在一片连续的内存中，支持立即访问任意一个随机数据，比如上述顺序表中
第 个节点是 s->data[i]
缺点
1. 插入、删除时需要保持数据的物理位置反映其逻辑关系，一般需要成片移动数据
2. 当数据节点数量较多时，需要一整片较大的连续内存空间
3. 当数据节点数量变化剧烈时，内存的释放和分配不灵活