数据结构

写嵌入式用的到数据结构吗？

看下linux内核就知道了，一堆数据结构，不学习数据结构，linux内核就看不懂了

使用数据结构是为了使代码结构更清晰，更容易把握代码结构、逻辑。

几个应用场景

1. “数组”。你肯定用过吧，属于数据结构“线性表”的一种形式。

   

3. “结构体”。学习过lwip可以知道从以太网上接收一堆数据后，把数据头的地址幅值给以太网包的数据结构定义的指针，可以直接使用此指针->成员变量的方式，使用接收到的数据。比使用一堆变量来利用接收到的数据方便太多了。

4. “队列”。热敏电阻测温，单片机用ADC测量电阻分压电压，然后对测量值用平滑均值滤波算法滤波，此时会用到“队列”，或用“环形队列”；

5. “树”。项目中经常会使用液晶屏作为显示，其中文本菜单有时用的比较多的一种方式，其中文本菜单常用“树”结构来实现。

6. “栈”。就不用说了，你已经用过了，不过不是你主动用的，它隐藏在你每次函数调用、中断调用中，可能你没有意识到。

简单几个例子，说明了数据结构非常常见，这个是必须要学的，不过有些不常用，比如图。

1. 【简答题】请写出至少两种野指针的成因

【答案】

（1）指针使用前未初始化

（2）指针越界访问

（3）指针指针已经释放的空间

2. 【简答题】非静态局部变量、全局变量、malloc()动态分配的内存分别存储在内存的什么区域。

【答案】

（1）非静态局部变量存储在内存的栈区域。

（1）全局变量存储在内存的全局静态区。

（2）malloc()动态分配的内存存储在内存的堆区域。

一、数据结构与算法的层次要求：

层次1：熟悉各种不同的数据结构：顺序表（一维数组）、链表、栈、队列；森林、树、二叉树；图等
了解不同的数据结构的特点、如何存储、优缺点等

层次2：如何编写相关的代码，实现对应的数据结构。（需要考虑对应的增、删、改、查、长度、遍历等）

层次3：算法层面的训练。 —> leetcode （力扣app）、牛客网等。 300+道打底

二、针对于层次1：

1. 什么是数据结构？ datastructure (D->S)

   数据 + 结构
   数据：多个相同类型的数据或变量
   结构：即关系
   目的：为了更高效的访问数据

2. 数据结构中有哪些内容？即问研究方向？
   研究方向1：数据之间的逻辑关系

   线性关系:（一对一的关系）。比如：顺序表、链表、栈、队列、数组、字符串、广义表等
   非线性关系：集合关系、树形关系（一对多的关系）、图形关系（多对多的关系）

研究方向2：数据的存储结构（或物理结构）
> 基本的两种：顺序存储结构、链式存储结构
> 拓展的两种：索引存储结构、哈希存储结构(散列存储结构)
研究方向3：数据之间的运算：增、删、改、查(CRUD)

三、具体的不同的数据结构的实现（对应着层次2）

1. 数组的实现和相关算法的封装。

2. 链表的实现和相关算法的封装。

   ​ 优点 缺点

   数组 通过索引查找、修改效率高：O(1) 插入、删除的效率差：O(n)

   ​ 同样大小的内存，数组可以存储更多的数据 当数据存满时，需要考虑扩容

   链表 插入、删除效率高：O(1) 通过索引查找、修改效率低：O(n)

   ​ 不需要考虑扩容问题 同样大小的内存，链表存储的数据较数组少

如何理解数据结构

数据结构的基本概念

1.数据结构定义：研究多个变量之间的结构，即数据与数据之间的关系。

2.研究目的：高效地进行数据的操作，如增删改查。

数据结构的主要内容

1.逻辑结构：研究数据之间的逻辑关系，分为集合关系、线性关系、树形关系和网状关系。

2.存储结构：研究数据在实际编程语言中的存储方式，分为顺序存储和链式存储。

3.运算：基于存储结构，研究数据的增删改查等操作。

线性结构和非线性结构

1.线性结构：如顺序表、链表、栈、队列、数组、广义表等。

2.非线性结构：如集合、树、图等。

存储结构的两种基本形式

1.顺序存储：将数据元素依次排列，通过数组等方式实现。

2.链式存储：通过链表方式，每个元素包含指向下一个元素的指针。

3.索引存储结构和哈希存储结构：基于顺序存储和链式存储的组合。

线性结构之数组

优 点

Ø 查找容易（通过下标），时间复杂度为O(1)。不需要额外申请或删除空间。

Ø 使用下标位置索引(index)十分高效的访问任意元素，修改快

缺 点

Ø 插入、删除元素难，效率低。（需要移动大量元素以使元素空间连续）。

Ø 插入操作平均需要移动n/2个元素。

Ø 删除操作平均需要移动(n-1)/2个元素。

​

Ø 扩展相对繁琐。一方面需要确保能提供更大区域的连续内存空间，另一方面需要将原有数据复制到新的顺序表中。

1.1.1 功能定义

前文提到过数组这一数据结构的一个局限性是长度固定，本节我们来实现一个增强版的数组——可变长的动态数组，需要实现以下函数：

//初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity)
//释放动态数组内存
void destroyDynamicArray(DynamicArray *array)
//调整动态数组内存大小
void resizeDynamicArray(DynamicArray *array, size_t newCapacity)
//获取动态数组长度（元素个数）
size_t getLength(const DynamicArray *array)
//在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element)
//在末尾插入新元素
void insertEnd(DynamicArray *array, int element)
//删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index)
//删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array)
//遍历所有的元素
void print(DynamicArray *array)

1.1.1 实现原理

可变长的动态数组是一种数据结构，它允许在运行时根据需要动态地调整数组的大小，而不需要提前指定固定的大小。这种动态数组通常被称为动态数组、动态分配数组、动态增长数组或动态内存数组。int arr[10];

C语言中是通过使用指针和内存分配函数来实现动态数组，常见的内存分配函数是malloc、realloc和free。下面是一些相关的概念和操作：

（1）分配内存（malloc）： 在C语言中，可以使用malloc函数来分配一块指定大小的内存。例如，int *arr = (int *)malloc(n * sizeof(int)); 将分配能够存储n个整数的内存空间。

（2）重新分配内存（realloc）： 如果需要改变动态数组的大小，可以使用realloc函数来重新分配内存。这允许你在保留原有数据的情况下扩展或缩小数组的大小。

（3）释放内存（free）： 当不再需要动态数组时，应使用free函数释放之前分配的内存，以避免内存泄露。à 内存溢出

代码实现

#include <stdio.h>
#include <stdlib.h>

// 动态数组结构体
typedef struct
{
    int *data;       // 指向动态数组的指针
    size_t size;     // 当前数组中的元素个数
    size_t capacity; // 当前数组的容量（可以容纳的最大元素个数）
} DynamicArray;

// 初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity)
{     //分配内存（malloc）
    array->data = (int *)malloc(initialCapacity * sizeof(int)); // 分配初始内存
    array->size = 0;       // 初始化元素个数为0
    array->capacity = initialCapacity;     // 设置初始容量
}

// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array)
{
    
    //释放内存（free）
    free(array->data);   // 释放动态数组内存
    array->size = 0;     // 重置元素个数为0
    array->capacity = 0; // 重置容量为0
}

// 调整动态数组内存大小
void resizeDynamicArray(DynamicArray *array, size_t newCapacity)
{ 	//重新分配内存（realloc）
    array->data = (int *)realloc(array->data, newCapacity * sizeof(int)); // 调整数组内存大小  
    array->capacity = newCapacity;       // 更新容量
}

// 获取动态数组长度（元素个数）
size_t getLength(const DynamicArray *array)
{
    return array->size; // 返回数组中的元素个数
}

// 在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element)
{
    if (index > array->size)
    {
        return; // 忽略无效的插入位置
    }

    if (array->size >= array->capacity)
    {
        size_t newCapacity = array->capacity * 2; // 如果容量不足，扩大容量
        resizeDynamicArray(array, newCapacity);
    }

    for (size_t i = array->size; i > index; i--)
    {
        array->data[i] = array->data[i - 1]; // 后移元素以腾出插入位置
    }

    array->data[index] = element; // 在指定位置插入新元素
    array->size++;                // 更新元素个数
}

// 在末尾插入新元素
void insertEnd(DynamicArray *array, int element)
{
    insertAt(array, array->size, element); // 在末尾插入新元素
}

