数据结构 表基础与构造

数据的组织

线性表

线性表指的是数据的组织是线性有序的，结构在一定的规则下“顺序”存储，中间不存在为空的元素。

随机访问与数组

通过一个确定的地址+地址偏移量完成对其他元素的访问。数组是这种思想的最直观例子，当我们定义了一个数组后，通过偏移量，完成对后续数组中的元素进行访问。

int array[] = {1,2,3,4,5,6} ; // 定义数组
printf("%d", array[3]) ; // 打印由数组起始地址偏移3个整型长度地址的对象
/ * 
1. 找到array的存储地址
2. 偏移对应类型长度* 偏移量的字节
3. 找到该内存地址，从该地址取4个字节，交给CPU执行打印
*/

通过确定的地址和偏移量信息，完成了对其他元素的查找。除此之外，C语言中的结构体定义，也是在内存中紧密排列的（绝大部分，某些定义中会进行字节对齐）。通过这种手段，可以使用确定的偏移量获取到其中的某一段数据，并通过强制转换的方式，将对应的这段数据转换为预先定义好的结构体，交给后续的函数处理。很多基于C的系统就是通过这样的偏移+强制转换的方式完成的数据处理

指针与链表

指针是一个占用4字节内存地址的结构，在该段内存中，存储了另一个内存地址。当我们定义了一个指针时，就通过一个指针存储了目标结构的地址信息

int a = 3 ;        // 初始化了一个整型结构a
int *p = &a ;      // 初始化一个指针指向a的内存地址
printf("%d", *p);
/*
1. 当前的指针p 指向 a的内存地址
2. 对p 进行解引用，即读取指针中的内存地址信息，查询对应的内存地址
3. 指针类型为int，则读取该内存地址四个字节的内存，将其以整数形式进行读取
*/

我们可以看到，在指针定义时，p表示的是该指针在内存中的起始地址，当我们进行解引用时，通过该指针结构查询到实际结构的内存地址，并且根据类型从实际结构的内存地址中获取数据，最终得到a的值。通过这种方式，我们可以更加灵活的记录和访问数据。而链表就是依赖于指针技术实现的线性表技术。它通过定义一系列的函数，完成结构的添加/删除/遍历过程。达到以一种灵活有序的结构管理数据的目的。

单链表实现

一个最简单的单链表需要具备以下结构

对于链表来说： 仅需要存储指向头节点的指针

对于中间节点来说： 需要定义存储的值和指向下一个节点的指针

函数签名：

#include <stdio.h>
#include <stdbool.h>  
typedef struct _node {  // 定义node结构，作为链表中的节点信息 
    int value;
    struct _node* next;  //  定义指向下一个node的指针信息
} node;

// 链表结构体
typedef struct _linkedlist {
    node* head;     // 头节点指针
} linkedlist;

// 函数声明
void add(linkedlist* lt, int value);  // 向链表中添加元素
bool remove_by_value(linkedlist* lt, int value); // 从链表中删除元素
bool has_next( node* current);  // 检查后续是否还存在元素
node* get_next(node* current);  // 获取下一个节点元素
void init_list(linkedlist* lt); // 初始化链表，将链表中的元素初始化

实现：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "linklist.h"

void init_list(linkedlist* lt){   //定义初始化过程，将head设置为空，
    lt->head = NULL ;
};

void add(linkedlist* lt , int value){
    node* new_node = (node*)malloc(sizeof(node));  // 动态申请内存创建新的节点
    new_node->value = value;  // 初始化节点
    new_node->next = NULL ;
    if(lt->head == NULL){   // 判断当前链表是否为空
       lt->head = new_node ;  // 如果为空，则将新节点设置为链表的head
    }else{
       node* current = lt->head;   // 否则获取到头节点开始遍历
       while(has_next(current)){
          current = get_next(current);
       }
       current->next = new_node ;  // 将新节点添加到末尾
    }
};

