Cấu trúc dữ liệu - Mở đầu



Cấu trúc dữ liệu là một khái niệm cơ bản và quan trọng trong khoa học máy tính và lập trình. Nó liên quan đến cách tổ chức, quản lý và lưu trữ dữ liệu sao cho việc truy xuất và xử lý dữ liệu trở nên hiệu quả hơn. Các cấu trúc dữ liệu phổ biến bao gồm mảng, danh sách liên kết, ngăn xếp, hàng đợi, cây và đồ thị. Mỗi loại cấu trúc dữ liệu có những đặc điểm và ứng dụng riêng, giúp giải quyết các vấn đề khác nhau trong lập trình. Hiểu rõ và áp dụng đúng các cấu trúc dữ liệu sẽ giúp lập trình viên tối ưu hóa hiệu suất của các chương trình và hệ thống, cũng như nâng cao khả năng giải quyết vấn đề. 


Các loại cấu trúc dữ liệu
Bây giờ chúng ta đã biết cấu trúc dữ liệu là gì và tại sao chúng quan trọng, hãy đi sâu vào các loại khác nhau. Cấu trúc dữ liệu có thể được phân loại rộng rãi thành:
  1. Primitive Data Structures(cấu trúc dữ liệu nguyên thủy): Đây là các cấu trúc dữ liệu cơ bản bao gồm Số nguyên, Số thực, Ký tự và Boolean.
  2. Non-Primitive Data Structures(cấu trúc dữ liệu không nguyên thủy): Đây là những cấu trúc dữ liệu phức tạp hơn và được phân loại thành:
    • Linear Data Structures(cấu trúc dữ liệu tuyến tính): Trong các cấu trúc dữ liệu này, các phần tử dữ liệu được sắp xếp tuần tự. Ví dụ bao gồm mảng, danh sách liên kết, ngăn xếp và hàng đợi.
    • Non-Linear Data Structures(cấu trúc dữ liệu phi tuyến tính): Ở đây, các phần tử dữ liệu không được đặt theo trình tự. Ví dụ là đồ thị và cây.

Primitive Data Structures(cấu trúc dữ liệu nguyên thủy)

Hãy tưởng tượng bạn đang lập một danh sách mua sắm. Bạn cần gì? Có thể là trái cây, rau củ, đồ ăn nhẹ, có thể là một số dụng cụ vệ sinh. Mỗi mục này có thể được coi là một thành phần dữ liệu riêng lẻ - một khối xây dựng trong danh sách của bạn. Cấu trúc dữ liệu nguyên thủy trong lập trình là tương tự nhau. Chúng là dạng cấu trúc dữ liệu đơn giản nhất và bao gồm:
  • Integers: Hãy coi đây là những con số nguyên, chẳng hạn như số táo bạn cần mua.
  • Float: Đây là những con số thực, chẳng hạn như trọng lượng của quả chuối bạn định mua.
  • Character: Một chữ cái, số hoặc ký hiệu, như 'A' hoặc '3'.
  • Boolean: Loại này chứa giá trị đúng hoặc sai.

Non-Primitive Data Structures(cấu trúc dữ liệu không nguyên thủy)

Ngược lại, cấu trúc dữ liệu không nguyên thủy phức tạp hơn. Chúng có nguồn gốc từ các cấu trúc dữ liệu nguyên thủy và có thể được chia thành các loại tuyến tính(linear) và phi tuyến tính(non-linear).
  • Linear Data Structures
