Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PPT | Số trang:19

Thêm vào BST

Báo xấu

96
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết" cung cấp cho người học các kiến thức: Đặt vấn đề, khái niệm về biến con trỏ, danh sách liên kết, ứng dụng của DSLK, một số CTDL khác dựa trên danh sách, giới thiệu Stack, Queue. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết

CHƯƠNG Click To Edit Master 3Title Style DANH SÁCH LIÊN KẾT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 1
Click To NỘI Edit DUNG Master Title Style  3.1. Đặt vấn đề  3.2. Khái niệm về biến con trỏ  3.3. Danh sách liên kết  3.4. Ứng dụng của DSLK  3.8. Một số CTDL khác dựa trên danh sách CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  3.9. Giới thiệu Stack, Queue Cấu trúc dữ liệu 1 2
3.1. Click To ĐặtMaster Edit vấn đềTitle Style  Mảng 1 chiều  Kích thước cố định (fixed size)  Chèn 1 phần tử vào mảng rất khó  Các phần tử tuần tự theo chỉ số 0 n-1  Truy cập ngẫu nhiên (random access) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT chèn Cấu trúc dữ liệu 1 0 1 2 3 4 n-2 n-1 3
BiếnClick Tĩnh To Edit Master Title Style  Được khai báo tường minh, có tên gọi  Tồn tại trong phạm vi khai báo  Được cấp phát trong stack  Kích thước không đổi => không tận dụng hiệu quả bộ nhớ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Ví dụ : int x,y; char c; Cấu trúc dữ liệu 1 float f[5];  Khi biết chắc nhu cầu sử dụng đối tượng trước khi thực sự xử lý : dùng biến không động 4
Click Ví Dụ To Của Hạn Chế EditBiến Master Tinh Title Style  Tổ chức danh sách lớp học  Dùng mảng tĩnh : typedef struct { char ten[20]; int maso; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT }Hocvien; Hocvien danhsach[50]; Cấu trúc dữ liệu 1  Số lượng học viên lãng phí  Số lượng học viện > 50 => thiếu chỗ ! 5
BiếnClick Động To Edit Master Title Style  Không được khai báo tường minh, không có tên gọi  Xin khi cần, giải phóng khi sử dụng xong  Được cấp phát trong heap CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Linh động về kích thước Cấu trúc dữ liệu 1  Vấn đề : biến động không có tên gọi tường minh, làm sao thao tác ? 6
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 3.2. Khái Click To niệm về biếnTitle Edit Master con Style trỏ 7
KiểuClick con trỏTo Edit Master Title Style  Kiểu con trỏ 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ỏ Tp là biến mà giá trị của nó là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL.  Khai báo trong C : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT typedef int *intpointer; intpointer p; Cấu trúc dữ liệu 1  Bản thân biến con trỏ là không động  Dùng biến con trỏ để lưu giữ điạ chỉ của biến động => truy xuất biến động thông qua biến con trỏ 8
CácClick thao tácTo Edit trên kiểu Master con trỏ Title Style  Tạo ra một biến động và cho con trỏ ‘p’ chỉ đến nó:  void* malloc(size);  void* calloc(n,size);  new // hàm cấp phát bộ nhớ  Hủy một biến động do p chỉ đến : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc hoặc calloc do p trỏ tới Cấu trúc dữ liệu 1  Hàm delete p huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới 9
Clickbiến Sử dụng Totinh, Edit conMaster Title trỏ và biến độngStyle int x; Biến không động x x = 5 ; 5 int *p; Biến con trỏ p 0xFF p = new(int); CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT *p = 5 0xFF Cấu trúc dữ liệu 1 5 Bieán ñoäng coù ñòa chæ 0xFF 10
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 3.3.To Click Danh Edit sách liênTitle Master kết Style 11
KiểuClick To Edit danh sách Master Title Style  Danh sách = { các phần tử có cùng kiểu}  Danh sách là một kiểu dữ liệu tuyến tính :  Mỗi phần tử có nhiều nhất 1 phần tử đứng trước  Mỗi phần tử có nhiều nhất 1 phần tử đứng sau CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Là kiểu dữ liệu quen thuộc trong thực tế :  Danh sách học sinh Cấu trúc dữ liệu 1  Danh mục sách trong thư viện  Danh bạ điện thoại  Danh sách các nhân viên trong công ty 12
CácClick TotổEdit hình thức chứcMaster danh sáchTitle Style  CTDL cho mỗi phần tử ?  Thể hiện liên kết của các phần tử ?  Hai hình thức cơ bản : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Liên kết ngầm : Mảng Cấu trúc dữ liệu 1  Liên kết tường minh : Danh sách liên kết 13
Click Danh To kết sách liên Edit Master Title ngầm(mảng) Style  Mối liên hệ giữa các phần tử được thể hiện ngầm:  xi : phần tử thứ i trong ds x0 … xi xi+1  xi , xi+1 là kế cận trong danh sách  Phải lưu trữ liên tiếp các phần tử trong bộ nhớ  công thức xác định địa chỉ phần tử thứ i: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT address(i) = address(1) + (i-1)*sizeof(T)  Ưu điểm : Truy xuất trực tiếp, nhanh chóng Cấu trúc dữ liệu 1  Nhược điểm:  Sử dụng bộ nhớ kém hiệu quả  Kích thước cố định  Các thao tác thêm vào, loại bỏ không hiệu quả 14
LiênClick Tominh(Danh kết tuờng Edit Master Title sánh liên kết)Style  CTDL cho một phần tử  Thông tin bản thân  Địa chỉ của phần tử kế trong danh sách x2 x0 x3 x1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Mỗi phần tử là một biến động Cấu trúc dữ liệu 1  Ưu điểm + Sử dụng hiệu quả bộ nhớ + Linh động về số lượng phần tử 15
CácClick Tosách loại danh EditliênMaster kết Title Style  Danh sách liên kết Đơn: Mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách A B C D  Danh sách liên kết Kép: Mỗi phần tử liên kết với CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT phần tử đứng trước và sau nó trong danh sách A B C D Cấu trúc dữ liệu 1  Danh sách liên Vòng: Phần tử cuối danh sách liên với phần tử đầu danh sách 16
CácClick Tosách loại danh EditliênMaster kết (tt) Title Style  Danh sách liên Vòng: Phần tử cuối danh sách liên với phần tử đầu danh sách  Danh sách liên kết đơn vòng A B C D CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Danh sách liên kết đôi vòng Cấu trúc dữ liệu 1 A B C D 17
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 3.4. To Click Ứng dụng Edit của DSLK Master Title Style 18
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 3.8.Click Một sốToCTDL khác dựa Edit Master Titletrên ds Style 19