zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách

Chia sẻ: Lelong Bao | Ngày: | Loại File: PPT | Số trang:80

Báo xấu

59
lượt xem 5
download

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

Danh sách là tập hợp hữu hạn các phần tửcùng kiểu (Elementtype) : a1, a2, …, an (n=1) với tính chất: nếu biết được ai sẽ biết ai+1 (0

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 - Chương 2 Cấu trúc dữ liệu danh sách

KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH BÀI GIẢNG CẤU TRÚC DỮ LIỆU (BẬC CAO ĐẲNG) Chương2: CẤU TRÚC DỮ LIỆU DANH SÁCH Nguyễn Thanh Cẩm
NỘI DUNG TRÌNH BÀY 1. Danh sách 2. Danh sách đặc 3. Danh sách liên kết 4. Ngăn xếp 5. Hàng đợi 1
1. Danh sách a. Định nghĩa b. Các phép toán trên danh sách
1. Danh sách a. Định nghĩa Danh sách là tập hợp hữu hạn các phần tử cùng kiểu (Elementtype) : a1, a2, …, an (n>=1) với tính chất: nếu biết được ai sẽ biết ai+1 (0
1. Danh sách b. Các phép toán trên danh sách Phép duyệt danh sách: là phép thăm tất cả các phần tử của danh sách thỏa mãn nào đó để thực hiện công việc Ví dụ: Phép tìm kiếm: là thao tác tìm phần tử trong danh sách thỏa mãn điều kiện nào đó Ví dụ:
1. Danh sách b. Các phép toán trên danh sách Thêm phần tử vào danh sách: là thao tác thêm phần tử mới Vào danh sách. Phần tử có thể được thêm vào cuối, đầu hoặc giữa danh sách. Chú ý danh sách đầy Ví dụ:
1. Danh sách b. Các phép toán trên danh sách Loại bỏ phần tử khỏi danh sách: là thao tác loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ phải xác định phần tử cần loại bỏ (tìm kiếm). Chú ý: sau khi loại bỏ, số phần tử của danh sách giảm đi 1 đơn vị Ví dụ:
1. Danh sách b. Các phép toán trên danh sách Sửa đổi phần tử trong danh sách: là thao tác hiệu chỉnh phần tử trong danh sách. Trước khi hiệu chỉnh cần phải xác định phần tử cần hiệu chỉnh (tìm kiếm) Ví dụ: Sắp xếp thứ tự danh sách: là thao tác sắp lại thứ tự các phần tử trong danh sách theo một quy tắc nào đó Ví dụ:
1. Danh sách b. Các phép toán trên danh sách Tách một danh sách thành nhiều danh sách: là thao tác tách một phần hoặc tất cả các phần tử trong DS đưa sang các danh sách khác Vd: Ghép nhiều danh sách thành danh sách mới: là thao tác ngược lại của quá trình tách. Trộn nhiều danh sách thành danh sách mới
2. Danh sách đặc a. Định nghĩa b. Khai báo c. Các phép toán d. Đặc điểm của danh sách đặc
2. Danh sách đặc a. Định nghĩa Danh sách đặc là danh sách mà các phần tử được sắp xếp kế tiếp nhau trong bộ nhớ, phần tử ai+1 đứng sau phần tử ai. a0 a1 … ai ai+1 … an-2 an-1 add[1] add[i] ←d → add[n] add[i] = add[1] + (i-1)*d
2. Danh sách đặc b. Khai báo #define MaxLength ... //Số nguyên thích hợp để chỉ độ dài của danh sách typedef ... ElementType; //kiểu của phần tử trong danh sách typedef int Position; //kiểu vị trí cuả các phần tử typedef struct { ElementType Elements[MaxLength]; //mảng chứa các phần tử của DS Position Last; //giữ độ dài danh sách } List; Vd:
2. Danh sách đặc c. Các phép toán i. Khởi tạo danh sách rỗng ii. Kiểm tra danh sách rỗng iii. Tìm kiếm phần tử trong danh sách iv. Chèn phần tử vào danh sách v. Loại bỏ phần tử khỏi danh sách
2. Danh sách đặc c. Các phép toán i. Khởi tạo danh sách rỗng void Make_List(List *L) { L->Last = 0; } Trong đó Last chỉ vị trí của phần tử cuối cùng trong danh sách và đó cũng là độ dài hiện tại của danh sách
2. Danh sách đặc c. Các phép toán ii. Kiểm tra danh sách rỗng Danh sách rỗng là một danh sách mà độ dài của nó bằng 0. int Empty_List(List L) { return L.Last == 0; }
2. Danh sách đặc c. Các phép toán iii. Chèn phần tử vào danh sách Giả sử ta chèn phần tử có nội dung x vào danh sách ở vị trí p. Khi đó các phần tử từ vị trí thứ p đến vị trí thứ last được di chuyển ra sau 1 đơn vị và độ dài danh sách tăng lên 1 đơn vị.
2. Danh sách đặc c. Các phép toán Giải thuật Chèn phần tử vào danh sách void Insert_List(ElementType X, Position P, List *L){ if (L->Last==MaxLength) printf("Danh sach day"); else if ((PL->Last)) printf("Vi tri khong hop le"); else{ Position i; for(i=L.Last; i>=p; i--) L->element[i+1]= L->element[i]; L->Elements[p]=X; L->Last++; } }
2. Danh sách đặc c. Các phép toán iv. Loại bỏ phần tử khỏi danh sách Để loại bỏ phần tử vị trí p ra khỏi danh sách L ta dời các phần tử từ vị trí p+1 đến cuối danh sách sang trái 1 vị trí. Lưu ý: độ dài của danh sách giảm đi 1 đơn vị
2. Danh sách đặc c. Các phép toán iv. Loại bỏ phần tử khỏi danh sách Giải thuật loại bỏ void Delete_List(Position P,List *L){ if ((PL->Last)) printf("Vi tri khong hop le"); else if (Empty_List(*L)) printf("Danh sach rong!"); else{ Position i; for(i=P;iLast;i++) L->Elements[i] = L->Elements[i+1]; L->Last--; } }
2. Danh sách đặc c. Các phép toán v. Tìm kiếm phần tử trong danh sách Trường hợp danh sách không thứ tự Position Search_List(ElementType X,List L){ Position found=0, i=0; if (Empty_List(L)) printf("Danh sach rong!"); else{ while (i

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.