YOMEDIA
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
81
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.
AMBIENT/
Chủ đề:
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
Ký 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
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
