栈的C实现(stack)
rows="2" cols="20" id="ctl00_ctl00_cphContent_cphDoc_EntryEditor1_richTextEditor" class="mceEditor" style="height:450px;width:100%;">
栈是数据结构中最基础也是最经典的数据结构,无论在应用还是操作系统中均可以看到其身影。栈是一种特殊的
线性表,即限制在表的一端进行插入、删除运算。通常插入、删除的一端称为栈顶,另一端称为栈底,当栈中没
有数据时称为空栈。
栈中数据的插入和删除只在栈顶进行,所以栈中的数据总是后进先出(LIFO)。
栈上基本的运算有五种:
* SETNULL(s) 置栈s为空栈。
* EMPTY(s) 判断栈s是否为空。
* PUSH(s,x) 往栈s压入数据x。
* POP(s) 若栈s不为空,则弹出栈顶数据。
* TOP(s) 若栈s不为空,取栈顶数据。
下面,给出栈的最基本的实现代码:
#include <assert.h>
#define STACK_SIZE (1 << 6)
static stack_t stack[STACK_SIZE];
static int top = -1;
static int stack_full(void)
{
return (top == STACK_SIZE - 1);
}
static int stack_empty(void)
{
return (top == -1);
}
void stack_push(stack_t val)
{
assert(!stack_full());
stack[++top] = val;
}
stack_t stack_pop(void)
{
assert(!stack_empty());
--top;
return stack[top + 1];
}
stack_t stack_top(void)
{
assert(!stack_empty());
return stack[top];
}
从上面的实现代码可以看出,实现栈的基本操作的代码是非常简单的,不过二三十行的代码量。如果在实际的代
码开发中,根据应用的特定数据类型实现上述几个操作接口也是很容易的,但存在几个明显的缺陷:
* 代码不具备复用性。
* 采用静态数组存储,栈空间需在编译前确定。
* 不支持存储多种数据类型,需要修改stack_t定义。
为此,我们重新实现了如下的一套结构,来满足上面的这些复用性特征需求,代码如下:
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct _stack {
int top;
size_t len;
size_t size;
char *base;
};
typedef unsigned int hdl;
typedef struct _stack stack;
hdl stack_create(size_t size, size_t len)
{
stack *vp = (stack*)malloc(sizeof(stack));
if (vp == NULL) {
return 0;
}
assert(size > 0 && len > 0);
vp->base = (char*)malloc(size *
相关文档:
#include <stdlib.h>
#include<stdio.h>
#include<time.h>
#define randomize() srand((unsigned)time(NULL)) //定义一个宏
int main(void)
{
int i;
printf("Ten random numbers from 0 to 99\n\n");
randomize();
for(i=0; i<100; i++)
{
printf("%d\n", rand() % 100);
sleep(1) ......
一:字符串类型分类:
1. C风格字符串:起源于C,并在C++中得到支持。
a. 存储方式:被存储在一个字符数组中,通过一个char*类型的指针来操纵它。
b. 提供的库函数:包含头文件:#include<cstring> ......
指针是C语言中广泛使用的一种数据类型。运用指针编程是C语言最主要的风格之一。利用指针变量可以表示各种数据结构;能很方便地使用数组和字符串;并能象汇编语言一样处理内存地址,从而编出精练而高效的程序。指针极大地丰富了C语言的功能。学习指针是学习C语言中最重要的一环,能否正确理解和使用指针是我们是否掌握 ......
C的由来
C语言是由UNIX的研制者Dennis Ritchie和Ken Thompson于1970年研制出的B语言的基础上发展和完善起来的.
C的特点
C语言是一种面向过程的语言,同时具有汇编语言和高级语言的优点.C语言可以广泛应用于不同的操作系统,如UNIX,DOS,Windows及Linux等.
C的发展
1973年,C语言第一次被用来编写操作系统(Unix)的内核.Denn ......