各种基本算法实现小结（二）—— 堆 栈

各种基本算法实现小结（二）—— 堆 栈

（均已测试通过）

==============================================================

栈——数组实现

测试环境：Win - TC

#include <stdio.h>
char stack[512];
int top=0;
void push(char c)
{
    stack[top]=c;
    top++;
}
char pop()
{
    top--;
    return stack[top];
}
int is_empty()
{
    return 0==top;
}
void main()
{
    push('1');
    push('2');
    push('3');
    push('4');
    push('5');
    while(!is_empty())
        putchar(pop());
    putchar('/n');
    getch();
}

运行结果：

====================================================

栈 ——数组实现2

测 试环境：Win - TC

#include <stdio.h>
#include <malloc.h>
/* typedef int DataType; */
#define DataType int
#define MAX 1024
typedef struct
{
    DataType data[MAX];
    int top;
}stack, *pstack;
pstack *init_stack()
{
    pstack ps;
    ps=(pstack)malloc(sizeof(stack));
    if(!ps)
    {
        printf("Error. fail malloc.../n");
        return NULL;
    }
    ps->top=-1;
    return ps;
}
int empty_stack(pstack ps)
{
    if(-1 == ps->top)
        return 1;
    else
        return 0;
}
int push(pstack ps, DataType data)
{
    if(ps->top == MAX-1)
    {
        printf("Stack is full.../n");
        return 0;
    }
    ps->top++;
    ps->data[ps->top]=data;
    return 1;
}
int pop(pstack ps, DataType *data)
{
    if(empty_stack(ps))
    {
        printf("Stack is empty.../n");
        return 0;
    }
    *data=ps->data[ps->top];
    ps->top--;
    return 1;
}
DataType top_stack(pstack ps)
{
    if(empty_stack(ps))
    {
        printf("Stack is empty.../n");
        return 0;
    }
    return ps->data[ps->top];
}
void display(pstack ps)
{
    int i;
    if(empty_stack(ps))
    {
        printf("Stack is empty.../n");
        return;
    }
    printf("printf the items of stack.../n");
    for(i=ps->top;i>-1;i--)
        printf("%4d", ps->data[i]);
    printf("/n/n");
}
void main()
{
    int i, num, data, *pdata;
    pstack ps;
    ps=init_stack();
    printf("Enter stack num:");
    scanf("%d", &num);
    for(i=0;i<num;i++)
    {
        scanf("%d", &data);
        push(ps, data);
    }
    display(ps);
    printf("Top is %d/n/n", top_stack(ps));
    for(i=0;i<num;i++)
    {
        pop(ps, pdata);
        printf("%3d", *pdata);
    }
    printf("/n/n");
    display(ps);
    getch();
}

运行结果：

====================================================

栈 ——链表实现

测 试环境：Win - TC

#include <stdio.h>
#include <malloc.h>
typedef char DataType;
struct _node
{
    DataType data;
    struct _node *next;
};
typedef struct _node node, *pstack;
pstack init_stack()
{
    pstack ps;
    ps=(pstack)malloc(sizeof(node));
    if(NULL == ps)
    {
        printf("Error. malloc is fail.../n");
        return NULL;
    }
    ps->data=-1;  /* base of stack: data=-1 and next=NULL */
    ps->next=NULL;
    return ps;
}
pstack push(pstack ps, DataType data)
{
    pstack ptop;
    ptop=(pstack)malloc(sizeof(node));
    if(NULL == ptop)
    {
        printf("Error. malloc is fail.../n");
        return NULL;
    }
    ptop->data=data;
    ptop->next=ps;   /* insert new item */
    ps=ptop;         /* move top */
    return ps;
}
pstack pop(pstack ps, DataType *data)
{
    if(ps->next == NULL)
    {
        printf("stack is empty.../n");
        return NULL;            
    }
    *data=ps->data;
    ps=ps->next;
    return ps;
}
DataType top_stack(pstack ps)
{
    if(ps->next == NULL)  /* if empty */
    {
        printf("stack is empty.../n");
        return -1;
    }
    return ps->data;
}
int len_stack(pstack ps)
{
    int len=0;
    pstack ptop=ps;
    while(ptop->next)
    {
        len++;
        ptop=ptop->next;
    }
    return len;
}
void display(pstack ps)
{
    pstack ptop;
    ptop=ps;
    while(ptop->next != NULL)
    {
        printf("%4c", ptop->data);
        ptop=ptop->next;
    }
    printf("/n/n");
}
void main()
{
    pstack ps;
    DataType *data=(DataType *)malloc(sizeof(DataType));
    ps=init_stack();
    ps=push(ps, 'a');
    ps=push(ps, 'b');
    ps=push(ps, 'c');
    ps=push(ps, 'd');
    ps=push(ps, 'e');
    display(ps);
    printf("len of stack is: %d/n/n", len_stack(ps));
    printf("top of stack is: %c/n/n", top_stack(ps));
    ps=pop(ps, data);
    printf("pop %c/n",*data);
    display(ps);
    ps=pop(ps, data);
    printf("pop %c/n",*data);
    display(ps);
    getch();
}

运行结果：

========================================================

堆 ——链表实现

测 试环境：Win - TC

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct _node
{
    int data;
    struct _node *next;
};
typedef struct _node node, *pnode;
struct _linkqueue
{
    pnode front;
    pnode rear;    
};
typedef struct _linkqueue linkqueue, *plinkqueue;
linkqueue init_queue()
{
    linkqueue lq;
    lq.front=lq.rear=(pnode)malloc(sizeof(node));
    if(NULL == lq.front)
    {
        printf("Error. malloc is fail.../n");
        exit(1);
    }
    lq.rear->data=lq.front->data=-1;
    lq.rear->next=lq.front->next=NULL;
    return lq;
}
int empty_queue(linkqueue lq)
{
    if(lq.front == lq.rear)
        return 1;
     else
        return 0;
}
linkqueue insert_item(linkqueue lq, int data)
{
    pnode pq;
    pq=(pnode)malloc(sizeof(node));
    if(pq == NULL)
    {
        printf("Error. malloc is fail.../n");
        exit(1);
    }
    pq->data=data;
    pq->next=lq.rear->next;
    lq.rear->next=pq;
    lq.rear=lq.rear->next;
    return lq;
}
linkqueue delete_item(linkqueue lq, int *data)
{
    if(empty_queue(lq))
    {
        printf("queue is empty.../n");
        exit(1);
    }
    *data=lq.front->data;
    lq.front=lq.front->next;
    return lq;
}
int len_queue(linkqueue lq)
{
    int len=0;
    while(lq.front)
    {
        len++;
        lq.front=lq.front->next;
    }
    return len;
}
void display(linkqueue lq)
{
    linkqueue p;
    p=lq;
    if(empty_queue(lq))
    {
        printf("queue is empty.../n");
        return;
    }
    while(p.front->next)
    {
        printf("%4d", p.front->data);
        p.front=p.front->next;
    }
    printf("%4d/n/n", p.front->data);
}
void main()
{
    int *data = (int *)malloc(sizeof(int));
    linkqueue lq;
    lq=init_queue();
    lq=insert_item(lq, 1);
    lq=insert_item(lq, 2);
    lq=insert_item(lq, 3);
    lq=insert_item(lq, 4);
    lq=insert_item(lq, 5);
    display(lq);
    printf("len of queue is: %d/n/n", len_queue(lq));
    lq=delete_item(lq, data);
    printf("delete %d/n", *data);
    display(lq);
    lq=delete_item(lq, data);
    printf("delete %d/n", *data);
    display(lq);
    getch();
}

运行结果：