静态数组

int arr[] = {1, 2, 4};

动态数组-int

DynamicArray.h

#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H

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

typedef struct DYNAMIC_ARRAY {
    int *pAddr;
    int capacity;
    int size;

} Dynamic_Array;

//初始化
Dynamic_Array *Init_Dynamic_Array();

//打印
void Print_Dynamic_Array(Dynamic_Array *arr);

//插入
void Push_Dynamic_Array(Dynamic_Array *arr, int val);

//删除
void Pop_Dynamic_Array(Dynamic_Array *arr,int idx);

int Find_Dynamic_Array(Dynamic_Array *arr,int val);
int Get_Dynamic_Array(Dynamic_Array *arr, int idx);
void Set_Dynamic_Array(Dynamic_Array *arr, int idx, int val);

// 释放空间
void Free_Dynamic_Array(Dynamic_Array *arr);

#endif //DYNAMIC_ARRAY_H

DynamicArray.c

#include "Dynamic_Array.h"

//初始化
Dynamic_Array *Init_Dynamic_Array() {
    Dynamic_Array *arr = (Dynamic_Array *) malloc(sizeof(Dynamic_Array));
    arr->capacity = 20;
    arr->size = 0;
    arr->pAddr = (int *) malloc(sizeof(int) * arr->capacity);
    return arr;
}

//插入
void Push_Dynamic_Array(Dynamic_Array *arr, int val) {
    if (arr == NULL) {
        return;
    }

    if (arr->size == arr->capacity) {
        int new_capacity = arr->capacity * 2;
        int *newPArr = (int *) malloc(sizeof(int) * arr->capacity);
        memcpy(newPArr, arr->pAddr, sizeof(int) * arr->capacity);
        free(arr->pAddr);

        arr->pAddr = newPArr;
        arr->capacity = new_capacity;
    }
    arr->pAddr[arr->size] = val;
    arr->size++;

}

//打印
void Print_Dynamic_Array(Dynamic_Array *arr) {
    if (arr == NULL) {
        return;
    }
    for (int i = 0; i < arr->size; i++) {
        printf("%d,", arr->pAddr[i]);
    }
    printf("\n");
}

//删除一个
void Pop_Dynamic_Array(Dynamic_Array *arr, int idx) {
    if (arr == NULL) {
        return;
    }
    if (idx < 0 || idx >= arr->size) {
        return;
    }

    arr->size--;
    for (int i = idx; i < arr->size; i++) {
        arr->pAddr[i] = arr->pAddr[i + 1];
    }

}

//取一个
int Get_Dynamic_Array(Dynamic_Array *arr, int idx) {
    return arr->pAddr[idx];
}
//赋值
void Set_Dynamic_Array(Dynamic_Array *arr, int idx, int val) {
    arr->pAddr[idx] = val;
}

//查找
int Find_Dynamic_Array(Dynamic_Array *arr, int val) {
    for (int i = 0; i < arr->size; i++) {
        if (arr->pAddr[i] == val) {
            return i;
        }
    }
    return -1;
}

//释放空间
void Free_Dynamic_Array(Dynamic_Array *arr) {
    if (arr == NULL) {
        return;
    }
    if (arr->pAddr != NULL) {
        free(arr->pAddr);
    }
    free(arr);
}

测试

#include <stdio.h>

#include "Dynamic_Array.h"

int main() {

    Dynamic_Array *arr = Init_Dynamic_Array();

    for (int i = 0; i < 30; i++) {
        Push_Dynamic_Array(arr, i);
    }

    Print_Dynamic_Array(arr);

    Pop_Dynamic_Array(arr, 3);
    Print_Dynamic_Array(arr);

    printf("%d\n", Find_Dynamic_Array(arr, 5));
    printf("%d\n", Get_Dynamic_Array(arr, 5));

    Set_Dynamic_Array(arr, 0, 30);
    Print_Dynamic_Array(arr);

    Free_Dynamic_Array(arr);

}

动态数组-二级指针

用二级指针，指向一个数组指针
数组指针中的一个元素（指针）指向一个结构体
可以用来做stack
还没做充分验证，例如内存释放是否彻底

DynamicArray.h

#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H

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

typedef struct DYNAMIC_ARRAY {
    void **pAddr;
    int capacity;
    int size;
} Dynamic_Array;

//遍历函数指针
typedef void (*PRINT_DATA)(void *);

//比较函数指针
typedef int (*COMPARE_DATA)(void *, void *);

//初始化
Dynamic_Array *Init_Dynamic_Array();

//打印
void Print_Dynamic_Array(Dynamic_Array *arr, PRINT_DATA printData);

