嵌入式学习路线

Appearance

经典抽象数据类型 ​

有些抽象数据类型(ADT)是不可或缺的工具,链表,堆栈, 队列, 树等

内存分配 ​

所有的ADT都必须确定一件事情,如何获取内存来存储值

  • 静态数组: 固定的长度,编译的时候确定
  • 动态分配数组: 运行时候决定
  • 动态分配链式结构: 最灵活

堆栈 ​

接口 ​

传统的堆栈有三种接口, push, top, pop

top: 查看顶层

push: 入栈

pop: 移出但是不返回

还需要一个判断栈是不是为空的函数, 以及一个判断是不是满了的函数

实现 ​

  • stack.h
C
  1 #define STACK_TYPE int                                                                
  2 #include <stddef.h>
  3 void push(STACK_TYPE value);
  4 STACK_TYPE pop(void);
  5 STACK_TYPE top(void);
  6 int is_empty(void);
  7 int is_full(void);
  8 void create_stack(size_t size);
  9 void destory_stack(void);
  • stack.c
C
  1 #include "stack.h"                                                                    
  2 #include <stdlib.h>
  3 #include <stdio.h>
  4 #include <assert.h>
  5 
  6 static size_t stack_size;
  7 static STACK_TYPE *stack;
  8 static int top_element = -1;
  9 
 10 void create_stack(size_t size)
 11 {
 12     assert(stack_size == 0);
 13     stack_size = size;
 14     stack = malloc(stack_size * sizeof(STACK_TYPE));
 15     assert(stack != NULL);
 16 }
 17 
 18 void destory_stack(void)
 19 {
 20     assert(stack_size > 0);
 21     stack_size = 0;
 22     free(stack);
 23     stack = NULL;
 24 }
 25 
 26 void push(STACK_TYPE value)
 27 {   
 28     assert(!is_full());
 29     top_element += 1;
 30     stack[top_element] = value;
 31 }
 32 
 33 STACK_TYPE pop(void)
 34 {
 35     STACK_TYPE temp;
 36     assert(!is_empty());
 37     temp = stack[top_element];
 38     top_element -= 1;
 39     return temp;
 40 }
 41 
 42 STACK_TYPE top(void)
 43 {
 44     assert(!is_empty());
 45     return stack[top_element];
 46 }
 47 int is_empty(void)
 48 {
 49     assert(stack_size > 0);
 50     return top_element == -1;
 51 }
 52 int is_full(void)
 53 {
 54     assert(stack_size > 0);
 55     return top_element == stack_size - 1;
 56 }
  • 链表实现
C
  1 #include <stdio.h>                                                                    
  2 #include <stdlib.h>
  3 #include "stack.h"
  4 #include <assert.h>
  5 
  6 #define FALSE 0
  7 
  8 typedef struct STACK_NODE{
  9     STACK_TYPE value;
 10     struct STACK_NODE *next;
 11 }StackNode;
 12 
 13 static StackNode *stack = NULL;
 14 
 15 void create_stack(size_t size){
 16 }
 17 
 18 void destory_stack(void)
 19 {
 20     while(!is_empty())
 21         pop();
 22 }
 23 void push(STACK_TYPE value)
 24 {
 25     StackNode *new_node;
 26     
 27     new_node = malloc(sizeof(StackNode));
 28     assert(new_node != NULL);
 29     new_node->value = value;
 30     new_node->next = stack;
 31     stack = new_node;
 32 }
 33 
 34 STACK_TYPE pop(void)
 35 {
 36     StackNode *first_node;
 37     STACK_TYPE temp;
 38     if(!is_empty()){
 39         first_node = stack;
 40         temp = first_node->value;
 41         stack = first_node->next;
 42         free(first_node);
 43     
 44         return temp;
 45     }
 46     return -1;
 47 }
 48 
 49 STACK_TYPE top(void)
 50 {
 51     assert(!is_empty());
 52     return stack->value;
 53 }
 54 int is_empty(void){
 55     return stack == NULL;
 56 }
 57 int is_full(void){
 58     return FALSE;
 59 }

队列FIFO ​

  • 循环数组

当用一个指针指向头部,一个指向尾部的时候, 在为空的时候,需要把尾部放在比头部小一个的位置,这时候和数组满了的时候的格式一样

**解决方法:**重新定义数组满的概念, 数组中有一个元素一直不使用

满:(rear + 2) % QUERE_SIZE == front

空: (rear + 1) % QUERE_SIZE == front

