嵌入式基础(二)

//stack.h:栈的各种声明
#ifndef __STACK_H
#define __STACK_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述栈的属性的结构体
typedef struct stack {
    int *arr; //首地址
    int cap; //容量
    int top; //记录栈顶位置
}stack_t;
//stack_t stack;//是否分配了内存 
//声明栈的操作函数 
extern void stack_init(stack_t *stack, int cap); //初始化栈
extern void stack_deinit(stack_t *stack);//释放栈内存
extern int stack_full(stack_t *stack);//判断栈是否满
extern int stack_empty(stack_t *stack);//判断栈是否空
extern void stack_push(stack_t *stack, int data); //压栈
extern int stack_pop(stack_t *stack); //出栈
extern int stack_size(stack_t *stack);//获取栈中有效数据个数
#endif

//stack.c:栈的各种定义
#include "stack.h"
//定义栈的初始化函数 
void stack_init(stack_t *stack, int cap) {
    stack->arr = malloc(sizeof(int)*cap);//给栈分配内存
    stack->cap = cap; //初始化容量
    stack->top = 0; //空栈,一开始没有数据 
}
//定义栈内存释放函数
void stack_deinit(stack_t *stack) {
    free(stack->arr);//释放栈内存
    stack->cap = 0;
    stack->top = 0;
}
//定义判断栈空和满的函数
int stack_full(stack_t *stack) {
    return stack->top == stack->cap; //满返回1,否则返回0
}
int stack_empty(stack_t *stack) {
    return stack->top == 0;//空返回1,否则返回0
}
//定义压栈函数
void stack_push(stack_t *stack, int data) {
    stack->arr[stack->top] = data;
    stack->top++;
}
//定义出栈函数
int stack_pop(stack_t *stack) {
    return stack->arr[--stack->top];
}
//定义获取栈有效数据个数函数
int stack_size(stack_t *stack) {
    return stack->top;
}

//main.c:测试
#include "stack.h" //声明
int main(void) {  
    //定义栈变量
    stack_t stack;//arr, cap, top 
    //初始化
    //通过stack的地址来访问stack的arr,cap,top 
    //stack_t* stack = &stack;
    stack_init(&stack, 10);//指定容量是10
    int data = 1;
    while(!stack_full(&stack))//循环压栈
        stack_push(&stack, data++);
    printf("有效个数是:%d\n", stack_size(&stack));
    while(!stack_empty(&stack))//循环出栈
        printf("%d ", stack_pop(&stack));
    printf("\n");
    printf("有效个数是:%d\n", stack_size(&stack));
    stack_deinit(&stack); //释放内存
    return 0;
}

//queue.h:队列的声明
#ifndef __QUEUE_H
#define __QUEUE_H
//包含功能的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述队列属性的结构体
typedef struct queue {
    int *arr; //首地址
    int cap;//容量
    int size; //有效数据个数
    int rear; //用于入队
    int front; //用于出队
}queue_t;
extern void queue_init(queue_t *queue, int cap);//初始化
extern void queue_deinit(queue_t *queue);//释放内存
extern int queue_full(queue_t *queue);//判断满
extern int queue_empty(queue_t *queue);//判断空
extern void queue_push(queue_t *queue, int data);//入队
extern int queue_pop(queue_t *queue);//出队
extern int queue_size(queue_t *queue);//获取有效数据个数
#endif

//queue.c:队列定义
#include "queue.h"
//定义初始化队列函数
void queue_init(queue_t *queue, int cap) {
    queue->arr = malloc(sizeof(int)*cap);//分配内存
    queue->cap = cap;
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}
//定义释放内存函数
void queue_deinit(queue_t *queue) {
    free(queue->arr);
    queue->cap = 0;
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}
//定义判断满的函数
int queue_full(queue_t *queue) {
    return queue->size >= queue->cap; //满返回1,否则返回0
}
//定义判断空的函数
int queue_empty(queue_t *queue) {
    return !queue->size; //空返回1,否则返回0
}
//定义判断入队和出队函数
void queue_push(queue_t *queue, int data) {
    if(queue->rear >= queue->cap)
        queue->rear = 0; //构造循环队列
    queue->arr[queue->rear++] = data;
    queue->size++; //更新计数
}
int queue_pop(queue_t *queue) {
    if(queue->front >= queue->cap)
        queue->front = 0;//构造循环队列
    queue->size--; //更新计数
    return queue->arr[queue->front++];
}
//定义获取有效数据个数函数
int queue_size(queue_t *queue) {
    return queue->size;
}