//插入
void Push_Last_Dynamic_Array(Dynamic_Array *arr, void *data);

//删除
void Pop_Dynamic_Array(Dynamic_Array *arr, int idx);

//插入到末尾
void Push_Dynamic_Array(Dynamic_Array *arr, int idx, void *data);

//删除末尾
void Pop_Last_Dynamic_Array(Dynamic_Array *arr);


int Find_Dynamic_Array(Dynamic_Array *arr, void *data);

void *Get_Dynamic_Array(Dynamic_Array *arr, int idx);

void Set_Dynamic_Array(Dynamic_Array *arr, int idx, void *data);

// 释放空间
void Free_Dynamic_Array(Dynamic_Array *arr);

//TODO:释放所指向的数据


#endif //DYNAMIC_ARRAY_H

DynamicArray.c

#include "DynamicArray.h"

//初始化
Dynamic_Array *Init_Dynamic_Array() {
    Dynamic_Array *arr = (Dynamic_Array *) malloc(sizeof(Dynamic_Array));
    arr->capacity = 50;
    arr->size = 0;
    arr->pAddr = (void *) malloc(sizeof(void *) * arr->capacity);
    return arr;

}

//插入
void Push_Last_Dynamic_Array(Dynamic_Array *arr, void *data) {

    Push_Dynamic_Array(arr, arr->size, data);

}


void Push_Dynamic_Array(Dynamic_Array *arr, int idx, void *data) {
    if (arr == NULL) {
        return;
    }
    if (idx < 0 || idx > arr->size) {
        return;
    }

    void **oldPAddr = arr->pAddr;
    if (arr->size == arr->capacity) {
        int new_capacity = arr->capacity * 2;
        void **newPAddr = (void *) malloc(sizeof(void *) * arr->capacity);

        for (int i = 0; i < idx; i++) {
            newPAddr[i] = oldPAddr[i];
        }
        newPAddr[idx] = data;
        for (int i = idx; i < arr->size; i++) {
            newPAddr[i + 1] = oldPAddr[i];
        }

        free(arr->pAddr);

        arr->pAddr = newPAddr;
        arr->capacity = new_capacity;
    } else {
        for (int i = arr->size; i > idx; i--) {
            oldPAddr[i] = oldPAddr[i - 1];
        }
        oldPAddr[idx] = data;
    }

    arr->size++;
}


//打印
void Print_Dynamic_Array(Dynamic_Array *arr, PRINT_DATA printData) {
    if (arr == NULL) {
        return;
    }
    for (int i = 0; i < arr->size; i++) {
//        printf("%p,", *(arr->pAddr)[i]);
        printData(arr->pAddr[i]);
    }
    printf("\n");
}

//删除一个
//TODO:被删除的内存需要释放吗？
void Pop_Dynamic_Array(Dynamic_Array *arr, int idx) {
    if (arr == NULL) {
        return;
    }
    if (idx < 0 || idx >= arr->size) {
        return;
    }

    arr->size--;
    for (int i = idx; i < arr->size; i++) {
        arr->pAddr[i] = arr->pAddr[i + 1];
    }

}

//取一个
void *Get_Dynamic_Array(Dynamic_Array *arr, int idx) {
    return arr->pAddr[idx];
}

//赋值
void Set_Dynamic_Array(Dynamic_Array *arr, int idx, void *data) {
    arr->pAddr[idx] = data;
}

//查找
int Find_Dynamic_Array(Dynamic_Array *arr, void *data) {
    for (int i = 0; i < arr->size; i++) {
        if (arr->pAddr[i] == data) {
            return i;
        }
    }
    return -1;
}


//从最后删除
void Pop_Last_Dynamic_Array(Dynamic_Array *arr) {
    Pop_Dynamic_Array(arr, arr->size - 1);
}


//释放空间
void Free_Dynamic_Array(Dynamic_Array *arr) {
    if (arr == NULL) {
        return;
    }
    if (arr->pAddr != NULL) {
        free(arr->pAddr);
    }
    free(arr);
}

测试

#include <stdio.h>

#include "DynamicArray.h"

typedef struct PERSON {
    char name[64];
    int age;
} Person;


void My_Print(Person *data) {
    printf("[name=%s,age=%d];", data->name, data->age);
}


