The fifth week linear table project of C/C + + builds the algorithm library of chain stack

/*  
*Copyright(c)2017, School of computer science, Yantai University  
*All right reserved.  
*File name: main.cpp sqstack.h sqstack.cpp  
*Author: Huang Shisheng  
*Completion date: September 28, 2017  
*Version number: v1.0  
*  
*Problem Description: build chain stack algorithm library  
*Enter Description: None 
*Program output: see operation results  
*/ 

Problem Description: define chain stack storage structure, implement its basic operation, and complete the test.

Refer to Item 1 to complete item 2

1. Header file: listack.h, including the code defining the chain stack data structure, the macro definition, and the declaration of the function to implement the algorithm;

#ifndef LISTACK_H_INCLUDED
#define LISTACK_H_INCLUDED

typedef char ElemType;
typedef struct linknode
{
    ElemType data;              //Data domain
    struct linknode *next;      //Pointer domain
} LiStack;                      //Chain stack type definition

void InitStack(LiStack *&s);  //Initialization stack
void DestroyStack(LiStack *&s);  //Destruction stack
int StackLength(LiStack *s);  //Return stack length
bool StackEmpty(LiStack *s);  //Judge whether the stack is empty
void Push(LiStack *&s,ElemType e);  //Push
bool Pop(LiStack *&s,ElemType &e);  //Stack out
bool GetTop(LiStack *s,ElemType &e);  //Top of stack element
void DispStack(LiStack *s);  //Output stack elements


#endif // LISTACK_H_INCLUDED

2. Source file: listack.cpp, including the definition of functions to implement various algorithms

#include <stdio.h>
#include <malloc.h>
#include "listack.h"

void InitStack(LiStack *&s)  //Initialization stack
{
    s=(LiStack *)malloc(sizeof(LiStack));
    s->next=NULL;
}

void DestroyStack(LiStack *&s)  //Destruction stack
{
    LiStack *p=s->next;
    while (p!=NULL)
    {
        free(s);
        s=p;
        p=p->next;
    }
    free(s);    //s points to the tail node, freeing its space
}

int StackLength(LiStack *s)  //Return stack length
{
    int i=0;
    LiStack *p;
    p=s->next;
    while (p!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}

bool StackEmpty(LiStack *s)  //Judge whether the stack is empty
{
    return(s->next==NULL);
}

void Push(LiStack *&s,ElemType e)  //Push
{
    LiStack *p;
    p=(LiStack *)malloc(sizeof(LiStack));
    p->data=e;              //New node * p corresponding to element e
    p->next=s->next;        //Insert * p node as start node
    s->next=p;
}

bool Pop(LiStack *&s,ElemType &e)  //Stack out
{
    LiStack *p;
    if (s->next==NULL)      //Stack empty
        return false;
    p=s->next;              //p points to the start node
    e=p->data;
    s->next=p->next;        //Delete * p node
    free(p);                //Release * p node
    return true;
}

bool GetTop(LiStack *s,ElemType &e)  //Top of stack element
{
    if (s->next==NULL)      //Stack empty
        return false;
    e=s->next->data;
    return true;
}

void DispStack(LiStack *s)  //Output stack elements
{
    LiStack *p=s->next;
    while (p!=NULL)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    printf("\n");
}

3. Establish a source file (such as main.cpp) in the same project, compile the main function, and complete the related test work.

The code is as follows

#include <stdio.h>
#include "../listack.h"

int main()
{
    ElemType e;
    LiStack *s;
    printf("(1)Initialize chain stack s\n");
    InitStack(s);
    printf("(2)Chain stack%s\n",(StackEmpty(s)?"empty":"Not empty"));
    printf("(3)Chain stack elements in sequence a,b,c,d,e\n");
    Push(s,'a');
    Push(s,'b');
    Push(s,'c');
    Push(s,'d');
    Push(s,'e');
    printf("(4)Chain stack%s\n",(StackEmpty(s)?"empty":"Not empty"));
    printf("(5)Chain stack length:%d\n",StackLength(s));
    printf("(6)Elements from top to bottom of chain stack:");DispStack(s);
    printf("(7)Outbound stack sequence:");
    while (!StackEmpty(s))
    {   Pop(s,e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(8)Chain stack%s\n",(StackEmpty(s)?"empty":"Not empty"));
    printf("(9)Release chain stack\n");
    DestroyStack(s);
    return 0;
}

Screenshot of operation result:



New experience:

Through these two projects, I really strengthened my deep understanding of stack. The differences and similarities between sequential stack and chained stack are understood.










Published 34 original articles· Zan Zan 9. 10000 visitors+
Private letter follow

Posted on Thu, 02 Apr 2020 15:49:25 -0700 by Lord Brar