Algorithms + Data Structures = Programs

关于c语言的基础补充

字符串不是数据类型，通常用字符型数组表示字符串

计算机结构，虚拟内存地址。
内存条，显卡，各种适配器都有其各自的存储地址空间，
这些空间被抽象成巨大的一维数组空间
alt text

当结构体比较大时，直接传递结构体变量会导致整个结构体的数据被复制一份，一般通过指针传递结构体变量，
使用时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h>

// 定义一个较大的结构体
typedef struct {
    char name[50];
    int age;
    double scores[10];
} Student;

// 传递结构体指针
void printStudentInfo(Student *s) {
    printf("Name: %s, Age: %d\n", s->name, s->age);
}

int main() {
    Student s;
    strcpy(s.name, "John");
    s.age = 20;
    // 传递指针
    printStudentInfo(&s);
    return 0;
}

内存分类
关于动态内存。malloc分配，free释放。java中的垃圾回收机制，c++中的析构函数，底层就是使用free函数释放内存

1
2
3
4
5
6
7
8
int main(int argc, char const *argv[]){
    int* p;
    p = (int*)malloc(sizeof(int));
    //sizeof(int)可用性更高，约定俗成
    //结构体由于补位的存在，所含字节不固定
    free(p);
    return 0;
}

alt text

算法分析

大 O 记法能客观地衡量各种算法的时间复杂度，是比较算法的利器

O(N), 处理一个 N元素的数组需花 N步的算法的效率——线性时间
二分查找的大 O 记法是：O(log N) ——对数时间

线性表（包含顺序表与链表）

顺序表：物理位置联续

1
2
3
4
5
6
7
8
9
10
11
12
//对于顺序表尾部增加元素
int apppendElem(SeqList *L, ElemType e)
{
    if (L->length>=MAXSIZE)
    {
        printf("已满");
        return 0;
    }
    L->data[L->length] = e;
    //此处，由于data是数组，故其元素是有顺序的
    return 1;
}

如果结构体中包含动态数据结构（如链表、树、图等），动态内存分配是必要的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//关于顺序表的动态分配内存初始化
typedef struct{
    ElemType *data;
    int length;
}SeqList;

SeqList* initList(SeqList *L)
{
    SeqList *L = (SeqList*)malloc(sieof(SeqList));
    //因为malloc默认开辟的的void*类型的内存空间，故要进行强制类型转换
    L->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    L->length = 0;
    return L;
}

链表

本质是指向地址，由一个结构体跳到另一个结构体

技巧：双指针法。通过快慢指针快速定位到指定倒数第几位的数
快慢指针间隔一定位置后同步前进，当快指针为NULL，慢指针即为所求