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

Giáo trình Cấu trúc dữ liệu và thuật giải 1: Phần 2 - ĐH Đà Lạt với 1 chương còn lại trang bị cho sinh viên các kiến thức về cách trình bày cấu trúc dữ liệu danh sách liên kết, các cấu trúc đặc biệt của danh sách liên kết đơn, định nghĩa và tổ chức danh sách liên kết,. Tài liệu này giúp ích cho quá trình học tập và giảng dạy. . | TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ THANH BÌNH TRẦN TUẤN MINH GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI 1 Dành cho sinh viên ngành Công Nghệ Thông Tin Đà Lạt - 2010 Cấu trúc dữ liệu và thuật giải 1 Chương 3. Cấu trúc danh sách liên kết Giới thiệu đối tượng dữ liệu con trỏ . Cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động Với kiểu dữ liệu tĩnh, đối tượng dữ liệu được định nghĩa đệ quy, và tổng kích thước vùng nhớ dành cho tất cả các biến dữ liệu tĩnh chỉ là 64Kb (1 segment bộ nhớ). Vì lý do đó, 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 động. Nhằm đáp ứng nhu cầu thể hiện sát thực bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, ta cần phải tìm cách tổ chức kết hợp dữ liệu với những hình thức linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu trúc dữ liệu động. Cấu trúc dữ liệu động cơ bản nhất là danh sách liên kết. . Kiểu con trỏ 1. Biến không động Biến không động (biến tĩnh) là những biến thỏa các tính chất sau: Được khai báo tường minh. Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này. Được cấp phát vùng nhớ trong vùng dữ liệu (Data segment) hoặc là Stack (đối với các biến nửa tĩnh, các biến cục bộ). Kích thước không thay đổi trong suốt quá trình sống. 2. Kiểu dữ liệu con trỏ Khi nói đến kiểu dữ liệu T, ta thường chú ý đến hai đặc trưng quan trọng và liên hệ mật thiết với nhau: Tập V các giá trị thuộc kiểu: đó là tập các giá trị hợp lệ mà đối tượng kiểu T có thể nhận được và lưu .