int main() {

    Dynamic_Array *dynamicArray = Init_Dynamic_Array();


    Person p1, p2, p3, p4, p5;
    strcpy(p1.name, "a");
    strcpy(p2.name, "b");
    strcpy(p3.name, "c");
    strcpy(p4.name, "d");
    strcpy(p5.name, "e");

    p1.age = 1;
    p2.age = 2;
    p3.age = 3;
    p4.age = 4;
    p5.age = 5;

    Push_Last_Dynamic_Array(dynamicArray, &p1);
    Push_Last_Dynamic_Array(dynamicArray, &p2);
    Push_Last_Dynamic_Array(dynamicArray, &p3);
    Push_Last_Dynamic_Array(dynamicArray, &p4);
    Push_Last_Dynamic_Array(dynamicArray, &p5);


    Print_Dynamic_Array(dynamicArray, (void *) My_Print);
    printf("\npush idx = 2:\n");
    Push_Dynamic_Array(dynamicArray, 2, &p5);


    Print_Dynamic_Array(dynamicArray, (void *) My_Print);

    printf("\ndelete idx = 3:\n");
    Pop_Dynamic_Array(dynamicArray, 3);
    Print_Dynamic_Array(dynamicArray, (void *) My_Print);

    printf("delete tail:\n");
    Pop_Last_Dynamic_Array(dynamicArray);
    Print_Dynamic_Array(dynamicArray, (void *) My_Print);


    printf("\nfind idx by data:\n");
    int idx_find = Find_Dynamic_Array(dynamicArray, &p2);
    printf("result is idx=%d:\n", idx_find);

    printf("get data by idx=2:");
    Person *p_find = Get_Dynamic_Array(dynamicArray, 2);
    My_Print(p_find);
    printf("\n");

    Set_Dynamic_Array(dynamicArray, 2, &p4);
    Print_Dynamic_Array(dynamicArray, (void *) My_Print);


// 释放空间
    Free_Dynamic_Array(dynamicArray);

}

链表

链表1

LinkList.h

#ifndef LINKLIST_H
#define LINKLIST_H

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

//链表结点
typedef struct LINKNODE{
    void* data;  //指向任何类型的数据
    struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef struct LINKLIST{
    LinkNode* head;
    int size;
}LinkList;



//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list,int pos,void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list,void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//释放链表内存
void FreeSpace_LinkList(LinkList* list);


//不知道用户要打印什么，所以定义一个打印函数指针，用户传入print即可
typedef void(*PRINTLINKNODE)(void*);
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);

#endif

LinkList.c

#include"LinkList.h"

//初始化链表
LinkList* Init_LinkList(){

    LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    list->size = 0;

    //头结点 不保存数据信息
    list->head = (LinkNode*)malloc(sizeof(LinkNode));
    list->head->data = NULL;
    list->head->next = NULL;

    return list;
}
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){

    if (list == NULL){
        return;
    }
    if (data == NULL){
        return;
    }

    if (pos < 0 || pos > list->size){
        pos = list->size;
    }

    //创建新的结点
    LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
    newnode->data = data;
    newnode->next = NULL; // 这个别忘了，有些操作系统不会格式化这块内存。

    //找结点
    //辅助指针变量
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos;i++){
        pCurrent = pCurrent->next;
    }

    //新结点入链表
    newnode->next = pCurrent->next;
    pCurrent->next = newnode;

    list->size++;

}
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos){
    if (list == NULL){
        return;
    }

    if (pos < 0 || pos >= list->size){
        return;
    }

    //查找删除结点的前一个结点
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos;i ++){
        pCurrent = pCurrent->next;
    }

    //缓存删除的结点
    LinkNode* pDel = pCurrent->next;
    pCurrent->next = pDel->next;
    //释放删除结点的内存
    free(pDel);

    list->size--;
}
//获得链表的长度
int Size_LinkList(LinkList* list){
    return list->size;
}
//查找
int Find_LinkList(LinkList* list, void* data){
    if (list == NULL){
        return -1;
    }

    if (data == NULL){
        return -1;
    }

    //遍历查找
    LinkNode* pCurrent = list->head->next;
    int i = 0;
    while (pCurrent != NULL){
        if (pCurrent->data == data){
            break;
        }
        i++;
        pCurrent = pCurrent->next;
    }

    return i;
}
//返回第一个结点
void* Front_LinkList(LinkList* list){
    return list->head->next->data;
}
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print){
    if (list == NULL){
        return;
    }
    //辅助指针变量
    LinkNode* pCurrent = list->head->next;
    while (pCurrent != NULL){
        print(pCurrent->data);
        pCurrent = pCurrent->next;
    }

}
//释放链表内存
void FreeSpace_LinkList(LinkList* list){

    if (list == NULL){
        return;
    }

    //辅助指针变量
    LinkNode* pCurrent = list->head;
    while (pCurrent != NULL){
        //缓存下一个结点
        LinkNode* pNext = pCurrent->next;
        free(pCurrent);
        pCurrent = pNext;
    }

    //释放链表内存
    free(list);
}

