Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cơ sở dữ liệu và giải thuật

CHƯƠNG 1. TỔNG QUAN VỀ CTDL & GTTrần Minh TháiEmail: minhthai@itc.edu.vnWebsite: www.minhthai.edu.vn 1Mục tiêuGiới thiệu vai trò của tổ chức dữ liệuMối quan hệ giữa GT & CTDLCác khái niệm và yêu cầu về CTDLNhắc lại các kiểu dữ liệu trong C++Tổng quan về đánh giá độ phức tạp GT2Suy nghĩ3 Theo bạn: trước khi viết một chương trình để giải quyết một bài toán nào đó trên máy tính thì cần phải làm những việc gì??Xét đoạn chương trình sauvoid main(){int n;cout>n;if(n%2==0)coutV = {Tập các giá trị}O = {Tập các thao tác xử lý}Ví dụ: Kiểu dữ liệu số nguyên short trong ngôn ngữ C T = short V = {-32768, 32767} O = {+, -, *, /, %}7Khái niệm về kiểu dữ liệuCác thuộc tính của một kiểu dữ liệu gồm:TênMiền giá trịKích thước lưu trữTập các thao tác tác động lên kiểu dữ liệu đóCác loại kiểu dữ liệuKiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bảnKiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, 8Khái niệm về kiểu dữ liệuTĩnh Được định nghĩa ở thời điểm biên dịch. Được cấp phát ở thời điểm liên kết. Có thể có giá trị ban đầu tùy theo từng ngôn ngữ lập trình. Tồn tại đến khi kết thúc chương trình.Động Được gắn kết với một con trỏ (tại thời điểm biên dịch chưa có). Phát sinh lúc thực thi. Không xác định giá trị ban đầu. Được giải phóng khỏi bộ nhớ khi cần.9Nhắc lại các kiểu dữ liệu C++Kiểu cơ sở: Số nguyên, số thực và kiểu logicKiểu mảng, chuỗiKiểu có cấu trúc1011Kiểu số nguyênSttTên kiểuGhi chúKích thước1charKý tự1 byteSố nguyên1 byte2unsigned charSố nguyên dương1 byte3shortSố nguyên2 bytes4unsigned shortSố nguyên dương2 bytes5intSố nguyên4 bytes6unsigned intSố nguyên dương4 bytes7longSố nguyên 4 bytes8unsigned longSố nguyên dương4 bytes12Kiểu số thựcSttTên kiểuGhi chúKích thước1float 4 bytes2double 8 bytes3long double 8 bytesSttTên kiểuGhi chúKích thước1boolGồm 2 giá trị: true hoặc falseKiểu luận lýKiểu mảng 1 chiềuKhai báo [];VD: int a[100];Gán giá trị ban đầuVD1: int a[100] = {0};VD2: int a[5] = {3, 6, 2, 10, 17}; hoặc: int a[] = {3, 6, 2, 10, 17};13Giá trị57103112Vị trí012n-2n-1Kiểu mảng 1 chiềuPhát sinh ngẫu nhiên Khởi tạo phát sinh ngẫu nhiên srand((unsigned int)time(NULL));Phát sinh giá trị ngẫu nhiên int x = rand()%k; k: Số nguyên dương x  [0..k-1]VD: Phát sinh 1 số nguyên có giá trị từ 0 đến 50 srand((unsigned int)time(NULL)); int x = rand()%51;14Bài tập 1Cài đặt hàm nhập mảng số nguyên, n phần tử Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số nguyênCài đặt hàm phát sinh n phần tử ngẫu nhiên có giá trị tăng dần cho mảng số nguyên15Kiểu chuỗi ký tựKhai báochar [] ;VD: char hoten[50];Xem lại các hàmcin.getline, cin.ignorestrcpy, strcat, strlenstrcmp, stricmpstrchr, strstr16Kiểu mảng – Khai báo kiểu con trỏ Mảng 1 chiều *;VD: int *a; Chuỗi ký tựchar *;VD: char *hoten;17Kiểu mảng – Khai báo kiểu con trỏLưu ý khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh deleteVD: int *a; int n = 10; a = new int[n]; .. delete a;18Bài tập 2Viết lại các hàm trong Bài tập 1 dùng khai báo kiểu con trỏ19Kiểu dữ liệu có cấu trúcstruct tên_struct{ khai báo các thuộc tính;};typedef struct tên_struct tên_kiểu;20Ví dụ kiểu dữ liệu có cấu trúcstruct ttDate{ char thu[9]; unsigned char ngay; unsigned char thang; int nam;};typedef struct ttDate DATE;21Truy cập thành phần có cấu trúcBiến cấu trúc kiểu tĩnh.thành phần cấu trúcVD: DATE d; d.nam = 2012;22Bài tập 3Viết hàm nhập và hàm xuất thông tin của một sinh viên gồm các thông tin:Mã sốHọ tênĐiểm trung bình23Truy cập thành phần có cấu trúcBiến cấu trúc kiểu con trỏ->thành phần cấu trúcVD: DATE *d;d->nam = 2012;24Bài tập 4Viết lại các hàm trong Bài tập 3 sử dụng khai báo biến kiểu con trỏ cấu trúc25Các phương pháp mô tả giải thuậtLưu đồMã giảMã tự nhiên26Các ký hiệu lưu đồBắt đầu/ kết thúcRẽ nhánhLuồng xử lýKhối xử lýNhập/ XuấtĐiều kiệnGiá trị trả vềĐiểm nối27Ký hiệu mã giảIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN 28Ví dụ mô tả giải thuậtTìm ước số chung lớn nhất của 2 số nguyên dương a và bĐầu vào: 2 số nguyên dương a và bĐầu ra: ước số chung lớn nhất của a và b29Mô tả bằng mã tự nhiênBước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết thúcBước 2: Nếu a > b thì a = a – b; Ngược lại thì b = b – a;Bước 3: Quay trở lại Bước 130Mô tả bằng mã giảWHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILEDISPLAY a31Mô tả bằng lưu đồ32Đánh giá độ phức tạp giải thuậtPhụ thuộc vào ngôn ngữ lập trìnhPhụ thuộc vào người lập trìnhPhụ thuộc vào bộ dữ liệu thửPhụ thuộc vào phần cứng33Q&A34?