Linux下学C语言——第二十一节 数据结构

数据结构"/>

Linux下学C语言——第二十一节 数据结构

顺序栈的实现：

sqstack.h

#ifndef SQSTACK_H__
#define SQSTACK_H__#define MAXSIZE 5typedef int datatype;typedef struct node_st
{datatype data[MAXSIZE];int top;}sqstack;sqstack *st_create(void);int st_push(sqstack *,datatype *);int st_pop(sqstack * ,datatype *);int st_top(sqstack * ,datatype *);int st_isempty(sqstack *);void  st_travel(sqstack *);void st_destroy(sqstack *);#endif

sqstack.c

#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h"sqstack *st_create(void)
{sqstack *st;st = malloc (sizeof(*st));if(st == NULL)return NULL;st ->top = -1;return st;
}int st_push(sqstack *st,datatype *data)
{if(st->top == (MAXSIZE -1))return -1;st ->data[++st->top]= *data;return 0;
}int st_pop(sqstack *st ,datatype *data)
{if(st_isempty(st))return -1;*data = st->data[st->top--];return 0;
}int st_top(sqstack *st,datatype *data)
{if(st_isempty(st))return -1;*data = st->data[st->top];return 0;
}int st_isempty(sqstack *st)
{return (st -> top == -1);
}void st_travel(sqstack *st)
{int i;if(st_isempty(st))return ;for(i = 0 ;i<= st ->top ; i++)printf("%d ",st->data[i]);printf("\n");
}void st_destroy(sqstack *st)
{free(st);
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h"int main()
{int i, ret;datatype arr[] = {19,23,45,67};sqstack *st;st = st_create();if(st == NULL)exit(1);for(i = 0;i<sizeof(arr)/sizeof(*arr);i++){// printf("arr[%d]===%d\n",i,arr[i]);st_push(st,&arr[i]);// printf("st->top===%d\n",st->data[i]);}st_travel(st);datatype tmp;while(st_pop(st,&tmp)== 0){printf("POP:%d\n",tmp);}
/*datatype tmp = 1;ret = st_push(st,&tmp);if(ret != 0)printf("st_push failed\n");*/  st_travel(st);st_destroy(st);exit(0);
}

 makefile:

all:main

main:sqstack.o main.o
    $(CC) $^ -o $@

clean:
    rm main  *.o -rf

执行：

arr[0]===19
st->top===19
arr[1]===23
st->top===23
arr[2]===45
st->top===45
arr[3]===67
st->top===67
19 23 45 67 
POP:67
POP:45
POP:23
POP:19

 链表栈：使用写好的循环链表

stack.h:

#ifndef STACK_H__
#define STACK_H__
#include "llist.h"typedef llist stack;stack *stack_create(int );int stack_push(stack *,const void *data);int stack_pop(stack *,void *data);void stack_destroy(stack *);#endif 

stack.c:

#include <stdio.h>
#include <stdlib.h>#include "stack.h"stack *stack_create(int init)\
{return llist_create(init);
}int stack_push(stack *ptr,const void *data)
{return llist_insert(ptr,data,FORWARD);
}static int always_match(const void *p1,const void *p2)
{return 0;
}
int stack_pop(stack *ptr,void *data)
{return llist_fetch(ptr,(void *)0,always_match,data);
}void stack_destroy(stack *ptr)
{llist_destroy(ptr);
}

main.c

#include <stdio.h>
#include <stdlib.h>#include "stack.h"#define NAME 32
struct score_st
{int id;char name[NAME];int math;int chinese;};static void print_s(void *record)
{struct score_st *r = record;printf("%d %s %d %d\n",r->id ,r->name,r->math,r->chinese);
}int main()
{stack *st;struct score_st tmp;int ret,i;st = stack_create(sizeof(struct score_st));if(st == NULL)exit(1);for(i = 0;i<7;i++){tmp.id = i;snprintf(tmp.name,NAME ,"std%d",i);tmp.math = rand () %100;tmp.chinese = rand () %100;if(stack_push(st,&tmp))exit(1);}while(1){ret = stack_pop(st ,&tmp);if(ret == -1)break;print_s(&tmp);}stack_destroy(st);exit(0);
}

 执行:

[tom@CentOS7 list]$ ./main
6 std6 90 59
5 std5 62 27
4 std4 49 21
3 std3 86 92
2 std2 93 35
1 std1 77 15
0 std0 83 86