CấU TRÚC Dữ LIệU VÀ
GIảI THUẬT
DATA STRUCTURE AND
ALGORITHMS
1
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Nội dung môn học

Chương 0: Giới thiệu chung về CTDL và GT

Chương 1: Ôn tập C/C++

Chương 2: Đệ quy (Recursion)

Chương 3: Tìm kiếm (Searching)

Chương 4: Sắp xếp (Sorting)

Chương 5: Ngăn xếp - Hàng đợi (Stacks -
Queues)

Chương 6: Danh sách liên kết (Linked List)

Chương 7: Cây (Tree)
2
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập

Đức, Trường ĐHKHTN – ĐHQG TP.HCM.

Phần mềm lập trình:

C-Free

Borland C++

…
4
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Nhắc nhở một số quy định

Đi học đúng giờ

Đeo thẻ SV

Không để chuông điện thoại reo trong giờ học

Không nghe điện thoại, nhắn tin trong giờ học

Không nói chuyện riêng, làm ồn khi nghe giảng

Mang đầy đủ tài liệu học tập của môn học (khi
học LT và TH): giáo trình, bài tập, tập chép bài
(hoặc slide bài giảng), usb để lưu bài tập



(1) Sự tổ chức hợp lý của các thành phần dữ liệu,

(2) Tập các thao tác để truy cập các thành phần dữ liệu.

Ví dụ:

Mảng (Array)

Danh sách liên kết (Linked List)

Ngăn xếp (Stack)

Hàng đợi (Queue)

Cây (Tree)

…

(1) the logical arrangement of data elements, combined with

(2) the set of operations we need to access the elements.
8
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Nội dung

Cấu trúc dữ liệu

B6: Quay lại B3

B7: Tổng cần tìm là S
10
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Mối quan hệ của CTDL và thuật toán
CTDL + Thuật toán = Chương
trình
11
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Nội dung

Cấu trúc dữ liệu

Thuật toán

Độ phức tạp của thuật toán (algorithm
complexity)
12

Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++


Thông thường số các phép tính được thực hiện phụ
thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào

Vì thế độ phức tạp thuật toán là một hàm phụ thuộc
đầu vào

Tuy nhiên, không cần biết chính xác hàm này mà chỉ
cần biết một ước lượng đủ tốt của chúng

Để ước lượng độ phức tạp của một thuật toán ta
thường dùng khái niệm
Big-O
14
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Ví dụ

Bước 1. Gán
T
ổng = 0. Gán i = 0.

Bước 2.
– Tăng i thêm 1 đơn vị.
– Gán Tổng = Tổng + i

Bước 3. So sánh i với
n


Độ phức tạp đa thức
:
O(P(n)), với P là đa thức
có

bậc
từ
2 trở lên

Độ phức tạp hàm mũ: O(2
n
)
16
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Bảng so sánh các độ phức tạp của
thuật toán

Một số lớp thuật toán
17
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Thứ tự độ phức tạp của thuật toán
18
(2 )

Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
1. Cấu trúc chương trình C/C++
#include "stdio.h"
#include "conio.h"

void main() /*ham chinh*/
{
int a=7;
printf( “%d”, a );
getch();
}
Cấu trúc chương trình C
21
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
1. Cấu trúc chương trình C/C++
#include "iostream.h"
#include "conio.h"

void main() /*ham chinh*/
{
int a=7;
cout<< a ;

5. M ng (ả Array)
6. M ng con tr (ả ỏ Pointer array)
7. M ng hai chi u (ả ề Two-dimensional array)
8. C u trúc (ấ Structure)
9. Con tr c u trúc (ỏ ấ Structure pointer)
10. Chu i (ỗ String)
11. T p tin (ậ File)
12. Hàm (Function)
24

Chương 1: Ôn tập
C/C++
Chương 1: Ôn tập
C/C++
2. Các cú pháp cơ bản

Khai báo biến:

Khai báo và khởi tạo biến:

Khai báo hằng số:
25
Kiểu_dữ_liệu tên_biến;
const Kiểu_dữ_liệu tên_biến =
giá trị;
Kiểu_dữ_liệu tên_biến = giá trị;
Chương 1: Ôn tập
C/C++