// 删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index)
{
    if (index >= array->size)
    {
        return -1; // 忽略无效的删除位置
}

    int deletedElement = array->data[index]; // 获取被删除的元素

    for (size_t i = index; i < array->size - 1; i++)
    {
        array->data[i] = array->data[i + 1]; // 前移元素以填补删除位置
    }

    array->size--; // 更新元素个数

    return deletedElement; // 返回被删除的元素
}

// 删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array)
{
    return deleteAt(array, array->size - 1); // 删除末尾的元素
}

// 遍历所有的元素
void print(DynamicArray *array)
{
    for (int i = 0; i < array->size; i++)
    {
        printf("%d  ", array->data[i]);
    }
    printf("\n");
}

int main()
{
    DynamicArray myArray; // 声明动态数组

    // 初始化动态数组
    initDynamicArray(&myArray, 2);
    printf("初始化动态数组,初始容量为2\n");

    // 向动态数组尾部插入元素
    insertEnd(&myArray, 1);
    insertEnd(&myArray, 2);
    printf("向动态数组尾部插入了2个元素\n");

    // 打印动态数组当前长度
 printf("动态数组当前长度:%zu\n", getLength(&myArray));

    // 在索引1的位置插入元素3
    insertAt(&myArray, 1, 3);
    printf("在索引1的位置插入元素3\n");

    // 再次打印动态数组当前长度
    printf("动态数组当前长度:%zu\n", getLength(&myArray));

    // 删除索引1的元素
    printf("删除索引1的元素,该元素是%d\n", deleteAt(&myArray, 1));

    // 删除动态数组末尾元素
    printf("删除动态数组末尾元素,该元素是%d\n", deleteEnd(&myArray));

    // 释放动态数组内存
    destroyDynamicArray(&myArray);
    printf("动态数组内存释放完成\n");

    return 0;
}

1.1 线性结构之链表

1.1.1 链表是什么

链表的主要特点包括：

1. 动态大小：链表可以根据需要动态调整大小，不需要预先分配固定的内存空间。
2. 插入和删除效率高：在已知位置插入或删除元素时，链表不需要移动其他元素，只需调整指针即可。
3. 顺序访问：链表不支持随机访问，要访问链表中的某个元素，必须从头节点开始逐个遍历。

链表有几种常见的类型：

• 单向链表：每个节点只指向下一个节点。
• 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
• 循环链表：链表的最后一个节点指向第一个节点，形成一个环。

相关概念

n个结点离散分配，彼此通过指针相连，每个结点只有一个前驱结点，每个结点只有一个后续结点，头结点没有前驱结点，尾结点没有后续结点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。

1）优点

（1）插入和删除操作效率高。

（2）动态扩展性能更好，链表不需要像数组那样预先指定固定的大小，而是可以随时动态的增长或缩小。链表是真正的动态数据结构，不需要处理固定容量的问题。

2）缺点

（1）查找慢。由于链表中的结点不是连续存储的，无法像数组一样根据索引直接计算出每个结点的地址。必须从头结点开始遍历链表，直到找到目标结点，这导致了链表的随机访问效率较低。

（2）额外的存储空间。链表的每个结点都需要存储指向下一个结点的指针，这会占用额外的存储空间。所以，相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。

初始化链表
void initLinkedList(LinkedList *list)
返回链表的长度
size_t getLength(const LinkedList *list)
在指定位置插入元素
void insertAt(LinkedList *list, size_t index, int element)
在末尾插入元素
void insertEnd(LinkedList *list, int element)
删除指定位置的元素并返回被删除的元素
int deleteAt(LinkedList *list, size_t index)
删除末尾元素
int deleteEnd(LinkedList *list)
获取指定位置的元素
int getElementAt(const LinkedList *list, size_t index)
修改指定位置的元素
void modifyAt(LinkedList *list, size_t index, int newValue)
释放链表内存
void destroyLinkedList(LinkedList *list)

#include <stdio.h>
#include <stdlib.h>

/*
自定义链表结构

 */

// 定义存储数据的结构体
typedef struct Node
{

    int data;          // 存储的数据
    struct Node *next; // 指向下个元素的指针

} Node;

// 定义虚拟头结点的结构体
typedef struct
{
    int size;   // 记录单链表中存储的数据的个数
    Node *next; // 指向保存数据的首元素
} LinkedList;

// 明确：在包含虚拟头结点的情况下，首个保存数据的结点的索引为0！

