堆栈:
//// Created by mao on 16-9-16.//#ifndef UNTITLED_STACK_H#define UNTITLED_STACK_H#define TRUE 1#define FALSE 0typedef int STACK_TYPE;typedef struct stack{ STACK_TYPE value; struct stack *next;} STACK;void create_stack();void destory_stack();void push(STACK_TYPE value);STACK_TYPE pop();int isEmpty();#endif //UNTITLED_STACK_H stack.h
//// Created by mao on 16-9-16.//#include#include "stack.h"static STACK *stack;void create_stack(){ stack = (STACK *)malloc(sizeof(STACK)); stack -> next = NULL;}void destory_stack(){ STACK *pStack; while((pStack = stack -> next) != NULL){ free(stack); stack = pStack; }}void push(STACK_TYPE value){ STACK *new = (STACK *)malloc(sizeof(STACK)); new -> next = stack; new -> value = value; stack = new;}STACK_TYPE pop(){ STACK_TYPE value = stack -> value; STACK *pStack = stack; stack = stack -> next; free(pStack); return value;}int isEmpty(){ return stack -> next == NULL ? TRUE : FALSE;}
stack.c
#include#include "stack.h"int main(){ //堆栈 create_stack(); push(10); push(20); push(30); pop(); push(22); while(isEmpty() == FALSE){ printf("%d \t", pop()); }}
main.c
运行:
队列:
当使用数组作为队列时，如果只是一端插入一端弹出，那么当尾部没有空间时，便无法插入元素，一种解决方法是使用“环绕”数组，新元素可以存储到以前删除元素所留出来的空间中，这种方法称为循环数组。
循环数组有个问题，当队列为空，或者为满时，首位的下标是一样的，无法判断出此时队列的状态，所以在队列的rear后加一个空余的不使用的位置，用来判断队列的状态是满队列，还是空队列。
当为满队列时:
(rear + 2) % QUEUE_SIZE = front
当为空队列时：
(rear + 1) % QUEUE_SIZE = front
队列实现:
//// Created by mao on 16-9-16.//#ifndef UNTITLED_QUEUE_H#define UNTITLED_QUEUE_H#define TRUE 1#define FALSE 0#define QUEUE_SIZE 100#define ARRAY_SIZE (QUEUE_SIZE + 1)typedef int QUEUE_TYPE;static QUEUE_TYPE queue[ARRAY_SIZE];static int front = 1;static int rear = 0;void Q_delete();QUEUE_TYPE Q_first();void Q_insert(QUEUE_TYPE value);int Q_isEmpty();int Q_isFull();#endif //UNTITLED_QUEUE_H
queue.h
//// Created by mao on 16-9-16.//#include "queue.h"#includevoid Q_delete(){ assert(Q_isEmpty() == FALSE); front = (front + 1) % QUEUE_SIZE; front = (front) % QUEUE_SIZE;}QUEUE_TYPE Q_first(){ assert(Q_isEmpty() == FALSE); return queue[front];}//队列插入数据,rear++void Q_insert(QUEUE_TYPE value){ assert(Q_isFull() == FALSE); rear = (rear + 1) % QUEUE_SIZE; queue[(rear) % QUEUE_SIZE] = value;}int Q_isEmpty(){ return (rear + 1) % QUEUE_SIZE == front ? TRUE: FALSE;}int Q_isFull(){ return (rear + 2) % QUEUE_SIZE == front ? TRUE : FALSE;}
queue.c
#include#include "queue.h"int main(){ //插入队列 Q_insert(10); Q_insert(12); Q_delete(); Q_insert(22); Q_insert(30); printf("%d\n", Q_first()); Q_delete(); printf("%d\n", Q_first()); Q_delete(); printf("%d\n", Q_first()); Q_delete(); return 1;}
main.c
运行:
二叉树:
#ifndef UNTITLED_BINARYTREE_H#define UNTITLED_BINARYTREE_H#include#define TREE_TYPE int#define ARRAY_SIZE 100#define TREE_SIZE (ARRAY_SIZE + 1)TREE_TYPE TREE[TREE_SIZE] = {0};static unsigned int leftChild(unsigned int current){ return current * 2;}static unsigned int rightChild(unsigned int current){ return current * 2 + 1;}void insert(TREE_TYPE value){ unsigned int current = 1; while(TREE[current] != 0){ if(value < TREE[current]){ current = leftChild(current); }else{ assert(TREE[current] != value); current = rightChild(current); } assert(current < TREE_SIZE); } TREE[current] = value;}TREE_TYPE *find(TREE_TYPE value){ unsigned int current = 1; while (current < TREE_SIZE && TREE[current] != value){ if(value < TREE[current]){ current = leftChild(current); }else if(value > TREE[current]){ current = rightChild(current); } } if(current < TREE_SIZE){ return TREE + current; }else{ return 0; }}//根据指针计算数组下标static unsigned long getIndex(TREE_TYPE *ptr){ assert(ptr >= TREE || ptr <= TREE + TREE_SIZE); return ptr - TREE;}//内置先遍历接口void pre_order_traverse(unsigned int current, void(*callback)(TREE_TYPE value)){ if(current < ARRAY_SIZE && TREE[current] != 0){ callback(TREE[current]); pre_order_traverse(leftChild(current), callback); pre_order_traverse(rightChild(current), callback); }}//先序遍历void do_pre_traverse(void(*callback)(TREE_TYPE value)){ pre_order_traverse(1, callback);}//中序遍历void mid_order_traverse(unsigned int current, void(*callback)(TREE_TYPE value)){ if(current < ARRAY_SIZE && TREE[current] != 0){ mid_order_traverse(leftChild(current), callback); callback(TREE[current]); mid_order_traverse(rightChild(current), callback); }}void do_mid_order_traverse(void(*callback)(TREE_TYPE value)){ mid_order_traverse(1, callback);}//后续遍历void after_order_traverse(unsigned int current, void(*callback)(TREE_TYPE value)){ if(current < ARRAY_SIZE && TREE[current] != 0){ after_order_traverse(leftChild(current), callback); after_order_traverse(rightChild(current), callback); callback(TREE[current]); }}void do_after_order_traverse(void(*callback)(TREE_TYPE value)){ after_order_traverse(1, callback);}void print_tree(TREE_TYPE value){ printf("%d\t", value);}#endif //UNTITLED_BINARYTREE_H
BinaryTree.h
#include#include "BinaryTree.h"int main(){ insert(20); insert(12); insert(5); insert(9); insert(16); insert(17); insert(25); insert(28); insert(26); insert(29); do_pre_traverse(print_tree); printf("\n"); do_mid_order_traverse(print_tree); printf("\n"); do_after_order_traverse(print_tree); return 1;}
main.c
运行：
数组形式存放二叉树，会导致内存空间的浪费，尤其是非对称的二叉树，会造成大量的数组空间闲置。通过链式二叉树可以解决数组不充分的问题
#include#include #include typedef int TREE_TYPE;typedef struct TREE_NODE { TREE_TYPE value; struct TREE_NODE *leftPtr; struct TREE_NODE *rightPtr;} TREE_NODE;//指向树的根节点的指针TREE_NODE *root;//创建根节点void createTree(TREE_TYPE value){ root = (TREE_NODE *) malloc(sizeof(TREE_NODE)); root -> leftPtr = NULL; root -> rightPtr = NULL; root -> value = value;}TREE_NODE * getRoot(){ return root;}//插入节点void insertNode(TREE_TYPE value){ TREE_NODE *current = root; //pos为待插入节点的父节点 TREE_NODE *parent = root; while(current != NULL){ //保存父节点信息 parent = current; if(current -> value < value){ current = current -> rightPtr; }else if(current -> value > value){ current = current -> leftPtr; }else{ //节点已存在 return ; } } TREE_NODE *node = (TREE_NODE *) malloc(sizeof(TREE_NODE)); assert(node != NULL); node -> leftPtr = NULL; node -> rightPtr = NULL; node -> value = value; //根据值得大小判断，node应该放在左节点还是右节点 if(parent -> value > value){ parent -> leftPtr = node; }else{ parent -> rightPtr = node; }}TREE_NODE * findNode(TREE_TYPE value){ TREE_NODE *current = root; while(current != NULL && current -> value != value){ if( current -> value > value){ current = current -> leftPtr; }else{ current = current -> rightPtr; } } return current;}void printNode(TREE_NODE * node){ printf("%d\t", node -> value);}void pre_order_traverse(TREE_NODE * current){ if(current != NULL){ printNode(current); pre_order_traverse(current -> leftPtr); pre_order_traverse(current -> rightPtr); }}void mid_order_traverse(TREE_NODE * current){ if(current != NULL){ mid_order_traverse(current -> leftPtr); printNode(current); mid_order_traverse(current -> rightPtr); }}void after_order_traverse(TREE_NODE * current){ if(current != NULL){ after_order_traverse(current -> leftPtr); after_order_traverse(current -> rightPtr); printNode(current); }}
BinaryTree.h
#include#include "BinaryTree.h"int main(){ createTree(20); insertNode(12); insertNode(5); insertNode(9); insertNode(16); insertNode(17); insertNode(25); insertNode(28); insertNode(26); insertNode(29); pre_order_traverse(root); printf("\n"); mid_order_traverse(root); printf("\n"); after_order_traverse(root); return 1;}
BinaryTree.c
运行:
