Kiều dữ liệu danh sách

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:17

0
97
lượt xem
10
download

Kiều dữ liệu danh sách

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

Tài liệu tham khảo về kiều dữ liệu danh sách - môn Khoa học máy tính

Chủ đề:
Lưu

Nội dung Text: Kiều dữ liệu danh sách

  1. 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
  2. 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
  3. 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
  4. 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) 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)
  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
  6. Cài ñ t danh sách b ng m ng a0 a1 . . . an ↑ ↑ ↑ ↑ 0 1 . . . N Max- 1 M ng m t chi u: dataType arrayName [Max]; Ví d : int scoreArr[100]; student studentArr[100];
  7. 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!!!
  8. Cài ñ t danh sách trong C++ Template 1. Generic function 2. Generic class ListArr project List.h List.cpp
  9. 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
  10. 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 1 2 3 3 1 4 6 5 Giá tr trong ô nh ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ð a ch ô nh 10 11 12 13 14 15 16 17
  11. 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)
  12. 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)
  13. 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)
  14. Danh sách liên k t M ng -1 1 3 2 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 int listArr[4] = {-1, 1, 3, 2} Danh sách -1 1 3 2 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
  15. Cài ñ t danh sách liên k t Xem chương trình
  16. 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
  17. 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

Đồng bộ tài khoản