// 初始化链表
void initLinkedList(LinkedList *list)
{
    // 初始化LinkedList内部的成员
    list->size = 0;
    list->next = NULL;
}

// 返回链表的长度
size_t getLength(const LinkedList *list)
{
    return list->size;
}

// 在指定位置插入元素
void insertAt(LinkedList *list, size_t index, int element)
{

    if (index < 0 || index > list->size)
    {
        printf("输入的index数据非法\n");
        return;
    }

    // 插入数据的过程
    // 1. 将数据封装到Node结构体的变量中
    Node *node = (Node *)malloc(1 * sizeof(Node));
    node->data = element;

    // 2. 找到index的位置进行插入操作
    if (index == 0)
    {

        node->next = list->next;
        list->next = node;
    }
    else
    {

        Node *currentNode = list->next; // 指向有数据的首元素
        for (int i = 0; i < index - 1; i++)
        {
            currentNode = currentNode->next;
        }

        node->next = currentNode->next;
        currentNode->next = node;
    }
    list->size++;
}

// 在末尾插入元素
void insertEnd(LinkedList *list, int element)
{
    insertAt(list, list->size, element);
}

// 删除指定位置的元素并返回被删除的元素
int deleteAt(LinkedList *list, size_t index)
{

    if (index < 0 || index >= list->size)
    {
        printf("输入的index不合法\n");
        return -1;
    }

    int deleteElement;
    Node *deleteNode;
    if (index == 0)
    {
        deleteNode = list->next;

        list->next = deleteNode->next;

        // 获取要删除的node的数据
        deleteElement = deleteNode->data;
    }
    else
    {
        Node *currentNode = list->next; // 指向有数据的首元素
        for (int i = 0; i < index - 1; i++)
        {
            currentNode = currentNode->next;
        }

        deleteNode = currentNode->next;
        currentNode->next = deleteNode->next;

        deleteElement = deleteNode->data;
    }
    free(deleteNode); // 释放node的内存空间

    list->size--;

    return deleteElement;
}

// 删除末尾元素
int deleteEnd(LinkedList *list) {
    deleteAt(list,list->size - 1);
}

// 获取指定位置的元素
int getElementAt(const LinkedList *list, size_t index) {

    if(index < 0 || index >= list->size){
        printf("输入的index不合法\n");
        return -1;
    }

    Node * currentNode = list->next;
    for(int i = 0;i < index ;i++){
        currentNode = currentNode->next;
    }

    return currentNode->data;

}

// 修改指定位置的元素
void modifyAt(LinkedList *list, size_t index, int newValue) {

    if(index < 0 || index >= list->size){
        printf("输入的index不合法\n");
        return -1;
    }

    Node * currentNode = list->next;
    for(int i = 0;i < index ;i++){
        currentNode = currentNode->next;
    }

    currentNode->data = newValue;

}

// 释放链表内存
void destroyLinkedList(LinkedList *list) {

    Node *currentNode = list->next;  //找到有数据的第1个结点

    for(int i = 0;i < list->size;i++){

        Node *tempNode = currentNode;
        currentNode = currentNode->next;

        free(tempNode);

        

    }

    //辅助操作
    list->next = NULL;
    list->size = 0;

}

int main()
{

    LinkedList list;
    initLinkedList(&list);

    insertAt(&list,0,10);
    insertAt(&list,0,20);
    insertAt(&list,0,30);

    size_t count = getLength(&list);
    printf("%d\n",count);


    getchar();  
    return 0;
}

释放链表内存 有什么用

释放链表内存”的主要用途在于管理动态分配的内存，确保程序运行期间不会造成内存泄漏。下面是这一过程的重要性和作用：

1. 防止内存泄漏：在程序中动态申请的内存（例如，通过 malloc）需要在不再使用时及时释放。如果在不再需要链表时不释放内存，程序会占用不必要的内存资源，从而导致内存泄漏。
2. 优化内存使用：及时释放内存可以确保系统资源的有效使用，特别是在运行长时间的程序或需要频繁创建和销毁对象的情况下。
3. 防止悬挂指针：在释放链表内存的同时，设置指向链表的指针（如头指针）为 NULL 坏境，可以避免访问已释放内存的风险。这有助于防止程序在试图访问无效内存时造成的未定义行为。
4. 提高程序稳定性：良好的内存管理使得程序更加稳定和健壮，降低了崩溃的概率。

