数据结构（顺序栈）（C语言）

小灰灰 2022-05-17 11:44 217阅读 0赞

### 利用C语言顺序结构实现栈的基本功能，以及对其进行排序： ###

*  头文件：

#ifndef _SEQUENCE_H
    #define _SEQUENCE_H
    
    #include <stdio.h>
    #include <stdlib.h>
    //#include <time.h>
    
    #define SIZE 10
    #define SUCCESS 10000
    #define FAILURE 10001
    #define TRUE    10002
    #define FALSE   10003
    
    typedef int Elemtype;
    
    typedef struct SequenceStack
    {
    	int top;
    	Elemtype *data;
    }Stack;
    
    int StackInit(Stack **stack);
    int StackEmpty(Stack *stack);
    int Push(Stack *stack, Elemtype e);
    int Pop(Stack *stack, Elemtype *e);
    int GetTop(Stack *stack, Elemtype *e);
    int StackClear(Stack *stack);
    int StackDestory(Stack **stack);
    
    #endif

功能函数：

#include "SequenceStack.h"
    
    int StackInit(Stack **stack)
    {
    	*stack = (Stack *)malloc(sizeof(Stack)*1);
    	if(NULL == *stack)
    	{
    		return FAILURE;
    	}
    	
    	(*stack)->top = -1;
    	(*stack)->data = (Elemtype *)malloc(sizeof(Elemtype)*SIZE);
    	if(NULL == (*stack)->data)
    	{
    		return FAILURE;
    	}
    	
    	return SUCCESS;
    	
    }
    
    int StackEmpty(Stack *stack)
    {
    	return (stack->top == -1) ? TRUE : FALSE;
    }
    
    int Push(Stack *stack, Elemtype e)
    {
    	if(NULL == stack || (SIZE-1) == stack->top)
    	{
    		return FAILURE;
    	}
    	
    	stack->data[stack->top+1] = e;
    	stack->top++;
    	
    	return SUCCESS;
    }
    
    int Pop(Stack *stack, Elemtype *e)
    {
    	if(NULL == stack || -1 == stack->top)
    	{
    		return FAILURE;
    	}
    	
    	*e = stack->data[stack->top];
    	stack->top--;
    	
    	return SUCCESS;
    }
    
    int GetTop(Stack *stack, Elemtype *e)
    {
    	if(NULL == stack || -1 == stack->top)
    	{
    		return FAILURE;
    	}
    	
    	*e = stack->data[stack->top];
    	
    	return SUCCESS;
    }
    
    int StackClear(Stack *stack)
    {
    	if(NULL == stack)
    	{
    		return FAILURE;
    	}
    	
    	stack->top = -1;
    	
    	return SUCCESS;
    }
    
    int StackDestory(Stack **stack)
    {
    	if(NULL == stack)
    	{
    		return FAILURE;
    	}
    	
    	free((*stack)->data);
    	free(*stack);
    	*stack = NULL;
    	
    	return SUCCESS;
    }

测试主函数：

#include "SequenceStack.h"
    
    int main()
    {
    	Stack *stack;
    	Elemtype e;
    	int ret, i;
    	
    	//srand(time(NULL));
    	
    	ret = StackInit(&stack);
    	if(SUCCESS == ret)
    	{
    		printf("Init success.\n");
    	}
    	else
    	{
    		printf("Init failure.\n");
    	}
    	
    	ret = StackEmpty(stack);
    	if(TRUE == ret)
    	{
    		printf("Stack is Empty.\n");
    	}
    	else
    	{
    		printf("Stack is not Empty.\n");
    	}
    	
    	for(i = 0; i < SIZE; i++)
    	{
    		ret = Push(stack, i+1);
    		if(SUCCESS == ret)
    		{
    			printf("Push Success.\n");
    		}
    		else
    		{
    			printf("Push Failure.\n");
    		}
    	}
    	
    	ret = Pop(stack, &e);
    	if(SUCCESS == ret)
    	{
    		printf("Pop the Element %d Success.\n", e);
    	}
    	else
    	{
    		printf("Pop Failure.\n");
    	}
    	
    	ret = GetTop(stack, &e);
    	if(SUCCESS == ret)
    	{
    		printf("Top is %d.\n", e);
    	}
    	else
    	{
    		printf("Get Top Failure.\n");
    	}
    	
    	ret = StackClear(stack);
    	if(TRUE == ret)
    	{
    		printf("Stack Clear Success.\n");
    	}
    	else
    	{
    		printf("Stack Clear Failure.\n");
    	}
    	
    	ret = StackDestory(&stack);
    	if(TRUE == ret)
    	{
    		printf("Stack Destory Success.\n");
    	}
    	else
    	{
    		printf("Stack Destory Failure.\n");
    	}
    	
    	return 0;
    }

*  排序方案：
    
        #include "SequenceStack.h"
        
        int main()
        {
        	int i, num, tmp;
        	Stack *s1, *s2;
        
        	if (StackInit(&s1) != SUCCESS || StackInit(&s2) != SUCCESS)
        	{
        		printf("Init Failure!\n");
        	}
        
        	for (i = 0; i < SIZE; i++)
        	{
        		scanf("%d", &num);
        		if (i == 0)
        		{
        			push(s1, num);
        		}
        		else
        		{
        			if (num >= GetTop(s1))
        			{
        				push(s1, num);
        			}
        			else
        			{
        				while (StackEmpty(s1) != TRUE && num < GetTop(s1))
        				{
        					tmp = GetTop(s1);	
        					pop(s1);
        					push(s2, tmp);
        				}
        				push(s1, num);
        				while (StackEmpty(s2) != TRUE)
        				{
        					tmp = GetTop(s2);
        					pop(s2);
        					push(s1, tmp);
        				}
        			}
        		}
        	}
        
        	for (i = 0; i < SIZE; i++)
        	{
        		printf("%d ", GetTop(s1));
        		pop(s1);
        	}
        	return 0;
        }