Programming Methodology Data Structure

NỘI DUNG  KỸ THUẬT LẬP TRÌNH

Các cấu trúc điều khiển  Chương trình con  Mảng 1 và 2 chiều  Chuỗi  Con trỏ  Đệ Quy  Các hàm xử lý trong C/C++ 

NỘI DUNG  CẤU TRÚC DỮ LIỆU

Chồng (stacks)  Hàng đợi (Queues)  Danh sach lien ket (Don va Doi)  Các thuật tóan tìm kiếm và sắp xếp  Cây nhị phân 

HÌNH THỨC THI TỰ LUẬN KỸ THUẬT LẬP TRÌNH: 5Đ CẤU TRÚC DỮ LIỆU:5Đ

Cấu trúc điều khiển  Cấu trúc chọn lựa

if…else  Switch..case  Tóan tử điều kiện: expression_condition?a:b 

 Cấu trúc lặp

For  While  Do…while 

Cấu trúc điều khiển  Cấu trúc chọn lựa 

if…else

If (Condition_Expression) Statement_1 else Statement_2; Statement_3;

Cấu trúc điều khiển: switch..case switch(value) { case value_1: Block_1; break; case value_2: Block_2; break; -----case value_n: Block_n; break; default: Block_n+1; }

Cấu trúc điều khiển  Cấu trúc lặp: for

for( exp_1;exp_2;exp_3) Block_1; Block_2;

Cấu trúc điều khiển  Cấu trúc lặp: while

while(expression) Block_1; Block_2;

Cấu trúc điều khiển  Cấu trúc lặp: do…while

do { Block_1; }while(Expression); Block_2;

Chương trình con (CTC)  CTC  Biến tòan cục và cục bộ  Truyền tham số cho CTC

Chương trình con (CTC)  Định nghĩa prototype cho CTC