//main.c:测试
#include "queue.h"
int main(void) {
    queue_t queue; //定义队列
    queue_init(&queue, 4);//初始化队列,容量为4个数据
    for(int i = 10; i <= 40; i += 10) 
        if(!queue_full(&queue))
            queue_push(&queue, i); //入队:10 20 30 40
    printf("有效数据个数:%d\n", queue_size(&queue));
    for(int i = 0; i < 2; i++)
        if(!queue_empty(&queue))
            printf("%d ", queue_pop(&queue)); //出10 20
    printf("\n");
    printf("有效数据个数:%d\n", queue_size(&queue));
    for(int i = 50; i <= 60; i += 10) 
        if(!queue_full(&queue))
            queue_push(&queue, i); //入队:50 60 30 40
    printf("有效数据个数:%d\n", queue_size(&queue));
    while(!queue_empty(&queue)) //整体出队:30 40 50 60
        printf("%d ", queue_pop(&queue));
    printf("\n");
    queue_deinit(&queue); //释放内存
    return 0;
}

//list.h:单链表的声明
#ifndef __LIST_H
#define __LIST_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述节点属性的结构体
typedef struct node {
    int data; //节点数据
    struct node *next;//保存下一个节点的首地址
}node_t;
//声明描述整个单链表的结构体
typedef struct list  {
    struct node *head; //保存头结点的首地址
    struct node *tail; //保存尾节点的首地址
}list_t;
extern void list_init(list_t *list);//初始化
extern void list_deinit(list_t *list);//释放内存
extern void list_travel(list_t *list);//遍历
extern void list_add(list_t *list, int data);//顺序插
extern void list_add_first(list_t *list, int data);//前插
extern void list_add_last(list_t *list, int data);//后插
extern void list_del(list_t *list, int data);//删除data所在的节点
#endif

//list.c:单链表的定义
#include "list.h"
//定义分配新节点内存函数
static node_t *create_node(int data) {
    node_t *pnew = malloc(sizeof(node_t)); //分配节点内存
    pnew->data = data; //初始化节点数据
    pnew->next = NULL;
    return pnew; //返回新节点的首地址
}
//定义单链表的初始化函数
void list_init(list_t *list) {
    //1.给头节点分配内存
    list->head = create_node(0);
    //2.给尾节点分配内存
    list->tail = create_node(0);
    //3.头指向尾
    list->head->next = list->tail;
    list->tail->next = NULL;
}
//定义单链表的遍历函数
void list_travel(list_t *list) {
    for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
        //1.定义三个游标
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        //2.判断pmid是否是有效节点
        if(pmid != list->tail)
            printf("%d ", pmid->data);
    }
    printf("\n");
}
//定义顺序新节点插函数
void list_add(list_t *list, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.遍历找到要插入的位置,让pmid指向后一个节点,pfirst指向前一个节点
    //那么pnew新节点就插入到pfirst和pmid中间即可
    for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
        //3.定义三个游标
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid->data >= pnew->data /*新节点小于后一个节点插入*/
                || pmid == list->tail/*新节点比前面的节点数据都大,放在最后一个即可*/) 
        {
            pfirst->next = pnew;
            pnew->next = pmid;
            break;
        }
    }
}
//定义前插函数和后插函数
void list_add_first(list_t *list, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.插入新节点pnew到头结点和原先的第一个节点中间
    node_t *ptmp = list->head->next; //临时备份原先的第一个节点
    list->head->next = pnew;
    pnew->next = ptmp; 
}
void list_add_last(list_t *list, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.遍历找到最后一个节点让pfirst指向最后一个节点,pmid指向尾节点
    for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
        //3.定义三个游标
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid == list->tail) { //如果pmid指向了尾节点,那么pfirst肯定指向原先的最后一个节点
            pfirst->next = pnew;
            pnew->next = pmid;
            break;
        }
    }
}
//定义删除指定数字所在的节点函数
void list_del(list_t *list, int data) {
    //1.遍历找到要删除的节点,然后让pmid指向要删除的节点,那么pfirst指向前一个节点
    //plast指向后一个节点
    for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
        //2.定义三个游标
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid->data == data && pmid != list->tail/*不能删除尾节点*/) {
            pfirst->next = plast;//让前一个节点pfirst指向后一个节点plast即可
            free(pmid); //释放内存
            break;
        }
    } 
}
//定义释放链表所有节点的函数
void list_deinit(list_t *list) {
    node_t *pnode = list->head;
    while(pnode) {
        node_t *ptmp = pnode->next; //临时备份下一个节点
        free(pnode); //释放pnode指向的节点内存
        pnode = ptmp; //pnode再指向要释放的下一个节点
    }
}

//main.c:单链表测试
#include "list.h"
int main(void) {
    //1.创建单链表
    list_t list;
    //2.初始化单链表
    list_init(&list);
    //3.各种插入和遍历
    list_add(&list, 10);
    list_add(&list, 20);
    list_add(&list, 30);
    list_travel(&list);
    list_add_first(&list, 5);
    list_add_first(&list, 3);
    list_travel(&list);
    list_add_last(&list, 40);
    list_add_last(&list, 50);
    list_travel(&list);
    //4.删除节点
    list_del(&list, 20);
    list_travel(&list);
    //5.释放整个链表
    list_deinit(&list);
    return 0;
}

//list.h:双链表的各种声明
#ifndef __LIST_H
#define __LIST_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述节点信息的结构体
typedef struct node {
    int data; //数据
    struct node *next;//保存下一个节点的首地址
    struct node *prev; //保存上一个节点的首地址
}node_t;
//声明描述整个链表的结构体
typedef struct list {
    struct node head;//头节点
    struct node tail;//尾节点
}list_t;
extern void list_init(list_t *list);//初始化函数
extern void list_deinit(list_t *list);//释放内存函数
extern int list_empty(list_t *list);//判断空
extern int list_size(list_t *list);//获取有效节点个数函数
extern void list_add(list_t *list, int data);//顺序插
extern void list_add_first(list_t *list, int data);//前插
extern void list_add_last(list_t *list, int data);//后插
extern void list_del(list_t *list, int data);//删除指定节点
extern void list_del_first(list_t *list);//只删除第一个节点
extern void list_del_last(list_t *list);//只删除最后一个节点
extern int list_get(list_t *list, int index);//根据节点编号获取节点数据
#endif

//list.c:双链表的各种定义
#include "list.h"
//定义初始化函数
void list_init(list_t *list) {
    //1.头指向尾
    list->head.next = &list->tail;
    //2.尾指向头
    list->tail.prev = &list->head;
    list->head.data = 0;
    list->tail.data = 0;
    list->head.prev = NULL;
    list->tail.next = NULL;
}
//定义判断链表是否为空
int list_empty(list_t *list) {
    return list->head.next == &list->tail;//空返回1,否则返回0
}
//定义获取节点个数的函数
int list_size(list_t *list) {
    int count = 0; //记录节点个数
    for(node_t *pnode = &list->head; pnode != &list->tail; pnode=pnode->next) {
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid != &list->tail) //pmid不等于尾节点,那么pmid指向的节点必然是有效节点
            count++; //更新计数
    }
    return count; //返回节点个数
}
//定义创建新节点函数
static node_t *create_node(int data) {
    node_t *pnew = malloc(sizeof(node_t)); //分配内存
    pnew->data = data;
    pnew->next = NULL;
    pnew->prev = NULL;
    return pnew; //返回新节点的首地址
}
//定义插入新节点函数,将新节点pnew插入到pfirst和pmid中间
static void insert_node(node_t *pfirst, node_t *pmid, node_t *pnew) {
    pfirst->next = pnew;
    pnew->prev = pfirst;
    pnew->next = pmid;
    pmid->prev = pnew;
}
//定义顺序插函数
void list_add(list_t *list, int data) {
    //1.给data创建所在的新节点
    node_t *pnew = create_node(data);
    //2.遍历找到要插入的位置,将新节点插入到pfirst和pmid中间
    for(node_t *pnode = &list->head; pnode != &list->tail; pnode=pnode->next) {
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid->data > pnew->data || pmid == &list->tail/*新节点最大,放到最后一个*/) {
            insert_node(pfirst, pmid, pnew); 
            break;
        }
    }
}
//定义前插函数
void list_add_first(list_t *list, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.造游标
    node_t *pfirst = &list->head; //pfirst指向头节点
    node_t *pmid = pfirst->next; //pmid指向原先的第一个节点
    node_t *plast = pmid->next; //plast指向第二个节点或者尾节点
    //3.将新节点pnew插入到pfirst和pmid中间,也就是插入到头节点和原先第一个节点中间
    insert_node(pfirst, pmid, pnew);
}
//定义后插函数
void list_add_last(list_t *list, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.造游标
    node_t *pfirst = list->tail.prev; //pfirst指向原先最后一个节点
    node_t *pmid = pfirst->next; //pmid指向尾节点
    node_t *plast = pmid->next; //plast指向NULL
    //3.将新节点pnew插入到pfirst和pmid中间,也就是插入到原先最后一个节点和尾节点中间
    insert_node(pfirst, pmid, pnew);
}
//定义删除pmid指向的节点函数
static void del_node(node_t *pfirst, node_t *pmid, node_t *plast) {
    pfirst->next = plast;
    plast->prev = pfirst;
    free(pmid); //释放节点内存
}
//定义删除指定的节点
void list_del(list_t *list, int data) {
    //1.遍历找到要删除的节点,然后让pmid指向要删除的节点
    for(node_t *pnode = &list->head; pnode != &list->tail; pnode=pnode->next) {
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(pmid->data == data && pmid != &list->tail/*尾节点不能删*/) {
            del_node(pfirst, pmid, plast);//删除pmid指向的节点,连接pfirst和plast
            break;        
        }
    }
}
//定义只删除第一个节点
void list_del_first(list_t *list) {
    //1.判断链表是否为空
    if(list_empty(list)) {
        printf("链表空了.\n");
        return;
    }
    //2.造游标
    node_t *pfirst = &list->head; //指向头
    node_t *pmid = pfirst->next; //指向要删除的第一个节点
    node_t *plast = pmid->next; //指向后一个节点或者尾节点
    //3.删除
    del_node(pfirst, pmid, plast);
}
//定义只删除最后一个节点
void list_del_last(list_t *list) {
    //1.判断链表是否为空 
    if(list_empty(list)) {
        printf("链表空了.\n");
        return;
    }
    //2.造游标
    node_t *plast = &list->tail; //plast指向尾节点
    node_t *pmid = plast->prev; //pmid指向要删除的最后一个节点
    node_t *pfirst = pmid->prev; //pfirst指向前一个节点或者head
    //3.删除
    del_node(pfirst, pmid, plast);
}
//定义根据节点编号获取节点数据
int list_get(list_t *list, int index) {
    int count = 0; //记录循环的次数
    for(node_t *pnode = &list->head; pnode != &list->tail; pnode = pnode->next) {
        node_t *pfirst = pnode;
        node_t *pmid = pfirst->next;
        node_t *plast = pmid->next;
        if(index == count && pmid != &list->tail)
            return pmid->data;
        count++;
    }
}
//定义清空双链表所有节点的函数
void list_deinit(list_t *list) {
    while(list->head.next != &list->tail) { //说明链表中还有节点
        node_t *pfirst = &list->head; //pfirst永远指向头结点
        node_t *pmid = pfirst->next; //pmid指向要清除的第一个节点
        node_t *plast = pmid->next; //plast指向第二个节点
        del_node(pfirst, pmid, plast);
    }
}

