Chương 3: danh sách tuyến tính

Chia sẻ: Kieu Quang Vinh | Ngày: | Loại File: PPT | Số trang:59

Thêm vào BST

Báo xấu

766
lượt xem 77
download

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

Danh sách là một dãy các phần tử thuộc cùng một lớp đối tượng nào đó gọi là kiểu phần tử...

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: danh sách tuyến tính

CHƯƠNG 3 DANH SÁCH TUYẾN TÍNH
NỘI DUNG Khái niệm danh sách tuyến tính  Lưu trữ kế tiếp của danh sách tuyến  tính Danh sách móc nối  Ngăn xếp  Hàng đợi  2/59
3.1 KHÁI NIỆM DANH SÁCH TUYẾN TÍNH Danh sách là một dãy các phần tử thuộc cùng một lớp  đối tượng nào đó gọi là kiểu phần tử Ví dụ : Danh sách số nguyên, danh sách sinh viên,...  Trong danh sách mối quan hệ lân cận giữa các phần tử  được thể hiện gọi là danh sách tuyến tính. Danh sách tuyến tính hoặc rỗng hoặc có dạng  L = { a1, a2, ..., an } 3/59
3.1 KHÁI NIỆM DANH SÁCH TUYẾN TÍNH Danh sách tuyến tính hoặc rỗng hoặc có d ạng  L = { a1, a2, ..., an } Trong đó gọi là độ dài hoặc kích thước của danh sách L n thì a1 là phần tử đầu danh sách, an là phần tử cuối  n>0 danh sách là phần tử thứ i trong danh sách với (1
3.1 KHÁI NIỆM DANH SÁCH TUYẾN TÍNH Định nghĩa các phép toán tác động vào danh sách Khởi tạo danh sách rỗng (creat)  Kiểm tra danh sách rỗng (empty)  Kiểm tra danh sách đầy (full)  Bổ sung một phần tử vào danh sách (insert)  Loại bỏ một phần tử khỏi danh sách (del)  Sắp xếp danh sách (sort)  Tìm kiếm trên danh sách (search)  Tách danh sách hoặc ghép danh sách...  5/59
3.2 LƯU TRỮ KẾ TIẾP CỦA DSTT Khái niệm  Định nghĩa và khai báo CTDL  Định nghĩa các phép toán và chương trình th ực hiện  các phép toán cơ bản 6/59
3.2.1 Khái niệm Sử dụng mảng một chiều làm cấu trúc lưu trữ danh sách  Mỗi phần tử của mảng lưu trữ một phần tử của danh sách, các phần tử  của danh sách nằm kế tiếp nhau trong bộ nhớ Ưu điểm  Truy cập trực tiếp tới các phần tử  Các thao tác được thực hiện khá đơn giản  Nhược điểm  Do kích thước mảng cố định khi khai báo nên có thể dẫn đến sự lãng  phí hoặc thiếu bộ nhớ. Phải dãn hoặc dồn danh sách khi chèn thêm hoặc loại bỏ phần tử  khỏi danh sách 7/59
3.2.2 Định nghĩa và khai báo CTDL Giả sử các phần tử của danh sách có kiểu dữ liệu là  Độ dài của danh sách là một số nguyên dương n  Danh sách được biểu diễn bởi một bản ghi gồm có  hai trường Trường thứ nhất: Là một số nguyên biểu diễn số phần tử có  trong danh sách Trường thứ hai : Là mảng một chiều có kích thước đủ lớn để  lưu các phần tử của danh sách 8/59
3.2.2 Định nghĩa và khai báo CTDL Khai báo cấu trúc dữ liệu :  const max = ; a1 0 struct list a2 { 1 Danh s¸ch int sopt ; ... an n-1 ptu[max] ; ....... }l; . Cha cã l.sopt = 0 -> danh sách l rỗng m ax - 1 l.sopt = max -> ds đầy Mảng lưu trữ danh sách l 9/59
3.2.3 Các phép toán cơ bản Khởi tạo danh sách rỗng (creat)  Kiểm tra danh sách rỗng (empty)  Kiểm tra danh sách đầy (full)  Bổ sung một phần tử vào danh sách (insert)  Loại bỏ một phần tử khỏi danh sách (del)  10/59
3.2.3 Các phép toán cơ bản  Khởi tạo danh sách rỗng void creat(list &l) { l.sopt = 0; } 11/59
3.2.3 Các phép toán cơ bản Kiểm tra danh sách rỗng  int empty(list l) { return l.sopt ==0 ; } 12/59
3.2.3 Các phép toán cơ bản Kiểm tra danh sách đầy  int full(list l) { return l.sopt ==max; } 13/59
3.2.3 Các phép toán cơ bản Phép bổ sung phần tử x vào vị trí thứ k trong danh sách l  Bổ sung x=24 vào vị trí k=2 0 1 k=2 3 4 5 max = 7 14 23 42 11 25 Mảng l.ptu l.sopt = 5 x= 24 0 1 k=2 3 4 5 max = 7 14 23 42 11 25 Mảng l.ptu l.sopt = 6 14/59
3.2.3 Các phép toán cơ bản Phép bổ sung một phần tử vào vị trí k trong danh sách l  Bổ sung x=24 vào vị trí k=2 0 1 2 3 4 5 max = 7 14 23 24 42 11 25 Mảng l.ptu l.sopt = 6 15/59
3.2.3 Các phép toán cơ bản Phép bổ sung một phần tử x vào vị trí k trong  danh sách l void insert ( x, int k, list &l) { if (l.sopt =0 && k k; i--) l.ptu[i] = l.ptu[i-1]; l.ptu[k] = x; l.sopt++; } } 16/59
3.2.3 Các phép toán cơ bản Phép loại bỏ một phần tử ở vị trí k trong danh sách l  Loại bỏ phần tử tại vị trí k=2 0 1 k=2 3 4 5 max = 7 14 23 42 11 25 Mảng l.ptu l.sopt = 5 0 1 2 3 4 5 max = 7 14 23 11 25 Mảng l.ptu l.sopt= 4 17/59
3.2.3 Các phép toán cơ bản Phép loại bỏ một phần tử khỏi danh  sách void del(int k, list &l) { if (k>=0 && k < l.sopt) { l.sopt-- ; for (int i=k; i
3.3 DANH SÁCH MÓC NỐI Danh sách móc nối đơn  Danh sách móc nối vòng  Danh sách móc nối kép  Ưu nhược điểm của danh sách móc nối  19/59
3.3.1 Danh sách móc nối đơn Định nghĩa và khai báo CTDL  Định nghĩa các phép toán và chương trình thực  hiện các phép toán cơ bản 20/59