1.实现栈的数据结构

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 20
#define INCREMENT_SIZE 5

typedef int SElemType;  
typedef int Status;

/*
 * 存储结构
 */
typedef struct  
{
    SElemType *base;    //栈尾指针
    SElemType *top;     //栈顶指针
    int size;           //栈的大小
}SqStack;

/*
 * 初始化栈
 */
Status InitStack(SqStack *S)  
{
    S->base = (SElemType*) malloc(INIT_SIZE * sizeof(SElemType));
    if (!S->base)
    {
        exit(OVERFLOW);
    }
    S->top = S->base;
    S->size = INIT_SIZE;
    return OK;
}

/*
 * 销毁栈
 */
Status DestroyStack(SqStack *S)  
{
    free(S->base);
    S->base = NULL;
    S->top = NULL;
    S->size = 0;
    return OK;
}

/*
 * 清空栈
 */
Status ClearStack(SqStack *S)  
{
    S->top = S->base;
    return OK;
}

/*
 * 判断栈是否为空
 */
Status IsEmpty(SqStack S)  
{
    if (S.top == S.base)
    {
        return TRUE;
    }
    else
        return FALSE;
}

/*
 * 获取栈的长度
 */
int GetLength(SqStack S)  
{
    return (S.top - S.base) / sizeof(SElemType);
}


/*
 * 获取栈顶元素
 */
Status GetTop(SqStack S, SElemType *e)  
{
    if (S.top > S.base)
    {
        *e = *(S.top - sizeof(SElemType));
        return OK;
    }
    else
    {
        return ERROR;
    }
}

/*
 * 压栈
 */
Status Push(SqStack *S, SElemType e)  
{
    if ((S->top - S->base) / sizeof(SElemType) >= S->size)
    {
        S->base = (SElemType*) realloc(S->base, (S->size + INCREMENT_SIZE) * sizeof(SElemType));
        if (!S->base)
        {
            exit(OVERFLOW);
        }
        S->top = S->base + S->size * sizeof(SElemType);
        S->size += INCREMENT_SIZE;
    }
    *S->top = e;
    S->top += sizeof(SElemType);
    return OK;
}

/*
 * 退栈
 */
Status Pop(SqStack *S, SElemType *e)  
{
    if (S->top == S->base)
    {
        return ERROR;
    }
    S->top -= sizeof(SElemType);
    *e = *S->top;
    return OK;
}

/*
 * 访问元素
 */
void visit(SElemType e)  
{
    printf("%d ", e);
}

/*
 * 遍历栈
 */
Status TraverseStack(SqStack S, void (*visit)(SElemType))  
{
    while (S.top > S.base)
    {
        visit(*S.base);
        S.base += sizeof(SElemType);
    }
    return OK;
}

int main()  
{
    SqStack S;
    if (InitStack(&S))
    {
        SElemType e;
        int i;

        printf("init_success\n");

        if (IsEmpty(S))
        {
            printf("Stack is empty\n");
        }

        for (i = 0; i < 10; i++)
        {
            Push(&S, i);
        }

        GetTop(S, &e);
        printf("The first element is %d\n", e);

        printf("length is %d\n", GetLength(S));

        Pop(&S, &e);
        printf("Pop element is %d\n", e);

        TraverseStack(S, *visit);

        if (DestroyStack(&S))
        {
            printf("\ndestroy_success\n");
        }
    }
}

2. 实现队列数据结构

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int QElemType;  
typedef int Status;

/*
 * 存储结构
 */
typedef struct QNode  
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct  
{
    QueuePtr front; //队头指针
    QueuePtr rear;  //队尾指针
}LinkQueue;

/*
 * 初始化队列
 */
Status InitQueue(LinkQueue *Q)  
{
    Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q->front)
    {
        exit(OVERFLOW);
    }
    Q->front->next = NULL;
    return OK;
}

/*
 * 销毁队列
 */
Status DestroyQueue(LinkQueue *Q)  
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

/*
 * 清空队列
 */
Status ClearQueue(LinkQueue *Q)  
{
    DestroyQueue(Q);
    InitQueue(Q);
}

