栈的顺序存储结构（C语言版）

我在准备的过程中，发现很多笔试题和面试的时候，都是用C语言来描述的，而且现在我的一些没有Java基础的师弟正在开始学习数据结构，所以为了方便他们也方便自己还是下定决心用C语言进行数据结构的代码实现，毕竟所有的语言都是相通的，学起来并不难，更何况我大一的时候学过呢，所以在此向一些希望看到我的Java版本实现的朋友道个歉。

 

栈的定义：限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈成为空栈，栈又称为先进后出的线性表。

 

有些初学者看不懂什么叫做顺序存储结构和链式存储结构，下面就补充一下他的定义

顺序存储结构 的定义：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的

 

链式存储结构 的定义 ：是把数据元素存放在任意的单元里，这组存储单元可以是连续的，也可以是不连续的

 

下面进行给出这个基本的代码实现，因为C语言是面向过程语言，所以我们就无法像之前线性表那样进行类的封装了，但是我们可以借鉴面向对象的思想，在下面的代码中，定义并且声明一个结构体，就相当于封装一个类，然后进行各种方法的封装，在main方法中我们就可以直接调用了。

/*
	这个是栈的线性存储结构 
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#define ERROR 0
#define OK 1
#define MAXSIZE 20
#define  random(x) (rand()%x)

typedef int SElemType, Status;                              

typedef struct {	//定义一个结构体栈并且用字符串SqStack来代表该结构体类型 
	SElemType data[MAXSIZE] ;
	int top;
} SqStack;

//在栈中插入元素 e 
Status push(SqStack *s, SElemType e) {
	if(s->top == MAXSIZE - 1) {
		printf("栈已满");
		return ERROR; 
	}
	s->top++;
	s->data[s->top] = e;
	return OK;
} 

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR 
Status pop(SqStack *s, SElemType *e) {
	if(s->top == -1) {
		printf("栈为空");
		return ERROR;
	}
	*e = s->data[s->top];
	s->top--;
}

//栈元素展示 
void display(SqStack s) {
	int i =0;
	for(i; i <= s.top; i++) {
		printf("%d ", s.data[i]);
	}
	printf("\n");
}

int main() {
	srand((int)time(NULL));	//用当前的时间作为随机数种子，这样就能保证每次运行时都能取到不同的随机数序列

	SqStack s;
	s.top = -1;
	int i = 0;
	
	for(i; i < random(MAXSIZE); i++) {	//创建一个原始栈并为其赋值 
		s.data[i] = random(MAXSIZE);
		s.top++;	
	}
	printf("原始栈为  ：");
	display(s);
	
	printf("插入后栈为：");
	push(&s, random(MAXSIZE));
	display(s);
	
	printf("弹出后栈为："); 
	int e;
	pop(&s,&e); 
	display(s);
	printf("弹出元素为：%d\n", e); 
}

 同样，我的main方法中的数据都是通过产生随机数来产生的，只要多运行几次，同样可以完善的测试，当然如果大家觉得手动多次运行不方便对比，也可以进行for循环。下面是运行结果之一：

原始栈为  ：5
插入后栈为：5 0
弹出后栈为：5
弹出元素为：0
请按任意键继续. . .

 

评论

1 楼 chenchuangfeng 2013-02-28  

不错不错