Bài giảng Cấu trúc dữ liệu - Chương 1: Giới thiệu môn học - Lê Minh Trung

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; int *foo = &myvar; int bar=*foo; //bar=myvar myvar và *foo giống nhau &myvar và foo giống nhau Ví dụ Ví dụ Phép toán với con trỏ char *mychar; short *myshort; long *mylong; ++mychar; ++myshort; ++mylong; mychar = mychar + 1; myshort = myshort + 1; 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 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ụ struct Employee { string Name; SexKind Sex; int Salary; Employee(){}; //phương thức khởi tạo Employee(string name, SexKind sex = Male, int salary =300) { Name = name; Sex = sex; Salary = salary; } string ToString(){ string s; s = Name; s+=", " ; s+= (Sex==Male)?"Male":"Female"; s+= ", $"; s += to_string(Salary); return s; } }; enum SexKind{ Male, Female }; 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<<emps[i].ToString()<<endl; } Con trỏ tới Struct 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++){ coutToString()<<endl; } } Khuôn mẫu (Template)  Khuôn mẫu hàm (function template)  Khuôn mẫu lớp (class template)  Hướng tới lập trình tổng quát (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 Khuôn mẫu hàm  Cần viết hàm cho phép tráo đổi (swap) hai số nguyên, 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="<<x<<" "<<"y="<<y<<endl; } Khuôn mẫu hàm //template tương tự như typename template//T là một kiểu dữ liệu nào đó void Swap(T &x, T &y) { T temp = x; x =y; y=temp; } void main() { string x="ngay",y="tho"; Swap(x,y); cout<<"x="<<x<<" "<<"y="<<y<<endl; } Khuôn mẫu dữ liệu  Tạo ra một bản ghi (struct) gồm hai trường: khóa (key) và giá trị (value)  Việc tìm kiếm, so sánh được thực hiện trên khóa template<class KEY, class VALUE> struct Record { KEY key; VALUE value; Record(){}; Record(KEY k, VALUE v) {key =k; value= v;} }; template int Search(const KEY &k, Record a[], int n) { int i; for(i=0; i<n;i++)if(a[i].key ==k)break; if(i<n)return i; return -1; } void main(){ Record a[]= {Record(1,"Minh"), Record(2,"Nghia"), Record(3,"Phuoc"), Record(4,"Tan")}; int i= Search(3, a, sizeof(a)/sizeof(Record)); if(i !=-1)cout<<"Found at "<<i+1<<", Value="<<a[i].value<<endl; else cout<<"Not found!"<<endl; } Con trỏ hàm  Cho mảng a[1], a[2], , a[n]. Ta cần tính:  𝑆1 = 𝑖=1 𝑛 𝑎[𝑖], 𝑆2 = 𝑖=1 𝑛 𝑎[𝑖]2, 𝑆3 = 𝑖=1 𝑛 𝑎[𝑖]3,  Để 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 Compute(double a[], int n, double (*f)(double x)) { double result =0; for(int i=0;i<n;i++) result += (*f)(a[i]); return result; } double f1(double x){ return x; } double f2(double x){ return x*x; } 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="<<s1<<","<<"s2="<<s2<<endl; } Lớp (Class)  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) vs. Lớp Đối tượng Khuôn Vật đúc từ khuôn Thiết kế lớp Time  Diễn tả một thời điểm trong ngày  9:30:25 AM hay 2:15:30 PM int Hour=14 int Minute=15 int Second=30 14:15:30 02:15:30 PM Class Time – Khai báo #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 Class Time – Thực thi #ifndef TIME_CPP #define TIME_CPP #include #include #include #include "Time.h" using namespace std; Time::Time(void) { Hour = Minute = Second =0; } #endif // !TIME_CPP Code file: Time.cpp Class Time – Thực thi 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=0) && (m=0) && (s<60)) { Hour=h; Minute= m; Second=s; }else throw invalid_argument("Hour, minute, or second was invalid"); } Class Time – Thực thi void Time::PrintUniversal const () { cout<<setfill('0')<<setw(2)<<Hour<<":“<<setw(2) <<Minute<<":"<<setw(2)<<Second<<endl; } void Time::PrintStandard() const{ cout<<setfill('0')<<setw(2) <<((Hour==0 ||Hour==12)?Hour:Hour %12)<<":“ <<setw(2)<<Minute<<":"<< setw(2)<<Second<<(Hour<12?" AM":" PM")<<endl; } Class Time – Thử nghiệm #include #include "Time.h" using namespace std; void main(){ Time time(18,5,30); time.Hour = 19; //19:5:30 cout<<"Standard Form:"; time.PrintStandard(); cout<<"Universal Form:"; time.PrintUniversal(); } Truy cập hợp lệ tới các thành viên public Nguy hiểm time.Hour =100 Class Time – Thiết kế lại 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 private 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. Constructor và Destructor  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(void); //constructor 1Time(int h,int m,int s);// constructor 2 Time t1; Time t2(10,35,20); 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; }; Class Time – Thực thi 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); } Thử nghiệm 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:"<<time - oldTime<<endl; } Hàm friend  Là hàm không phải thành viên của một lớp nhưng lại có khả năng truy cập các thành viên (public, protected , private) của lớp đó. class Time { public: // thành viên khác friend bool IsNoon(const Time &t); private: int Hour; int Minute; int Second; }; bool IsNoon(const Time &t){ return ((t.Hour==12)&&(t.Minute==0)&& (t.Second==0)); } Thử nghiệm void main(){ Time time(11,59,59); cout<<"Is Noon:"<<(IsNoon(time)?"Yes":"No")<<endl; time++; cout<<"Is Noon:"<<(IsNoon(time)?"Yes":"No")<<endl; } Tính kế thừa (Inheritance)  Diễn tả quan hệ IsA giữa các thực thể.  Giúp chương trình được tổ chức tốt hơn Sơ đồ phân cấp của các lớp Sự kế thừa Lớp A Thành viên của lớp A Lớp B Thành viên của lớp A Thành viên riêng của B IsA Lớp cha -Lớp cơ sở (base class) Lớp con-Lớp dẫn xuất (derived class) Lớp dẫn xuất kế thừa tất cả từ lớp cơ sở ngoại trừ:  Constructor và destructor Hàm quá tải các toán tử (+,-,+=,-=,++,--) Hàm friend Từ khóa protected  Cung cấp hoạt vi trung gian giữa public và private. Cú pháp – Kiểu kế thừa  class derived-class: access-specifier base-class  access- specifier (kiểu kế thừa)  public, protected, private  Mặc định là private Class Shape #include using namespace std; // Base class class Shape { public: void setWidth(int w) { width = w; } void setHeight(int h) { height = h; } protected: int width; int height; }; Class Rectangle include "shape.h" class Rectangle : public Shape { public: int getArea() { return (width * height); } }; Thử nghiệm #include "Rectangle.h" #include using namespace std; int main(void) { Rectangle Rect; Rect.setWidth(5); Rect.setHeight(7); // Print the area of the object. cout << "Total area: " << Rect.getArea() << endl; return 0; } Tính đa hình  Một đặc tính rất quan trọng của lập trình hướng đối tượng.  Làm cho việc lập trình trở nên dễ dàng hơn. Con trỏ của lớp cha có thể trỏ vào đối tượng của lớp con. Thông qua con trỏ này có thể gọi phương thức chung của cả hai lớp và phiên bản của lớp con sẽ được thực hiện. #include using namespace std; class Shape { protected: int width, height; public: Shape( int a=0, int b=0) { width = a; height = b; } int area() { cout<<"Parent class area :"<<endl; return 0; } }; Class Shape #include "Shape.h" class Rectangle: public Shape{ public: Rectangle( int a=0, int b=0):Shape(a, b) { } int area () { cout<<"Rectangle class area:" <<endl; return (width * height); } }; Class Rectangle #include "Shape.h" class Triangle: public Shape{ public: Triangle(int a=0, int b=0):Shape::Shape(a,b) { } int area () { cout<<“Triangle class area:" <<endl; return (width * height/2); } }; Class Triangle Thử nghiệm #include "Rectangle.h" #include "Triangle.h" #include using namespace std; // Main function for the program int main( ) { Shape *shape; Rectangle rec(10,7); Triangle tri(10,5); // store the address of Rectangle shape = &rec; // call rectangle area. coutarea()<<endl; // store the address of Triangle shape = &tri; // call triangle area. coutarea()<<endl; return 0; } Early binding hay static linkage #include using namespace std; class Shape { protected: int width, height; public: Shape( int a=0, int b=0) { width = a; height = b; } virtual int area() { cout<<"Parent class area :"<<endl; return 0; } }; Class Shape #include "Shape.h" class Rectangle: public Shape{ public: Rectangle( int a=0, int b=0):Shape(a, b) { } int area () { cout<<"Rectangle class area:" <<endl; return (width * height); } }; Class Rectangle #include "Shape.h" class Triangle: public Shape{ public: Triangle( int a=0, int b=0):Shape(a, b) { } int area () { cout<<“Triangle class area:" <<endl; return (width * height/2); } }; Class Triangle Dùng từ khóa virtual để cho phép late binding hay dynamic linkage Thử nghiệm #include "Rectangle.h" #include "Triangle.h" #include using namespace std; // Main function for the program int main( ) { Shape *shape; Rectangle rec(10,7); Triangle tri(10,5); // store the address of Rectangle shape = &rec; // call rectangle area. coutarea()<<endl; // store the address of Triangle shape = &tri; // call triangle area. coutarea()<<endl; return 0; } Late binding hay dynamic linkage Lớp trừu tượng  Trong lớp Shape, phương thức int area() không cần thực thi  biến nó thành phương thức trừu tượng  Lớp có ít nhất một phương thức trừu tượng là lớp trừu tượng và không thể khởi tạo đối tượng từ lớp này.  Lớp trừu tượng chỉ được dùng cho mục đích làm lớp cơ sở cho lớp khác kế thừa. #include using namespace std; class Shape { protected: int width, height; public: Shape( int a=0, int b=0) { width = a; height = b; } virtual int area()=0; }; Class Shape Khuôn mẫu lớp template class MyArray { public: MyArray(int s=5){ if(s<=0)s=5; data = new T[s]; size=s;} ~MyArray(void){ delete data;} void SetValues() const{ for(int i=0;i>data[i];cout<<endl;} } T Max() const{ T max = data[0]; for(int i=1;imax)max=data[i]; return max;} void PrintOut() const{ for(int i=0; i<size;i++)cout<<setw(5)<<data[i]; cout<<endl;} private: int size; T *data; //chứa dữ liệu }; Thử nghiệm #include "MyArray.h" #include using namespace std; void main(){ MyArray a(4); //khởi tạo và cấp phát vùng nhớ cho a a.SetValues(); a.PrintOut(); cout<<"Max="<<a.Max()<<endl; }