Type_data Fuction_Name (param_list); Type_data: mô tả kiểu dữ liệu trả về của CTC Ví dụ: int sum(float a, float b); Or: int sum(float, float); Đ/N chi tiết cho CTC Type_data Fuction_Name (param_list) { //write code here; // [ return value ] }

Chương trình con (CTC) float sum (float x, float y) { float kq; kq=x+y; return kq; } void outPut ( int n) { int i; for(i=0;i
Chương trình con (CTC)  Cách gọi CTC 

đ/v CTC có giá trị trả về  



Kq=sum (5,7) Cout<<“\n Tong la:”<<sum(5,7)

đ/v CTC không có giá trị trả về 

outPut(10);

Chương trình con (CTC)  Biến trong chương trình

Biến tòan cục  Biến cục bộ 

 Cách truyền tham số cho CTC

Truyền tham biến  Truyền tham thị 

Ví dụ về truyền tham số CTC float sum (float &x, float y) //truyen bang tham tri { float kq; kq=x+y; x--; return kq; } void swap( float &x, float &y)// truyen bang tham bient { //code here }

Mảng 1 và 2 chiều  Khai báo mảng 1 chiều:

Data_type array_name[num];  Data_type array_name[num]={initialize};  Data_type array_name[ ]={initialize} 

Ví dụ: int a[10]; float b[3]={2.4, 5.7, 10}; int c[ ]={4,7,-5,9,15};

Mảng 1 và 2 chiều  Các bài tóan liên quan đến thao tác trên

mảng một chiều: Tính tóan: theo một điều kiện nào đó  Tìm kiếm  Sắp xếp 

Mảng 1 và 2 chiều  Cách xử lý bài tóan liên quan đến thao tác

trên mảng một chiều: Giả sử mảng a có kích thước n phần tử: Xét các phần tử a[i] Nếu a[i] thỏa điều kiện bài tóan xử lý a[i] theo yêu cầu bài tóan

Mảng 1 và 2 chiều for(i=0;i
Mảng 1 và 2 chiều  Ví dụ: Viết chương trình nhập vào mảng a có kích thước n phần tử. Hãy thực hiện các thao tác sau: - Tính tổng các phần tử trong mảng - Tính tổng chẳn các phần tử trong mảng - Tính tổng các số nguyên tố có trong mảng - Đếm có bao nhiêu số nguyên tố có trong mảng Sắp xếp các phần tử chẳn trong mảng theo thứ tự tăng dần.

Mảng 1 và 2 chiều  Khai báo mảng 2 chiều:

Data_type array_name[Row][Col];  Data_type array_name[Row]{Col]={initialize};  Data_type array_name[ ][Col ]={initialize} 

Ví dụ: int a[2][2]; float b[2][2]={{2.4, 5.7},{3.5, 10}}; int c[ ][2]={{4},{7,-5},{9,15}};

Mảng 1 và 2 chiều  Cách xử lý bài tóan liên quan đến thao tác

trên mảng hai chiều: Giả sử mảng a có kích thước m dòng và n cột: Xét các phần tử a[i][j] Nếu a[i][i] thỏa điều kiện bài tóan xử lý a[i][j] theo yêu cầu bài tóan

Mảng 1 và 2 chiều for(i=0;i<m;i++) for(j=0;j
Mảng 1 và 2 chiều  Đối với mảng hai chiều nhưng yêu cầu xử lý

trên một dòng hoặc trên một cột, ta xử lý như sau: 

Nếu xử lý trên dòng: ta cố định dòng đó và chỉ số cột sẽ biến đổi

for( j=0;j
Mảng 1 và 2 chiều 

Nếu xử lý trên cột: ta cố định cột đó và chỉ số dòng sẽ biến đổi.

for( i=0;i<m;i++) if( a[i][const] thỏa đk) xử lý a[i][const];

Mảng 1 và 2 chiều  Ví dụ: Viết chương trình nhập vào mảng a có kích thước mxn Hãy thực hiện các thao tác sau: - Nhập/ xuất - Tính tổng các phần tử trong mảng - Tính tổng các số nguyên tố có trong mảng - Tính tổng các số không âm trên cột k - Tìm số nguyên tố lớn nhất trên dòng r - Sắp xếp các phần tử trong cột k theo thứ tự tăng dần. - Sắp xếp các phần tử nguyên tố trên cột k theo thứ tự giảm dần.

Chuỗi Chuỗi là tập hợp nhiều ký tự. Mỗi chuỗi kết thúc bởi \0. Khai báo: char variable[length]; char str[]={‘H’,’e’,’l’,’l’,’o’,’\0’}; char str[10]; char str[]=“Hello”; char *str=“Hello”;

Chuỗi Nhập: gets(str); cin>>str; Xuất: puts(str); cout<<str;

Chuỗi Bài tập: Cách giải bài tập chuỗi: Chúng ta cần tính chiều dài chuỗi Duyệt từng ký tự trong chuỗi (tương tự mảng) Xóa các ký tự x trong một chuỗi Đếm có bao nhiêu từ trong một chuỗi Đếm số lần xuất hiện của các ký tự trong chuỗi

Con trỏ  Con trỏ lưu địa chỉ của 1 biến

Type_data *pointer ; Ví dụ int x; int *p1,*p2; p=&x; p2=p1;

int a[10]; int *p; p=a; Khi đó: *(p+i) tương ứng với lệnh a[i]

Con trỏ  Phép tóan trên con trỏ (+,-)  Việc tăng lên giá trị tùy thuộc vào kiểu dữ liệu

của con trỏ.  Truy xuất giá trị: *pointer  Cấp phát bộ nhớ động Type_data *pointer; pointer=(type_data*)malloc(sizeof(type-data)) Hàm free(pointer) giải phóng bộ nhớ

Con trỏ  Cấp phát nhớ động trongC++: new, delete

Type_data *pointer; pointer= new type_data; delete pointer;

Đệ qui  Một hàm gọi là đệ qui nếu bên trong thân

hàm của nó gọi chính nó.  Khi viết đệ qui chúng ta cần xác định điều kiện dừng của bài tóan.

Đệ qui int giaiThua(int n) { int gt; if(n==1) return(1); gt =giaiThua(n-1)*n; return gt; }

int tongArray(int a[],int n) { int s; if(n==1) return a[0]; s=tongArray(a,n-1)+a[n-1]; return s; }

Data Structure  Một cấu trúc dữ liệu là một tập hợp của

những kiểu dữ liệu khác nhau được gộp lại với một cái tên duy nhất. Dạng thức của nó như sau: struct model_name { type1 element1; type2 element2; type3 element3; . .} object_name;

Data Structure struct products { char name [30]; float price; } Sanpham; products apple;products orange, melon; Tóan tử dấu chấm (“.”) Toán tử (->)

Data Structure products a,b; products *p; a. name; b. price p-> name; p->price (*p). name; (*p). price

Data Structure Từ khóa : typedef typedef struct { define attribute } type_data; typedef struct { char title[10] float price; } Products;

Ví dụ struct tagStudent { char name[10]; int birthday; 1. int result[5]; 5. }Student; 6. void main() 7. { 8. tagStudent p; 9. cin>>p.name; 10. cin>>p.birthday; 11. cin>>p.result[0]; 12. } 1. 2. 3. 4.

Ví dụ 1. 2. 3. 4. 1. 2. 3. 4. 5. 6. 7. 8.

struct tagStudent { char name[10]; int birthday; int result[5]; }Student; void main() { tagStudent *p; cin>>p->name; cin>>p->birthday; cin>>p->result[0]; }

Ví dụ 1. 2. 3. 4. 1. 2. 3. 4. 5. 6. 7. 8. 9.

struct tagStudent { char name[10]; int birthday; int result[5]; }; typedef tagStudent *Student; void main() { Student p; // tagStudent *p; cin>>p->name; cin>>p->birthday; cin>>p->result[0]; }

Thành phần cấu trúc chứa một cấu trúc 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

struct tagDMY { int day; int month; int year; }; struct tagPerson { char name[10]; tagDMY birthday; }Person;

Thành phần cấu trúc chứa một cấu trúc 1. tagPerson p; 2. 3. 4. 5. 6.

cin>>p.name; cin>>p.birthday.day; cin>>p.birthday.month; cin>>p.birthday.year;

Cấp phát và hủy vùng nhớ 1. new 2. delete

type_data *p; p=new type_data delete p;

Danh sách liên kết Sự khác nhau giữa mảng và DSLK. Array:

DSLK

Danh sách liên kết Các lọai danh sách liên kết DSLK đơn DSLK kép DSLK vòng

Danh sách liên kết đơn Mỗi phần tử trong danh sách chứa 2 thành phần: - Thông tin(hay dữ liệu) lưu trữ - Thông tin kết nối

Danh sách liên kết đơn infor

infor

pHead

typedef struct tagNode { information infor; struct tagNode *pNext; }NODE;

infor

infor

Danh sách liên kết đơn typedef struct tagList { NODE *pHead; NODE *pTail; }LIST; Mục tiêu lưu con trỏ pHead và pTail?

Cách tạo 1 Node Tạo mới 1 Node cần 2 yếu tố: - Cấp phát vùng nhớ cho Node - Gán thông tin cho Node: + Thông tin lưu trữ + Thông tin liên kết với phần tử kế tiếp.

Cách tạo 1 Node NODE* getNode(information object) { NODE *p; p=new NODE; if(p==NULL) exit(1); p->infor=object; p->pNext=NULL; return p; }

Ví dụ: tagPerson p; NODE *pNode; cin>>p.name; cin>>p.birthday.day; cin>>p.birthday.month; cin>>p.birthday.year; pNode=getNode(p);

Các thao tác trên DSLK đơn 1. Thêm   

Đầu Giữa Cuối

1. Xóa 2. Sửa 3. Duyệt

Các thao tác trên DSLK đơn 1. Thêm đầu

Có 2 trường hợp: - Danh sách rỗng - Danh sách đã có vài node Để thêm vào danh sách chúng ta cần các thông tin: - Danh sách cần thêm - Node cần thêm

Các thao tác trên DSLK đơn pHead

infor pHead

NULL

infor

infor

infor

NULL

Các thao tác trên DSLK đơn void AddFirst(LIST &list, NODE *pNew) { if(list.pHead==NULL) { list.pHead=pNew; list.pTail=list.pHead; } else { pNew->pNext=list.pHead; list.pHead=pNew; } }

Các thao tác trên DSLK đơn 2. Thêm cuối Có 2 trường hợp: - Danh sách rỗng - Danh sách đã có vài node Để thêm vào danh sách chúng ta cần các thông tin: - Danh sách cần thêm - Node cần thêm

Các thao tác trên DSLK đơn pHead

infor

NULL

infor

infor

infor

pHead pTail

NULL

Các thao tác trên DSLK đơn pHead

NULL

pNew

NULL

Các thao tác trên DSLK đơn pHead

pNew

pTail

NULL

Các thao tác trên DSLK đơn infor

infor

infor

infor

NULL

pHead pTail

pNew

NULL

Các thao tác trên DSLK đơn infor

infor

infor

infor

pHead pTail

pNew

NULL

Các thao tác trên DSLK đơn infor

infor

infor

infor

pHead pTail

pNew

NULL

Các thao tác trên DSLK đơn void AddEnd(LIST &list, NODE *pNew) { if(list.pHead==NULL) { list.pHead=pNew; list.pTail=list.Head; } else { list.pTail->pNext=pNew; list.pTail=pNew; } }

Các thao tác trên DSLK đơn 3. Thêm vào sau 1 node Có 2 trường hợp: - Danh sách rỗng - Danh sách đã có vài node Để thêm vào danh sách chúng ta cần các thông tin: - Danh sách cần thêm - Node cần thêm - Cần thêm vào sau node nào.

Các thao tác trên DSLK đơn pHead

NULL

q

infor

infor

infor

infor

pHead pNew

?

pTail

NULL

Các thao tác trên DSLK đơn

q

infor

infor

infor

infor

pHead pNew

?

pTail

NULL

Các thao tác trên DSLK đơn

q

infor

infor

infor

infor

pHead pNew

pTail

NULL

Các thao tác trên DSLK đơn

q

infor

infor

infor

infor

pHead pNew

pTail

NULL

Các thao tác trên DSLK đơn

q

infor pHead

infor

NULL

pTail pNew

?

Các thao tác trên DSLK đơn

q

infor pHead

infor

NULL

pTail pNew

?

Các thao tác trên DSLK đơn

q

infor pHead

infor pTail pNew

NULL

Các thao tác trên DSLK đơn

q

infor pHead

infor pTail pNew

NULL

Các thao tác trên DSLK đơn

q

infor pHead

infor pTail pNew

NULL

Các thao tác trên DSLK đơn void AddAfter(LIST &list, NODE *q, NODE *pNew) { if(q!=NULL) { pNew->pNext=q->pNext; q->pNext=pNew; if(q==list.pTail) list.pTail=pNew; } else { AddFirst(list,pNew); } }

Các thao tác trên DSLK đơn 4. Tìm kiếm 1 node Chúng ta duyệt tuần tự qua các node, xuất phát từ phần tử pHead. Chúng ta sẽ so sánh thông tin trong infor cái mà node lưu trữ so với thông tin tìm kiếm. Nếu không tìm thấy chúng ta sẽ di chuyển qua node kế tiếp dựa vào pNext.

Các thao tác trên DSLK đơn Các thông tin cần thiết cho duyệt 1 một tử: - Danh sách - Thông tin tìm kiếm B1 Tạo 1 con trỏ trỏ đến đầu danh sách. B2 Xét node hiện hành và so sánh với giá trị tìm kiếm B3 Lặp lại B2 đến khi gặp thông tin tìm kiếm hoặc duyệt đến cuối danh sách.

Các thao tác trên DSLK đơn NODE* FindInformation(LIST list, Information object) { NODE *p; p=list.pHead; while((p!=NULL)&&(p->infor!=object) p=p->pNext; return p; }

Các thao tác trên DSLK đơn 5. Hủy 1 node - Đầu -Giữa

Hủy phần tử đầu danh sách pHead

NULL

Hủy

infor pHead

infor

infor

infor

NULL

Hủy phần tử đầu danh sách

Hủy

infor

infor

pHead P

infor

infor

NULL

Hủy phần tử đầu danh sách

Hủy

infor

infor

pHead P

infor

infor

NULL

Hủy phần tử đầu danh sách

Hủy

infor

infor

pHead P

infor

infor

NULL

Hủy phần tử đầu danh sách

Hủy

infor

infor

pHead P

infor

infor

NULL

1. void DeleteNodeFirst(LIST &list) 2. { 3. NODE *p; 4. if(list.pHead!=NULL) 5. { 6. p=list.pHead; 7. list.pHead=p->pNext; 8. delete p; 9. if(list.pHead==NULL) 10. list.pTail=NULL; 11. } 12. }

Hủy phần tử sau một phần tử q pHead

NULL

q

infor

pHead

infor

Hủy

infor

p q

infor

pHead pTail

NULL

Hủy phần tử sau một phần tử q pHead

NULL

q

infor

pHead

infor

Hủy

infor

q

infor

pHead pTail

NULL

Hủy phần tử sau một phần tử q pHead

NULL

q

infor

pHead

infor

Hủy

infor

q

infor

pHead pTail

NULL

Hủy phần tử sau một phần tử q pHead

NULL

q

infor

pHead

infor

Hủy

infor

q

infor

pHead pTail

NULL

1. void DeleteNodeAfter(LIST &list,NODE *q) 2. { 3. NODE *p; 4. if(q!=NULL) 5. { 6. p=q->pNext; 7. if(p!=NULL) 8. { if(list.pTail==p) 9. list.pTail=q; 10. q->pNext=p->pNext; 11. delete p; 12. } 13. } 14. }