//main.c:双链表测试
#include "list.h"
int main(void) {
    list_t list;//定义
    list_init(&list);//初始化
    //各种插入
    list_add_first(&list, 50);
    list_add_first(&list, 20);
    list_add_last(&list, 70);//20 50 70 
    list_add_last(&list, 100);//20 50 70 100
    list_add(&list, 80);
    list_add(&list, 30);
    list_add(&list, 40);
    list_add(&list, 60);
    list_add(&list, 90);
    list_add(&list, 10);
    int size = list_size(&list);//获取节点个数
    for(int i = 0; i < size; i++)
        printf("%d ", list_get(&list, i));//遍历
    printf("\n");
    list_del_first(&list);
    list_del_last(&list);
    list_del(&list, 50);
    size = list_size(&list);//获取节点个数
    for(int i = 0; i < size; i++)
        printf("%d ", list_get(&list, i));//遍历
    printf("\n");
    list_deinit(&list); //清除链表
    return 0;
}

//tree.h:二叉树各种声明
#ifndef __TREE_H
#define __TREE_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述节点属性的结构体
typedef struct node {
    int data; //数据
    struct node *left; //保存左节点的首地址
    struct node *right; //保存右节点首地址
}node_t;
//声明描述整个二叉树的结构体
typedef struct tree {
    struct node *root; //保存根节点的首地址
    int cnt; //保存节点个数
}tree_t;
extern void tree_travel(tree_t *tree); //遍历
extern void tree_clear(tree_t *tree); //清空所有节点
extern void tree_insert(tree_t *tree, int data);//插入新节点
extern void tree_del(tree_t *tree, int data);//删除指定节点
extern void tree_modify(tree_t *tree, int old_data, int new_data);//修改节点值
#endif

//tree.c:有序二叉树各种定义
#include "tree.h"

