zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết - Lê Thị Ngọc Hạnh

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:22

Báo xấu

70
lượt xem 3
download

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

Chương này cung cấp những kiến thức về danh sách liên kết trong cấu trúc dữ liệu và giải thuật. Những nội dung chính gồm có: Cấp phát động và cấp phát tĩnh, con trỏ và cấp phát động, danh sách liên kế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: Danh sách liên kết - Lê Thị Ngọc Hạnh

DANH SÁCH LIÊN KẾT GV: LÊ THỊ NGỌC HẠNH 1 9/10/2015 Data structure & Algorithms
NỘI DUNG  Cấp phát động và cấp phát tĩnh  Con trỏ và cấp phát động  Danh sách liên kết 9/10/2015 Data structure & Algorithms 2
BIẾN TĨNH  Đượ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.  Kích thước không thay đổi trong suốt quá trình sống. 9/10/2015 Data structure & Algorithms 3
BIẾN ĐỘNG  Không được khai báo tường minh  Có thể được cấp phát hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu.  Các biến này không theo quy tắc phạm vi (tĩnh)  Vùng nhớ của biến được cấp phát trong Heap.  Kích thước có thể thay đổi trong quá trình sống 9/10/2015 Data structure & Algorithms 4
CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 5
CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 6
CON TRỎ VÀ CẤP PHÁT ĐỘNG 9/10/2015 Data structure & Algorithms 7
DANH SÁCH LIÊN KẾT (LINKED LIST)  Mảng là một hình thức liên kết ngầm  Các phần tử trong mảng được cấp phát vùng nhớ một cách liên tiếp nhau  Với T là kiểu dữ liệu cho trước, xét mảng các phần tử kiểu T. Ta có: Address(i)=Address(0)+(i-1)*sizeof(T) 9/10/2015 Data structure & Algorithms 8
DANH SÁCH LIÊN KẾT  Một số loại danh sách liên kết (DSLK): • Danh sách liên kết đơn • Danh sách liên kết kép • Danh sách liên kết vòng • ….. 9/10/2015 Data structure & Algorithms 9
DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 10
DANH SÁCH LIÊN KẾT  Mỗi phần tử của danh sách đơn là một cấu trúc chứa 2 thành phần chính: - data: lưu trữ các thông tin về bản thân phần tử. - link: lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh sách.  Con trỏ Head: dùng để lưu trữ địa chỉ phần tử đầu ds, nên ta gọi Head là đầu xâu(ds).  Con trỏ Tail: giữ địa chỉ phần tử cuối xâu. 9/10/2015 Data structure & Algorithms 11
DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 12
DANH SÁCH LIÊN KẾT 9/10/2015 Data structure & Algorithms 13
KHAI BÁO DSLK typedef struct NODE { int data; NODE* next; }NODE; typedef struct LIST { NODE* pHead; NODE* pTail; }LIST; 9/10/2015 Data structure & Algorithms 14
CÁC THAO TÁC TRÊN DSLK  Khai báo danh sách  Tạo một phần tử cho danh sách  Chèn một phần tử vào danh sách  Tìm một phần tử trong danh sách đơn  Huỷ một phần tử khỏi danh sách  Duyệt danh sách  Sắp xếp danh sách 9/10/2015 Data structure & Algorithms 15
TẠO PHẦN TỬ TRONG DSLK void Initial(LinkList &l) { l.head = l.tail = NULL; } 9/10/2015 Data structure & Algorithms 16
THÊM 1 NÚT VÀO ĐẦU DSLK 9/10/2015 Data structure & Algorithms 17
THÊM 1 NÚT VÀO CUỐI DSLK 9/10/2015 Data structure & Algorithms 18
THÊM 1 NÚT VÀO SAU 1 NÚT 9/10/2015 Data structure & Algorithms 19
THÊM 1 NÚT VÀO TRƯỚC 1 NÚT 9/10/2015 Data structure & Algorithms 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.