1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3 - Nguyễn Khánh Phương

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3 - Nguyễn Khánh Phương

Chương 3 - Các cấu trúc dữ liệu cơ bản. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Kiểu dữ liệu (Data types), Các kiểu dữ liệu dựng sẵn (Built-in data types), dữ liệu đối với kiểu nguyên thuỷ, mảng (array), bản ghi (record), danh sách liên kết (linked list), ngăn xếp (stack), hàng đợi (queue). TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science dep

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 257

Ngày tạo 10/10/2021 7:18:27 PM +00:00

Loại tệp PDF

Kích thước 5.84 M

Tên tệp

Tải Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3... (.pdf)

Xem mẫu

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Nội dung khóa học Chương 1. Các khái niệm cơ bản om Chương 2. Các sơ đồ thuật toán .c ng Chương 3. Các cấu trúc dữ liệu cơ bản co Chương 4. Cây an Chương 5. Sắp xếp th o ng du Chương 6. Tìm kiếm u cu Chương 7. Đồ thị 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Chương 3. Các cấu trúc dữ liệu cơ bản an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Kiểu dữ liệu (Data types) • Kiểu dữ liệu (data type) được đặc trưng bởi: – Tập các giá trị (a set of values); om – Cách biểu diễn dữ liệu (data representation) được sử dụng chung .c cho tất cả các giá trị này và ng – Tập các phép toán (set of operations) có thể thực hiện trên tất cả co các giá trị. an • Chú ý: th ng – Mỗi giá trị có một cách biểu diễn nào đó mà người sử dụng o không nhất thiết phải biết du – Mỗi phép toán được cài đặt theo một cách nào đó mà người sử u cu dụng cũng không cần phải biết 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Các kiểu dữ liệu dựng sẵn (Built-in data types) • Trong các ngôn ngữ lập trình thường có một số kiểu dữ liệu nguyên thuỷ đã được xây dựng sẵn. Ví dụ: om – Kiểu số nguyên (Integer numeric types) .c • byte, char, short, int, long ng – Kiểu số thực dấu phảy động (floating point numeric types) co • float, double an th – Các kiểu nguyên thuỷ khác (Other primitive types) ng • boolean o du – Kiểu mảng (Array type) u • mảng các phần tử cùng kiểu cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. Dữ liệu đối với kiểu nguyên thuỷ Trong ngôn ngữ lập trình C om Type Byte Minimum value Maximum value .c byte 1 -128 127 ng co short 2 -32768 32767 an char 2 0 65535 th int 4 -2147483648 = -231 2147483647 = 231-1 ng long 8 -9223372036854775808 9223372036854775807 o du 45 38 float 4 1 . 40 10 3 . 40 10 u cu 324 308 double 8 4 . 94 10 1 . 80 10 Có thể có kiểu boolean với hai giá trị true hoặc false 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. Phép toán đối với kiểu dữ liệu nguyên thuỷ • Đối với kiểu: byte, char, short, int, long  +, - , *, /, %, đổi thành xâu, ... om • Đối với kiểu: float, double .c  +, -, *, /, round, ceil, floor, ... ng • Đối với kiểu: boolean co  kiểm giá trị true, hay kiểm giá trị false an th • Nhận thấy rằng: Các ngôn ngữ lập trình khác nhau có thể sử dụng mô tả ng kiểu dữ liệu khác nhau. Chẳng hạn, PASCAL và C có những mô tả các o du dữ liệu số khác nhau. u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. Nội dung 1. Mảng (Array) om 2. Bản ghi (Record) .c 3. Danh sách liên kết (Linked List) ng co 4. Ngăn xếp (Stack) an 5. Hàng đợi (Queue) th o ng du u cu 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Nội dung 1. Mảng (Array) om 2. Bản ghi (Record) .c 3. Danh sách liên kết (Linked List) ng co 4. Ngăn xếp (Stack) an 5. Hàng đợi (Queue) th o ng du u cu 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. 1. Mảng (Array) • Giả sử có 100 tỉ số (scores) trong một giải đấu bóng chuyền. Chúng ta cần tiến hành các thao tác: lấy thông tin của 100 tỉ số đó (read them), rồi đem xử lý các tỉ số này om (process them), và cuối cùng là in chúng (print/write them). • Để làm được điều này, ta cần lưu trữ 100 tỉ số này vào bộ nhớ trong suốt quá trình .c thực hiện chương trình. Do đó, ta sẽ sử dụng 100 biến, mỗi biến một tên tương ứng ng với 1 tỉ số: (Xem hình 1) co an th o ng du Hình 1 Sử dụng 100 biến Hình 2 Xử lý dữ liệu tỉ số trên 100 biến u cu • Sử dụng 100 biến dẫn đến vấn đề: ta cần phải viết lệnh đọc (read) 100 lần, lệnh xử lý (process) 100 lần và lệnh in (write) 100 lần (xem Hình 2). 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. 1. Mảng (Array) • Thay vì khai báo biến một cách rời rạc 100 biến score1, score2, …, score100, ta có thể khai báo một mảng các giá trị om như scores[1], scores[2] và … scores[100] để biểu diễn các giá trị .c riêng biệt. ng co an th o ng du u cu Hình 1 Sử dụng 100 biến Hình 2 Sử dụng mảng scores gồm 100 phần tử 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. 1. Mảng (Array) Mảng là một kiểu dữ liệu chứa dãy các phần tử được đánh chỉ số, thông thường các phần tử này có cùng kiểu dữ liệu. om • Mỗi phần tử của mảng có một chỉ số cố định duy nhất .c – Chỉ số nhận giá trị trong khoảng từ một cận dưới đến một cận trên nào đó ng Ví dụ: Trong ngôn ngữ C, mảng scores kích thước N = 9, mỗi phần tử được đánh ti n 0
  13. Tên mảng vs. Tên phần tử của mảng Trong 1 mảng, ta có 2 kiểu định danh: • Tên của mảng om • Tên của các phần tử riêng biệt thuộc mảng. .c Tên của mảng là tên của toàn bộ cấu trúc, còn tên của một phần tử cho phép ta truy cập đến phần tử đó. ng Ví dụ: co an th o ng du u cu Tên của mảng: scores, Tên mỗi phần tử của mảng: gồm tên của mảng theo sau là chỉ số của phần tử, ví dụ scores[0], scores[1], … 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. 1. Mảng (Array) • Mảng (Array): tập các cặp (chỉ số (index) và giá trị (value)) – Cấu trúc dữ liệu: mỗi chỉ số, sẽ tương ứng với 1 giá trị. om – Lưu trữ trong bộ nhớ: mảng được lưu trữ ở các ô nhớ liền kề nhau .c (cách lưu trữ này được gọi là lưu trữ kế tiếp). Địa chỉ thấp nhất tương ng ứng với thành phần đầu tiền và địa chỉ cao nhất tương ứng với thành co phần cuối cùng của mảng. an th o ng du u cu 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Mảng trong các ngôn ngữ lập trình • Các chỉ số có thể là số nguyên (C/C++, Java) hoặc là các giá trị kiểu rời rạc (Pascal, Ada) om .c • Cận dưới là 0 (C/C++, Java), 1 (Fortran), hoặc tuỳ chọn bởi ng co người lập trình (Pascal, Ada) an th • Trong hầu hết các ngôn ngữ, mảng là thuần nhất (nghĩa là o ng tất cả các phần tử của mảng có cùng một kiểu); trong một số du ngôn ngữ (như Lisp, Prolog) các thành phần có thể là không u cu thuần nhất (có các kiểu khác nhau) 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Khai báo mảng 1 chiều (one-dimensional array) Khi khai báo mảng, ta cần kiểu mảng (type), tên mảng (arrayName) và số phần tử trong mảng (arraySize > 0) : om type arrayName [arraySize]; .c ng Ví dụ: khai báo int A[5]; co tạo mảng A gồm 5 phần tử kiểu số nguyên (vì là kiểu nguyên, nên mỗi phần tử an chiếm 4 bytes trong bộ nhớ) th ng • Nếu kích thước mảng arraySize là hằng số thì cho ta mảng có độ dài cố định o (fixed length array), nếu là 1 biến (variable) thì cho ta mảng có độ dài thay đổi du (variable-length arrays) u – Ví dụ: double A[10]; Mảng A cố định gồm 10 phần tử cu int n; Mảng B có độ dài thay đổi qua giá trị của biến n double B[n]; • Chú ý: trước khi sử dụng một mảng, ta luôn phải khai báo và khởi tạo nó 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Mảng trong ngôn ngữ C Ngôn ngữ C hỗ trợ 2 kiểu mảng:  Mảng có độ dài cố định (Fixed Length Arrays) : lập trình viên om “hard codes” (cố định) độ dài của mảng. .c  Mảng có độ dài thay đổi (Variable-Length Arrays): lập trình viên ng không biết độ dài của mảng cho đến khi chạy chương trình. co an th o ng du u cu NGUYỄN KHÁNH PHƢƠNG17 Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. Ví dụ: Khai báo mảng có độ dài cố định (fixed length array) om (kiểu số nguyên: int) .c ng co (kiểu kí tự: char) an th o ng (kiểu số thực: float) du u cu NGUYỄN KHÁNH PHƢƠNG18 Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. Khai báo mảng 1 chiều có độ dài cố định • Ta có thể khởi tạo giá trị cho các phần tử của mảng cùng lúc với khai báo mảng om • Nếu số giá trị dùng khởi tạo nhỏ hơn kích thước mảng, C sẽ tự động gán .c cho các thành phần còn lại nhận giá trị 0 ng co an th o ng du u cu 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. Truy cập phần tử của mảng Để truy cập vào phần tử của một mảng, ta cần một giá trị nguyên xác định chỉ số của phần tử mà ta muốn truy cập. om • Có thể dùng chỉ số là 1 hằng số: scores[0]; .c • Cũng có thể dùng chỉ số là 1 biến (variable): ng for(i = 0; i < 9; i++) co scoresSum += scores[i]; an th o ng du u cu NGUYỄN KHÁNH PHƢƠNG20 Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường