Chương 3: CẤU TRÚC DỮ LIỆU ĐỘNG

Giới thiệu khái niệm cấu trúc dữ liệu động.Giới thiệu danh sách liên kết:Các kiểu tổ chức dữ liệu theo DSLK. Danh sách liên kết đơn: tổ chức, các thuật toán, ứngdụng.
Nội dung trích xuất từ tài liệu:
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 // hàm cấp phát bộ nhớ trong C++ new8 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Ví dụ: //Trong C 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( ...