深圳网站建设的,我的家乡网页制作步骤,嘉兴教育网站建设,阿里巴巴网站优化一、个人理解栈是线性表的一种衍生#xff0c;和之前的顺序表和链表在插入和删除元素上有较大差异#xff0c;其他基本相同#xff0c;栈是数据只能插入表的尾部#xff08;栈顶#xff09;#xff0c;删除数据时只能删除表的尾部#xff08;栈顶#xff09;数据#…一、个人理解栈是线性表的一种衍生和之前的顺序表和链表在插入和删除元素上有较大差异其他基本相同栈是数据只能插入表的尾部栈顶删除数据时只能删除表的尾部栈顶数据就是大家经常背的顺口溜后入先出。后插入的数据先删除。二、图解这里把数组竖起来了是方便理解看得更清楚。三、名词解释1、出栈、弹栈是一个意思就是把数据从栈顶移除。2、入栈、压栈是一个意思就是把数据从栈顶插入。3、LIFOLAST IN FIRST OUT的简写也就是后进先出的意思。4、顺序栈和链栈实现方式上的不同顺序栈是用数组实现而链栈是用链表实现。5、上溢栈已满但数据还需要继续入栈。上溢一般认为是一种错误因为可能导致数据录入失败或者导致数据录入延时。当是顺序栈时对此情况有两种措施一是抛出错误。二是重新申请新栈把旧栈数据写入到新栈中不推荐比较耗时。6、下溢栈已空但还是要出栈。下溢一般认为是一种结束标志因为并不会有数据上的缺失。四、函数实现1、InitSqStack1用途初始化顺序栈。2源码Status InitSqStack(SqStack* S)
{printf(Init SqStack : );JudgeAllNullPointer(S);S-BasePointer (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S-TopPointer S-BasePointer;S-SqStackMaxSize SQ_STACK_MAX_SIZE;printf(OK\n);PrintPretty();return SuccessFlag;
}3参数参数名说明S需要初始化的SqStack*类型顺序栈。2、JudgeSqStackIsEmpty1用途判断顺序栈是否为空。当栈顶指针和栈底指针相等时表示栈为空反之非空。2源码Status JudgeSqStackIsEmpty(SqStack* S)
{printf(Judge SqStack : );JudgeAllNullPointer(S);if(S-BasePointer S-TopPointer){printf(Empty\n);PrintPretty();return SuccessFlag;}printf(Not Empty\n);PrintPretty();return FailFlag;
}3参数参数名说明S需要判断是否为空的SqStack*类型顺序栈。3、GetSqStackLen1用途求顺序栈的长度。栈顶指针减去栈底指针为顺序栈的长度原理为相同类型的指针相减得到字节数它会再除以一个栈类型头文件中的结构体SqElemType的字节长度得到最终的顺序栈的长度。2源码SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S-TopPointer - S-BasePointer;
}3参数参数名说明S需要求栈长度的SqStack*类型顺序栈。五、测试代码1、SqStack.c#include stdio.h
#include string.h
#include stdlib.h
#include sys/time.h
#include SqStack.hvoid PrintPretty()
{printf(*********************************\n);
}void PrintPretty_V1()
{printf(################\n);
}void *MyMalloc(size_t size)
{void *Result (void *)malloc(size);if(Result NULL){printf(malloc Function Exec Fail , Out Of Memory ,Exit!!!\n);exit(ExceptionExitFlag);}return Result;
}void JudgeAllNullPointer(void* P)
{if(!P){printf(Pointer Is Null ,Exit !\n);exit(ExceptionExitFlag);}
}Status InitSqStack(SqStack* S)
{printf(Init SqStack : );JudgeAllNullPointer(S);S-BasePointer (SqElemType*)MyMalloc(sizeof(SqElemType) * SQ_STACK_MAX_SIZE);S-TopPointer S-BasePointer;S-SqStackMaxSize SQ_STACK_MAX_SIZE;printf(OK\n);PrintPretty();return SuccessFlag;
}Status JudgeSqStackIsEmpty(SqStack* S)
{printf(Judge SqStack : );JudgeAllNullPointer(S);if(S-BasePointer S-TopPointer){printf(Empty\n);PrintPretty();return SuccessFlag;}printf(Not Empty\n);PrintPretty();return FailFlag;
}SqStackMaxSizeType GetSqStackLen(SqStack* S)
{JudgeAllNullPointer(S);return S-TopPointer - S-BasePointer;
}2、SqStack.h#ifndef SqStack_H
#define SqStack_H#define InsertDataArrayLen 8
#define SQ_STACK_MAX_SIZE 6#define ExceptionExitFlag -1
#define SuccessFlag 1
#define FailFlag 0
#define StudentNumLen 8
#define StudentNameLen 8typedef int Status;
typedef long long int SqStackMaxSizeType;typedef struct SqElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int StudentScore;
}SqElemType;typedef struct
{SqElemType* BasePointer;SqElemType* TopPointer;SqStackMaxSizeType SqStackMaxSize;
}SqStack;void *MyMalloc(size_t size);
void JudgeAllNullPointer(void* P);
void PrintPretty();
void PrintPretty_V1();Status InitSqStack(SqStack* S);
Status JudgeSqStackIsEmpty(SqStack* S);
SqStackMaxSizeType GetSqStackLen(SqStack* S);#endif3、main.c#include stdio.h
#include string.h
#include stdlib.h
#include SqStack.hint main()
{//测试数据生成SqElemType *InsertSqElemArray (SqElemType *)MyMalloc(sizeof(SqElemType) * InsertDataArrayLen);int i;for(i0; iInsertDataArrayLen; i){strcpy(InsertSqElemArray[i].StudentNum ,X666);strcpy(InsertSqElemArray[i].StudentName,Sun);InsertSqElemArray[i].StudentScore i 100;}//测试顺序栈SqStack* S (SqStack*)MyMalloc(sizeof(SqStack));InitSqStack(S);JudgeSqStackIsEmpty(S);printf(SqStack Len : %lld\n,GetSqStackLen(S));PrintPretty();//释放内存free(InsertSqElemArray);InsertSqElemArray NULL;return SuccessFlag;
}4、makefileCC gcc
CFLAG_EXEC -Wall -O3
CFLAG_ALIAS -o
RM_COMM rm -rfall : mainmain : $(CC) $(CFLAG_EXEC) SqStack.c main.c $(CFLAG_ALIAS) TestSqStackclean : $(RM_COMM) TestSqStack六、测试结果[gbaseczg2 LinearTable_Stack]$ make clean
rm -rf TestSqStack[gbaseczg2 LinearTable_Stack]$ make
gcc -Wall -O3 SqStack.c main.c -o TestSqStack[gbaseczg2 LinearTable_Stack]$ ./TestSqStack
Init SqStack : OK
*********************************
Judge SqStack : Empty
*********************************
SqStack Len : 0
*********************************七、顺序栈的应用大家可以参考一下之前写的文章《leecode-C语言实现-20. 有效的括号》里面用到了顺序栈的知识。