bool remove_by_value(linkedlist* lt , int value){  
     node* current = lt->head;  // 设置当前节点
     if(current == NULL){  
        return false ;
     }
     if(current->value == value){
        lt->head = current->next ;
        free(current);
        return true ;
     }                              // 处理头节点删除过程
     while(has_next(current)){
        if(current->next->value == value){
          node* temp = current->next ;
          current->next = temp->next ;
          free(temp);
          return true ;
        }else {
          current = current->next;
        }                           // 从头节点开始遍历，判断下一个节点的值是否与待删除值相等
                                    // 相等则删除，将下一个节点删除，并将指针指向下下个节点
     }
     return false ;
}

bool has_next(node* current){
     if(current == NULL){
        return false;
     }
     return current->next != NULL;
}

node* get_next(node* current){
     if(current == NULL){
        return current;
     }
     return current->next ;
}

散列表

散列表指的是在存储上，结构的存储是无序的，结构与结构“之间”可能存在空的部分。

哈希计算与哈希集合

哈希本身是一种通过筛选进行的数据查询，通过一个哈希函数，我们可以得到某个结构的特征，最终可以获得该结构与存储位置的特征，存储/读取时的哈希函数不会发生变化，那么通过这个函数维护的映射关系就是固定的，于是我们就可以通过这种关系，来完成结构的存储和查找。

int array[9] ;        //  声明一个长度为9的数组
int a = 26 ;          //  初始化一个整型数据a,值为26
int posit = a%9 ;     //  对a进行对9的取余
array[posit] = a ;    //  将a存储到数组中的对应位置
printf("%d", array[a%9]); // 查询a的位置获取a
/*
1. 这里是一个概念性的实现，即通过hash算法使用特征对数值进行存储
2. 在后续获取时就可以通过特征，将存储的结构取出
3. 实际实现中有更多实际问题的考量，比如hash的碰撞，以及扩容，以及散列的结构存储均匀性
*/

使用hash的一大优点是通过hash就可以直接从数组中取出值，其时间复杂度为O(1)。但是 hash的缺点是数据的存储过程是无序的，因为它是依照数据的特征进行的存储，而非按照存储的顺序完成的存储。但同时因为不需要顺序插入，就不再需要像链表一样遍历整个链表来决定插入位置，也不需要像数组那样需要提前获取偏移量信息，能够更便捷的访问到存储的数据。

表结构数据组织的局限性

1. 数组（Array）

优势 ：提供有序的逻辑存储，支持O(1)随机访问
局限 ：存储布局与物理位置强耦合，插入/删除操作需要大量元素移动

• 插入操作最坏时间复杂度：O(n)
• 根本原因：连续内存布局要求保持元素间的相对位置

2. 链表（Linked List）

优势 ：保持插入顺序，通过指针灵活管理元素关联
局限 ：存储位置与逻辑顺序分离，只能通过节点间链接进行顺序访问

• 查询操作最坏时间复杂度：O(n)
• 根本原因：缺乏随机访问能力，必须从头节点开始遍历

3. 哈希表（Hash Table）

优势 ：通过哈希函数映射实现O(1)平均查询效率
局限 ：存储位置完全由哈希值决定，无法维护元素间的顺序关系

• 遍历操作：无法保证有序性
• 根本原因：哈希散列破坏了元素的原始顺序信息

局限性的本质

这些权衡的根本原因在于： 单一组织方式只能优化一个维度的性能 。每种结构的存储策略决定了其擅长的操作类型，同时也限制了其他方面的表现。

受限表结构

所谓受限表结构，就是对于表结构只提供了部分受限方法，来达成一些面向应用的处理过程

队列

队列结构就是一种受限表结构，其提供的方法只允许数据依照LILO的方式被存储/读取。

队列在编程中存在广泛应用，它提供了一种手段用于数据的临时有序存储，经典的生产者/消费者就是依赖于队列的数据结构，进行生产消费过程。作为一种消息中间件，解耦了生产者和消费者之间的强绑定关系

栈

栈结构也是一种受限表结构，其提供的方法只允许数据依照LIFO的方式被存储/读取。

栈结构主要应用于函数栈/运算/以及存在嵌套执行的调用关系上，系统栈以及各种编程语言的本地方法栈都是通过栈结构完成的函数执行。