Cơ bản về cấu trúc dữ liệu và giải thuật – Phần hai: Giới thiệu cấu trúc dữ liệu

Thảo luận trong 'ACM/Programming' bắt đầu bởi avnh, 14/02/17, 12:02 PM.

  1. avnh

    avnh W-------

    Tham gia: 28/04/16, 02:04 PM
    Bài viết: 10
    Đã được thích: 6
    Điểm thành tích:
    8
    Trong topic này mình xin chia sẻ cho các bạn kiến thức cơ bản về cấu trúc dữ liệu – một kiến thức nên tảng trong lập trình.
    Theo định nghĩa, cấu trúc dữ liệu là cách tổ chức dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Mỗi loại cấu trúc dữ liệu lại phù hợp với các chương trình khác nhau, việc hiểu và áp dụng đúng các kiểu cấu trúc dữ liệu sẽ giúp chương trình của chúng ta tốt hơn, hiệu năng cao hơn, đôi khi còn giải quyết nhiều vấn đề khiến ra đau đầu.
    Để mô tả một cấu trúc dữ liệu, ta cần mô tả các thành phần (phần tử) là các dữ liệu cơ bản, các mối liên kết giữa các phần tử ấy và các thao tác cơ bản trên chúng.
    Có rất nhiều các kiểu cấu trúc dữ liệu khác nhau, tuy nhiên, các cấu trúc dữ liệu thường dung có thể kể đến đó là: mảng (array), danh sách (list), ngăn xếp (stack), hàng đợi (queue), cây (tree), đồ thị (graph)…
    Trong bài đầu tiên này mình xin giới thiệu cho các bạn về mảng.
    Mảng là gì?
    Đó là cấu trúc dữ liệu được dùng phổ biến nhất trong các chương trình. Một mảng gồm các phẩn tử có cùng kiểu, được lưu trữ có thứ tự liện tiếp nhau trong bộ nhớ.

    [​IMG]
    Mô tả một mảng với 6 phần tử​
    Các phần tử trong mảng có thể truy cập qua chỉ mục của phần tử đó. Một mảng có thể có một hoặc nhiều chiều.
    Để lưu trữ một mảng, ta cần biết kích thước của một phần tử, địa chỉ phần tử đầu tiên và số phần tử trong mảng đó. Ví dụ cụ thể với mảng trong ngôn ngữ C, cú pháp khai báo một mảng là:

    [​IMG]
    Cú pháp khai báo và khởi tạo một mảng trong C

    Trong đó, địa chỉ được gán cho mảng array chính là địa chỉ của phần tử đầu tiên trong mảng.
    Trong mảng thì các thao tác với các phần tử tương đối hạn chế. Mảng có kích thước cố đinh nên không thể them số lương phần tử cũng như thay đổi kiểu dữ liệu mỗi phần tử. Ta chỉ có thể thay đồi giá trị của phần tử trong mảng mà thôi. Tuy nhiên, lợi thế khi sử dụng mảng đó là việc truy xuất các phần tử dễ dàng dựa và chỉ mục.
    Mảng là cấu trúc dữ liệu cơ bản nhất, đơn giản và dễ hiểu nên việc sử dụng cài đặt và sử dụng mảng cũng rất dễ dàng. Mình xin tạm dừng ở đây, trong những bài sau mình sẽ giới thiệu các cấu trúc dữ liệu phổ biến khác.
    Have Fun !
     
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
    Kpwalking and blackarch like this.