Bài giảng Kỹ thuật lập trình - Chương 02: Một số vấn đề trong KTLT - Lương Mạnh Bá

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 02: Một số vấn đề trong KTLT - Lương Mạnh Bá

1. Chương II 1. Tổ chức chương trình 2. Biến cục bộ/Biến toàn cục 3. Cấu trúc dữ liệu động 4. Cấp phát tĩnh và cấp phát động Last update 8-2010 SE-SoICT KTLT-2.2
2. CT con (tiếp) • CT con thường gồm 2 loại tùy theo cách sử dụng: – CT con Hàm – CT con Thủ tục • CT con Hàm là CT con dùng để thực hiện 1 tính toán và trả về 1 giá trị của 1 kiểu DL hợp lệ qui định bởi NNLT đó. • CT con thủ tục thực hiện 1 nhiệm vụ phức tạp hơn (không nhất thiết là tính toán) và không trả về 1 kết quả nào. • Trong C không phân biệt 2 khái niệm này. Tuy nhiên vẫn được dùng theo phong cách chung . Last update 8-2010 SE-SoICT KTLT-2.4
3. CT con (tiếp) • Trong hàm, để trả về kết quả tính toán người ta dùng lệnh/biểu thức. Lệnh/biểu thức phụ thuộc vào NNLT. Trong C, lệnh trả về kết quả tính toán: return • Trong thủ tục không trả về kết quả nên dùng dạng “void” có nghĩa là rỗng, không có: không có giá trị, không có tham số. • Thí dụ void main(void) == main() • Lệnh gọi CT con hàm xuất hiện trong bt; lệnh gọi CT con thủ tục là 1 lệnh hợp lệ. Last update 8-2010 SE-SoICT KTLT-2.6
4. Quan hệ giữa CT gọi và CT được gọi • Khi CT con gọi (calling) 1 CT con khác (called) “giá trị” của tham số thực sẽ truyền cho tham số hình thức. • Như vậy mối quan hệ “gọi & được gọi” thông qua tham số (cách thức chuẩn trong LT). • Có nhiều cách truyền tham số: •Truyền trị (by val): giá trị của th/số thực sẽ truyền cho th/số hình thức. Mọi thay đổi giá trị của tham số hình thức trong CT con không làm thay đổi giá trị của tham số thực khi quay về CT gọi. • Cú pháp, ngữ nghĩa của Th/số hình thức!!! Last update 8-2010 SE-SoICT KTLT-2.8
5. Tham số truyền trị #include #include swap (int a, int b); { int temp = a; a = b; b= temp); Kết quả in ra } main() c = 5 d = 7 { int c = 5; int d = 7; clrscr(); swap (c,d); printf("\n c= %d d=%d",c,d); getch(); } Last update 8-2010 SE-SoICT KTLT-2.10
6. Tổ chức CT con • Để tiện sử dụng CT con được tổ chức theo nhiều hình thức khác nhau: 1. Trong cùng 1 chương trình với CT chính 2. Ghép thành đơn vị CT 3. Ghép thành mô đun (đơn thể chương trình) • Cách tổ chức thứ 2 và 3 tiện dụng hơn vì tính tái sử dụng. Các CT con của ND có thể chuyển vào Thư Viện chương trình của NNLT đó (các NNLT đều có công cụ hỗ trợ việc này. • TD: minh họa qua C/ Pascal. Last update 8-2010 SE-SoICT KTLT-2.12
7. 2.2 Biến cục bộ (local) và toàn cục (global) • Khi 1 CT được gọi nó được nạp vào bộ nhớ và thường trú trong bộ nhớ đến khi kết thúc thực hiện. Đó chính là vòng đời của CT => Do vậy các đại lượng định nghĩa trong CT đó cũng kết thúc vòng đời của mình. => Nảy sinh khái niệm biến cục bộ và biến toàn cục. • Biến cục bộ (local variables): Các biến được định nghĩa trong 1 CT và chỉ được sử dụng trong CT con đó. Nó có cùng vòng đời với CT sinh ra nó. Khái niệm cục bộ cũng là tương đối và phụ thuộc vào cách tổ chức CT. Nó là cục bộ của CT con đó song là toàn cục với CT con của nó. Last update 8-2010 SE-SoICT KTLT-2.14
8. Thí dụ int V[ ]; void inmang(int n) { Biến cục bộ của CT con inmang int i; for (i=0;i Lưu 8-2010 ý sử dụng biến toàn cSEục-SoICT để liên kết với CT con!!! KTLT-2.16
9. 2.3 Cấu trúc dữ liệu thay đổi • Trong quá trinh lập trình nhiều khi ta cần có kiểu dữ liệu đáp ứng được tình huống cụ thể. TD: 1. Học sinh phải học các môn học văn hóa như nhau. Tuy nhiên việc học nghề lại phụ thuộc vào giới tính: Nam học Mộc, Cơ khí; Nữ học Thêu, Cắm hoa, Vậy cấu trúc nào hỗ trợ biểu diễn đáp ứng tình huống trên. • Pascal: cấu trúc mẫu tin thay đỏi • C: dùng cấu trúc Union Last update 8-2010 SE-SoICT KTLT-2.18
10. Mẫu tin biến thể (tiếp) Typedef union { struct { long abscisse ; long ordonne; }cart; struct { float rho; float theta; }pol; coord p1,p2;// định nghĩa 2 điểm p1 và p2 => Truy nhập tới thành phần của các điểm: P1.cart.abscisse, p2.pol.theta Last update 8-2010 SE-SoICT KTLT-2.20
11. TD đọc ghi tệp nhị phân void main() { int i , j, n; mang A, B; FILE *fp; char filename[]="Mang.Txt"; clrscr(); if ((fp=fopen(filename,"w+"))==NULL) printf("\n Khong mo duoc tep!"); else { do { printf("\n so phan tu (1 10)); printf("\n nhap cac phan tu:"); for (i =0;i<n;i++) for (j=0;j<n;j++) {printf("\n A[%d,%d]=",i,j); scanf("%d",&A[i][j]); } fwrite(&A,sizeof(int), MAX * MAX,fp); Last update 8-2010 SE-SoICT KTLT-2.22
12. TD đọc ghi tệp văn bản void main() { char c; FILE *fv, *fr; char *filename="D_ghitep.cpp"; clrscr(); if ((fv=fopen(filename,"r+"))==NULL) printf("\n Khong mo duoc tep!"); else { filename= "D_ghitep.Txt"; if ((fr = fopen(filename,"w+")) == NULL); do { c = fgetc(fv); fputc(c,fr); } while (c != EOF); fclose(fv); fclose(fr); } Last update 8-2010 SE-SoICT KTLT-2.24
13. Cấu trúc bộ nhớ cơ bản • Vùng nhớ tĩnh còn gọi là stack dùng để lưu các CT hệ thống, Vùng nhớ các CT người dùng. Kích thước thấp Bộ nhớ tĩnh cố định (biết trước). Được cấp (Stack) phát từ địa chỉ thấp nhất và đi dần lên. •Vùng nhớ động gọi là Heap: vùng nhớ dành cho cấp phát động (không biết trước về số Bộ nhớ động lượng và kích thước). (Heap) • Các NNLT có các dẫn hướng Vùng cho phép LTV điều chỉnh/xin cấp nhớ cao phát vùng nhớ cho Heap và Stack. Last update 8-2010 SE-SoICT KTLT-2.26
14. Cấp phát động • Các biến này được cấp phát tại vùng nhớ động: Heap. Mỗi khi có yêu cầu sẽ được cấp phát. • Mỗi NNLT có cơ chế riêng: – Trong C ta dùng các hàm malloc, calloc, realloc và free để xin cấp phát, tái cấp phát và giải phóng bộ nhớ. Trong C++ là new vàdelete . – Việc cấp phát có thể cho từng biến (biến động có kiểu) hay cho cả 1 vùng nhớ (biến động không kiểu). – Khi vùng nhớ động bị tràn, HT sẽ thông báo heap overflow. TD: xem trong phần bổ sung trong C/C++ Last update 8-2010 SE-SoICT KTLT-2.28
15. Giải phóng bộ nhớ • delete ptr; // xóa1 biến đơn • delete [] ptr; // xóa1 biến mảng • ví dụ : #include int main() { int i,n; long total=100,x,*l; cout > n; l = new long [n]; if (l==NULL) exit(1); for (i=0;i > l[i] } Cout << “Danh sach cac so : \n” for (i=0;i<n;i++) cout << l[i] << “,”; delete []l; return 0; } Last update 8-2010 SE-SoICT KTLT-2.30
16. Bài tập 2 • Viết lại chương trình nhân hai ma trận của bài tập trước: ma trận được cấp phát động theo 2 cách. • Nộp listing CT kèm theo kết quả (ít nhất 3 kết quả). CT viết trên C hoặc C++. Chú ý in ma trận cùng với phân phối địa chỉ các phần tử • Đối sánh kết quả với bài tập trước Last update 8-2010 SE-SoICT KTLT-2.32
17. 1. Mảng • Là một dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên • Có thể là 1 hay nhiều chiều, C không giới hạn số chiều của mảng • Khai báo theo cú pháp sau : DataType ArrayName [size]; hooặc DataType ArrayN [Size1][Size2] ; Last update 8-2010 SE-SoICT KTLT-2.34
18. 2. Con trỏ • Khái niệm : Giá trị các biến được lưu trữ trong bộ nhớ MT, có thể truy cập tới các giá trị đó qua tên biến, đồng thời cũng có thể qua địa chỉ của chúng trong bộ nhớ (CTDL>). • Con trỏ thực chất là 1 biến mà nội dung của nó là địa chỉ của 1 đối tượng khác (biến, hàm, nhưng không phải 1 hằng số). • Có nhiều kiểu biến với các kích thước khác nhau, nên có nhiều kiểu con trỏ. Con trỏ int để trỏ tới biến hay hàm kiểu int, • Việc sử dụng con trỏ cho phép ta truy nhập tới 1 đối tượng gián tiếp qua địa chỉ của nó. • Trong C, con trỏ là một công cụ rất mạnh, linh hoạt. Last update 8-2010 SE-SoICT KTLT-2.36
19. Ví dụ : Đ/c bộ nhớ Giá trị Biến int i,j, *p; 100 i i= 5; p= & i; 102 j j= *p; *p= j+2; 104 p 100 5 i 100 5 i Gán i=5 gán p = & i 102 j 102 j 104 p 104 100 p 100 5 i 100 7 i gán j = *p *p = j+2 102 5 j 102 5 j 104 100 p 104 100 p Last update 8-2010 SE-SoICT KTLT-2.38
20. Các phép toán trên con trỏ • Một biến trỏ có thể cộng hoặc trừ với 1 số nguyên n để cho kết quả là 1 con trỏ cùng kiểu, là địa chỉ mới trỏ tới 1 đối tượng khác nằm cách đối tượng đang bị trỏ n phần tử • Phép trừ giữa 2 con trỏ cho ta khoảng cách (số phần tử ) giữa 2 con trỏ • Không có phép cộng, nhân, chia 2 con trỏ • Có thể dùng các phép gán, so sánh các con trỏ, nhưng cần chú ý đến sự tương thích về kiểu. Ví dụ : char *pchar; short *pshort; long *plong; sau khi xác lập địa chỉ cho các con trỏ, nếu : pchar ++; pshort ++; plong ++; và các địa chỉ ban đầu tương ứng của 3 con trỏ là 100, 200 và 300, thì kết quả ta có các giá trị tương ứng là : 101, 202 và 304 tương ứng. Last update 8-2010 SE-SoICT KTLT-2.40
21. Con trỏ void* • Là con trỏ không định kiểu (void *). Nó có thể trỏ tới bất kì một loại biến nào. Thực chất một con trỏ void chỉ chứa một địa chỉ bộ nhớ mà không biết rằng tại địa chỉ đó có đối tượng kiểu dữ liệu gì. => không thể truy cập nội dung của một đối tượng thông qua con trỏ void. Để truy cập được đối tượng thì trước hết phải ép kiểu con trỏ void về con trỏ có định kiểu của kiểu đối tượng. float x; int y; void *p; // khai báo con trỏ void p = &x; // p chứa địa chỉ số thực x *p = 2.5; // báo lỗi vì p là con trỏ void /* cần phải ép kiểu con trỏ void trước khi truy cập đối tượng qua con trỏ */ *((float*)p) = 2.5; // x = 2.5 p = &y; // p chứa địa chỉ số nguyên y *((int*)p) = 2; // y = 2 Last update 8-2010 SE-SoICT KTLT-2.42
22. Con trỏ xâu • Ta có : char tinhthanh[30] =“Da lat”; • Tương đương : char *tinhthanh; • tinhthanh=“Da lat”; • Hoặc : char *tinhthanh =“Da lat”; • Ngoài ra các thao tác trên xâu cũng tương tự như trên mảng • *(tinhthanh+3) = “l” • Chú ý : với xâu thường thì không thể gán trực tiếp như dòng thứ 3 Last update 8-2010 SE-SoICT KTLT-2.44
23. • Một ưu điểm khác của mảng trỏ là ta có thể hoán chuyển các đối tượng ( mảng con, cấu trúc ) được trỏ bởi con trỏ này bằng cách hoán chuyển các con trỏ • Ưu điểm tiếp theo là việc truyền tham số trong hàm • Ví dụ : Vào ds lớp theo họ và tên, sau đó sắp xếp để in ra theo thứ tự ABC. #include #include #define MAXHS 50 #define MAXLEN 30 Last update 8-2010 SE-SoICT KTLT-2.46
24. Con trỏ trỏ tới con trỏ • Bản thân con trỏ cũng là1 biến, vì vậy nó cũng có địa chỉ và có thể dùng1 con trỏ khác để trỏ tới địa chỉ đó. • ; • Ví dụ : int x 12= ; int *ptr = &x; int ptr_to_ptr = &ptr; • Có thể mô tả1 mảng 2 chiều qua con trỏ của con trỏ theo công thức : ArrName[i][k] = *(*(ArrName+i)+k) Với ArrName+i là địa chỉ của phần tử thứ i của mảng *(ArrName+i) cho nội dung ftử trên *(ArrName+i)+k là địa chỉ phần tử [i][k] Last update 8-2010 SE-SoICT KTLT-2.48
25. Dùng bộ nhớ động cho mảng Ta có thể coi một mảng 2 chiều là 1 mảng 1 chiều như hình sau : Gọi X là mảng hai chiều có kích thước m dòng và ncột. A là mảng một chiều tương ứng ,thì X[i][j] = A[ i*n +j]nếu phân bố theo hàng. Last update 8-2010 SE-SoICT KTLT-2.50
26. Dùng bộ nhớ động cho mảng (tiếp) void main() { int *A; int row, col, i, j; clrscr(); printf("\n so hang"); scanf("%d",&row); printf("\n so cot"); scanf("%d",&col); // cap phat vung nho cho mang A A = (int *) malloc (row * col *sizeof(int)); // nhap mang 1 for (i=0;i<row;i++) for (j=0;j<col;j++) { printf("M1[%d][%d]=",i,j); scanf("%d",A +i*row+j); } Last update 8-2010 SE-SoICT KTLT-2.52
27. Dùng bộ nhớ động cho mảng (cách 2) // chuong trinh thu cap phat dong cho mang 2 chieu row x col phan tu. // CT cap phat lan dau theo hang: Spt bang so hang voi con tro *A. // CT cap phat tiep theo cot voi con tro *(A+i) void main() { int A; int row, col, i, j; clrscr(); printf("\n so hang"); scanf("%d",&row); printf("\n so cot"); scanf("%d",&col); // cap phat vung nho cho mang 1, mang 2 *A = (int *) malloc (row *sizeof(int)); for (i=0;i <row;i++) *( A+i) = (int *) malloc (col *sizeof(int)); Last update 8-2010 SE-SoICT KTLT-2.54
28. CT cộng hai ma trận với mỗi ma trận được cấp phát động #include #include int main() { int M,N; int *A = NULL,*B = NULL,*C = NULL; clrscr(); cout >M; cout >N; //Cấp phát vùng nhớ cho ma trận A if (!AllocMatrix(&A,M,N)) { cout<<"Khong con du bo nho!"<<endl; return 1; } //Cấp phát vùng nhớ cho ma trận B if (!AllocMatrix(&B,M,N)) { cout<<"Khong con du bo nho!"<<endl; FreeMatrix(A);//Giải phóng vùng nhớ A return 1; Last update} 8-2010 SE-SoICT KTLT-2.56
29. //Cộng hai ma trận void AddMatrix(int *A,int *B,int*C,int M,int N) { for(int I=0;I<M*N;++I) C[I] = A[I] + B[I]; } //Cấp phát vùng nhớ cho ma trận int AllocMatrix(int A,int M,int N) { *A = new int [M*N]; if (*A == NULL) return 0; return 1; } //Giải phóng vùng nhớ void FreeMatrix(int *A) { if (A!=NULL) delete [] A; } Last update 8-2010 SE-SoICT KTLT-2.58
30. Phép tham chiếu Trong C, hàm nhận tham số là con trỏ đòi hỏi chúng ta phải thận trọng khi gọi hàm. Chúng ta cần viết hàm hoán đổi giá trị giữa hai số như sau: void Swap(int *X, int *Y); { int Temp = *X; *X = *Y; *Y = *Temp; } Để hoán đổi giá trị hai biến A và B thì chúng ta gọi hàm: Swap(&A, &B); Rõ ràng cách viết này không được thuận tiện lắm. Last update 8-2010 SE-SoICT KTLT-2.60
31. • Khi một hàm trả về một tham chiếu, chúng ta có thể gọi hàm ở phía bên trái của một phép gán. #include int X = 4; int & MyFunc() { return X; } int main() { cout<<"X="<<X<<endl; cout<<"X="<<MyFunc()<<endl; MyFunc() = 20; //Nghĩa là X = 20 cout<<"X="<<X<<endl; return 0; } Last update 8-2010 SE-SoICT KTLT-2.62
32. Chồng hàm (Functions overloading) • Trong c phải dùng 3 hàm để tính trị tuyệt đối ?: int abs(int i); long labs(long l); double fabs(double d); • C++ cho phép chúng ta tạo ra các hàm khác nhau có cùng một tên. int abs(int i); long abs(long l); double abs(double d); Last update 8-2010 SE-SoICT KTLT-2.64
33. Chồng toán tử • Trong ngôn ngữ C, khi chúng ta tự tạo ra một kiểu dữ liệu mới, chúng ta thực hiện các thao tác liên quan đến kiểu dữ liệu đó thường thông qua các hàm, điều này trở nên không thoải mái. • Ví dụ: cài đặt các phép toán cộng và trừ số phức Last update 8-2010 SE-SoICT KTLT-2.66
34. SP SetSP(double R,double I) { SP Tmp; Tmp.THUC = R; Tmp.Image = I; return Tmp; } SP AddSP(SP C1,SP C2) { SP Tmp; Tmp.THUC = C1.THUC+C2.THUC; Tmp.Image = C1.Image+C2.Image; return Tmp; } SP SubSP(SP C1,SP C2) { SP Tmp; Tmp.THUC = C1.THUC-C2.THUC; Tmp.Image = C1.Image-C2.Image; return Tmp; } void DisplaySP(SP C) { cout <<C.THUC <<‘ i ’ <<C.Image; Last update} 8-2010 SE-SoICT KTLT-2.68
35. #include //Dinh nghia so phuc struct { double THUC; double AO; }SP; SP SetSP(double R,double I); void DisplaySP(SP C); SP operator + (SP C1,SP C2); SP operator - (SP C1,SP C2); int main() { SP C1,C2,C3,C4; C1 = SetSP(1.1,2.0); C2 = SetSP(-3.0,4.0); cout<<"\nSo phuc thu nhat:"; DisplaySP(C1); cout<<"\nSo phuc thu hai:"; DisplaySP(C2); C3 = C1 + C2; C4 = C1 - C2; cout<<"\nTong hai so phuc nay:"; DisplaySP(C3); cout<<"\nHieu hai so phuc nay:"; DisplaySP(C4); return 0; } Last update 8-2010 SE-SoICT KTLT-2.70
36. Các giới hạn của chồng toán tử • Không thể định nghĩa các toán tử mới. • Hầu hết các toán tử của C++ đều có thể được chồng. Các toán tử sau không được chồng là : :: Toán tử định phạm vi. .* Truy cập đến con trỏ là trường của struct hay class. . Truy cập đến trường của struct hay class. ?: Toán tử điều kiện sizeof Các ký hiệu tiền xử lý . • Không thể thay đổi thứ tự ưu tiên của một toán tửcũng như số các toán hạng của nó. • Không thể thay đổi ý nghĩa của các toán tử khi áp dụng cho các kiểu có sẵn. • Chồng các toán tử không thể có các tham số có giá trịmặc định. Last update 8-2010 SE-SoICT KTLT-2.72