tailieunhanh - Giáo trình cấu trúc dữ liệu part 3

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu part 3', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Cấu trúc dữ liệu Chương II Các kiểu dữ liệu trừu tượng cơ bản Hình Danh sách liên kết đơn Để quản lý danh sách ta chỉ cần một biến giữ địa chỉ ô chứa phần tử đầu tiên của danh sách tức là một con trỏ trỏ đến phần tử đầu tiên trong danh sách. Biến này gọi là chỉ điểm đầu danh sách Header . Để đơn giản hóa vấn đề trong chi tiết cài đặt Header là một biến cùng kiểu với các ô chứa các phần tử của danh sách và nó có thể được cấp phát ô nhớ y như một ô chứa phần tử của danh sách hình . Tuy nhiên Header là một ô đặc biệt nên nó không chứa phần tử nào của danh sách trường dữ liệu của ô này là rỗng chỉ có trường con trỏ Next trỏ tới ô chứa phần tử đầu tiên thật sự của danh sách. Nếu danh sách rỗng thì Header- next trỏ tới NULL. Việc cấp phát ô nhớ cho Header như là một ô chứa dữ liệu bình thường nhằm tăng tính đơn giản của các giải thuật thêm xoá các phần tử trong danh sách. Ở đây ta cần phân biệt rõ giá trị của một phần tử và vị trí position của nó trong cấu trúc trên. Ví dụ giá trị của phần tử đầu tiên của danh sách trong hình là a1 Trong khi vị trí của nó là địa chỉ của ô chứa nó tức là giá trị nằm ở trường next của ô Header. Giá trị và vị trí của các phần tử của danh sách trong hình như sau Phần tử thứ Giá trị Vị trí 1 ai HEADER 1 2 a2 1 . . . . . . . . . n an n-1 Sau phần tử cuối cùng Không xác định N và n- next có giá trị là NULL Như đã thấy trong bảng trên vị trí của phần tử thứ i là i-1 như vậy để biết được vị trí của phần tử thứ i ta phải truy xuất vào ô thứ i-1 . Khi thêm hoặc xoá một phần tử trong Trang 33 Cấu trúc dữ liệu Chương II Các kiểu dữ liệu trừu tượng cơ bản danh sách liên kết tại vị trí p ta phải cập nhật lại con trỏ trỏ tới vị trí này tức là cập nhật lại p-1 . Nói cách khác để thao tác vào vị trí p ta phải biết con trỏ trỏ vào p mà con trỏ này chính là p-1 . Do đó ta định nghĩa p-1 như là vị trí của p. Có thể nói nôm na rằng vị trí của phần tử ai là địa chỉ của ô đứng ngay phía trước ô chứa ai. Hay chính xác hơn ta nói vị trí của .