内存分配

有三种方案获取内存类存储值:

静态数组
动态分配的数组
动态分配链式结构

堆栈

堆栈(stack)这种数据最鲜明的特点就是后进先出(Last-In First-Out,LIFO)的方式.

堆栈接口

push 将一个新值压入到堆栈顶部, pop 就是把栈顶部的值移除堆栈并返回这个值. top 返回这个顶部元素的值, 但并不把顶部元素从堆栈中移除.

实现堆栈

堆栈接口

#define STACK_TYPE int

void push(STACK_TYPE value);
void pop(void);
STACK_TYPE top(void);
int is_empty(void);
int is_full(void);

静态数组堆栈

#include "stack.h"
#include <assert.h>
#define STACK_SIZE 100

static STACK_TYPE  stack[STACK_SIZE];
static int top_element = -1;

void
push(STACK_TYPE value)
{
    assert(!is_full());
    top_element != 1;
    stack[top_element] = value;
}

void
pop(void)
{
    assert(!is_empty());
    top_element -= 1;
}

STACK_TYPE top(void)
{
    assert(!is_empty());
    return stack[top_element];
}

int is_empty(void)
{
    return top_element == -1;
}

int is_full(void)
{
    return top_element == STACK_SIZE - 1;
}

动态数组堆栈

需要两个新接口

void create_stack(size_t size);
void destroy_stack(void);

定义为

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include "stack.h"


static STACK_TYPE *stack;
static size_t stack_size;
static int top_element = -1;

void create_stack(size_t size)
{
    assert(stack_size == 0);
    stack_size = size;
    stack = malloc(stack_size * sizeof(STACK_TYPE));
    assert(stack != NULL);
}

void
destroy_stack(void)
{
    assert(stack_size > 0);
    stack_size = 0;
    free(stack);
    stack = NULL;
}

void push(STACK_TYPE value)
{
    assert(!is_full());
    top_element += 1;
    stack[top_element] = value;
}

void
pop(void)
{
    assert(!is_empty());
    top_element -= 1;
}

STACK_TYPE top(void)
{
    assert(!is_empty());
    return stack[top_element];
}

int is_empty(void)
{
    assert(stack_size > 0);
    return top_element == -1;
}

int is_full(void)
{
    assert(stack_size > 0);
    return top_element == stack_size - 1;
}

链式堆栈

/*
 * 一个用链表实现的堆栈, 这个堆栈没有长度限制
 */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include "stack.h"

#define FALSE 0

typedef struct STACK_NODE {
    STACK_TYPE   value;
    struct STACK_NODE *next;
} StackNode;

static StackNode *stack;

void create_stack(size_t size)
{
}

void destroy_stack(void)
{
    while (!is_empty())
        pop();
}

void push(STACK_TYPE value)
{
    StackNode *new_node;
    new_node = malloc(sizeof(StackNode));
    assert(new_node != NULL);
    new_node->value = value;
    new_node->next = stack;
    stack = new_node;
}

void
pop(void)
{
    StackNode *first_node;
    assert(!is_empty());
    first_node = stack;
    stack = first_node->next;
    free(first_node);
}

STACK_TYPE top(void)
{
    assert(!is_empty());
    return stack->value;
}

int
is_empty(void)
{
    return stack == NULL;
}

int is_full(void)
{
    return FALSE;
}

队列

队列和堆栈的顺序不同: 队列是一种先进先出(First-In First-OUT, FIFO)的结构.

队列接口

#include <stdlib.h>

#define QUEUE_TYPE int

void create_queue(size_t size);
void destroy_queue(void);

void insert(QUEUE_TYPE value);
void delete(void);
QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);

静态数组实现

#include <stdio.h>
#include <assert.h>
#include "queue.h"

#define QUEUE_SIZE
#define ARRAY_SIZE (QUEUE_SIZE + 1)

static QUEUE_TYPE queue[ARRAY_SIZE];
static size_t front = 1;
static size_t rear = 0;

void
insert(QUEUE_TYPE value)
{
    assert(!is_full());
    rear = (rear + 1) % ARRAY_SIZE;
    queue[rear] = value;
}

void delete(void)
{
    assert(!is_empty());
    front = (front + 1) % ARRAY_SIZE;
}

QUEUE_TYPE first(void)
{
    assert(!is_empty());
    return queue[front];
}

int is_empty(void)
{
    return (rear + 1) % ARRAY_SIZE == front;
}

int is_full(void)
{
    return (rear + 1)  % ARRAY_SIZE == front;
}

树

树的种类繁多, 这里介绍一种非常有用的数: 二叉搜索树(binary search tree).

树是一种数据结构, 它要么为空, 要么具有一个值并具有零个或多个孩子, 每个孩子本身也是树. 树的高度并没有内在的限制.

二叉树(binary tree)是树的一种特殊形式, 它的每个节点至多有两个子树.

二叉搜索树具有一个额外属性:每个节点的值都币它的左子树的所有节点的值都要打, 但币它右梓树的所有节点的值都要小. 树中不存在相同的节点. 这些属性使二叉搜索数称为一种用关键值查找数据的优秀工具.

