zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Khoa học máy tính - Kiểu dữ liệu danh sách

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:17

Báo xấu

134
lượt xem 15
download

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

Tài liệu tham khảo dành cho giáo viên, sinh viên các trường cao đẳng, đại học chuyên ngành khoa học máy tính - Kiểu dữ liệu danh sách.

Chủ đề:

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

Lưu

Nội dung Text: Khoa học máy tính - Kiểu dữ liệu danh sách

Ki u d li u danh sách Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
Danh sách Danh sách là gì? Danh sách là c u trúc d li u tuy n tính, trong ñó các ph n t d li u ñư c s p x p theo m t th t xác ñ nh Ví d : Danh sách sinh viên – Danh sách ñi n tho i – Danh sách môn h c – Danh sách bài hát – Danh sách công vi c –
Danh sách Tr u tư ng hóa c u trúc danh sách 1. Mô t d li u A = (a0, a1, …, an) trong ñó ai là ph n t th i c a danh sách A Ví d : A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tu n’,. ‘Ánh’) 2. Mô t các phép toán trên c u trúc danh sách • empty (A): Ki m tra danh sách có r ng hay không • length (A): Cho bi t s ph n t c a danh sách • element (A, i) : Tr ph n t v trí th i c a A. Ví d : A =(1,3,5) Element (A, 0) → 1 Element (A, 2) → 5
Danh sách • insert (A, i, x): Thêm ph n t x vào danh sách A t i v trí i. A = (a0, a1,…, an) → A = (a0,a1,…,ai-1, x, ai,…an) Ví d : A = (1,3,5) insert (A, 1, 4) → A = (1, 4, 3, 5) • append (A, x): Thêm x vào ñuôi danh sách A A = (a0, a1,…, an) → A = (a0,a1,…,an , x) x) Ví d : A = (1,3,5) append (A, 8) → A = (1, 3, 5, 8) • delete (A, i): Lo i ph n t v trí th i trong danh sách A A = (a0, a1,…ai-1, ai, ai+1, an) → A = (a0,a1,…,ai-1, ai+1,…an) Ví d : A = (1,3,5) delete (A, 1) → A = (1, 5)
Cài ñ t danh sách b ng m ng M ng (array) • T p h p các ph n t (các bi n) có cùng m t ki u • M t ph n t c th trong m ng s ñư c xác ñ nh và truy c p b i m t ch s • Trong C/C++, các ph n t c a m ng ñư c ñ t c nh nhau t o thành m t kh i liên t c. ð a ch th p nh t tương ng v i ph n t ñ u tiên, ñ a ch cao nh t tương ng v i ph n t cu i cùng • M ng thì có th là m t chi u ho c nhi u chi u
Cài ñ t danh sách b ng m ng . . . an a0 a1 ↑ ↑ ↑ ↑ . . . 0 1 N Max- 1 M ng m t chi u: dataType arrayName [Max]; Ví d : int scoreArr[100]; student studentArr[100];
Danh sách Tóm t t v tr u tư ng hóa c u trúc danh sách • Mô t d li u A = (a0, a1, …, an) • Mô t các phép toán trên c u trúc danh sách • empty (A): Ki m tra danh sách có r ng hay không • length (A): Cho bi t s ph n t c a danh sách • element (A, i) : Tr ph n t v trí th i c a A. • insert (A, i, x): Thêm ph n t x vào danh sách A t i v trí i. • append (A, x): Thêm x vào ñuôi danh sách A • delete (A, i): Lo i ph n t v trí th i trong danh sách A • Các phép toán trên c u trúc danh sách không ph thu c vào ki u d li u c a các ph n t trong danh sách!!!
Cài ñ t danh sách trong C++ Template 1. Generic function 2. Generic class ListArr project List.h List.cpp
Các phép toán khác trên danh sách • Tìm ph n t l n nh t • ð i ch hai ph n t • S p x p tăng d n
Con tr (pointer) • Là ñi m m nh nh t, nhưng cũng nguy hi m nh t c a C/ C++ • Ch a ñ a ch c a m t t bào nh trong máy tính 3 1 2 3 1 4 6 5 Giá tr trong ô nh ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ð a ch ô nh 10 11 12 13 14 15 16 17
Con tr (pointer) Khai báo con tr type * pointerVariable ví d : int *p C p phát b nh (allocate memory) pointerVariable = new type (initializer) Ví d : p = new int (-1) Gi i phóng b nh delete pointerVariable; ví d : delete p (xem ví d chương trình)
Con tr (pointer) C p phát b nh cho m t ñ i tư ng d li u pointerVariable = new objectDataType (xem ví d chương trình)
Con tr (pointer) C p phát m ng ñ ng pointerVariable = new arrayType[size] ví d : int* p; p = new int[10] Gi i phóng m ng ñ ng delete [] pointerVariable ví d : delete [] p; (xem ví d chương trình)
Danh sách liên k t -1 1 3 2 M ng ↑↑↑ ↑↑↑ ↑↑↑↑ ↑↑ 11 12 13 14 15 16 17 18 19 20 21 22 int listArr[4] = {-1, 1, 3, 2} -1 1 3 2 Danh sách liên k t ↑↑↑ ↑↑↑ ↑↑↑↑ ↑↑ 11 12 13 14 15 16 17 18 19 20 21 22 (-1, 15) → (1, 16) → (3, 21) → (2, NULL) ↑ ↑ head tail
Cài ñ t danh sách liên k t Xem chương trình
Các phép toán khác trên danh sách liên k t • Tìm ph n t l n nh t • ð i ch hai ph n t • S p x p tăng d n
M ng và danh sách liên k t • Truy c p ph n t • Thêm ph n t • Xóa ph n t

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.