/*
 * 判断队列是否为空
 */
Status IsEmpty(LinkQueue Q)  
{
    if (Q.front->next == NULL)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

/*
 * 获取队列的长度
 */
int GetLength(LinkQueue Q)  
{
    int i = 0;
    QueuePtr p = Q.front;
    while (Q.rear != p)
    {
        i++;
        p = p->next;
    }
    return i;
}

/*
 * 获取队头元素
 */
Status GetHead(LinkQueue Q, QElemType *e)  
{
    QueuePtr p;
    if (Q.front == Q.rear)
    {
        return ERROR;
    }
    p = Q.front->next;
    *e = p->data;
    return OK;
}

/*
 * 入队
 */
Status EnQueue(LinkQueue *Q, QElemType e)  
{
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p)
    {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

/*
 * 出队
 */
Status DeQueue(LinkQueue *Q, QElemType *e)  
{
    QueuePtr p;
    if (Q->front == Q->rear)
    {
        return ERROR;
    }
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)
    {
        Q->rear = Q->front;
    }
    free(p);
    return OK;
}

/*
 * 访问元素
 */
void visit(QElemType e)  
{
    printf("%d ", e);
}

/*
 * 遍历队列
 */
Status TraverseQueue(LinkQueue Q, void (*visit)(QElemType))  
{
    QueuePtr p = Q.front->next;
    while (p)
    {
        visit(p->data);
        p = p->next;
    }
    return OK;
}

int main()  
{
    LinkQueue Q;
    if (InitQueue(&Q))
    {
        QElemType e;
        int i;

        printf("init_success\n");

        if (IsEmpty(Q))
        {
            printf("queue is empty\n");
        }

        for (i = 0; i < 10; i++)
        {
            EnQueue(&Q, i);
        }

        GetHead(Q, &e);
        printf("The first element is %d\n", e);

        printf("length is %d\n", GetLength(Q));

        DeQueue(&Q, &e);
        printf("delete element is %d\n", e);

        TraverseQueue(Q, *visit);

        if (DestroyQueue(&Q))
        {
            printf("\ndestroy_success\n");
        }
    }
}

3. 实现树的数据结构

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

#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define OK 1
#define ERROR 0

typedef int Status;  
typedef int TElemType;

/*
 * 存储结构
 */
typedef struct BiTNode  
{
    TElemType data; //数据
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*
 * 创建二叉树,输入0表示创建空树
 */
Status CreateBiTree(BiTree *T)  
{
    TElemType e;
    scanf("%d", &e);
    if (e == 0)
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if (!T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = e;
        CreateBiTree(&(*T)->lchild);    //创建左子树
        CreateBiTree(&(*T)->rchild);    //创建右子树
    }
    return OK;
}

/*
 * 访问元素
 */
void visit(TElemType e)  
{
    printf("%d ", e);
}

/*
 * 先序遍历二叉树
 */
Status PreOrderTraverse(BiTree T, void (*visit)(TElemType))  
{
    if (T)
    {
        visit(T->data);
        PreOrderTraverse(T->lchild, visit);
        PreOrderTraverse(T->rchild, visit);
    }
}

/*
 * 中序遍历二叉树
 */
Status InOrderTraverse(BiTree T, void (*visit)(TElemType))  
{
    if (T)
    {
        InOrderTraverse(T->lchild, visit);
        visit(T->data);
        InOrderTraverse(T->rchild, visit);
    }
}

/*
 * 后序遍历二叉树
 */
Status PostOrderTraverse(BiTree T, void (*visit)(TElemType))  
{
    if (T)
    {
        PostOrderTraverse(T->lchild, visit);
        PostOrderTraverse(T->rchild, visit);
        visit(T->data);
    }
}

int main()  
{
    BiTree T;
    printf("创建树，输入0为空树：\n");
    CreateBiTree(&T);
    printf("先序遍历：");
    PreOrderTraverse(T, *visit);
    printf("\n中序遍历：");
    InOrderTraverse(T, *visit);
    printf("\n后序遍历：");
    PostOrderTraverse(T, *visit);
    printf("\n");
}