C
  1 #include "queue.h"                                                                    
  2 #include <stdio.h>
  3 #include <assert.h>
  4 #define QUEUE_SIZE 100
  5 #define ARRAY_SIZE (QUEUE_SIZE + 1)
  6 
  7 static QUEUE_TYPE queue[ARRAY_SIZE];
  8 static size_t front = 1;
  9 static size_t  rear = 0;
 10 
 11 void insert(QUEUE_TYPE value){
 12     assert(!is_full());
 13     rear = (rear+1) % ARRAY_SIZE;
 14     queue[rear] = value;
 15 }
 16 void delect(void)
 17 {
 18     assert(!is_empty());
 19     front = (front + 1) % ARRAY_SIZE;
 20 }
 21 
 22 QUEUE_TYPE first(void)
 23 {
 24     assert(!is_empty());
 25     return queue[front];
 26 }
 27 
 28 int is_empty(void)
 29 {
 30     return (rear + 1) % ARRAY_SIZE == front;
 31 }
 32 int is_full(void)
 33 {
 34     return (rear + 2) % ARRAY_SIZE == front;
 35 }

树 ​

要么为空,要么具有零个或多个孩子, 每个孩子本身也是树, 递归的设置提示了树的高度没有内在的限制

二叉搜索树 ​

树的特殊形式

  • 每个节点最多有两个孩子, 左孩子, 右孩子
  • 每个节点比他所有的左子树的值要大, 但是比右子树的值要小
  • 排除了相等的可能性

没有孩子的节点被称为叶节点

在二叉树之中插入 ​

树为空:
	新的值作为根节点插入
否则:
	小于当前:
		插入左侧
	否则:
		右侧

在二叉树中删除 ​

  • 删除没有孩子的节点
  • 删除有一个孩子
  • 删除有两个: 删除左侧最的大一个值把他替换这个值

在二叉树中查找 ​

树为空:
	不存在
否则:
	和根节点相等:
		成功
	否则:
		小于:
			左侧
		否则:
			右侧

树的遍历 ​

有几种不同的次序

  • 前序: 检查节点然后递归的遍历左子树右子树
  • 中序: 先遍历左侧然后检测当前节点, 最后右侧
  • 后序: 首先遍历左右然后当前节点
  • 层次遍历: 处理根节点, 然后他的儿子, 然后孙子

实现 ​

数组类型 ​

  • 节点N的双亲节点是N/2
  • 节点N左孩子是2N
  • 节点右孩子是2N+1

问题: 数组是从零开始的

  1. 忽略第一个元素
  2. 更改规则
  • 节点N的双亲节点是(N+1)/2-1
  • 节点N左孩子是2N+1
  • 节点右孩子是2N+2

数组存在的问题:

  • 不能够随意插入, 会导致浪费,
  • 分配不同元素利用率不同
C
  1 #include <stdio.h>                                                                    
  2 #include <assert.h>
  3 #include "tree.h"
  4 
  5 #define TREE_SIZE 100
  6 #define ARRAY_SIZE (TREE_SIZE + 1)
  7 
  8 static TREE_TYPE tree[ARRAY_SIZE];
  9 //查询分支的位置
 10 static int left_child(int current)
 11 {
 12     return current * 2;
 13 }
 14 
 15 static int right_child(int current)
 16 {
 17     return current * 2 + 1;
 18 }
 19 //插入一个元素
 20 void insert(TREE_TYPE value)
 21 {
 22     int current;
 23     assert(value != 0);
 24     current = 1;
 25     while(tree[current] != 0){//根据数值寻找位置所在
 26         if(value < tree[current])
 27             current = left_child(current);
 28         else{
 29             assert(value != tree[current]);//保证不会有重复的元素
 30             current = right_child(current);
 31         }
 32         assert(current<ARRAY_SIZE);
 33     }
 34     tree[current] = value;
 35 }
 36 
 37 TREE_TYPE *find(TREE_TYPE value)
 38 {   
 39     int current;
 40     current = 1;
 41     while(current < ARRAY_SIZE && tree[current] != value){
 42         if(value < tree[current])
 43             current = left_child(current);
 44         else
 45             current = right_child(current);
 46     }
 47     if(current < ARRAY_SIZE)
 48         return tree + current;
 49     else
 50         return 0;
 51 }
 52 static void do_per_order_traverse(int current, void (*callback)(TREE_TYPE value))
 53 {//遍历到每一个元素并进行一定的处理
 54     if(current < ARRAY_SIZE && tree[current] != 0)
 55     {
 56         callback(tree[current]);
 57         do_per_order_traverse(left_child(current), callback);
 58         do_per_order_traverse(right_child(current), callback);
 59     }
 60 }
 61 //外部可以使用的
 62 void pre_order_traverse(void (*callback)(TREE_TYPE value))
 63 {
 64     do_per_order_traverse(1, callback);
 65 }

链表类型 ​

由于每一个节点必须有左右两个孩子, 所以用两个指针