测试

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkList.h"


//自定义数据类型
typedef struct PERSON{
    char name[64];
    int age;
    int score;
}Person;


//打印函数
void MyPrint(void* data){
    Person* p = (Person*)data;
    printf("Name:%s Age:%d Score:%d\n",p->name,p->age,p->score);
}

int main(void){


    //创建链表
    LinkList* list = Init_LinkList();

    //创建数据
    Person p1 = { "aaa", 18, 100};
    Person p2 = { "bbb", 19, 99 };
    Person p3 = { "ccc", 20, 101 };
    Person p4 = { "ddd", 17, 97 };
    Person p5 = { "eee", 16, 59 };

    //数据插入链表
    Insert_LinkList(list, 0, &p1);
    Insert_LinkList(list, 0, &p2);
    Insert_LinkList(list, 0, &p3);
    Insert_LinkList(list, 0, &p4);
    Insert_LinkList(list, 0, &p5);

    //打印
    Print_LinkList(list, MyPrint);

    //删除3
    RemoveByPos_LinkList(list, 3);

    //打印
    printf("---------------\n");
    Print_LinkList(list, MyPrint);

    //返回第一个结点
    printf("-----查找结果------------\n");
    Person* ret = (Person*)Front_LinkList(list);
    printf("Name:%s Age:%d Score:%d\n", ret->name, ret->age, ret->score);

    //销毁链表
    FreeSpace_LinkList(list);

    return 0;
}

说明

我试着把新的node定义在栈上，但不成功，因为在循环中重复定义，还是指向同一块内存
看 leetcode 上也都是用 malloc 放到堆上的
C++ 的 new 方法，也是放到堆上的

更好用的现代链表

上一种实现的缺点：

每个节点（一个 struct）访问 next 的时候（pCurrent->next），都要做指针偏移
链表很多算法都要频繁做 next，这就有大量的偏移操作（？？？为什么不把next放到第一个个字段）
如果节点拥有的数据类型是有变化的，这个偏移量也是有变化的（？？？导致什么问题呢）

LinkList.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

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

typedef struct LINKED_NODE {
    struct LINKED_NODE *next;
} Linked_Node;


typedef struct LINKED_LIST {
    Linked_Node head;
    int size;
} Linked_List;


//遍历函数指针
typedef void (*PRINT_NODE)(Linked_Node *);

//比较函数指针
typedef int (*COMPARE_NODE)(Linked_Node *, Linked_Node *);


Linked_List *Init_Linked_List();

//插入
void Insert_Linked_List(Linked_List *linkedList, int idx, Linked_Node *data);

//删除
void Remove_Linked_List(Linked_List *linkedList, int idx);

//查找
int Find_Linked_List(Linked_List *linkedList, Linked_Node *data, COMPARE_NODE compareNode);

//打印
void Print_Linked_List(Linked_List *linkedList, PRINT_NODE printNode);

//释放内存
void Free_Linked_List(Linked_List *linkedList);

#endif //LINKED_LIST_H

LinkList.c

#include "LinkedList.h"

Linked_List *Init_Linked_List() {
    Linked_List *linkedList = (Linked_List *) malloc(sizeof(Linked_List));
    linkedList->head.next = NULL;
    linkedList->size = 0;
    return linkedList;
}


void Insert_Linked_List(Linked_List *linkedList, int idx, Linked_Node *data) {
    if (linkedList == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }
    if (idx < 0 || idx > linkedList->size) {
        idx = linkedList->size;
    }

    Linked_Node *pCurr = &(linkedList->head);
    for (int i = 0; i < idx; i++) {
        pCurr = pCurr->next;
    }

    data->next = pCurr->next;
    pCurr->next = data;
    linkedList->size++;

}

void Remove_Linked_List(Linked_List *linkedList, int idx) {
    if (linkedList == NULL) {
        return;
    }
    if (idx < 0 || idx >= linkedList->size) {
        return;
    }

    Linked_Node *pCurr = &(linkedList->head);
    for (int i = 0; i < idx; i++) {
        pCurr = pCurr->next;
    }

    pCurr->next = pCurr->next->next;
    linkedList->size--;
}