栈的定义

特点：后进先出 (LIFO，Last In First Out)或先进后出 (FILO，First In Last Out)的线性表。

栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。栈顶由一个称为栈顶指针的位置指示器（其实就是一个变量）来指示，它是动态变化的。

- 栈底(Bottom)：是固定不变的，不允许进行插入和删除的一端，又称为表头。

- 空栈：不含任何元素的空表。

- 设栈S=(a1,a2,…,an )，则a1称为栈底元素，an为栈顶元素，栈中元素按a1,a2,…,a_n的次序进栈(压栈、push)，出栈(弹栈，pop)的第一个元素应为栈顶元素，出栈顺序为：an,…,a2,a1。

初始化栈
void initStack(Stack *stack, size_t capacity)
返回栈内元素个数
size_t getSize(const Stack *stack)
添加新元素
void push(Stack *stack, int element)
在末尾插入元素
void insertEnd(LinkedList *list, int element)
栈顶元素出栈并返回
int pop(Stack *stack)
释放栈内存
void destroyStack(Stack *stack)

#include <stdio.h>
#include <stdlib.h>

/* 

  自定义实现栈结构：使用顺序存储结构实现--> 顺序栈

 */

typedef struct {

    //存储数据的指针
    int *data;
    //指明存储容器的容量
    size_t capacity;
    //指明存储容器中实际存储的数据量
    size_t size;

}Stack;



// 初始化栈
void initStack(Stack *stack, size_t capacity)
{
    stack->data = (int *)malloc(capacity *sizeof(int));//动态内存分配
    if(stack->data == NULL){
        printf("内存分配失败\n");
        exit(1);
    }

    stack->capacity = capacity;         
    stack->size = 0;


}

// 返回栈内元素个数
size_t getSize(const Stack *stack)
{
    
    return stack->size;
}

// 添加新元素
void push(Stack *stack, int element)
{
    //考虑是否存满了
    if(stack->size == stack->capacity){
        //扩容
        resizeCapacity(stack,stack->capacity + stack->capacity >> 1); //扩容为原来的1.5倍
        printf("容量已满，进行扩容操作\n");
    }

    stack->data[stack->size] = element;
    stack->size++;

}


void resizeCapacity(Stack *stack,int newCapacity){

    stack->data = (int *)realloc(stack->data,newCapacity * sizeof(int)); //扩容操作
    stack->capacity = newCapacity; //指明新的容量值
    
}



// 栈顶元素出栈并返回
int pop(Stack *stack)
{
    //判断是否为空
    if(stack->size == 0){
        printf("当前栈为空,弹栈失败\n");
        return -1;
    }

    // int popElement = stack->data[stack->size-1];
    // stack->size--;

    // return popElement;

    return stack->data[--stack->size];//


//这是一个前缀自减操作。它的作用是将 stack->size 的值减一，然后返回这个新的值。
//例如，如果 stack->size 原本是 3，经过 --stack->size 处理后，
//stack->size 会变为 2。这意味着我们将要弹出栈中索引为 2 的元素（即第三个元素，因为索引从 0 开始）。
}

// 释放栈内存
void destroyStack(Stack *stack)
{
    free(stack->data);
    stack->data = NULL;
    stack->capacity = 0;
    stack->size = 0;
}

//遍历栈中的元素
void print(Stack *stack){
    for(int i = 0;i < stack->size;i++){
        printf("%d  ",stack->data[i]);
    }
    printf("\n");
    
}


int main()
{

    //声明结构体变量
    Stack myStack;

    initStack(&myStack,3);

    push(&myStack,1);
    push(&myStack,2);
    push(&myStack,3);
    push(&myStack,4);


    printf("栈中元素的个数为：%d\n",getSize(&myStack));

    print(&myStack);

    printf("弹栈，弹出的数据是：%d\n",pop(&myStack));
    printf("弹栈，弹出的数据是：%d\n",pop(&myStack));


    print(&myStack);

    getchar();

    return 0;
}

线性结构之队列

基本概念

