栈的实现与应用

亦凉 2022-08-10 00:57 168阅读 0赞

## 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素   2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。   3. 调用栈的基本操作，实现行编辑程序，假设“\#”为退格符，“@”为退行符。 ##

#include<stdio.h>
    #include<fstream>
    #include<malloc.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    #define TURE 1
    #define FALSE 0
    #define OVERFLOW -1
    #define OK 1
    #define ERROR 0
    typedef int Status;
    typedef char SElemType;
    typedef struct
    {
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }SqStack;
    Status InitStack(SqStack &S)
    {//构造一个空栈
    	S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    	if(!S.base)exit(OVERFLOW);//存储分配失败
    	S.top=S.base;
    	S.stacksize=STACK_INIT_SIZE;
    	return OK;
    }//InitStack
    Status Push(SqStack &S,SElemType e)
    {//插入元素e为新的栈顶元素
    	if(S.top-S.base>=S.stacksize)
    	{//栈满,追加存储空间
    		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(SElemType));
    		if(!S.base)
    			exit(OVERFLOW);//存储分配失败
    		S.top=S.base+S.stacksize;
    		S.stacksize+=STACKINCREMENT;
    	}
    	*S.top++=e;
    	return OK;
    }//push
    Status Pop(SqStack &S,SElemType &e)
    {
    	if(S.top==S.base)return ERROR;
    	e=*--S.top;
    	return OK;
    }//Pop
    Status GetTop(SqStack S,SElemType &e)
    {//若栈不空，则返回S的栈顶元素，并返回OK;否则返回ERROR
    	if(S.top==S.base) return ERROR;
    	e=*(S.top-1);                     
    	return OK;
    }//GetTop
    Status StackEmpty(SqStack S)
    {//判空
    	if(S.top==S.base)
    	{
    		return OK;
    	}
    	return ERROR;
    }//StackEmpty
    Status ClearStack(SqStack &S)
    {//清空栈
        if(S.top=S.base)
        return OK;
    }//ClearStack
    Status DestroyStack(SqStack &S)
    {//销毁栈
    	S.base=NULL;
    	return OK;
    }//DestroyStack
    Status StackTraverse(SqStack S)
    {//遍历
    	while(S.top!=S.base)
    	{
    		printf("%d\t",*--S.top);
    	}
    	return OK;
    }//StatusTraverse
    void Conversion()
    {//对于输入的任意一个非负十进制整数，输出其等值的十六进制数
        SqStack S;
        SElemType N;
    	SElemType e;
        InitStack(S);
    	scanf("%d",&N);
    	printf("转换后的值为：");
    	while(N)
    	{
    		Push(S,N%16);
    		N=N/16;
    	}
    	while(!StackEmpty(S))
    	{
    		Pop(S,e);
    		printf("%d",e);
    	}
    	printf("\n");
    	
    }//conversion
    void LineEdit()
    {
        SqStack tS;
    	SElemType e;
    	InitStack(tS);
    	fstream f("t.txt",ios::ate|ios::out);
    	if(!f)
    	{
    		printf("文件操作失败！");
    		return;
    	}
    
    char c=getchar();//从终端接收第一个字符
    	while(c!=EOF)
    	{
    		while(c!=EOF && c!='\n')
    		{
    			switch(c)
    			{
    			case'#':Pop(tS,e);break;//仅当栈非空时退栈
    			case'@':ClearStack(tS);break;//重置S为空栈
    			default:Push(tS,c);//有效字符进栈，为考虑栈满
    			}
    			c=getchar();//从终端接收下一个字符
    		}
    		SElemType *p=tS.base;
    		while(p!=tS.top)
    		f<<char(*p++);
    		f<<endl;
    		ClearStack(tS);
    		if(c!=EOF)
    			c=getchar();
    	}
    	DestroyStack(tS);
    	printf("输入内容为：\n");
    	f.close();
    	f.open("t.txt",ios::in|ios::out|ios::app);
    	if(!f)
    	{
    		printf("文件操作失败!");
    		return;
    	}
    	while(f.get(c))
    		printf("%c",c);
    	printf("\n");
    	f.close();
    }//LineEdit
    int main()
    {
    	SqStack S;
        SElemType N;
        char c;
    	InitStack(S);
        printf("请输入要进栈的数：");
        while((c=getchar())!='\n')
    	{  
    		Push(S,c);  
    	}
        GetTop(S,c);
    	printf("栈顶元素为：%c\n",c);
        for(int i=0;S.top!=S.base;i++)
    	{       
    		Pop(S,c);     
    	printf("栈中第%d元素值为：%c\n",i+1,c);
    	}
        printf("请输入要转换的数值：\n");
    	Conversion();
        LineEdit();
    	return 0;
    }