公告:本站提供编程开发方面的技术交流与分享,打造最佳教程网,希望能为您排忧解难!

C语言教程数据结构C语言实现系列[2]——栈

数据结构C语言实现系列[2]——栈

更新时间:2013-04-02 12:31:46 |
#include <stdio.h>
#include <stdlib.h>

typedef int elemType;
/************************************************************************/
/*                      以下是关于栈顺序存储操作的6种算法                            */
/************************************************************************/
struct stack{
    elemType 
*stack;        /* 存储栈元素的数组指针 */
    int top;                /* 存储栈顶元素的下标位置 */
    int maxSize;            /* 存储stack数组的长度 */
};

void againMalloc(struct stack *s)
{
    
/* 空间扩展为原来的2倍,原内容被自动拷贝到p所指向的存储空间中 */
    elemType *p;
    p 
= realloc(s->stack, 2 * s->maxSize * sizeof(elemType));
    
if(!p){
        printf(
"内在分配失败!");
        exit(
1);
    }
    s
->stack = p;        /* 使stack指向新的栈空间 */
    s->maxSize = 2 * s->maxSize;        /* 把栈空间的大小修改新的长度 */
    return;
}


/* 1.初始化栈s为空 */
void initStack(struct stack *s, int ms)
{
    
if(ms <=0){
        printf(
"ms的值非法!");
        exit(
1);
    }
    s
->maxSize = ms;
    s
->stack = malloc(ms * (sizeof(elemType)));
    
if(!s->stack){
        printf(
"内在分配失败!");
        exit(
1);
    }
    s
->top = -1;        /* 初始置栈为空 */
    return;
}


/* 2.新元素进栈,即把它插入到栈顶 */
void push(struct stack *s, elemType x)
{
    
/* 若栈空间用尽则重新分配更大的存储空间 */
    if(s->top == s->maxSize - 1){
        againMalloc(s);
    }
    s
->top++;        /* 栈顶指针后移一个位置 */
    s->stack[s->top] = x;        /* 将新元素插入到栈顶 */
    return;
}


/* 3.删除(弹出)栈顶元素并返回其值 */
elemType pop(struct stack *s)
{
    
/* 若栈空则退出运行 */
    if(s->top == -1){
        printf(
"栈空,无元素出栈!");
        exit(
1);
    }
    s
->top--;        /* 栈顶指针减1表示出栈 */
    return s->stack[s->top+1];        /* 返回原栈顶元素的值 */
}

/* 4.读取栈顶元素的值 */
elemType peek(struct stack *s)
{
    
/* 若栈空则退出运行 */
    if(s->top == -1){
        printf(
"栈空,无元素可读取!");
        exit(
1);
    }
    
return s->stack[s->top];        /* 返回原栈顶元素的值 */ 
}


/* 5.判断s是否为空,若是则返回1表示真,否则返回0表示假 */
int emptyStack(struct stack *s)
{
    
if(s->top == -1){
        
return 1;
    }
else{
        
return 0;
    }
}


/* 6.清除栈s中的所有元素,释放动态存储空间 */
void clearStack(struct stack *s)
{
    
if(s->stack){
        free(s
->stack);
        s
->stack = NULL;
        s
->top = -1;
        s
->maxSize = 0;
    }
    
return;
}


/************************************************************************/

int main()
{
    
struct stack s;
    
int a[8= {385179301522};
    
int i;
    initStack(
&s, 5);
    
for(i = 0; i < 8; i++){
        push(
&s, a[i]);
    }
    printf(
"%d ", pop(&s)); printf("%d ", pop(&s));
    push(
&s, 68);
    printf(
"%d ", peek(&s));    printf("%d ", pop(&s));
    
while(!emptyStack(&s)){
        printf(
"%d ", pop(&s));
    }
    printf(
"");
    clearStack(
&s);
    system(
"pause");
    
return 0;
}
/************************************************************************/
/*                      以下是关于栈链接存储操作的6种算法                 */
/************************************************************************/

struct sNode{
    elemType data;
    
struct sNode *next;
};


/* 1.初始化链栈为空 */
void initStack(struct sNode* *hs)
{
    
*hs = NULL;    
    
return;
}


/* 2.向链中插入一个元素(入栈) */
void push(struct sNode* *hs, elemType x)
{
    
struct sNode *newP;
    newP 
= malloc(sizeof(struct sNode));
    
if(newP == NULL){
        printf(
"内在空间分配失败!");
        exit(
1);
    }
    newP
->data = x;        /* 给新分配的结点赋值 */
    /* 向栈顶插入新结点 */
    newP->next = *hs;
    
*hs = newP;
    
return;
}


/* 3.从链栈中删除一个元素并返回它(出栈) */
elemType pop(struct sNode* *hs)
{
    
struct sNode *p;
    elemType temp;
    
if(*hs == NULL){
        printf(
"栈空无法删除!");
        exit(
1);
    }
    
/* 暂存栈顶结点指针,并使栈顶指针指向下一个结点 */
    p = *hs;
    
*hs = p->next;
    
/* 暂存原栈顶元素以便返回,同时回收原栈顶结点 */
    temp = p->data;
    free(p);
    
return temp;        /* 返回原栈顶元素 */
}

/* 4.读取栈顶元素 */
elemType peek(struct sNode* *hs)
{
    
/* 对于空栈则退出运行 */
    if(*hs == NULL){
        printf(
"栈空,无栈顶元素!");
        exit(
1);
    }
    
return (*hs)->data;        /* 返回栈顶结点的值 */
}

/* 5.判断链栈是否为空,为空返回1,否则返回0 */
int emptyStack(struct sNode* *hs)
{
    
if(*hs == NULL){
        
return 1;
    }
else{
        
return 0;
    }
}


/* 6.清除链栈为空 */
void clearStack(struct sNode* *hs)
{
    
struct sNode *cp, *np;
    cp 
= *hs;        /* 使cp指向栈顶结点 */
    /* 从栈底依次删除每个结点 */
    while(cp != NULL){
        np 
= cp->next;
        free(cp);
        cp 
= np;
    }
    
*hs = NULL;        /* 置链栈为空 */
    return;
}
最佳教程网

最大的技术交流平台 www.goodxyx.com© CopyRight 2011-2013, All Rights Reserved

浙ICP备11033019号