队列(Queue)：也是操作受限的线性表，限制为仅允许在表的一端进行插入(入队或进队），在表的另一端进行删除(出队或离队)操作。

- 队首(front) ：允许进行删除的一端称为队首。

- 队尾(rear)： 允许进行插入的一端称为队尾。

在空队列中依次加入元素a1,a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1,a2, …, an。队列，是一种先进先出(First In First Out ，简称FIFO)的线性结构。类似于生活中的排队行为。

队列中没有元素时，称为空队列。

队列的存储结构

可用顺序表(数组)和链表来存储队列，队列按存储结构可分为顺序队列和链式队列两种。

功能定义

初始化队列
void initQueue(Queue *queue, size_t capacity)
返回队列内元素个数
size_t getSize(const Queue *queue)
添加新元素
void enqueue(Queue *queue, int element)
元素出队列
int dequeue(Queue *queue)
释放队列内存
void destroyQueue(Queue *queue)
遍历队列
void printQueue(Queue *queue)

#include <stdio.h>
#include <stdlib.h>
/* 
    自定义结构实现队列：使用循环队列

 */


//声明队列对应的结构体
typedef struct{

    int *data;
    int capacity; //记录存储的最大容量
    int size ; //记录存储的元素的个数
    int front ;  //记录要出队的索引位置
    int rear;  //记录入队后的索引位置


}Queue;



// 初始化队列
void initQueue(Queue *queue, size_t capacity)
{
    queue->data = (int *)malloc(capacity * sizeof(int));
    queue->capacity = capacity;
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}

// 返回队列内元素个数
size_t getSize(const Queue *queue)
{
    return queue->size;    
}

// 添加新元素
void enqueue(Queue *queue, int element)
{
    if(queue->size == queue->capacity){
        //容量已满
        printf("队列已满，入队失败\n");
        return;
    }

    queue->data[queue->rear] = element;
    queue->size++;
    //queue->rear++; //存在问题，需要使用下面的方式替换

    queue->rear = (queue->rear + 1) % queue->capacity;
}

// 元素出队列
int dequeue(Queue *queue)
{
    // if(queue->front == queue->rear);//此语句满足的情况：① 队列为空 ② 队列已满
    if(queue->size == 0){
        printf("队列为空，出队失败\n");
        return -1;
    }

    int dequeueData = queue->data[queue->front];
    queue->size--;

    queue->front = (queue->front + 1) % queue->capacity;

    return dequeueData;

}

// 释放队列内存
void destroyQueue(Queue *queue)
{
    free(queue->data);
    queue->data = NULL;
    queue->capacity = 0;
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}


//遍历队列
void printQueue(Queue *queue){
    
    for(int i = queue->front,j = 0;j < queue->size;i++,j++){


        printf("%d  ",queue->data[i % queue->capacity]);
    }

    printf("\n");


}




int main()
{

    Queue myQueue;

    initQueue(&myQueue,3);

    enqueue(&myQueue,1);
    enqueue(&myQueue,2);
    enqueue(&myQueue,3);
    enqueue(&myQueue,4); //已满，未入队

    printQueue(&myQueue);

    printf("出队，元素是：%d\n",dequeue(&myQueue));
    printf("出队，元素是：%d\n",dequeue(&myQueue));

    printQueue(&myQueue);

    enqueue(&myQueue,5);
    enqueue(&myQueue,6);

    printQueue(&myQueue);


    getchar();


    return 0;
}

空间复杂度

假设一个 int 变量占 4个字节，则所需内存空间 = 4 + 4 = 8，则S(n) = O(1)。

假设一个 int 变量占 4个字节，则所需内存空间 = 4 + 4n + 4 = 4n + 8，则S(n) = O(n)。

代码实现

顺序查找:

#include <stdio.h>

// 顺序查找:
int sequenceSearch(int arr[], int size, int target)
{

    for(int i = 0;i < size;i++)
    {
        if(arr[i] == target)
        {
            return i;
        }
    }

    return -1; //表示没有找到指定的元素 
}

int main()
{
    int arr[] = {23,45,76,44,22,88,9,12,22,5,80};

    int size = sizeof(arr) / sizeof(int);

    int target = 9;

    int targetIndex = sequenceSearch(arr,size,target);
    if(targetIndex == -1){
        printf("未找到\n");
    }else{
        printf("找到了%d，对应的索引为%d\n",target,targetIndex);
    }


    getchar();

    return 0;
}

sizeof是运算符，返回 unsigned int，其值在编译时即计算好了，参数可以是数组、指针、类型、对象、函数等。
它的功能是：获得保证能容纳实现所建立的最大对象的字节大小

sizeof(ary) / sizeof(int) <==> sizeof(ary) / sizeof(ary[0]) ; 得到 ary 内的元素的个数

二分查找

二分查找（Binary Search）是一种高效的搜索算法，通常用于有序数据集中查找目标元素。其原理是通过将数据集划分为两半并与目标进行比较，以确定目标在哪一半中，从而逐步缩小搜索范围，直到找到目标元素或确定不存在。基本原理如下：

（1）选择中间元素： 在有序数据集中，选择数组的中间元素。

（1）比较目标： 将中间元素与目标元素进行比较。

（2）查找成功： 如果中间元素等于目标元素，则查找成功，返回中间元素的索引。

（3）缩小搜索范围： 对于一个升序的数据集，如果中间元素大于目标元素，说明目标可能在左半部分；如果中间元素小于目标元素，说明目标可能在右半部分。根据比较结果，将搜索范围缩小到一半，继续查找。

（4）重复步骤： 重复上述步骤，不断将搜索范围缩小，直到找到目标元素或搜索范围为空。

​

#include <stdio.h>

/* 

    使用二分查找法，查找数组中的元素
 */


int binarySearch(int arr[],int size,int target){

    int low = 0;
    int high = size - 1;


    while(low <= high){

        int middle = (low + high) / 2;
        if(arr[middle] == target){
            return middle;
        }else if(arr[middle] > target){
            high = middle - 1;
        }else{
            low = middle + 1;
        }

    }

    //表示未找到
    return -1;

}


int main()
{

    int arr[] = {4,7,9,12,16,19,22,28,34,57,69,78,90};
    int target = 12;
    target = 91;
    int size = sizeof(arr) / sizeof(int);

    int targetIndex = binarySearch(arr,size,target);
    if(targetIndex == -1){
        printf("未找到\n");
    }else{
        printf("找到了%d，对应的索引为%d\n",target,targetIndex);
    }

    getchar();

    return 0;
}

冒泡排序

#include <stdio.h>

/* 

    冒泡排序:实现从小到大排序
 */

void bubbleSort(int arr[],int size){

    //外层循环：控制轮数
    for(int i = 0;i < size - 1;i++){

        //内层循环：依次比较相邻的两个元素的大小
        for(int j = 0;j < size - 1 - i;j++){
            
            if(arr[j] > arr[j + 1]){
                //交互j 和 j+1索引位置的元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

            }

        }

    }


}


int main(){

    int arr[] = {23,45,2,46,77,2,99,-9,-32,0,66};

    int size = sizeof(arr) / sizeof(int);
    //遍历
    for(int i = 0;i < size;i++){
        printf("%d  ",arr[i]);
    }

    printf("\n");

    //排序
    bubbleSort(arr,size);


    //遍历
    for(int i = 0;i < size;i++){
        printf("%d  ",arr[i]);
    }

    printf("\n");

    getchar();

    return 0;
}

快速排序

#include <stdio.h>

/*

    快速排序:实现从小到大排序
 */

void quickSort(int arr[], int size)
{

    subSort(arr, 0, size - 1);
}

void subSort(int arr[], int start, int end)
{

    if (start < end)
    {
        int base = arr[start];
        int low = start;
        int high = end + 1;

        while (1)
        {

            while (low < end && arr[++low] <= base)
                ; // 找到从前往后第1个比base大的元素
            while (high > start && arr[--high] >= base)
                ; // 找到从后往前第1个比base小的元素

            if (low < high)
            {
                // 交换low和high位置的元素
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
            else
            {
                break;
            }
        }

        // 交换start和high索引位置上的元素
        int temp1 = arr[start];
        arr[start] = arr[high];
        arr[high] = temp1;

        // 递归调用
        subSort(arr, start, high - 1); // 前半段继续排序
        subSort(arr, high + 1, end);   // 后半段继续排序
    }
}

int main()
{

    int arr[] = {23, 45, 2, 46, 77, 2, 99, -9, -32, 0, 66};

    int size = sizeof(arr) / sizeof(int);
    // 遍历
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }

    printf("\n");

    // 排序
    quickSort(arr, size);

    // 遍历
    for (int i = 0; i < size; i++)
    {
        printf("%d  ", arr[i]);
    }

    printf("\n");

    getchar();

    return 0;
}