Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Cấu trúc dữ liệu động

Chương 3 trình bày về cấu trúc dữ liệu động với các nội dung chi tiết như: Kiểu dữ liệu con trỏ, danh sách liên kết (link list), danh sách liên kết đơn, sắp xếp danh sách, các cấu trúc đặc biệt của danh sách liên kết đơn. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Cấu trúc dữ liệu động Chương 3: CẤU TRÚC DỮ LIỆU ðỘNG 3.1. Kiểu dữ liệu con trỏ 3.2. Danh sách liên kết (link list) 3.3. Danh sách liên kết ñơn 3.4. Sắp xếp danh sách 3.5. Các cấu trúc ñặc biệt của danh sách liên kết ñơn 3.5.1. Stack 3.5.2. Hàng ñợi (Queue) 3.6. Bài tập1 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.1. Kiểu Dữ Liệu Con Trỏ 3.1.1. Biến không ñộng 3.1.2. Kiểu con trỏ 3.1.3. Biến ñộng2 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.1.1. Biến không ñộng Dùng ñề lưu trữ những ñối tượng dữ liệu ñược sử dụng không có nhu cầu thay ñổi và kích thước, số lượng . . . • ðược khai báo tường minh • Tồn tại trong phạm vi khái báo • Kích thước không thay ñổi trong suốt quá trình sống Ví dụ: int a; char b[10];3 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.1.2. Kiểu con trỏ Kiểu con trỏ là kiểu cơ sở dùng lưu ñịa chỉ của một ñối tượng dữ liệu khác. Biến thuộc kiểu con trỏ là biến mà giá trị của nó là ñịa chỉ một vùng nhớ của một biến hoặc là giá trị Null. Tùy vào loại con trỏ gần (near pointer) hay con trỏ xa (far pointer) mà kiểu dữ liệu con trỏ có các kích thước khác nhau: + Con trỏ gần: 2 bytes + Con trỏ xa: 4 bytes4 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Cú pháp ñịnh nghĩa một kiểu con trỏ typedef *; Ví dụ: typedef int *intpointer; inpointer p; Hay int *p; Các thao tác: - Khi 1 biến con trỏ p lưu ñịa chỉ của ñối tượng x, ta nói “p trỏ x” - Gán ñịa chỉ của biến cho con trỏ p: p=& -Truy xuất nội dung của ñối tượng do p trỏ ñến *p5 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM c. Ví dụ: void main() { int a,b,*pa,*pb; a=2; b=3; cout 3.1.3. Biến ñộng Trong trường hợp, tại thời ñiểm biên dịch không thể xác ñịnh trước kích thước chính xác của ñối tượng dữ liệu (do chúng phụ thuộc vào ngữ cảnh). Các ñối tượng dữ liệu này ñược khai báo như biến ñộng. Biến ñộng là những biến thỏa: Không ñược khai báo tường minh. ðược cấp phát/giải phóng bộ nhớ khi yêu cầu. Các biến này không theo qui tắc phạm vi. Vùng nhớ của biến ñược cấp phát trong Heap. Kích thước thay ñổi trong quá trình sống.7 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Các thao tác trên biến ñộng: Tạo biến ñộng và cho con trỏ p trỏ ñến: Các hàm cấp phát bộ nhớ: void* malloc(size); // trả về con trỏ chỉ ñến một vùng // nhớ size byte vừa ñược cấp phát. void* calloc(n,size);// trả về con trỏ chỉ ñến một vùng // nhớ vừa ñược cấp phát gồm n //phần tử,mỗi phần tử có kích //thước size byte new // hàm cấp phát bộ nhớ trong C++8 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Hủy một biến ñộng do p chỉ ñến: Hàm free(p): Huỷ vùng nhớ cấp phát bởi hàm malloc do p trỏ tới Hàm delete p: huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới9 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Ví dụ: int* p1, p2; //Cấp phát vùng nhớ cho 1 biến ñộng kiểu int p1 = (int*)malloc(sizeof(int)); //ðặt giá trị 5 cho biến ñộng p1 p1* = 5; //Cấp phát biến ñộng kiểu mảng 10 p.tử kiểu int p2 = (int*)calloc(10, sizeof(int)); //ðặt giá trị 0 cho phần tử thứ 4 của mảng p2 (p2+3)* = 0; free(p1); free(p2);10 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.2. Danh Sách Liên Kết 3.2.1. Ðịnh nghĩa 3.2.2. Các hình thức tổ chức danh sách11 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.2.1. Ðịnh nghĩa Kiểu danh sách Tx gồm các phần tử thuộc kiểu ...