Bài giảng Kỹ thuật lập trình – Chương 7: Cấu trúc dữ liệu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:121

Thêm vào BST

Báo xấu

28
lượt xem 6
download

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

Bài giảng Kỹ thuật lập trình – Chương 7: Cấu trúc dữ liệu trang bị cho người học những kiến thức cơ bản như: Định nghĩa cấu trúc dữ liệu; dữ liệu, kiểu dữ liệu & cấu trúc dữ liệu; các kiểu dữ liệu; mảng; danh sách; ngăn xếp; hàng đợi; cây.

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 Kỹ thuật lập trình – Chương 7: Cấu trúc dữ liệu

Trịnh Thành Trung (ThS) trungtt@soict.hust.edu.vn om .c ng Bài 4 co an CẤU TRÚC DỮ LIỆU th ng o du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các bài toán thực tế thường rất om phức tạp .c ng co Phải xác định được an o Các dữ liệu liên quan th đến bài toán ng o Các thao tác cần thiết o để giải quyết bài toán du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Mô tả Cấu trúc  Các dữ liệu cấu thành dữ liệu  Mối liên kết về mặt cấu om trúc giữa các dữ liệu .c đó ng co là cách tổ chức và thao tác Cung cấp các thao tác an có hệ thống trên dữ liệu trên dữ liệu đó th ng Đặc trưng cho 1 kiểu dữ o liệu du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Dữ liệu, kiểu dữ liệu & cấu trúc dữ liệu om .c Machine Level Data Storage 0100110001101001010001 ng co an Primitive Data Types 28 3.1415 'A' th o ng array Basic Data Structures du u cu High-Level Data Structures stack queue list hash table tree CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các kiểu dữ liệu om .c Kiểu dữ liệu cơ bản Kiểu dữ liệu có cấu trúc ng (primitive data type) (structured data type) co ▪Đại diện cho các dữ liệu ▪Được xây dựng từ các an giống nhau, không thể kiểu dữ liệu (cơ bản, có th phân chia nhỏ hơn được ng cấu trúc) khác nữa ▪Có thể được các ngôn ▪Thường được các ngôn ngữ lập trình định nghĩa o du ngữ lập trình định nghĩa sẵn hoặc do lập trình viên u sẵn tự định nghĩa cu ▪Ví dụ ▫C/C++: int, long, char, bool... ▫Thao tác trên các số nguyên: + - * / ... CuuDuongThanCong.com https://fb.com/tailieudientucntt
om Nội dung .c ng co an 1. Mảng th ng 2. Danh sách o du 3. Ngăn xếp u cu 4. Hàng đợi 5. Cây CuuDuongThanCong.com https://fb.com/tailieudientucntt
om .c 1. ng co Mảng an Array th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Mảng Array om .c ▪ Dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên ng ▪ Một hay nhiều chiều co ▫ C không giới hạn số chiều của mảng an th ng Cú pháp o DataType ArrayName[size]; du mảng nhiều chiều u cu DataType ArrayName[size 1][size 2]...[size n]; CuuDuongThanCong.com https://fb.com/tailieudientucntt
Khởi tạo giá trị mảng om .c ▪ C1. Khi khai báo ng co float y[5] = { 3.2, 1.2, 4.5, 6.0, 3.6 } int m[6][2] = { { 1, 1 }, { 1, 2 }, { 2, 1 }, { 2, 2 an }, { 3, 1 }, { 3, 2 } }; th char s1[6] = { 'H', 'a', 'n', 'o', 'i', '\0' }; //hoặc ng char s1[6] = "Hanoi"; o char s1[] = "Dai hoc Bach Khoa Hanoi"; //L = 24 du int m[][] = { { 1, 2, 3 }, { 4, 5, 6 } }; u cu ▪ C2. Khai báo rồi gán giá trị cho từng phần tử của mảng. int m[4]; m[0] = 1; m[1] = 2; m[2] = 3; m[3] = 4; CuuDuongThanCong.com https://fb.com/tailieudientucntt
om .c 2. ng co Danh sách an List th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Danh sách List om .c ▪ Danh sách ng ▫ Tập hợp các phần tử cùng kiểu co ▫ Số lượng các phần tử của danh sách không cố định an ▪ Phân loại th ▫ Danh sách tuyến tính: ng ▸ Có phần tử đầu tiên, phần tử cuối cùng ▸ Thứ tự trước / sau của các phần tử được xác định rõ ràng, ví dụ o du sắp theo thứ tự tăng dần, giảm dần hay thứ tự trong bảng chữ cái ▸ Các thao tác trên danh sách phải không làm ảnh hưởng đến trật u tự này cu ▫ Danh sách phi tuyến tính: các phần tử trong danh sách không được sắp thứ tự CuuDuongThanCong.com https://fb.com/tailieudientucntt
Danh sách List om .c ▪ Lưu trữ ng ▫ Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ  danh sách kế co tiếp an ▫ Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ  danh th sách móc nối ng ▸ Danh sách nối đơn o ▸ Danh sách nối kép du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Thao tác trên danh sách om .c  Khởi tạo danh sách (create) ng  Kiểm tra danh sách rỗng (isEmpty) co  Kiểm tra danh sách đầy (isFull)  Tính kích thước (sizeOf) an  Xóa rỗng danh sách (clear) th  Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert) ng  Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách o (remove) du  Lấy một phần tử tại một vị trí cụ thể (retrieve) u  Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace) cu  Duyệt danh sách và thực hiện một thao tác tại các vị trí trong danh sách (traverse) CuuDuongThanCong.com https://fb.com/tailieudientucntt
Danh sách kế tiếp om .c ▪ Sử dụng một vector lưu trữ gồm một số các ô nhớ liên tiếp ng ▫ Các phần tử liền kề nhau được lưu trữ trong những ô nhớ liền co kề nhau an ▫ Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ tự th được lưu trữ trong vector ng ▫ Tham chiếu đến các phần tử sử dụng địa chỉ được tính giống o như lưu trữ mảng. du u cu 0 1 2 i last n-1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Danh sách kế tiếp om .c ▪ Ưu điểm ng ▫ Tốc độ truy cập vào các phần tử của danh sách nhanh co ▪ Nhược điểm an ▫ Cần phải biết trước kích thước tối đa của danh sách th ? o ng ▫ Thực hiện các phép toán bổ sung các phần tử mới và loại bỏ các du phần tử cũ khá tốn kém u ? cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Thêm vào danh sách kế tiếp om .c ▪ Điều kiện tiên quyết: ng ▫ Danh sách phải được khởi tạo rồi co ▫ Danh sách chưa đầy an ▫ Phần tử thêm vào chưa có trong danh sách ▪ Điều kiện hậu nghiệm: th ng ▫ Phần tử cần thêm vào có trong danh sách o du insert(3, ‘z’) u cu 0 1 2 3 4 5 6 7 8 9 z a b c d e f g h count=9 count=8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Thêm vào danh sách kế tiếp om .c Algorithm Insert ng Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào co Output: tình trạng danh sách an if list đầy th return overflow ng if index nằm ngoài khoảng [0..count] return range_error o du //Dời tất cả các phần tử từ index về sau 1 vị trí for i = count-1 down to index u entry[i+1] = entry[i] cu entry[index] = element // Gán element vào vị trí index count++ // Tăng số phần tử lên 1 return success; End Insert CuuDuongThanCong.com https://fb.com/tailieudientucntt
Xóa khỏi danh sách kế tiếp om .c ng co remove(3, ‘d’) an 0 1 2 3 th 4 5 6 7 8 9 o ng a b c d e f g h du u cu count=7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Xóa khỏi danh sách kế tiếp om .c Algorithm Remove Input: index là vị trí cần xóa bỏ, element là giá trị lấy ra được ng Output: danh sách đã xóa bỏ phần tử tại index co if list rỗng an return underflow th if index nằm ngoài khoảng [0..count-1] ng return range_error o element = entry[index] //Lấy element tại vị trí index ra du count-- //Giảm số phần tử đi 1 //Dời tất cả các phần tử từ index về trước 1 vị trí u cu for i = index to count-1 entry[i] = entry[i+1] return success; End Remove CuuDuongThanCong.com https://fb.com/tailieudientucntt
Duyệt danh sách kế tiếp om .c Algorithm Traverse ng Input: hàm visit dùng để tác động vào từng phần tử Output: danh sách được cập nhật bằng hàm visit co an //Quét qua tất cả các phần tử trong list for index = 0 to count-1 th Thi hành hàm visit để duyệt phần tử entry[index] o ng End Traverse du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt