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)
Push, Pop, Peek
Thao tác:
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;
myvar và *foo giống nhau &myvar và foo giống nhau
Ví dụ int myvar=25; int *foo = &myvar; int bar=*foo; //bar=myvar
Ví dụ
Ví dụ
mychar = mychar + 1; myshort = myshort + 1; mylong = mylong + 1;
++mychar; ++myshort; ++mylong;
Phép toán với con trỏ char *mychar; short *myshort; long *mylong;
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
Con trỏ hàm
Const và con trỏ
Con trỏ không hằng trỏ tới dữ liệu không hằng
int *countPtr;
Con trỏ trỏ tới hằng số const int *countPtr;
Con trỏ hằng trỏ tới dữ liệu
int *const countPtr;
Con trỏ hằng trỏ tới hằng số const int *const countPtr;
Ví dụ
Ví dụ
Mảng Mảng là tập hợp các phần tử liên tục có cùng một kiểu
dữ liệu Khai báo
type arrayName[arraySize];
int c[ ]={-45,6,0,72,1543,-89,0,62,-3,1,6453,78};
Ví dụ
Mảng và Con trỏ int a[ ]={1,2,4,8,16};
a là một hằng con trỏ
int *const a;
int *bPtr =a; int *cPtr =&a[1]; bPtr[2]=10; *(bPtr+3)=20; a = &x; //lỗi vì a là hằng con trỏ
Mảng nhiều chiều
Cấp phát vùng nhớ động
Dùng toán tử new để cấp phát vùng nhớ động cho con trỏ
pointer = new type; pointer = new type[size];
Dùng toán tử delete để thu hồi (hủy) vùng nhớ đã được
cấp phát delete pointer; delete[] pointer;
Ví dụ int * foo; foo = new int [5];
foo = new int [5]; //phát sinh exception nếu không đủ bộ nhớ
int * foo; foo = new (nothrow) int [5]; if (foo == nullptr)
{ // error assigning memory. Take measures. }
delete[] foo;
Vùng nhớ Stack và Heap Vùng nhớ cấp phát cho một chương trình bao gồm:
Vùng nhớ tĩnh (static area)
Các biến tĩnh và toàn cục
Vùng nhớ Stack
Các biến cục bộ, tham số hàm …
Vùng nhớ Heap
Dữ liệu được cấp phát động (new/delete)
Struct Dùng để lưu trữ dữ liệu có cấu trúc Struct cũng có thể có phương thức khởi tạo (constructor)
và phương thức khác
Khai báo
struct type_name {
member_type1 member_name1; //trường 1 member_type2 member_name2; //trường 2 member_type3 member_name3; //trường 3 . . } object_names;
Ví dụ
enum SexKind{
struct Employee { Male, Female
};
Employee(){}; //phương thức khởi tạo
string Name; SexKind Sex; int Salary;
Employee(string name, SexKind sex = Male, int salary =300) { Name = name; Sex = sex; Salary = salary; }
string s; s = Name; s+=", " ; s+= (Sex==Male)?"Male":"Female"; s+= ", $"; s += to_string(Salary); return s;
string ToString(){
} };
Ví dụ
void main(){
Employee emps[]={Employee("Le Van Minh",Male,200),Employee("Nguyen Thi No",Female,250), Employee("Tran Van Chi",Male)}; for(int i=0; i<3;i++)
cout< } void main(){ Employee emps[]={Employee("Le Van Minh",Male,200),Employee("Nguyen Thi No",Female,250),
Employee("Tran Van Chi",Male)}; Employee *ptr=emps;
for(int i=0; i<3;i++){ cout<< ptr++ ->ToString()< } } Khuôn mẫu hàm (function template)
Khuôn mẫu lớp (class template) Hướng tới (generic programming)
Tạo ra các hàm, các cấu trúc dữ liệu có tính tái sử dụng cao (reusability) Khó debug và gỡ rối số thực, chuỗi… void Swap(int &x, int &y){ int temp =x; x=y; y= temp; } void Swap(float &x, float &y){ float temp =x; x=y; y= temp;} void Swap(double &x, double &y){
double temp =x; x=y; y= temp;} void main(){ int x =3, y=5;
Swap(x,y);
cout<<"x="< Record } 𝑛 𝑎[𝑖]3,… Cho mảng a[1], a[2], …, a[n]. Ta cần tính:
𝑛 𝑎[𝑖]2, 𝑆3 = 𝑖=1 𝑛 𝑎[𝑖], 𝑆2 = 𝑖=1 𝑆1 = 𝑖=1 Để thực hiện công việc trên một cách thuận lợi, có thể sử dụng con trỏ hàm. double f1(double x){ double Compute(double a[], int n,
double (*f)(double x)) } return x; { double f2(double x){ double result =0;
for(int i=0;i } result += (*f)(a[i]); return result; } void main(){ double a[] = {1,2,3};
int n = sizeof(a)/sizeof(a[0]);
double s1= Compute(a,n,f1);
double s2= Compute(a,n,f2);
cout<<"s1="< } Lớp là một cấu trúc dữ liệu dùng để diễn tả các thực thể trong một chương trình
Người, nhân viên, cây, xe cộ, xe ô tô… Lớp dùng để khai báo các thực thể. Các đối tượng có thể được khởi tạo từ lớp Là chất liệu cơ bản cho lập trình hướng đối tượng (Object-Oriented Programming) Lớp Đối tượng Vật đúc từ khuôn 9:30:25 AM hay 2:15:30 PM 14:15:30 int Hour=14
int Minute=15
int Second=30 02:15:30 PM #ifndef TIME_H
#define TIME_H class Time
{
public: int Hour;
int Minute;
int Second;
Time(void); //phương thức khởi tạo (constructor)
Time(int h,int m,int s); // constructor
void SetTime(int h,int m,int s);
void PrintUniversal() const;
void PrintStandard() const;
~Time(void);//phương thức hủy (destructor) }; #endif // !TIME_H Header file: Time.h #ifndef TIME_CPP
#define TIME_CPP #include Time::Time(void)
{ Hour = Minute = Second =0; } #endif // !TIME_CPP Code file: Time.cpp Time::Time(int h, int m, int s)
{ SetTime(h,m,s); } void Time::SetTime(int h, int m, int s)
{ if((h>=0) && (h<24) && (m>=0) && (m<60) && (s>=0)
&& (s<60))
{ Hour=h; Minute= m; Second=s; }else throw invalid_argument("Hour, minute, or second was invalid"); } void Time::PrintUniversal const ()
{ cout< < } void Time::PrintStandard() const{ cout< } #include void main(){ Truy cập hợp lệ tới các
thành viên public Time time(18,5,30);
time.Hour = 19; //19:5:30
cout<<"Standard Form:";
time.PrintStandard();
cout<<"Universal Form:";
time.PrintUniversal(); } class Time
{
public: Time(void); //phương thức khởi tạo (constructor)
Time(int h,int m,int s); // constructor
void SetTime(int h,int m,int s);
void PrintUniversal() const;
void PrintStandard() const;
~Time(void);//phương thức hủy (destructor) private: int Hour;
int Minute;
int Second; }; Từ khóa qui định hoạt vi truy cập Từ khóa Bên trong lớp Đối tượng khởi tạo từ lớp public Yes Yes Yes No Tập các thành viên dữ liệu, thành viên hàm có từ khóa qui
định hoạt vi public được gọi là giao diện (interface) của lớp. Phương thức khởi tạo được gọi khi khởi tạo một đối tượng mới từ lớp. Phương thức hủy được thực thi khi một đối tượng bị hủy, kết thúc vòng đời (lifetime) của nó. Time(int h,int m,int s);// constructor 2 Time(void); //constructor 1 Time t2(10,35,20); Time t1; Quá tải toán tử (Overload Operator)
Chúng ta sẽ quá tải các phép toán: +=, ++, >=, - class Time
{
public: // thành viên khác
void operator+=(int n); //time += n
void operator++(); // time++
bool operator>=(const Time &t);//time1>=time2
int operator-(const Time &t);//time1 – time2 private: int Hour; int Minute; int Second; }; void Time::operator+=(int n){ Second += n; Minute += Second / 60; Second %=60;
Hour += Minute/60; Minute %=60; Hour %=24; } void Time::operator++(){ (*this)+=1; } int Time::operator-(const Time &t){ int elapsed1 = Hour*3600 + Minute*60 + Second;
int elapsed2 = t.Hour*3600 + t.Minute*60 + t.Second;
return (elapsed1 - elapsed2); } void main(){ Time time(18,5,30), oldTime;
cout<< "Time:";
time.PrintStandard();
oldTime = time;
time += 105; time ++;
cout<<"Time + 105 + 1:";
time.PrintStandard();
cout<<"Elapsed time:"<Con trỏ tới Struct
Khuôn mẫu (Template)
lập trình tổng
quát
Khuôn mẫu hàm
Cần viết hàm cho phép tráo đổi (swap) hai số nguyên,
Con trỏ hàm
Lớp (Class)
vs.
Khuôn
Thiết kế lớp Time
Diễn tả một thời điểm trong ngày
Class Time – Khai báo
Class Time – Thực thi
Class Time – Thực thi
Class Time – Thực thi
Class Time – Thử nghiệm
Nguy hiểm
time.Hour =100
Class Time – Thiết kế lại
private
Constructor và Destructor
Class Time – Thực thi
Thử nghiệm
