数据结构与算法(绪论) && 线性表

什么是数据结构

牛客网：可以查找大厂公司笔试题
画图 思考
顺序表
链表
栈 队列
二叉树
排序

数据结构：是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合（在实现项目的时候，需要在内存中把数据存储起来，数据的存储方式）

算法：一系列的计算步骤，用来将输入数据转化成输出结果
排序 查找 去重 …
推荐算法

C语言中常用的数据结构有

1. 数组：一组连续的内存单元，用于存储同类型数据。
2. 链表：数据元素分散在内存中，通过指针将它们连接在一起，形成一种逻辑上的有序结构。
3. 树：由节点和指向它们的指针构成的数据结构，每个节点最多有一个父节点和多个子节点，经常用于表示层次关系。
4. 栈：后进先出的数据结构，插入和删除数据均在栈顶进行。
5. 队列：先进先出的数据结构，插入在队尾，删除在队头进行。
6. 串：串是由字符组成的有限序列，对于字符串的操作需要一些复杂的处理方法，并需要掌握一些字符串处理的库函数。
7. 图：由节点和边构成的数据结构，节点可以表示对象，边可以表示它们之间的关系，广泛应用于网络、路由算法、搜索和排序等领域。
   这些数据结构都可以在C语言中使用，可以根据具体的需求选择不同的数据结构。

C语言中常用的算法有：

1. 排序算法：包括冒泡排序、选择排序、插入排序、快速排序、归并排序等，用于将一组数据按照一定的顺序进行排列。
2. 查找算法：包括线性查找、二分查找、哈希查找等，用于在一组数据中寻找指定元素。
3. 递归算法：通过函数自身的调用来解决问题，常用于解决具有递归结构的问题，如树的遍历、阶乘等。
4. 动态规划算法：将复杂问题分解成简单子问题，并记录子问题的结果，以便重复利用，常用于求解最优化问题。
5. 贪心算法：每一步都选择当前最优解，希望最终得到全局最优解，常用于求解某些最优化问题。
6. 图算法：包括深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（如Dijkstra算法、Floyd-Warshall算法）、最小生成树算法（如Prim算法、Kruskal算法）等，用于解决图相关的问题。
   这些算法是C语言中常用的基本算法，可以根据具体的问题选择合适的算法来解决。此外，还有很多高级算法和数据结构，如红黑树、堆、哈夫曼编码等，可以根据需要学习和应用。

时间复杂度

算法效率的分析：
①时间复杂度：衡量一个算法的运行快慢
②空间复杂度：衡量一个算法运行所需要的额外空间(基本不太关注内存占用空间了)
时间复杂度是一个函数(数学表达式)
实际上算的是算法的执行次数

关注影响最大的那个项(n越大，其他对结果的影响越小)不需要精确值，只保留对结果影响最大的那一项

大O的渐进表示法
①用常数1取代运行时间中所有的加法常数
②在修改后的运行次数函数中，只保留最高阶项
③如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

1.双重循环的时间复杂度

for (i = 0; i < n; i++) {
       for (j = 0; j < n; j++) {
           printf("i = %d, j = %d\n", i, j);
       }
   }

F(n) = n * (n + 1) / 2
时间复杂度：O(n^2)

2.嵌套循环的时间复杂度

for (i = 0; i < n; i++) {
       for (j = i; j < n; j++) {
           printf("i = %d, j = %d\n", i, j);
       }
   }

时间复杂度：O(n^2)

3.常数循环的时间复杂度

时间复杂度：O(1)

4.strchar的时间复杂度

最好情况、最坏的情况

5.冒泡排序的时间复杂度

void bubble_sort(int arr[], int n) {
    int i, j, temp;
      for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

n-1
n-2
…
1
(n-1 + 1) * (n-1) / 2 = n(n-1)/2
(首项+尾项)x项数/2
F(n) = n(n-1)/2
时间复杂度：O(n^2)

6.二分查找的时间复杂度

int binary_search(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;  //找到目标值，返回索引
        }else if (arr[mid] < target) {
            left = mid + 1;  //目标值在右边，继续在右半部分查找
        }else {
            right = mid - 1;  //目标值在左边，继续在左半部分查找
        }
    }

    return -1;  //目标值不存在，返回 -1
}