C
  1 #include "tree.h"                                                                     
  2 #include <assert.h>
  3 #include <stdio.h>
  4 #include <malloc.h>
  5 
  6 typedef struct TREE_NODE{//用于存储数据的结构体
  7     TREE_TYPE value;
  8     struct TREE_NODE *left;
  9     struct TREE_NODE *right;
 10 }TreeNode;
 11 
 12 static TreeNode *tree;//建立一个指向根部的指针
 13 
 14 void insert(TREE_TYPE value)
 15 {
 16     TreeNode *current;
 17     TreeNode **link;//用来指向上一级的指针的指针
 18 
 19     link = &tree;//初始化为根部
 20     while((current = *link) != NULL)
 21     {
 22         if(value < current->value)
 23             link = &current->left;
 24         else{
 25             assert(value != current->value);
 26             link = &current->right;
 27         }
 28     }
 29 
 30     current = malloc(sizeof(TreeNode));
 31     assert(current != NULL);
 32     current->value = value;
 33     current->left = NULL;
 34     current->right = NULL;
 35     *link = current;//创建与上一级的链接
 36 }
 37 
 38 TREE_TYPE *find(TREE_TYPE value)
 39 {
 40     TreeNode *current;
 41     current = tree;//指向根部
 42     while(current != NULL && current->value != value)
 43     {
 44         if(value<current->value)
 45             current = current->left;
 46         else      
 47             current = current->right;                                                 
 48     }
 49     if(current != NULL)
 50         return &current->value;//返回一个指向数据的指针
 51     else
 52         return NULL;
 53 }   
 54 
 55 static void do_pre_order_traverse(TreeNode *current,
 56     void (*callback)(TREE_TYPE value))
 57 {
 58     if(current != NULL)
 59     {
 60         callback(current->value);//对每一个数据进行处理
 61         do_pre_order_traverse(current->left, callback);//对左侧进行遍历
 62         do_pre_order_traverse(current->right, callback);//右侧
 63     }
 64 }
 65 
 66 void pre_order_traverse(void (*callback)(TREE_TYPE value))
 67 {
 68     do_pre_order_traverse(tree, callback);//外部调用
 69 }

实现的改进 ​

拥有超过一个堆栈 ​

由用户进行对堆栈的创建,再通过参数进行访问, 用户可以创建任意数量的堆栈, 然后进行访问

拥有超过一种的类型 ​

  • 为每一种类型写代码
  • 实现#define的宏
  • 使用void *类型

名字冲突 ​

不同的结构之间可能有相同的函数名字

标准库的ADT ​

C语言暂时没有提供,但是可以用#define模拟

  • g_atck.h
C
  1 #include <assert.h>                                                                   
  2 /*建立一个栈初始化的声明,数据类型,标记,大小*/
  3 #define GENERIC_STACK(STACK_TYPE, SUFFIX, STACK_SIZE)   \
  4     static STACK_TYPE stack##SUFFIX[STACK_SIZE];        \
  5     static int top_element##SUFFIX = -1;                \
  6     int is_empty##SUFFIX(void)                          \
  7     {                                                   \
  8         return top_element##SUFFIX == -1;               \
  9     }                                                   \
 10     int is_full##SUFFIX(void)                           \
 11     {                                                   \
 12         return top_element##SUFFIX == STACK_SIZE -1;    \
 13     }                                                   \
 14     void push##SUFFIX(STACK_TYPE value)                 \
 15     {                                                   \
 16         assert(!is_full##SUFFIX());                     \
 17         top_element##SUFFIX += 1;                       \
 18         stack##SUFFIX[top_element##SUFFIX] = value;     \
 19     }                                                   \
 20     void pop##SUFFIX(void)                              \
 21     {                                                   \
 22         assert(!is_empty##SUFFIX());                    \
 23         top_element##SUFFIX -= 1;                       \
 24     }                                                   \
 25     STACK_TYPE top##SUFFIX(void)                        \
 26     {                                                   \
 27         assert(!is_empty##SUFFIX());                    \
 28         return stack##SUFFIX[top_element##SUFFIX];      \
 29     }
  • g_atck.c
C
  2 #include <stdio.h>
  3 #include "g_atck.h"
  4 
  5 GENERIC_STACK(int, _int, 10)//建立第一个栈
  6 GENERIC_STACK(float, _float, 10)
  7 int main(){
  8     push_int(5);
  9     push_int(22);
 10     push_int(15);
 11     push_float(25.4);
 12     push_float(-40.5);
 13     
 14     while(!is_empty_int()){
 15         printf("*Popping %d\n", top_int());
 16         pop_int();
 17     }   
 18     while(!is_empty_float()){
 19         printf("*Popping %f\n", top_float());
 20         pop_float();
 21     }
 22     return EXIT_SUCCESS;
 23 }

result:
*Popping 15
*Popping 22
*Popping 5
*Popping -40.500000
*Popping 25.400000