C指针编程之道（三）- 数据结构中指针的应用

# include <stdio.h>

# define CIRQUEUE_LENGTH 8

typedef struct {
    int font; //对头标识
    int rear; //队尾标识
    int counter; //计数器
    int data[CIRQUEUE_LENGTH]; //队列数据
} cirqueue;

int main() {
    cirqueue *queue;
    void init_queue(cirqueue *);
    int is_queue_full(cirqueue *);
    int is_queue_empty(cirqueue *);
    int in_queue(cirqueue *, int);
    int out_queue(cirqueue *, int *);
    void traverse_queue(cirqueue *);
    
    //初始化
    init_queue(queue);
    
    //入队
    in_queue(queue, 1);
    in_queue(queue, 2);
    in_queue(queue, 3);
    traverse_queue(queue);
    
    //出队
    int out_data = 0;
    out_queue(queue, &out_data);
    printf("out_data=%d\n", out_data);
    out_queue(queue, &out_data);
    printf("out_data=%d\n", out_data);
    out_queue(queue, &out_data);
    printf("out_data=%d\n", out_data);
    traverse_queue(queue);
    
    return 0;
}

//队列初始化
void init_queue(cirqueue *q){
    q->font = 0;
    q->rear = 0;
    q->counter = 0;
}

//判断队满
int is_queue_full(cirqueue *q) {
    return q->counter==CIRQUEUE_LENGTH;
}

//判断队空
int is_queue_empty(cirqueue *q) {
    return q->counter==0;
}

//入队
int in_queue(cirqueue *q, int data) {
    if (is_queue_full(q)) {
        printf("栈已满！\n");
        return 0;
    } else {
        q->data[q->rear] = data;
        q->counter++;
        q->rear = (q->rear+1) % CIRQUEUE_LENGTH;
        return 1;
    }
}

//出队
int out_queue(cirqueue *q, int *pdata) {
    if (is_queue_empty(q)) {
        return 0;
    } else {
        *pdata = q->data[q->font];
        q->counter--;
        q->font = (q->font+1) % CIRQUEUE_LENGTH;
        return 1;
    }
}

//遍历队列
void traverse_queue(cirqueue *q) {
    if (is_queue_empty(q)) {
        printf("栈为空！\n");
    } else if (is_queue_full(q) || q->font > q->rear) {
        for (int i=q->font; i<q->rear+CIRQUEUE_LENGTH; i++) {
            printf("%d ", q->data[i%CIRQUEUE_LENGTH]);
        }
        printf("\n");
    } else if (q->font < q->rear) {
        for (int i=q->font; i<q->rear; i++) {
            printf("%d ", q->data[i]);
        }
        printf("\n");
    }
}

# include <stdio.h>

# define STACK_LENGTH 8

typedef struct {
    int top;
    int data[STACK_LENGTH];
} stack;

int main() {
    stack *pstack;
    void init_stack(stack *);
    int is_stack_empty(stack *);
    int is_stack_full(stack *);
    int push_stack(stack *, int);
    int pop_stack(stack *, int *);
    void print_pop_stack(stack *, int *);
    
    //初始化
    init_stack(pstack);
    
    //入栈
    push_stack(pstack, 1);
    push_stack(pstack, 2);
    push_stack(pstack, 3);
    
    //出栈
    int data = 0;
    print_pop_stack(pstack, &data);
    print_pop_stack(pstack, &data);
    print_pop_stack(pstack, &data);
    
    return 0;
}

//栈的初始化
void init_stack(stack *pstack) {
    pstack->top = 0; //栈顶位置=栈底位置
}

//栈空判断
int is_stack_empty(stack *pstack) {
    return pstack->top==0;
}

//栈满判断
int is_stack_full(stack *pstack) {
    return pstack->top==STACK_LENGTH;
}

//进栈
int push_stack(stack *pstack, int data){
    if (is_stack_full(pstack)) {
        printf("堆栈已满！\n");
        return 0;
    } else {
        pstack->data[pstack->top] = data;
        pstack->top++;
        return 1;
    }
}

//出栈
int pop_stack(stack *pstack, int *data) {
    if (is_stack_empty(pstack)) {
        printf("堆栈为空！\n");
        return 0;
    } else {
        pstack->top--;
        *data = pstack->data[pstack->top];
        return 1;
    }
}

//打印出栈
void print_pop_stack(stack *pstack, int *data) {
    int status = pop_stack(pstack, data);
    if (status) {
        printf("%d\n", *data);
    }
}

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

typedef struct tree_node {
    char data; //值域
    struct tree_node *lchild, *rchild; //左右指针域
} Tnode;

Tnode * create_tree(Tnode *);
void pre_traverse_tree(Tnode *);
void mid_traverse_tree(Tnode *);
void post_traverse_tree(Tnode *);

int main() {
    printf("please input tree data:\n");
    Tnode * tree;
    tree = create_tree(tree);
    
    printf("\n前序遍历:\n");
    pre_traverse_tree(tree);
    
    printf("\n中序遍历:\n");
    mid_traverse_tree(tree);
    
    printf("\n后序遍历:\n");
    post_traverse_tree(tree);
    
    printf("\n");
    return 0;
}

//递归创建树
Tnode * create_tree(Tnode *tnode) {
    char ch;
    ch = getchar();
    
    if (ch == '*') {
        tnode = NULL;
    } else {
        tnode = (Tnode *) malloc(sizeof(Tnode));
        tnode->data = ch;
        tnode->lchild = create_tree(tnode->lchild);
        tnode->rchild = create_tree(tnode->rchild);
    }
    return tnode;
}

//遍历一般分为三种：前序遍历、中序遍历、后序遍历，三种遍历均是以根节点为核心命名的
//前序遍历：根节点--->左子树--->右子树
//中序遍历：左子树--->根节点--->右子树
//后序遍历：左子树--->右子树--->根节点

void pre_traverse_tree(Tnode *tnode) { //前序遍历
    if (tnode) {
        printf(" %c\t", tnode->data);
        pre_traverse_tree(tnode->lchild);
        pre_traverse_tree(tnode->rchild);
    }
}

void mid_traverse_tree(Tnode *tnode) { //中序遍历
    if (tnode) {
        mid_traverse_tree(tnode->lchild);
        printf(" %c\t", tnode->data);
        mid_traverse_tree(tnode->rchild);
    }
}

void post_traverse_tree(Tnode *tnode) { //后序遍历
    if (tnode) {
        post_traverse_tree(tnode->lchild);
        post_traverse_tree(tnode->rchild);
        printf(" %c\t", tnode->data);
    }
}

/*
    -------------------
             a
      b             c

    d   e         f   g
      
           h
      
        j
    -------------------

 运行结果：
 please input tree data:
 abd**e*hj***cf**g**
 
 前序遍历:
 a	 b	 d	 e	 h	 j	 c	 f	 g
 中序遍历:
 d	 b	 e	 j	 h	 a	 f	 c	 g
 后序遍历:
 d	 j	 h	 e	 b	 f	 g	 c	 a
 */