Bài giảng Cấu trúc dữliệu và giải thuật: Ôn tập - Đậu Ngọc Hà Dương

Bài giảng Cấu trúc dữliệu và giải thuật: Ôn tập - Đậu Ngọc Hà Dương có nội dung trình bày các kiến thức về con trỏ, đệ quy, cấu trúc; đồng thời đưa ra các dạng bài tập khác nhau để sinh viên luyện tập, nâng cao khả năng lập trình. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữliệu và giải thuật: Ôn tập - Đậu Ngọc Hà DươngCấutrúcdữliệuvàgiảithuật Ôn tập Giảng viên: Đậu Ngọc Hà Dương Nội dung trình bày2  Con trỏ  Đệ quy  Cấu trúc  Bài tập CấutrúcdữliệuvàgiảithuậtHCMUS2012 Nội dung trình bày3  Con trỏ  Đệ quy  Cấu trúc  Bài tập CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ4  Địa chỉ trong bộ nhớ: CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ5  Địa chỉ trong bộ nhớ: intX; X=5; CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ6  Khái niệm đặc biệt trong C/C++.  Biến con trỏ: loại biến dùng để chứa địa chỉ.  Khai báo: *; CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ7  Ví dụ: int*a; /*contrỏđếnkiểuint*/ float*b; /*contrỏđếnkiểufloat*/ NGAY*pNgay;/*contrỏđếnkiểuNGAY*/ SINHVIEN*pSV;/*contrỏđếnkiểuSINHVIEN*/ CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ8  Lưu ý:  Xácđịnhđịachỉônhớ:toántử&  Xácđịnhgiátrịcủaônhớtạiđịachỉtrongbiếncon trỏ:toántử*  ContrỏNULL.  Truycậpthànhphầntrongcấutrúc:> Cấutrúcd ữliệuvàgiảithuậtHCMUS2012 Con trỏ9  Cấp phát vùng nhớ động:  Cấpphát:toántửnew.  Hủy:toántửdelete.  Ví dụ: int *p; p = new int; //delete p; pấutrúcd C = new int[100]; ữliệ //delete uvàgiảithuậtHCMUS2012 []p; Con trỏ10  Ví dụ: int i; int *p; p = &i; int j; j = *p; int day = pNgay->ngay; CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ - Ví dụ11 #include int main() { int i,j; int *p; p = &i; *p = 5; j = i; printf(%d %d %d , i, j, *p); return Cấutrúcd 0; ảithuậtHCMUS2012 ữliệuvàgi Con trỏ - Ví dụ12 #include int main() { int i,j; int *p; /* a pointer to an integer */ p = &i; *p=5; j=i; printf(%d %d %d , i, j, *p); return 0; } CấutrúcdữliệuvàgiảithuậtHCMUS2012 Con trỏ - Ví dụ13 #include int main() { int i; int *p; p = &i; *p=5; printf(%d %d %d %d, i, *p, p, &p); return 0; }ấutrúcdữliệuvàgiảithuậtHCMUS2012 C Con trỏ - Ví dụ14 #include int main() { int i; int *p; p = &i; *p=5; printf(%d %d %d %d, i, *p, p, &p); return 0; }ấutrúcdữliệuvàgiảithuậtHCMUS2012 C Nội dung trình bày15  Con trỏ  Đệ quy  Cấu trúc  Bài tập CấutrúcdữliệuvàgiảithuậtHCMUS2012 Khái niệm16  Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách tường minh hay tiềm ẩn. CấutrúcdữliệuvàgiảithuậtHCMUS2012 Chú ý17  Khi viết hàm đệ quy, cần xác định:  Điềukiệndừng  Trườnghợpđệquy CấutrúcdữliệuvàgiảithuậtHCMUS2012 Ví dụ18  Tính tổng S(n) = 1 + 2 + … + n  Ta có:  S(n)=(1+2+…+n1)+n  Trườnghợpn>0:  S(n) = S(n-1) + n (điều kiện đệ quy)  Trườnghợpn=0  S(0) = 0 (điều kiện dừng) CấutrúcdữliệuvàgiảithuậtHCMUS2012 Ví dụ19  Tính tổng S(n) = 1 + 2 + … + n int Tong(int n) { if (n == 0)//điều kiện dừng return 0; return Tong(n-1) + n; } CấutrúcdữliệuvàgiảithuậtHCMUS2012 Ví dụ20  Viết hàm tính n! trong hai trường hợp: không đệ quy và đệ quy. Biết:  n!=1x2x3x…xn  0!=1 CấutrúcdữliệuvàgiảithuậtHCMUS2012 ...