1 * 2 * 2 * 2 * 2…=n
2^x = n
x = ㏒₂n
最好：O(1)
最坏：O(㏒₂n)
时间复杂度：O(㏒₂n)
log^2^(8) = 3

7.斐波那契的时间复杂度

递归算法：递归次数 * 每次递归调用的次数

//计算阶乘递归  
unsigned long long factorial(unsigned int n) {
    if (n <= 1) {
        return 1;
    }
    else {
        return n * factorial(n - 1);
    }
}

return n * factorial(n - 1);
时间复杂度：O(n)

//斐波那契
unsigned long long fibonacci(unsigned int n) {
    if (n <= 1) {
        return n;
    }
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

等比数列
return fibonacci(n - 1) + fibonacci(n - 2);
Fib(n) = 2^0 + 2^1 + 2^2 +…+2^(n-1) - x(缺少的次数)
   = 2^n - 1
时间复杂度：O(n^2)

一.线性表

线性表：是n个具有相同特性的数据元素的有序列表
线性表在逻辑上是线性结构，是连续的一条直线。
但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存在
常见的线性表：顺序表、链表、栈、队列、字符串

1.顺序表

(本质上是数组，还要求数据是从头连续存储的，不能跳跃)
静态顺序链表：如果满了就不让插入，n个给小不够，给大浪费
用动态

尾部插入数据时要考虑的情况

1. 整个顺序表没有空间
2. 空间不够(扩容)
3. 空间足够，直接插入数据即可
   为了提高效率，在扩容的时候，我们选择扩容扩两倍

typedef struct SeqList{
    //SLDataType a[N]; //静态
    SLDataType* a; //动态存储顺序表的数据
    //存储有效数据的个数
    int size; //表示数据的个数，同时可以表示数组下一个位置的索引值
    int capacity; //数组实际能存储数据的空间容量是多大
}SL;


//初始化
void SeqListInit(SL* ps){
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}


//检查扩容
void SeqListCapacity(SL* ps){
    //空间满了or没有空间
    if(ps->size == ps->capacity){
        //扩容
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        //先给到一个临时空间上面
        SLDataType *tmp =(SLDataType*)realloc(ps->a,newCapacity*sizeof (SLDataType));
        //realloc失败了，退出
        if(tmp == NULL){
            printf("realloc fail\n");
            fflush(stdout);
            exit(-1);
        }
        //扩容成功
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
}



/** 查询 找到返回x下标 没找到返回-1 (针对无序) */
int SeqListFind(SL* ps,SLDataType x){
    for (int i = 0; i < ps->size; ++i) {
        if(ps->a[i] == x){
            return i;
        }
    }
    return -1;
}



/** 在指定位置插入数据 */
void SeqListInsert(SL* ps,int pos,SLDataType x){
    //判断pos是否合法
    if(pos > ps->size || pos < 0){
        printf("pos invalid\n");
        fflush(stdout);
        return;
    }
    //插入可能需要扩容
    SeqListCapacity(ps);

    //将要插入位置及以后的数据往后挪，从后往前挪
    int end = ps->size -1;
    while (end >= pos){
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    //插入数据
    ps->a[pos] = x;
    ps->size++;
}



/** 删除指定位置数据 */
void SeqListErase(SL* ps,int pos){
    //合法判断
    if(pos > ps->size -1 || pos < 0){
        printf("pos invalid\n");
        fflush(stdout);
        return;
    }
    //将要删除数据的位置之后的数据 从前往后挪一个位置
    //直接用后面的数据覆盖掉
    int begin = pos + 1;
    while (begin < ps->size){
        ps->a[begin -1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}


//打印 把顺序表里面的东西打印出来
void SeqListPrint(SL* ps){
    for(int i = 0;i<ps->size;++i){
        printf("%d ",ps->a[i]);
        fflush(stdout);
    }
    printf("\n");
}


//用完了，不用了要销毁
void SeqListDestroy(SL* ps){
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

2.链表

(用指针把一块一块的这些内存连接起来)

单链表

双向链表

3.顺序表和链表的区别和联系

Donate