各种基本算法实现小结(二)—— 堆 栈
(均已测试通过)
==============================================================
栈——数组实现
测试环境: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();
}
运行结果:
参考推荐: