tailieunhanh - Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2

Ebook Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2 trình bày những kiến thức về cấu trúc dữ liệu động và cấu trúc cây. Qua các nội dung chi tiết này, người học có thể hiểu được: Kiểu dữ liệu con trỏ, danh sách liên kết (Link list), danh sách đơn, một số cấu trúc dữ liệu dạng danh sách liên kết khác, cấu trúc cây, cây nhị phân, cây nhị phân tìm kiếm, cây nhị phân tìm kiếm. . | CHƯƠNG 3 CẤU TRÚC DỮ LIỆU ĐỘNG Mục tiêu Giới thiệu khái niệm cáu trúc dữ liệu động. Danh sách liên kết tổ chức các thuật toán ứĩ g dụng. I. ĐẶT VẤN ĐỀ Với các cấu trúc dừ liệu được xáy dựng từ các kiểu cơ sở như kiếu thực kiểu nguyên kiểu ký tự . hoác từ các cấu trúc đơn giản như mẩu tin tập hợp mảng . lập trình viên có thể giải quyết hầu hết các bài toán đạt ra. Các đối tượng dừ liệu được xác định thuộc những kiểu dừ liệu này có đậc điểm chung là không thay đổi được kích thước cấu trúc trong quá trình sống do vậy thường cứng nhấc gò bó khiến đôi khi khó diên tà được thực tế vốn sinh động phong phú. Các kiểu dừ liệu kể trên được gọi là các kiểu dữ liệu tĩnh. Ví du. 1. Trong thực tế một sô đối tượng có thể được định nghĩa đệ qui ví dụ để mô tả đối tượng con người cán thể hiện các thông tin tối thiểu như Họ tên Số CMND 97 Thông tin về cha mẹ Để biều diễn một đối tượng có nhiều thành phắn thông tin như trèn có thể sử dụng kiểu mấu tin. Tuy nhièn cổn lưu ý cha mẹ cùa một người cũng là các đối tưựng kiểu NGƯỜI do vậy vé nguyên tắc cần phải có định nghĩa như sau typedef struct NGUOI char HotenOOJ intSoCMND NGUOI Cha Me I Tuy nhicn với khai báo trèn các ngôn ngữ lập trình gặp khó khản trong việc cài đặt không vượt qua được như xác định kích thước cùa đối tượng kiểu NGƯOI 2. Một số đối tượng dừ liệu trong chu kỳ sống cùa nó có thể thay đổi vẻ cấu trúc độ lớn như danh sách các học viên trong một lớp học có thể tâng thêm giảm di . Khi đó nếu CỐ tình dùng những cấu trúc dử liệu tĩnh đã biết như màng để biểu diẻn nhưng đôi tượng do lập trình viên phâi sử dụng những thao tác phức tạp kém tự nhiên khiến chương . trình ườ nên khó đọc do đó khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách cố hiệu quả. 3. Một lý do nữa làm cho các kiểu dừ liệu tình khỗng thể đáp ứng được nhu cầu cùa thực tê là tổng kích thước vùng nhớ dành cho tát cà các biến tĩnh chỉ là 64kb 1 Segment bộ nhớ . Khi có nhu cầu dùng nhiều bộ nhớ hơn ta phải sử dụng các cấu trúc dữ liệu dộng. 4. Cuối cùng do