- Trang Chủ
- Cơ sở dữ liệu
- Bài giảng Cấu trúc dữ liệu: Ngôn ngữ lập trình C++ - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết
Xem mẫu
- TS. Lê Minh Trung
Th.S Lương Trần Ngọc Khiết
Khoa CNTT, Đại học Sư phạm TP. HCM
- Lời nói đầu
“Algorithms + Data Structures = Programs”
N. Wirth
“Computing is an art form. Some programs are
elegant, some are exquisite, some are sparkling.
My claim is it is possible to write grand programs,
noble programs, truly magnificent programs”
D.E.Knuth
- Giải thuật (Thuật toán)
Chỉ ra làm thế nào để giải quyết bài toán.
Một dãy hữu hạn các thao tác mà cung cấp lời giải cho
bài toán.
Input (đầu vào)
Output (đầu ra)
Mô tả thuật giải
Bằng lời
Lưu đồ thuật giải (flow chart)
Giả mã (pseudo code): Pascal like, C like, C++ like…
- Tính chất của giải thuật
Tính chính xác (correctness)
Tính duy nhất (uniqueness)
Tính hữu hạn (finiteness)
Tính tổng quát (generality)
- Cấu trúc dữ liệu
Cách tổ chức dữ liệu để thuận tiện cho các thao tác
của thuật toán.
- Cấu trúc dữ liệu
Một cấu trúc dữ liệu bao gồm
Một tập hợp các giá trị
Một tập hợp các thao tác (phép toán) trên các giá trị
này
Stack (ngăn xếp)
Thao tác:
Push, Pop, Peek
- Cấu trúc dữ liệu tuyến tính
1. Đứng sau mỗi phần tử có tối đa một phần tử.
2. Mỗi phần tử có không quá 1 phần tử đứng trước.
- Cấu trúc dữ liệu phi tuyến
Một trong hai điều kiện 1 hoặc 2 bị vi phạm.
- Nội dung học
Giới thiệu và khái niệm cơ bản
Ôn tập lập trình C++
Các giải thuật tìm kiếm, sắp xếp
Ngăn xếp, hàng đợi và ứng dụng
Danh sách liên kết
Cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng
Bảng băm – Hash table
- Điểm số - Đánh giá
Số tuần học: 10 buổi
Đánh giá giữa kì: 30% (thi thực hành)
Thi cuối kì: 70% (thi giấy)
Bài tập lớn miễn thi (nhóm 2- 3 sinh viên)
- Tài liệu tham khảo
Data Structures and Problem Solving Using C++, Mark
Allen Weiss, Pearson Education International Inc.
Data Structures and Algorithm Analysis, Clifford A.
Shaffer, Dover Publications.
Algorithms, Robert Sedgewick and Kevin Wayne,
Addison Wesley
Cấu trúc dữ liệu và Giải thuật, Đinh Mạnh Tường,
Nhà xuất bản Giáo dục
Giải thuật và Lập trình, Lê Minh Hoàng, Đại học Sư
phạm Hà Nội
- TS. Lê Minh Trung – Lương Trần Ngọc Khiết
Khoa CNTT, Đại học Sư phạm TP. HCM
- Nội dung
Con trỏ (Pointer)
Mảng một chiều, nhiều chiều
Cấp phát vùng nhớ động
Struct
Khuôn mẫu (template)
Con trỏ hàm
Lớp và lập trình hướng đối tượng
- Con trỏ
Con trỏ là biến chứa địa chỉ của một biến khác
Khai báo
type * name;
int * number;
char * character;
double * decimals;
- Ví dụ
int myvar=25; myvar và *foo giống nhau
int *foo = &myvar; &myvar và foo giống nhau
int bar=*foo; //bar=myvar
- Ví dụ
- Ví dụ
- Phép toán với con trỏ
char *mychar; ++mychar; mychar = mychar + 1;
short *myshort; ++myshort; myshort = myshort + 1;
long *mylong; ++mylong; mylong = mylong + 1;
- Con trỏ tới con trỏ
char a;
char * b;
char ** c;
a = 'z';
b = &a;
c = &b;
- Con trỏ trống (void)
Rất linh động, có thể trỏ tới bất cứ kiểu dữ liệu nào như int,
char, string …
Tuy nhiên, không thể lấy nội dung (dereference) của con trỏ
trống một cách trực tiếp mà không ép kiểu thành kiểu con trỏ
khác
nguon tai.lieu . vn
