- Chương 3: Cấu trúc dữ liệu. - 3.4 Nội dung và mục đích của cấu trúc dữ liệu 3.4 Cài đặt một số cấu trúc với C++. - Phần lớn các bài toán trong thực tế liên quan tới các dữ liệu phức hợp, những kiểu dữ liệu cơ bản trong ngôn ngữ lập trình không đủ biểu diễn. - Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV,.... - Phương pháp biểu diễn dữ liệu: định nghĩa kiểu dữ liệu mới sử dụng cấu trúc (struct, class, union,. - Đa số những dữ liệu thuộc một ứng dụng có liên quan với nhau =>. - Danh sách sinh viên: Các dữ liệu sinh viên được sắp xếp theo thứ tự Alphabet. - Vấn đề: Biểu diễn tập hợp dữ liệu. - Vấn đề: Quản lý dữ liệu. - Sử dụng kết hợp một cách khéo léo kiểu cấu trúc và kiểu mảng đủ để biểu diễn các tập hợp dữ liệu bất kỳ. - Các giải thuật (hàm) thao tác với dữ liệu, nhằm quản lý dữ liệu một cách hiệu quả:. - Bổ sung một mục dữ liệu mới vào một danh sách, một bảng, một tập hợp,. - Xóa một mục dữ liệu trong một danh sách, bảng, tập hợp,... - Tìm một mục dữ liệu trong một danh sách, bảng tập hợp,.... - Hiệu quả quản lý dữ liệu phụ thuộc vào. - Cấu trúc dữ liệu được sử dụng. - Giải thuật được áp dụng cho bổ sung, tìm kiếm, sắp xếp, xóa bỏ. - Các cấu trúc dữ liệu thông dụng. - Mảng (nghĩa rộng): Tập hợp các dữ liệu có thể truy nhập tùy ý theo chỉ số. - Danh sách (list): Tập hợp các dữ liệu được móc nối đôi một với nhau và có thể truy nhập tuần tự. - Cây (tree): Tập hợp các dữ liệu được móc nối với nhau theo cấu trúc cây, có thể truy nhập tuần tự từ gốc. - Hàng đợi (queue): Tập hợp các dữ liệu có sắp xếp tuần tự, chỉ bổ sung vào từ một đầu và lấy ra từ đầu còn lại. - Ngăn xếp (stack): Tập hợp các dữ liệu được sắp xếp tuần tự, chỉ truy nhập được từ một đầu. - Mảng cho phép biểu diễn và quản lý dữ liệu một cách khá hiệu quả:. - Đọc và ghi dữ liệu rất nhanh qua chỉ số hoặc qua địa chỉ – Tiết kiệm bộ nhớ. - Toán tử new chấp nhận kiểu dữ liệu phần tử kèm theo số lượng phần tử của mảng cần cấp phát bộ nhớ (trong vùng heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công.. - Các giải thuật sắp xếp cơ bản. - Các giải thuật sắp xếp nâng cao-Sắp xếp nhanh. - Vấn đề phối hợp với các giải thuật đơn giản khác:. - Giải thuật tương đối phức tạp =>. - Nhận xét các giải thuật sắp xếp. - Các giải thuật sắp xếp đơn giản. - Các giải thuật sắp xếp nâng cao. - Giải thuật tìm kiếm chia đôi. - Ý tưởng giải thuật. - Củng cố và nâng cao kiến thức cơ bản về cấu trúc dữ liệu và giải thuật của ngành khoa học máy tính.. - Giới thiệu các cấu trúc dữ liệu từ đơn giản (các cấu trúc tuyến tính như : mảng, danh sách) đến phức tạp (các cấu trúc phi tuyến như: cây, đồ thị) và các thao tác cơ bản tương ứng trên các cấu trúc dữ liệu.. - Tìm hiểu các giải thuật từ cơ bản như các giải thuật sắp xếp, tìm kiếm, đến một số giải thuật nâng cao như các giải thuật đệ quy, các giải thuật trên các cấu trúc dữ liệu cây, đồ thị. - Nắm được cách tổ chức và cài đặt cho cấu trúc danh sách sinh viên nói riêng, khái quát hơn là cho cấu trúc danh sách nói chung cần nắm được cấu trúc dữ liệu. - Nắm được ý tưởng và cách cài đặt cho các thao tác cơ bản như tìm kiếm, sắp xếp cần nắm được giải thuật. - Các khái niệm cơ bản về CTDL và giải thuật. - Giải thuật (algorithm):. - Giải thuật. - Một số yêu cầu của giải thuật. - Có mô tả các đối tượng dữ liệu mà thuật toán sẽ thao tác như dữ liệu vào (nguồn), dữ liệu ra (đích) và các dữ liệu trung. - Dữ liệu. - Dữ liệu (data):. - Dữ liệu gồm có hai mặt:. - Cấu trúc dữ liệu. - Cấu trúc dữ liệu (data structure. - Là kiểu dữ liệu mà bên trong nó có chứa nhiều thành phần dữ liệu và các thành phần dữ liệu đấy được tổ chức theo một cấu trúc nào đó. - Cấu trúc dữ liệu thể hiện khía cạnh logic của dữ liệu.. - Còn các dữ liệu không có cấu trúc được gọi là các dữ liệu vô hướng hay các dữ liệu đơn giản. - VD: các kiểu dữ liệu số nguyên (integer), số thực (real), logic (boolean) là các kiểu dữ liệu đơn giản.. - Có hai loại cấu trúc dữ liệu chính:. - Cấu trúc tuyến tính: là cấu trúc dữ liệu mà các phần tử bên trong nó luôn được bố trí theo một trật tự tuyến tính hay trật tự trước sau. - Đây là loại cấu trúc dữ liệu đơn giản nhất.. - Cấu trúc lưu trữ của một cấu trúc dữ liệu thể hiện khía cạnh vật lý (cài đặt) của cấu trúc dữ liệu đó.. - Tuy nhiên trong thực tế sử dụng, cấu trúc lưu trữ thường được hiểu là cấu trúc kiểu dữ liệu mà một ngôn ngữ lập trình hỗ trợ, và số lượng các cấu. - trúc lưu trữ thường là số lượng các kiểu dữ liệu của ngôn ngữ lập trình đó cuu duong than cong . - CTLT này có tính lưu tồn và cho phép chúng ta lưu trữ các dữ liệu có kích thước rất lớn.. - Cấu trúc lưu trữ tĩnh: là CTLT mà kích thước dữ liệu luôn cố định. - Cấu trúc lưu trữ động: là CTLT mà kích thước dữ liệu có thể thay đổi trong khi chạy chương trình. - Ngôn ngữ diễn đạt giải thuật. - Có hai nguyên tắc cần lưu ý khi chọn ngôn ngữ diễn đạt giải thuật:. - Các loại ngôn ngữ diễn đạt giải thuật. - Lưu đồ giải thuật:. - Sử dụng các hình vẽ, biểu tượng để biểu diễn cho các thao tác của giải thuật. - Các thành phần cơ bản của lưu đồ giải thuật. - Điểm bắt đầu giải thuật Điểm kết thúc giải thuật. - Thiết kế và Phân tích giải thuật. - Thiết kế giải thuật. - Hay nói đúng hơn là thiết kế cấu trúc chương trình mà cài đặt giải thuật. - Trong giai đoạn này, chúng ta phải tìm cách biến đổi từ đặc tả giải thuật (mô tả giải thuật làm cái gì, các bước thực hiện những gì) thành một chương trình được viết bằng một ngôn ngữ lập trình cụ thể (giải thuật được cài đặt như thế nào) mà có thể chạy tốt trên máy tính (minh hoạ hoạt động cụ thể của giải thuật).. - Thiết kế sơ bộ: đây là giai đoạn cần tìm hiểu cặn kẽ các thành phần của giải thuật. - Mỗi thành phần cơ bản được goi là một mô dul của giải thuật. - chỉnh thực hiện giải thuật ban đầu. - Chúng ta sẽ chia giải thuật ban đầu thành các giải. - thuật con (mô dul), mỗi giải thuật con sẽ thực hiện một phần chức năng của giải thuật ban đầu. - Trong bước đầu tiên, ta có đặc tả giải thuật bằng ngôn ngữ tự nhiên hay lưu đồ giải thuật. - Lặp lại quá trình trên cho đến khi tạo ra một chương trình hoàn chỉnh có thể chạy được, thực hiện giải thuật yêu cầu cuu duong than cong . - Phân tích giải thuật. - Các phương pháp phân tích giải thuật. - thước dữ liệu vào của giải thuật A (nếu không có gì nhầm lẫn giải thuật thì ta kí hiệu ngắn gọn là T(n)).. - Nên để biểu diễn độ phức tạp của giải thuật ta luôn chọn f(n) nhỏ nhất và đơn giản nhất sao cho T(n. - 4 Một số cấu trúc dữ liệu. - Là tập hợp các phần tử dữ liệu không liên tục được kết nối với nhau thông qua một liên kết (thường là con trỏ). - Dữ liệu trong nút. - Giải thuật thêm một phần tử vào danh sách liên kết. - Các thao tác với dữ liệu trên Node. - Mỗi node trong list chỉ chứa một dữ liệu thuộc kiểu int.. - list Dữ liệu node. - Giải thuật:. - Giải thuật: node. - Mục đích: trả về một phần tử có dữ liệu bằng dữ liệu cho trước. - Các thao tác cơ bản - Giải thuật duyệt cây. - Giải thuật duyệt theo thứ tự trước (preorder traversal, còn gọi là duyệt cây theo chiều sâu): đây là giải thuật đệ quy. - Giải thuật duyệt cây. - Giải thuật duyệt theo thứ tự giữa (inorder travelsal): đây là giải thuật đệ quy.. - Giải thuật duyệt theo thứ tự sau (postorder travelsal): đây là giải thuật đệ quy.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt