Biểu diễn stack bằng danh sách liên kết đơn

Yêu cầu:

Minh họa cài đặt stack bằng danh sách liên kết. Mỗi phần tử của stack sẽ chứa 1 số nguyên. Do vậy mỗi node của danh sách liên kết sẽ gồm 1 trường dữ liệu kiểu int, 1 con trỏ next. Thao tác loại bỏ (pop()) hay bổ sung (push()) sẽ thực hiện với ô đầu tiên của danh sách liên kết.


Các phép toán cơ bản:
1. Khởi tạo
2. Kiểm tra ngăn xếp rỗng:
3. Nạp vào : nạp phần tử vào đầu ngăn xếp
4. Lấy ra : trả lại giá trị của phần tử ở đầu ngăn xếp và xóa bỏ phần tử đó khỏi ngăn xếp
5. Hiển thị các phần tử của ngăn xếp

// Cai dat stack bang dslk don
/************************************************************
* Author:        VNCODING
* History 
* 2014/03/16     first create    VNCODING
* 2014/12/12     update          VNCODING
*************************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct stack
{
    int n;
    stack *pNext;
}STACK, *P_STACK, **PP_STACK;

void InitStack(PP_STACK top);
bool IsStackEmpty(P_STACK top);
bool Push(int n, PP_STACK top);
int Pop(PP_STACK top);
void DisplayStack(P_STACK top);

void main()
{
    P_STACK top;
    int sel = 0;
    int n;
    char isContinue;
    printf("\n****************Express stack by Single Link List**************");
    InitStack(&top);
    printf("\n1. Nap thong tin vao stack");
    printf("\n2. Lay thong tin tu stack");
    printf("\n3. Hien thi stack");
    printf("\n4. Exit");
    do
    {
        printf("\nMoi ban chon: ");
        scanf("%d", &sel);
        switch(sel)
        {
        case 1:
            printf("\n2. Nap thong tin vao stack: ");
            scanf("%d", &n);
            if(Push(n, &top))
                printf("\nNap thong tin thanh cong");
            break;
        case 2:
            printf("\n3. Lay thong tin tu stack: ");
            printf("\nn = %d",Pop(&top));
            break;
        case 3:
            printf("\n4. Hien thi stack: ");
            DisplayStack(top);
            break;
        default:
            printf("\nExit");
        }
        printf("\nBan muon thao tac tiep ko (Y/N)? ");
        fflush(stdin);
        isContinue = getchar();
    }
    while(isContinue == 'y' || isContinue == 'Y');
    getch();
}

/**********************************************************************
Description: - Ham khoi tao stack
- Khoi tao tro con tro toi dau stack = NULL
Return : - void
***********************************************************************/
void InitStack(PP_STACK top)
{
    *top = NULL;
}

/**********************************************************************
Description: - Kiem tra stack rong
Return : - 1 neu stack # rong
- 0 neu stack rong
***********************************************************************/
bool IsStackEmpty(P_STACK top)
{
    if(top == NULL)
        return false;
    else
        return true;
}

/**********************************************************************
Description: - Nap du lieu vao stack
Return : - TRUE neu push thanh cong
- FALSE neu push fail
***********************************************************************/
bool Push(int n, PP_STACK top)
{
    P_STACK pstack, p;
    pstack = (P_STACK)malloc(sizeof(STACK));
    if(pstack == NULL)
    {
        return false;
    }
    else
    {
        pstack->n = n;
        pstack->pNext = NULL;
    }
    p = *top;
    if(*top == NULL)
    {
        *top = pstack;
    }
    else
    {
        *top = pstack;
        pstack->pNext = p;
    }
    return true;
}

/**********************************************************************
Description: - Lay du lieu tu stack
Return : - gia tri cua ptu dau tien cua stack
***********************************************************************/
int Pop(PP_STACK top)
{
    int a;
    P_STACK p;
    p = (*top);
    if(IsStackEmpty(*top))
    {
        a = (*top)->n;
        (*top) = (*top)->pNext;
        free(p);
        return a;
    }
}

/**********************************************************************
Description: - Hien thi du lieu cua stack
Return : - void
***********************************************************************/
void DisplayStack(P_STACK top)
{
    P_STACK p;
    p = top;
    if(IsStackEmpty(top))
    {
        while(p)
        {
            printf("%d\t", p->n);
            p = p->pNext;
        }
    }
    else
        printf("\n Stack is empty");
}

Kết quả:

Biểu diễn stack bằng danh sách liên kết đơn
Biểu diễn stack bằng danh sách liên kết đơn

Be the first to comment

Leave a Reply

Your email address will not be published.

*