intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 4 DANH SÁCH TUYẾN TÍNH

Chia sẻ: Lê Ngọc Hoàng | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST
Báo xấu
118
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Danh sách là một tập các phần tử thuộc cùng một lớp đối tượng nào đó Dãy số nguyên, danh sách sinh viên,... Giả sử L là một danh sách có n phần tử L = { a1, a2, ..., an } n gọi là độ dài của danh sách L n0 thì a1 là phần tử đầu tiên, an là phần tử cuối cùng Với L, ta nói ai đứng trước ai+1 và đứng sau ai-1 (i=1...n). Danh sách mà các phần tử có thứ tự “trước-sau” gọi là “DSTT”...

Chủ đề:

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

Lưu

Nội dung Text: CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 4 DANH SÁCH TUYẾN TÍNH

  1. CHƯƠNG 4 DANH SÁCH TUYẾN TÍNH
  2. MỤC TIÊU Khái niệm danh sách tuyến tính  Các phép toán với danh sách  Lưu trữ kế tiếp của danh sách tuyến tính  Danh sách móc nối đơn  Danh sách nối đôi  Danh sách móc nối vòng  Ngăn xếp  Hàng đợi 
  3. KHÁI NIỆM DSTT Danh sách là một tập các phần tử thuộc cùng một  lớp đối tượng nào đó Dãy số nguyên, danh sách sinh viên,...  Giả sử L là một danh sách có n phần tử  L = { a1, a2, ..., an } n gọi là độ dài của danh sách L  n>0 thì a1 là phần tử đầu tiên, an là phần tử cuối cùng  Với L, ta nói ai đứng trước ai+1 và đứng sau ai-1 (i=1...n).  Danh sách mà các phần tử có thứ tự “trước-sau” gọi là  “DSTT”
  4. CÁC PHÉP TOÁN TRÊN DSTT 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 (add)  Loại bỏ một phần tử khỏi danh sách (remove)  Sắp xếp danh sách (sort)  Tìm kiếm trên danh sách (search)  ... 
  5. LƯU TRỮ KẾ TIẾP CỦA DSTT DSTT được lưu trữ trong bộ nhớ bởi một mảng một chiều  gọi là lưu trữ kế tiếp. Mỗi phần tử của mảng lưu trữ một phần tử của danh sách  Ưu điểm  Truy cập nhanh và đồng đều đối với mọi 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ớ.
  6. BIỂU DIỄN CẤU TRÚC DỮ LIỆU Giả sử các phần tử của danh sách có kiểu dữ liệu  là “Item” Độ 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 cấu trúc gồm  hai thành phần Thành phần thứ nhất: biến “count” lưu chỉ số phần tử  mảng, lưu trữ phần tử cuối cùng của danh sách. Thành phần thứ hai: mảng một chiều “E” lưu các phần  tử của danh sách L, E[i-1] lưu ai
  7. LƯU TRỮ KẾ TIẾP CỦA DSTT Biểu diễn danh sách  Danh sách cần lưu trữ: L = { a1, a2, ..., an } 0 1 … n-1 … Max-1 a1 a2 an … … Mảng E count = n-1
  8. LƯU TRỮ KẾ TIẾP CỦA DSTT Cấu trúc dữ liệu được khai báo như sau  #define Max N L.count = -1 -> ds L rỗng L.count = Max-1 -> ds L đầy struct Item { Các thành phần dữ liệu; }; struct List { int count; Item E[Max]; }; List L; //Khai báo ds L
  9. LƯU TRỮ KẾ TIẾP CỦA DSTT Ví dụ  #define Max 7 struct List { struct Sinhvien { int count; char hoten[30]; Sinhvien E[Max]; char gioitinh[4]; }; int tuoi; List L; //Khai báo ds L };
  10. LƯU TRỮ KẾ TIẾP CỦA DSTT Ví dụ  0 1 2 3 4 5 6 L.E S1 S2 S3 S4 S5 E L.count count = 4 Danh sách L chứa 5 sinh viên
  11. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Khởi tạo danh sách rỗng  Kiểm tra danh sách rỗng  Kiểm tra danh sách đầy  Phép loại bỏ một phần tử khỏi danh sách  Bổ sung một phần tử vào danh sách  Thống kê danh sách  Tính toán trên danh sách  Tìm kiếm trên danh sách  Sắp xếp danh sách 
  12. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Khởi tạo danh sách rỗng  void creat(List &L) { L.count = -1; } Max = 7 0 1 2 3 4 5 6 Mảng E count = -1 Danh sách rỗng
  13. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Kiểm tra danh sách rỗng  int empty(List L) { return (L.count == -1); } Hàm empty trả về giá trị 1 nếu danh sách rỗng, ngược lại trả về 0
  14. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Kiểm tra danh sách đầy  int full(List L) { return (L.count == Max-1); } Max = 7 0 1 2 3 4 5 6 14 23 11 25 37 19 29 Mảng E count = 6 Danh sách đầy
  15. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Thêm một phần tử vào cuối danh sách  Điều kiện: Danh sách chưa đầy  Max = 7 0 1 2 3 4 5 6 14 23 11 25 37 29 Mảng E count = 5 count = 4 Danh sách chưa đầy X 29
  16. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Thêm một phần tử vào cuối danh sách  int Add(List &L, Item X) { if (full(L)) return 0; else{ L.count++; L.E[L.count] = X; return 1; } }
  17. LƯU TRỮ KẾ TIẾP CỦA DSTT CHƯƠNG TRÌNH TẠO VÀ HiỂN THỊ DANH SÁCH SINH VIÊN
  18. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Phép loại bỏ phần tử thứ k khỏi danh sách L  Loại bỏ phần tử tại vị trí thứ k=3 for (i=k;i
  19. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Phép loại bỏ một phần tử khỏi danh sách L  int Remove(int k, List &L) { if (k 0) { for (int i = k; i
  20. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP Phép loại bỏ một phần tử khỏi danh sách L  Hàm Remove loại bỏ phần tử thứ k trong danh sách L  Phép loại bỏ thành công khi L không rỗng và k là một vị trí nằm  trong ds L Hàm trả về 1 nếu loại bỏ thành công, ngược lại trả về 0 
ADSENSE

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.

 

Đồng bộ tài khoản
2=>2