Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Võ Quang Hoàng Khang

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

78
lượt xem 3
download

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

Chương 1 giới thiệu tổng quan về cấu trúc dữ liệu và giải thuật. Mục tiêu của bài giảng này nhằm: Giới thiệu vai trò của tổ chức dữ liệu, trình bày mối quan hệ giữa cấu trúc dữ liệu và giải thuật, các khái niệm và yêu cầu về CTDL, nhắc lại các kiểu dữ liệu trong C++, tổng quan về đánh giá độ phức tạp GT. Mời các bạn cùng tham khảo.

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 1 - ThS. Võ Quang Hoàng Khang

CHƯƠNG 1. TỔNG QUAN VỀ CTDL & GT Võ Quang Hoàng Khang Email: vqhkhang@gmail.com 1
Mục tiêu Giới thiệu vai trò của tổ chức dữ liệu Mối quan hệ giữa GT & CTDL Các khái niệm và yêu cầu về CTDL Nhắc lại các kiểu dữ liệu trong C++ Tổng quan về đánh giá độ phức tạp GT 2
Suy nghĩ ? 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ì? 3
Xét đoạn chương trình sau void main() { int n; coutn; if(n%2==0) cout
Vai trò của CTDL & GT Cấu Giải trúc dữ thuật liệu Chương trình 5
Các tiêu chuẩn đánh giá CTDL Phản ánh đúng thực tế Phù hợp với thao tác Tiết kiệm tài nguyên hệ thống 6
Khái niệm về kiểu dữ liệu T = V = {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 trong ngôn ngữ C T = short V = {-32768, 32767} O = {+, -, *, /, %} 7
Khái niệm về kiểu dữ liệu Các thuộc tính của một kiểu dữ liệu gồm:  Tên  Miề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ệu  Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản  Kiể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, … 8
Khái niệm về kiểu dữ liệu Tĩnh Động • Được định nghĩa ở thời • Được gắn kết với một con điểm biên dịch. trỏ (tại thời điểm biên dịch chưa có). • Được cấp phát ở thời • Phát sinh lúc thực thi. điểm liên kết. • Có thể có giá trị ban đầu • Không xác định giá trị ban tùy theo từng ngôn ngữ lập đầu. trình. • Được giải phóng khỏi bộ • Tồn tại đến khi kết thúc nhớ khi cần. chương trình. 9
Nhắc lại các kiểu dữ liệu C++ Kiểu cơ sở: Số nguyên, số thực và kiểu logic Kiểu mảng, chuỗi Kiểu có cấu trúc 10
Kiểu số nguyên Stt Tên kiểu Ghi chú Kích thước Ký tự 1 byte 1 char Số nguyên 1 byte 2 unsigned char Số nguyên dương 1 byte 3 short Số nguyên 2 bytes 4 unsigned short Số nguyên dương 2 bytes 5 int Số nguyên 4 bytes 6 unsigned int Số nguyên dương 4 bytes 7 long Số nguyên 4 bytes 8 unsigned long Số nguyên dương 4 bytes 11
Kiểu số thực Stt Tên kiểu Ghi chú Kích thước 1 float 4 bytes 2 double 8 bytes 3 long double 8 bytes Kiểu luận lý Stt Tên kiểu Ghi chú Kích thước 1 bool Gồm 2 giá trị: true hoặc false 12
Kiểu mảng 1 chiều Khai báo [] ; VD: int a[100]; Gán giá trị ban đầu VD1: int a[100] = {0}; VD2: int a[5] = {3, 6, 2, 10, 17}; hoặc: int a[] = {3, 6, 2, 10, 17}; 13
Kiểu mảng 1 chiều Phá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] 14
Kiểu chuỗi ký tự Khai báo char [] ; VD: char hoten[50]; Xem lại các hàm -gets, puts -strcpy, strcat, strlen -strcmp, stricmp -strchr, strstr 15
Kiể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; 16
Bài tập 1. Cài đặt hàm nhập mảng số nguyên, n phần tử 2. Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số nguyên 3. Cà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ên 17
Kiể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 delete VD: int *a; int n = 10; a = new int[n]; ….. delete a; 18
Kiểu dữ liệu có cấu trúc struct tên_struct { khai báo các thuộc tính; }; typedef struct tên_struct tên_kiểu; 19
Ví dụ kiểu dữ liệu có cấu trúc struct ttDate { char thu[9]; unsigned char ngay; unsigned char thang; int nam; }; typedef struct ttDate DATE; 20