Trong cấu trúc dữ liệu tuyến tính, các phần tử được sắp xếp một cách tuần tự. Hãy nghĩ về chúng như một dòng người đang chờ xe buýt. Một số ví dụ:

        •  Arrays: Hãy tưởng tượng mảng giống như một dãy tủ khóa. Mỗi tủ chứa một vật phẩm và được xác định bằng một số duy nhất.
        • Linked Lists: Hãy tưởng tượng một chuỗi trong đó mỗi mắt xích được nối với mắt xích tiếp theo.
        • Stacks and Queues: Stacks giống như một chồng sách, nơi bạn chỉ có thể tương tác với cuốn sách trên cùng. Mặt khác, Queues giống như hàng đợi ở cửa hàng tạp hóa - người xếp hàng đầu tiên sẽ được phục vụ trước.
      • Non-Linear Data Structures
      Cấu trúc dữ liệu phi tuyến tính, như tên gọi của nó, không duy trì một trình tự cụ thể để sắp xếp các phần tử. Những ví dụ bao gồm:
          • Trees: Hãy nghĩ về một cây gia phả trong đó mỗi người là một nút có mối liên hệ với cha mẹ và con cái của họ.
          • Graphs: Chúng giống như mạng xã hội, nơi mỗi người (nút) có thể được kết nối với nhiều người (nút) khác.

         Ở đây chúng ta chỉ mới tìm hiểu sơ qua về cấu trúc dữ liệu. Khi tìm hiểu sâu hơn về từng loại, bạn sẽ hiểu rõ hơn về cách chúng hoạt động và nơi chúng có thể được áp dụng.

         

         



        Nhận xét

        Đăng nhận xét

        Bài đăng phổ biến từ blog này

        Cài đặt SSL cho website sử dụng certbot

        Hình ảnh
        1. SSL là gì. Trước khi nói về ssl chúng ta nhắc lại về HTTP là gì đã nhé.HTTP là giao thức dùng để truyền nhận dữ liệu.Nhược điểm của http là dữ liệu được truyền dưới dạng plain text, không hề được mã hóa hay bảo mật nên nếu gói tin chúng ta gửi bằng http bị tin tặc bắt được thì mọi thông tin sẽ bị lộ. SSL viết tắt của cụm từ Secure Sockets Layer là tiêu chuẩn về an ninh công nghệ trên toàn cầu, nói dễ hiểu thì ssl thực hiện mã hóa thông tin truyền nhận, các dữ liệu được gửi qua phương thức này sẽ được mã hóa, website của bạn nếu sử dụng ssl thì sẽ có https trên url.Nhìn chung phương thức https có độ bảo mật cao hơn nhiều so với http, mặc dù không phải tuyệt đối. 2.Cài đặt SSL. A.Trước tiên chúng ta cần cài đặt nginx để làm web server Đối với ubuntu thì các bạn chạy các lệnh sau: $ sudo apt update $ sudo apt install nginx $ sudo ufw allow 'Nginx HTTP' Đối với Centos thì các bạn chạy lệnh : $ sudo yum install epel-release $ sudo yum install nginx $ sudo systemctl start nginx N
        Read more »

        Xây dựng một hệ thống comment real-time hoặc chat đơn giản sử dụng Pusher

        Hình ảnh
        Hế lô các bạn, các bạn khỏe không?Sau một thời gian nghỉ ngơi vì dịch nên mình đã quên hết code rồi :)).Sợ code không nổi nữa nên nay lên mò mò làm một app chat đơn giản cho đỡ lụt nghề.Lên mạng đọc tới đọc lui thấy khó thực sự =)).Bất ngờ đọc được một vài bài giới thiệu pusher nên mình cũng lọ mọ thử viết một cái ai ngờ nó chạy được nên tranh thủ viết lại cho cho các bạn cùng xem cho vui. 1.Pusher là gì? Pusher là một dịch vụ cloud, tạo ra một server trung gian giúp chúng ta có thể xử lý các tác vụ thời gian thực. Dữ liệu được gửi tới pusher, và pusher lại gửi nó đi tới các client đã subscribe (đăng ký) và các channel. Trong đó Pusher Channel cung cấp giao tiếp thời gian thực giữa các máy chủ, ứng dụng và thiết bị. Các kênh được sử dụng cho các biểu đồ thời gian thực, danh sách người dùng thời gian thực, bản đồ thời gian thực, chơi trò chơi nhiều người chơi và nhiều loại cập nhật giao diện người dùng khác. Nó có một thư viện hỗ trợ mọi thứ như trình duyệt web, ứng dụng iOS và Andr
        Read more »

        CÁC BÀI TẬP SQL CƠ BẢN - PART 1

        Hình ảnh
          Thời gian gần đây mình có được nhờ giải mấy bài SQL cho các em, lâu không làm lại, thấy khá thú vị nên hôm nay lên mạng tìm mấy bài làm cho zui.Mình viết lại đây coi như note lại để lưu lại,các bạn cùng làm với mình nhé Đề 1: Giải thích qua về đề bài. Query 2 thành phố có tên ngắn nhất và dài nhất  cùng với số ký tự trong tên của 2 thành phố ấy trong bảng STATION. Đáp án : SELECT CITY, LENGTH (CITY) FROM STATION ORDER BY LENGTH (CITY) ASC , CITY LIMIT 1; SELECT CITY, LENGTH (CITY) FROM STATION ORDER BY LENGTH (CITY) DESC , CITY LIMIT 1; Đề 2: Giải thích qua về đề bài : Query danh sách tên thành phố bắt đầu bằng các nguyên âm (a, e, i, o, u) Đáp án : SELECT DISTINCT CITY FROM STATION WHERE CITY LIKE "A%" OR CITY LIKE "E%" OR CITY LIKE "I%" OR CITY LIKE "O%" OR CITY LIKE "U%" ; Đề 3:  Giải thích đề bài : Query danh sách tên thành phố kết thúc bằng các nguyên âm (a, e , i, o,u), tương tự bài trên chỉ cần đổi logi
        Read more »

        Xây dựng một hệ thống tracking hành vi người dùng (phần 1)

        Hình ảnh
         Hiện nay trên các trang thương mại điện tử việc tracking hành vi người dùng rất là phổ biến vậy nên hôm nay mình sẽ viết một bài viết về hệ thống tracking đơn giản đã từng được sử dụng trên một website thương mại điện tử nhé.Ngôn ngữ mình sử dụng trong bài viết này là ruby(ruby on rails) 1.Sơ đồ tổng quan hệ thống <Image invalid> 2.Triển khai project Mô tả sơ qua về cách xây dựng hệ thống(bỏ qua các giai đoạn xây dựng xác thực tài khoản và phân quyền,vì chỉ là thành phần phụ trợ). Tạo tag -> lưu tag vào database -> render thành file js với đầu vào là các tag được tạo từ  trước 2.1.Các model tương ứng Tag model class Tag include Mongoid::Document include Mongoid::Timestamps belongs_to :user field :name, type: String, default: "" field :selector, type: Hash, default: {} field :trigger, type: Hash, default: {} field :handle, type: Hash, default: {} field :author, type: String, default: "" end User
        Read more »

        Xây dựng một hệ thống tracking hành vi người dùng (phần 2)

        Hình ảnh
        Các bạn có thể xem lại phần 1 tại đây. Sau khi đã có được các tag tiến hành xây dựng các Helper để hỗ trợ việc render ra file tracking.js Helper này có nhiệm vụ xử lý các logic của file tracking.js nhưng nếu xử lý trực tiếp trên file js thì nó quá dài dòng và dễ bị lộ logic của file. JS helper module JsHelper def renderBindClicks(tags) click_tags = tags.inject([]) do |click_tags, tag| if tag&.trigger[:value] == 'click' event_type = tag&.selector[:dom] selector = if event_type == "classes element" ".#{tag&.selector[:value]}" elsif event_type == "id element" "\##{tag&.selector[:value]}" end if selector.present? click_tags << "'#{selector}'" end end click_tags end if click_tags.present? return "[#{click_tags.uniq.join(', ')}].forEach(bindClick);".html_safe end
        Read more »

        Enterprise architecture trên 1 tờ A4

        Hình ảnh
        Enterprise architecture là một chủ đề rộng và có rất nhiều quan điểm chi phối và thực thi. Trên thực tế có rất nhiều quan điểm về vấn đề này, mình xin giới thiệu qua một quan điểm khá hay ho trong hình dưới đây. Nếu khó nhìn các bạn có thể tải về máy và phóng to lên nhé !
        Read more »

        Web caching (P2)

        Hình ảnh
        Sau khi đọc Web caching (P1), chúng ta đã hiểu đường tác dụng, cơ chế của việc caching và đi chi tiết về Browser caching và CDN caching. Ở phần 2 chúng ta sẽ tìm hiểu về server caching và cách vận dụng linh hoạt caching để giải quyết các bài toàn performance. Mục lục Reverse proxy caching. Application caching. Áp dụng bài toán thực tế. Lời kết 1.Reverse proxy caching Reverse Proxy là gì? - Là một loại proxy server trung gian giữa một server và các clients gửi request. - Nó kiểm soát yêu cầu của các clients, nếu hợp lệ, sẽ luân chuyển đến các servers thích ứng. - Ưu điểm lớn nhất của việc sử dụng Reverse proxy là khả năng quản lý tập trung. Nó giúp kiểm soát mọi requests do clients gửi lên servers. Cơ chế: - Tương tự như Browser caching và CDN caching. Reverse proxy cache lại tất cả các request resources(image, css, js, ...) và trả lại client ở tầng Proxy. Ưu điểm: - Giảm lượng request lên server. - Có thể quản lý được cache. Nhược điểm:
        Read more »

        Bàn về async/await trong vòng lặp javascript

        Hình ảnh
          Lâu nay mình đang phải làm một dự án sdk javascript nên khá đau đầu với cái bất đồng bộ trong vòng lặp của  javascript.Để tránh quên nên mình viết lên đây cho đỡ quên.Bài viết này mình chỉ viết về một số ví dụ sử dụng async/await cho dễ hiểu nhé. 1. Chuẩn bị cho ví dụ sắp tới Giả sử chúng ta có một giỏ trái cây và số lượng của từng trái cây trong giỏ const fruitBasket = { apple: 27, grape: 0, pear: 14 } Bây giờ mình muốn lấy số lượng hoa quả trong giỏ mình sẽ viết một hàm như sau  const getNumFruit = fruit => { return fruitBasket[fruit] } const numApples = getNumFruit('apple') console.log(numApples) Giờ giả sử fruitBasket được lấy từ server chứ không phải mình khai báo biến như trên nữa việc lấy dữ liệu sẽ mất một vài giây, mình sẽ giả lập công việc lấy dữ liệu từ server như sau const sleep = ms => { return new Promise(resolve => setTimeout(resolve, ms)) } const getNumFruit = (s, fruit) => { return sleep(s).then(v =&
        Read more »

        Web caching (P1)

        Hình ảnh
        Câu chuyện hư cấu 1: A: *** hiểu sao code tao chỉnh sửa rồi mà deploy lên *** thấy thay đổi gì? B: Mày đã xóa cache chưa vậy? A: Làm sao để biết có cache hay không. Mà cache làm *** gì để suốt ngày phải xóa. Mất công, mất việc. One few moments later ... A: Xóa hết cache trình duyệt rồi, sao vẫn ko thay đổi code đã chỉnh sửa mày ơi. B: Ờ, cũng *** biết, đọc bài ở dưới xem sao :)) Câu chuyện hư cấu 2: C: Sao dạo này con web của tao nó chạy chậm thế nhờ? Có cách nào ko mày? D: Thế mày đã caching cho nó chưa? C: Tao đang nói web chạy chậm mà, có khi do code lởm mà, cache ciếc gì ở đây. Mà cache là cái gì vậy? D: Thôi đọc bài ở dưới đi rồi nói chuyện tiếp :)) Ok, qua 2 câu chuyện hư cấu trên, chắc các bạn cũng mường tượng được ưu, nhược điểm của Caching rồi đúng không? Vậy trong bài viết này, mình sẽ trình bày về Caching để các bạn hiểu vì sao nó lại quyền năng mà cũng lại rắc rối như thế.Hôm nay chúng ta cùng tìm hiểu về vấn đề này nhé. Mục lục Đường đi của 1 reques
        Read more »

        Cài đặt môi trường để code website Rails

        Hình ảnh
        Để xây dựng một website bẳng rails đầu tiên chúng ta cần phải xây dựng môi trường đúng chứ.Bài này mình sẽ hướng dẫn các bạn cài đặt môi trường để làm việc nhé. 1.Hệ điều hành Để làm việc được đơn giản mình gợi ý là dùng ubuntu,nếu bạn nào dùng mac thì quá tuyệt rồi.Mình không có tiền mua mac để code nên mình cài ubuntu để làm việc nhé,bạn nào có sử dụng window mà không muốn đổi hệ điều hành thì mình gợi ý nên sử dụng wubi để cài song song ubuntu nghịch cho biết, đây là bài hướng dẫn cài wubi nhé các bạn . 2.Cài đặt ruby Rails là một framework xây dựng website của ngôn ngữ ruby nên chắc chắn chúng ta phải cài ruby để làm việc rồi.Để cài đặt ruby chúng ta làm như sau: +,Bước đầu cần cài node và các công cụ phụ trợ của node curl -sL https://deb.nodesource.com/setup_8.x | sudo -E bash - curl -sS https://dl.yarnpkg.com/debian/pubkey.gpg | sudo apt-key add - echo "deb https://dl.yarnpkg.com/debian/ stable main" | sudo tee /etc/apt/sources.list.d/yarn.list s
        Read more »