//定义遍历的递归函数
static void travel(node_t *proot) {

    //中序遍历
    if(proot != NULL) {
        travel(proot->left); //打印左节点
        printf("%d ", proot->data); //打印节点数据
        travel(proot->right); //打印右节点
        return;
    }
    /*
    //先序遍历
    if(proot != NULL) {
        printf("%d ", proot->data); //打印节点数据
        travel(proot->left); //打印左节点
        travel(proot->right); //打印右节点
        return;
    }
    //后序遍历
    if(proot != NULL) {
        travel(proot->left); //打印左节点
        travel(proot->right); //打印右节点
        printf("%d ", proot->data); //打印节点数据
        return;
    }
    */
    return;
};
//定义有序二叉树遍历函数
void tree_travel(tree_t *tree) {
    //调用递归函数从根节点开始遍历
    travel(tree->root);
    printf("\n");
}

//定义清空节点的递归函数
void clear(node_t **pproot) {
    if(*pproot != NULL) {
        clear(&(*pproot)->left); //清空左子树
        clear(&(*pproot)->right); //清空左子树
        free(*pproot); //释放节点内存
        *pproot = NULL; //修改指向释放节点的父节点指向NULL,否则就是野指针
        return;
    }
    return;
}
//定义清空二叉树所有节点函数
void tree_clear(tree_t *tree) {
    //调用递归函数从根节点开始清空
    clear(&tree->root);
}
//定义分配新节点的内存函数
static node_t *create_node(int data) {
    node_t *pnew = malloc(sizeof(node_t));
    pnew->data = data;
    pnew->left = NULL;
    pnew->right = NULL;
    return pnew;
}

//定义插入新节点的递归函数
static void insert(node_t **pproot, node_t *pnew) {
    if(*pproot == NULL) {
        *pproot = pnew; //插入新节点
        return;
    }
    if((*pproot)->data > pnew->data) {
        insert(&(*pproot)->left, pnew); //将新节点插入插入到左子树
        return;
    } else {
        insert(&(*pproot)->right, pnew); //将新节点插入插入到右子树
        return;
    }
    return;
}
//定义插入新节点的函数
void tree_insert(tree_t *tree, int data) {
    //1.创建新节点
    node_t *pnew = create_node(data);
    //2.调用递归函数插入新节点
    insert(&tree->root, pnew);
    //3.更新计数
    tree->cnt++;
}

//定义查找节点的递归函数
static node_t **find(node_t **pproot, int data) {
    //1.停止查找
    if(*pproot == NULL)
        return pproot; //没有找到
    //2.比较
    if((*pproot)->data == data)
        return pproot; //找到了
    else if(data < (*pproot)->data)
        return find(&(*pproot)->left, data); //左边找
    else
        return find(&(*pproot)->right, data); //右边找
}
//定义查找节点函数
static node_t **find_node(tree_t *tree, int data) {
    //调用递归函数从根节点开始查找要删除的节点
    return find(&(tree)->root, data);
}
//定义删除指定的节点函数
void tree_del(tree_t *tree, int data) {
    //1.找节点
    node_t **ppnode = find_node(tree, data);
    if(*ppnode == NULL) {
        printf("没有找到节点.\n");
        return;
    }
    //2.找新爹:如果要删除的节点的左子树不为空,将左子树插入到右子树上
    if((*ppnode)->left != NULL)
        insert(&(*ppnode)->right, (*ppnode)->left);
    //3.提一级:将要删除的节点的父节点的左子树指向要删除的节点的右子树上
    //(*ppnode):就是50的L
    //(*ppnode)->right:删除的节点的右子树
    node_t *ptmp = *ppnode; //临时备份要删除的节点,将来用于free,ptmp指向20
    (*ppnode) = (*ppnode)->right; //50的L指向40
    free(ptmp); //释放20
    tree->cnt--; //更新计数
}
//定义修改节点值的函数
void tree_modify(tree_t *tree, int old_data, int new_data) {
    //1.先删除节点
    tree_del(tree, old_data);
    //2.插入新节点
    tree_insert(tree, new_data);
}

//main.c:有序二叉树测试
#include "tree.h"
int main(void) {
    tree_t tree;
    tree.root = NULL;
    tree.cnt = 0;
    tree_insert(&tree, 50);
    tree_insert(&tree, 70);
    tree_insert(&tree, 60);
    tree_insert(&tree, 20);
    tree_insert(&tree, 40);
    tree_insert(&tree, 30);
    tree_insert(&tree, 10);
    tree_insert(&tree, 90);
    tree_insert(&tree, 80);
    tree_travel(&tree);
    tree_del(&tree, 40);
    tree_del(&tree, 40);
    tree_travel(&tree);
    tree_modify(&tree, 10, 520);
    tree_travel(&tree);
    tree_clear(&tree);
    tree_travel(&tree);
    return 0;
}