Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

163
lượt xem 9
download

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

Chương 1 của bài giảng Cấu trúc dữ liệu 1 giới thiệu chung về cấu trúc dữ liệu với một số nội dung chủ yếu sau: Vai trò của cấu trúc dữ liệu, một số tiêu chuẩn chọn cấu trúc dữ liệu, kiểu dữ liệu, độ phức tạp giải thuật. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

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 1: Chương 1 - Lương Trần Hy Hiến

ðại Họ Học Sư Phạ Phạm Tp. Hồ Hồ Chí Chí Minh Thông tin giảng viên • LƯƠNG TRẦN HY HIẾN • Bộ Môn Tin Học CẤU TRÚC DỮ LIỆU 1 • Khoa Toán – Tin học • Phone: 0989 366 990 • Email: hienlth@hcmup.edu.vn Chương 01: Mở ñầu về CTDL Chương 1. Giới thiệu về cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu 1.2 Một số tiêu chuẩn chọn CTDL Thông tin Thao tác 1.3 Kiểu dữ liệu nghiệp vụ Bài toán nghiệp vụ 1.4 ðộ phức tạp giải thuật thực tế thực tế ðối tượng Bài toán trên Yêu cầu dữ liệu máy tính xử lý
1.1 Vai trò của cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu Bài toán trên Yêu cầu Cấu trúc dữ liệu + giải thuật = chương trình ðối tượng dữ liệu máy tính xử lý Ví dụ 1: Chương trình quản lý ñiểm sinh viên của một Khi giải quyết các bài toán thực tế cần quan tâm: khóa học. Mỗi sinh viên học 4 môn học và các ñiểm Tổ chức biểu diễn các ñối tượng thực tế tương ứng như sau: Chọn cấu trúc dữ liệu phù hợp Môn 1 Môn 2 Môn 3 Môn 4 Xây dựng các thao tác xử lý dữ liệu Sinh viên 1 7 8 5 6 Tìm giải thuật giải quyết bài toán. Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Cấu trúc dữ liệu + giải thuật = chương trình Sinh viên 4 9 7 6 5 … … … … … 1.1 Vai trò của cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu ðối tượng dữ liệu Phân tích ví dụ 1 Phương án 1 Chương Dùng mảng một chiều Môn 1 Môn 2 Môn 3 Môn 4 trình quản lưu trữ ñiểm của tất Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 lý ñiểm cả các sinh viên Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 ðối tượng dữ liệu Yêu cầu xử lý … … … … … Môn 1 Môn 2 Môn 3 Môn 4 Nhập ñiểm Sinh viên 1 Sinh viên 2 Sinh viên 3 Sinh viên 4 Sinh viên 1 7 8 5 6 Xuất danh sách ñiểm Sinh viên 2 8 6 4 5 Tính ñiểm trung bình Thống kê tỉ lệ ñậu, hỏng R 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 Các thao tác tìm kiếm theo ñiểm R[I] = Bảng ñiểm( dòng (I / số môn) , cột (I % số môn) ) … … … … …
1.1 Vai trò của cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu ðối tượng dữ liệu Phương án 1 Phương án 2 Môn 1 Môn 2 Môn 3 Môn 4 Dùng mảng hai chiều R 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5 lưu trữ ñiểm của tất Sinh viên 1 7 8 5 6 R[I] = Bảng ñiểm(I / số môn , I % số môn) Sinh viên 2 8 6 4 5 cả các sinh viên Sinh viên 3 3 7 9 5 int R[16] = {7,8,5,6,8,6,4,5,3,7,9,5,9,7,6,5}; Sinh viên 4 9 7 6 5 int SO_MON = 4; int SO_SV = 4; void xuat() { R Cột 0 Cột 1 Cột 2 Cột 3 Dòng 0 R[0][0]=7 R[0][1]=8 R[0][2]=5 R[0][3]=6 for( int I =0 ; I < SO_MON*SO_SV ; I++){ int SV = I / SO_MON; Dòng 1 R[1][1]=8 R[0][1]=6 R[0][1]=4 R[0][3]=5 int MON = I % SO_MON; Dòng 2 R[2][1]=3 R[0][1]=7 R[0][1]=9 R[0][3]=5 cout
1.1 Vai trò của cấu trúc dữ liệu 1.2 Một số tiêu chí chọn cấu trúc dữ liệu Phương án 3 a. CTDL phải phản ánh ñúng thực tế. ðây là yếu tố quyết ñịnh tính ñúng ñắn của bài toán. Cần R[I][J] = Bảng ñiểm( dòng I , cột J ) xem xét trạng thái biến ñổi của dữ liệu nhằm chọn CTDL struct DiemSV { phù hợp. int Mon1,Mon2,Mon3,Mon4; }; b. CTDL phải phù hợp với thao tác trên ñó. DiemSV R[4]; Tiêu chuẩn này giúp tăng tính hiệu quả của bài toán.Mỗi int SO_SV = 4; CTDL có các thao tác ñi tương ứng. Nên chọn CTLD sao void xuat() { cho các thao tác ñược xử lý ñược ñơn giản và tự nhiên. for( int I=0 ; I < SO_SV ; ++I) { c. CTDL phải tiết kiệm tài nguyên hệ thống. cout
1.3 Kiểu dữ liệu 1.3 Kiểu dữ liệu 1.3.2 Các kiểu dữ liệu cơ bản 1.3.1 ðịnh nghĩa kiểu dữ liệu Kiểu dữ liệu có thứ tự rời rạc: Số nguyên, ký tự, logic, Các thuộc tính cần quan tâm về kiểu dữ liệu: liệt kê, miền con Kiểu dữ liệu không rời rạc: số thực Tên kiểu dữ liệu Một số kiểu dữ liệu cơ bản trong ngôn ngữ C Miền giá trị Tên kiểu dữ liệu Kích thước Miền giá trị Kích thước lưu trữ char 01 Byte -128 ñến 127 unsign char 01 Byte 0 ñến 255 Tập các toán tử, thao tác xử lý tác ñộng lên int 02 byte 0 ñến 65535 ñối tượng có kiểu dữ liệu long 04 byte -231 ñến 231 -1 unsign long 04 byte 0 ñến 232 - 1 float 04 Byte 3.4E-38 ñến 3.4E38 double 08 byte 1.7E-308 ñến 1.7E308 long double 10 byte 3.4E-4932 ñến 1.1E4932 1.3 Kiểu dữ liệu 1.3 Kiểu dữ liệu 1.3.2 Các kiểu dữ liệu có cấu trúc 1.3.2 Các kiểu dữ liệu có cấu trúc Ví dụ: ðể mô tả thông tin sinh viên cần quan tâm ñến thông tin sau: Các thao tác trên chuỗi Mã số sinh viên : 12 ký tự Tên hàm Công dụng Tên sinh viên : 30 ký tự strcmp(s1,s2) So sánh 2 chuỗi s1 và s2 Ngày sinh : kiểu ngày strcpy(dest,src) Sao chép src vào dest Nơi sinh : 255 ký tự strstr(s1,s2) Kiểm tra s2 có nằm trong ðiểm trung bình : Số thực chuỗi s1 khong? a. Kiểu chuỗi ký tự itoa(n,s,c) ðổi số nguyên n thành chuỗi ở dạng cơ số c Chuỗi ký tự trong là một dãy các ký tự liên tiếp kết thúc bằng ký atoi(sn) ,atof(sf), atol(sl) ðổi 1 chuỗi thành số tự có mã ASCII bằng 0. Chuỗi ký tự có tối ña 65535 ký tự gets(st) Nhập một chuỗi Ví dụ: char S[10]; puts(st) Xuất một chuỗi char S[] = “ABC”; char *S = “ABC”;
1.3 Kiểu dữ liệu 1.3 Kiểu dữ liệu b. Kiểu mảng c. Kiểu mẩu tin(cấu trúc) Mảng là kiểu dữ liệu lưu trữ các phần tử cùng kiểu. Mỗi phần tử Kiểu mẫu tin là kiểu dữ liệu mà mỗi phần tử của nó là tập hợp ñược xác ñịnh bởi một vị trí trí của nó trong mảng. các giá trị có thể khác cấu trúc. Kiểu mẫu tin cho phép mô tả các Khai báo mảng 1 chiều ñối tượng có cấu trúc phức tạp. []; Khai báo int a[100]; struct { int a[5]={4, 3, 6, 7, 2}; ; int a[ ] = {1, 4 , -3, 5, 6}; ; Khai báo mảng 2 chiều …. [][]; }; int a[10][10]; int a[3][2]={{4, 3},{ 6, 7},{2,3}}; 1.3 Kiểu dữ liệu 1.4 ðánh giá ñộ phức tạp của thuật toán d. Kiểu Union Phương pháp thực nghiệm: Kiểu Union giống như Struct, nhưng các trường dùng chung Cài ñặt thuật toán, chọn các bộ dữ liệu thử, thống kê các vùng nhớ. thông số nhận ñược. Khai báo Một số nhược ñiểm: union { Phụ thuộc vào ngôn ngữ lập trình dùng ñể cài ñặt ; ; Phụ thuộc vào trình ñộ của người cài ñặt …. Việc chọn ra bộ dữ liệu thử ñặc trưng cho tất cả các }; trường hợp rất khó khăn. Phụ thuộc vào phần cứng khi thực thi thuật toán
1.4 ðánh giá ñộ phức tạp của thuật toán 1.4 ðánh giá ñộ phức tạp của thuật toán Phương pháp hình thức: Sự phân lớp các ñộ phức tạp của thuật toán ðây là phương pháp ñánh giá ít phụ thuộc vào môi ðộ phức tạp là hằng số O(1) trường cũng như phần cứng.ðánh giá theo hướng xấp ðộ phức tạp là logN O(logN) xỉ tiệm cận thông qua khái niệm toán học O-lớn O(). ðộ phức tạp là N O(N) Thời gian tính toán sẽ phụ thuộc vào kích thước ðộ phức tạp là NlogN O(NlogN) của dữ liệu ñầu vào(thường gọi là N) và ñánh giá theo ðộ phức tạp là N2 O(N2) 3 trường hợp: ðộ phức tạp là N3 O(N3) Trường hợp tốt nhất Trường hợp xất nhất ðộ phức tạp là 2N O(2N) Trường hợp trung bình ðộ phức tạp là N! O(N!) Câu hỏi và thảo luận 27