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

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

（均已测试通过）

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

栈——数组实现

测试环境：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(); }

运行结果：