二叉搜索树基本算法

如果数为空:
        把心智作为根节点插入
    否则:
        如果新值小于当前节点的值:
            把新值插入到当前节点的左子树
        否则:
            把新值插入到当前节点的右子树

由于递归在算法的尾部出现(尾部递归), 所以我们可以使用迭代更有效的实现这个算法

从二叉搜索树删除节点

删除节点必须将它的子树和父节点重新连接, 否则它们将会丢失.

在二叉搜索树中查找

基本算法

如果树为空:
        这个值不存在与树中
    否则:
        如果这个值和根节点值相等:
            成功找到这个值
        否则:
            如果这个值小于根节点的值:
                查找左子树
            否则:
                查找右子树

这个递归算法也属于尾部递归, 所以采用迭代方案来实现效率更高.

树的遍历

遍历树的节点有几种不懂的次序:

前序(pre-order)
中序(in-order)
后序(post-order)
层次遍历(breadth-first)

所有类型的遍历都是从树的根节点或你希望开始遍历子树的根节点开始

前序遍历检查节点的值, 然后递归地遍历左子树和右子树

中序遍历首先遍历左子树, 然后检查当前节点的值, 最后遍历右子树

后序遍历首先遍历右子树, 然后检查当前节点的值

层次遍历逐层的检查数的节点. 首先处理根节点, 接着是子树, 在接着是子树的子树.

二叉搜索树接口

/*
 * 二叉搜索树模块的接口
 */
#define TREE_TYPE int

void insert(TREE_TYPE value);
TREE_TYPE *find(TREE_TYPE value);
void pre_order_raverse(void(*callback)(TREE_TYPE value));

静态数组二叉搜索树

/*
 * 用数组表示数的关键是使用下标来寻找某个特定值的父节点和子节点
 *  节点 N 的父节点是 N/2
 *  节点 N 的左子树节点是 2N
 *  节点 N 的右子树的节点是 2N+1
 */
#include <assert.h>
#include <stdio.h>
#include "tree.h"

#define TREE_SIZE 100
#define ARRAY_SIZE (TREE_SIZE + 1)

static TREE_TYPE tree[ARRAY_SIZE];

static int left_child(int current)
{
    return current * 2;
}

static int right_child(int current)
{
    return current * 2 + 1;
}

void insert(TREE_TYPE value)
{
    int current;
    assert(value != 0);
    current = 1;
    while (tree[current] != 0){
        if (value < tree[current])
            current = left_child(current);
        else{
            assert(value != tree[current]);
            current = right_child(current);
        }
        assert(current < ARRAY_SIZE);
    }

    tree[current] = value;
}

TREE_TYPE *
find(TREE_TYPE value)
{
    int current;
    current = 1;
    while (current < ARRAY_SIZE && tree[current] != value){
        if (value < tree[current])
            current = left_child(current);
        else
            current = right_child(current);
        if (current < ARRAY_SIZE)
            return tree + current;
        else
            return 0;
    }
    return 0;
}

static void do_pre_order_traverse(int current,
        void (*callback)(TREE_TYPE value))
{
    if (current < ARRAY_SIZE && tree[current] != 0){
        callback(tree[current]);
        do_pre_order_traverse(left_child(current), callback);
        do_pre_order_traverse(right_child(current), callback);
    }
}

void pre_order_traverse(void(*callback)(TREE_TYPE value))
{
    do_pre_order_traverse(1, callback);
}

链式二叉搜索树

#include <assert.h>
#include <stdio.h>
#include <malloc.h>
#include "tree.h"

typedef struct TREE_NODE {
    TREE_TYPE value;
    struct TREE_NODE *left;
    struct TREE_NODE *right;
} TreeNode;

static TreeNode *tree;

void insert(TREE_TYPE value)
{
    TreeNode *current;
    TreeNode **link;

    link = &tree;

    while ((current = *link) != NULL){
        if (value < current->value)
            link = &current->left;
        else{
            assert(value != current->value);
            link = &current->right;
        }
    }
    current = malloc(sizeof(TreeNode));
    assert(current != NULL);
    current->value = value;
    current->left = NULL;
    current->right = NULL;
    *link = current;
}

TREE_TYPE *
find(TREE_TYPE value)
{
    TreeNode *current;

    current = tree;
    while (current != NULL && current->value != value){
        if (value < current->value)
            current = current->left;
        else
            current = current->right;
    }
    if (current != NULL)
        return &current->value;
    else
        return NULL;
}

static void
do_pre_order_traverse(TreeNode *current,
        void (*callback)(TREE_TYPE value))
{
    if (current != NULL){
        callback(current->value);
        do_pre_order_traverse(current->left, callback);
        do_pre_order_traverse(current->right, callback);
    }
}

void
pre_order_traverse(void(*callback)(TREE_TYPE value))
{
    do_pre_order_traverse(tree, callback);
}

实现改进

多个堆栈
多个类型