int Find_Linked_List(Linked_List *linkedList, Linked_Node *data, COMPARE_NODE compareNode) {
    if (linkedList == NULL) {
        return -1;
    }
    if (data == NULL) {
        return -1;
    }

    Linked_Node *pCurr = &(linkedList->head);

    int idx = 0;

    while (pCurr != NULL) {
        if (compareNode(pCurr, data) == 0) {
            return idx;
        }
        pCurr = pCurr->next;
        idx++;
    }

    return idx;


}


void Print_Linked_List(Linked_List *linkedList, PRINT_NODE printNode) {
    if (linkedList == NULL) {
        return;
    }

    Linked_Node *pCurr = linkedList->head.next;
    while (pCurr != NULL) {
        printNode(pCurr);
        pCurr = pCurr->next;
    }
    printf("\n");
}


void Free_Linked_List(Linked_List *linkedList) {
    if (linkedList == NULL) {
        return;
    }

    free(linkedList);
}

测试

#include <stdio.h>
#include <string.h>
#include <string.h>
#include "LinkedList.h"

typedef struct PERSON {
    Linked_Node linkedNode;
    char name[64];
    int age;
} Person;

void My_Print(Linked_Node *node) {
    Person *p = (Person *) node;
    printf("[name = %s, age = %d] -> ", p->name, p->age);
}

int My_Compare(Linked_Node *node1, Linked_Node *node2) {
    Person *p1 = (Person *) node1;
    Person *p2 = (Person *) node2;

    if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age) {
        return 0;
    }
    return -1;
}

int main() {

    Linked_List *linkedList = Init_Linked_List();
    Person p1, p2, p3, p4, p5;
    strcpy(p1.name, "a");
    strcpy(p2.name, "b");
    strcpy(p3.name, "c");
    strcpy(p4.name, "d");
    strcpy(p5.name, "e");

    p1.age = 1;
    p2.age = 2;
    p3.age = 3;
    p4.age = 4;
    p5.age = 5;

    Insert_Linked_List(linkedList, 0, (Linked_Node *) &p1);
    Insert_Linked_List(linkedList, 0, (Linked_Node *) &p2);
    Insert_Linked_List(linkedList, 0, (Linked_Node *) &p3);
    Insert_Linked_List(linkedList, 0, (Linked_Node *) &p4);
    Insert_Linked_List(linkedList, 0, (Linked_Node *) &p5);

    Print_Linked_List(linkedList, My_Print);

    Remove_Linked_List(linkedList, 1);

    Print_Linked_List(linkedList, My_Print);

//    查找
    Person p_find;
    strcpy(p_find.name, "b");
    p_find.age = 2;
    int idx = Find_Linked_List(linkedList, (Linked_Node *) &p_find, My_Compare);
    printf("%d", idx);

//    释放内存
    Free_Linked_List(linkedList);
}

知识点：

先定义一个函数指针，实现中使用这个函数指针。用户时候的时候再定义这个函数指针。
实现一个只有 next 的链表。用户自定义的类把它“包起来”。使用时做指针转换，因为它俩指向同一个内存。

双向链表

循环链表

链表中，初始化的时候把指针指向自己。不多说。

栈

可以用数组来模拟栈，
（后面添加）
关键代码

#define MAX_SIZE 1024

typedef struct SEQSTACK{
	void* data[MAX_SIZE];
	int size;
}SeqStack;

3种方式

静态数组
动态数组
链表。链表的头是栈顶

队列

也是用数组来模拟

出队的时，是做个遍历，把后一个复制到前一个。

（好像用链表效率更高？）

实现方式

静态数组做环形

二叉树

typedef struct BINARYNODE{
	char ch;
	struct BINARYNODE* lchild;
	struct BINARYNODE* rchild;
}BinaryNode;

编程技巧

c的一些编程技巧

数值

n&(n-1) 作用是消除数字 n 的二进制表示中的最后一个 1

不用临时变量交换两个数

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1

0x00_读论文 8

0x10_计算机基础 2

0x11_算法平台 15

0x12_Pandas与numpy 12

0x13_特征工程 4

0x21_有监督学习 21

0x23_深度学习 7

0x24_NLP 13

0x25_CV 14

0x26_torch 11

0x31_降维 10

0x32_聚类 5

0x33_图模型 9

0x41_统计模型 9

0x42_概率论 7

0x43_时间序列 10

0x44_随机过程 2

0x51_代数与分析 15

0x52_方程 2

0x53_复分析与积分变换 8

0x55_数值计算 7

0x56_最优化 11

0x58_密码学 12

0x59_应用数学 9

0x60_启发式算法 8

0x70_可视化 13

0x80_数据结构与算法 17

0xa0_蒙特卡洛方法 6

0xb0_Python语法 18

0xd0_设计模式 6

【C7】数据结构

目录