[Cấu trúc dữ liệu] Stacks - Kiểu dữ liệu ngăn xếp trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 388

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Ở bài trước mình đã giới thiệu cho các bạn về Danh sách móc nối đơn. Vì thế ở kiểu dữ liệu stacks mình sẽ dùng kiểu danh sách móc nối đơn để trình bày thông tin.


    Ngăn xếp là dạng đặc biệt của danh sách tuyến tính hoạt động theo nguyên tắc vào trước ra sau.
    Các phép toán cơ bản với ngăn xếp gồm có:

    • top(): Trả về phần từ nạp vào sau cùng hay là phân tử đầu tiên trong ngăn xếp.
    • push(data): Bổ sung vào ngăn xếp một phần tử.
    • put(): Lấy ra một phần tử và trả về phần tử ngay sau đó chính là phần tử top.
    • size(): Trả về số lượng phần tử được lưu trữ.
    • empty() : Kiểm tra xem ngăn xếp có bị rỗng hay không.


    [​IMG]
    hoạt động của ngăn xếp - vào sau ra trước.
    Các hàm sử dụng trong ngăn xếp gồm các hàm cơ bản sau:


    http://www.mediafire.com/?nh5g8be463brqnb

    Mã:
    struct Node{
        char info;
        Node* next;
    };
    Node* top=NULL;
    
    int stackEmpty(){
        if(top==NULL) return 1;
        else return 0;
        }
    
    void push(char x){                         //cho 1 phần tử vào trong ngăn xếp
        Node* p;
        p= new Node;
        p->info =x;
        p->next =top;
        top =p;
        }
    
    char pop(){                     //lấy 1 phần tử ra khỏi ngăn xếp và trả về giá trị của phần tử đó
        char x= top->info;
        Node* p= top;
        top= top ->next;
        delete p;
        return x;
        }
    Nhưng ở trên ngôn ngữ lập trình C++ hiện nay, đều hỗ trợ thư viện stack, vì thế mà mọi người sẽ không phải lập trình lại nữa mà có thể sử dụng ngay. Mình sẽ giới thiệu cho các bạn một thuật toán sử dụng thư viện stack.

    Bài toán: Kiểm tra sự hợp lý của dãy ngoặc bao gồm; (),[],{}

    Cài đặt thuật toán.


    Mã:
    #include<stdio.h>
    #include <stdlib.h>
    #include<stack>
    #include<iostream>
    
    using namespace std;
    bool match(char a, char b){
        if (a=='('&& b==')') return 1;
        if (a=='['&& b==']') return 1;
        if (a=='{'&& b=='}') return 1;
        return 0;
        }
    int main(){
        string a;
        int n=6;
        stack<char> S;
        bool OK=true;
        cout << "Nhap chuoi ngoac can kiem tra: ";
        getline(cin,a);
        fflush(stdin);
        for (int i=0;i<a.length();i++){
            if (a[i]=='('||a[i]=='['||a[i]=='{')
                S.push(a[i]);
            else{
                if (S.empty()){
                    OK=false;
                    break;
                    }
               
                else{
                    char c=S.top();
                    S.pop();
                    if(!match(c,a[i])){
                    OK=false;
                    break;
                    }
                }
       
        }
        }
        if (OK) printf("OK n");
        else printf("NO n");
    }
    chúc mọi người thành công!!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap