chapter4栈与队列 1.顺序栈实现-白红宇

chapter4栈与队列 1.顺序栈实现

阅读量：3936 次

发布时间：2019-05-23

本文共 3129 字，大约阅读时间需要 10 分钟。

栈

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

栈的抽象数据类型

ADT 栈(stack)Data    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。Operation    InitStack(*S):    初始化操作，建立一个空栈S。    DestroyStack(*S): 若栈存在，则销毁它。    ClearStack(*S):   将栈清空。    StackEmpty(S):    若栈为空，返回true，否则返回false。    GetTop(S, *e):    若栈存在且非空，用e返回S的栈顶元素。    Push(*S, e):      若栈S存在，插入新元素e到栈S中并成为栈顶元素。    Pop(*S, *e):      删除栈S中栈顶元素，并用e返回其值。    StackLength(S):   返回栈S的元素个数。endADT

由于栈本身就是一个线性表，那么上一章我们讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

下面上代码：

顺序栈实现

ElementType.h 元素类型定义

#ifndef ELEMENT_H_INCLUDED#define ELEMENT_H_INCLUDED#define MAX_SIZE 100#define  true 1#define false 0// 用来定义一些常用的数据元素typedef struct{
       int id;    char * name;}ElementType;#endif // ELEMENT_H_INCLUDED

SeqStack.h 顺序栈头文件（包含栈数据结构、函数方法声明）

#ifndef SEQSTACK_H_INCLUDED#define SEQSTACK_H_INCLUDED/****************************** * Project: 第三章栈与队列 * 这里是顺序栈 用数组来实现 * ******************************/#include 
   
    #include 
    
     #include "Element.h"//定义一些栈的数据结构typedef struct SeqStack{
       ElementType elements[MAX_SIZE];//顺序栈中用来存放数据元素的数组    int top;    //栈顶（数组中的下标），如果为-1则代表栈为空    int length; //当前栈的元素个数}SeqStack;//定义一下栈的方法void InitSeqStack(SeqStack* seqstack);//向栈中压入元素 返回成功与否int PushSeqStack(SeqStack* seqstack,ElementType element);//出栈 返回出站元素，以指针的方式返回 返回值表示出栈是否成功int PopSeqStack(SeqStack* seqstack,ElementType* element);//清空栈void ClearSeqStack(SeqStack* seqstack);//返回栈顶元素 与出栈一样，只是不需要返回状态了。#endif // SEQSTACK_H_INCLUDED

SeqStack.c 顺序栈实现文件（包含栈函数方法实现）

#include "SeqStack.h"//初始化栈void InitSeqStack(SeqStack* seqstack){
       seqstack->top = -1;     //栈顶指向-1的下标    seqstack->length = 0;}//向栈中压入元素 返回成功与否int PushSeqStack(SeqStack* seqstack,ElementType element){
       //首先判断是否满了    if(seqstack->top == MAX_SIZE -1){
           printf("满栈了，压栈失败\n");        return 0;    }    seqstack->top++;    seqstack->elements[seqstack->top] = element;    seqstack->length++;    return 1;}//出栈 返回出站元素，以指针的方式返回，返回值表示出栈是否成功int PopSeqStack(SeqStack* seqstack,ElementType* element){
       //首先判断是否为空    if(seqstack->top == -1){
           printf("空栈，出栈失败\n");        return false;    }    *element = seqstack->elements[seqstack->top];    seqstack->top--;    seqstack->length--;}void ClearSeqStack(SeqStack* seqstack){
       //因为是数组实现的栈，不能删除空间，所以只要把指针搞定就好了    seqstack->top = -1;    seqstack->length = 0;    return;}

main.c 测试文件

#include 
   
    #include 
    
     #include "SeqStack.h"ElementType datas[] = {
   {
   1,"xxxx"},{
   2,"zzz"},{
   3,"yyyy"} };void TestSeqStack();int main(){
       TestSeqStack();    printf("Hello world!\n");    return 0;}void TestSeqStack(){
       SeqStack seqstack;    InitSeqStack(&seqstack);    for(int i =0;i < 3;i++){
           PushSeqStack(&seqstack,datas[i]);        printf("当前入栈：%d\t%s\n",datas[i].id,datas[i].name);    }    ElementType element;    PopSeqStack(&seqstack,&element);    printf("当前出栈元素为：%d\t%s\n",element.id,element.name );    printf("当前栈内元素为\n");    for(int i =0;i < seqstack.length;i++){
           printf("%d\t%s\n",seqstack.elements[i].id,seqstack.elements[i].name);    }    free(&seqstack);}

转载地址：http://vjzwi.baihongyu.com/

你可能感兴趣的文章