›
›

Bài giảng Kỹ thuật lập trình - Con trỏ - Pointer

pdf 53 trang hapham 1640
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Con trỏ - Pointer", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ky_thuat_lap_trinh_con_tro_pointer.pdf

Nội dung text: Bài giảng Kỹ thuật lập trình - Con trỏ - Pointer

  1. ConCon tr trỏỏ PointerPointer Trần Phước Tuấn tranphuoctuan.khoatoan.dhsp@gmail.com
  2. NNộộii dung dung 1. Đặt vấn đề - ctdl động, tại sao? 2. Con trỏ và kiểu dữ liệu động 3. Cấu trúc và con trỏ 4. Danh sách liên kết 5. Sắp xếp trên danh sách 9/16/2008 T.P.Tuấn - LTC 2
  3. 1.1. ĐĐặặtt v vấấnn đđềề ctdlctdl đđộộng,ng, t tạạii sao? sao?  Nhu cầu thực tế về kiểu dữ liệu: typedef struct NGUOI { char hoten[30]; CTDL động giải quyết được vấn đề này. Nó int soCMND; giải quyết như thế nào? NGUOI cha,me; }NGUOI; Khi khai báo một kiểu dữ liệu thì NNLT thường yêu cầu kiểu dữ liệu phải được xác định kích thước rõ ràng. Với nhu cầu trên không thể tính kích thước rõ ràng cho kiểu dữ liệu người. 9/16/2008 T.P.Tuấn - LTC 3
  4. 1.1. ĐĐặặtt v vấấnn đđềề ctdlctdl đđộộng,ng, t tạạii sao? sao? Vấn đề về hiệu quả sử dụng bộ nhớ Biến tĩnh trong NNLT Nhu cầu thực tế  Vùng nhớ của kiểu dữ liệu  Có nhiều biến tĩnh không cần tĩnh sẽ được sinh ra khi ta sử dụng nữa nhưng nó vẫn khai báo biến và mất đi khi ra tồn tại và chiếm bộ nhớ cho khỏi phạm vi khai báo hoặc đến khi chương trình hủy nó khi chương trình kết thúc đối đi theo đúng cơ chế của biến với các biến toàn cục. tỉnh gây lãng phí bộ nhớ.  Biến tĩnh trong chương trình  Trong chu kỳ sống của một không thay đổi được cấu trúc số đối tượng dữ liệu có thể hay độ lớn trong khi thực thi. thay đổi về cấu trúc, độ lớn như: danh sách học viên có thể tăng lên hoặc giảm xuống bất hợp lý. CTDL động giải quyết được vấn đề này. Nó 9/16/2008 giải quyếtT.P.Tu nhưấn thế- LTCnào? 4
  5. 1.1. ĐĐặặtt v vấấnn đđềề ctdlctdl đđộộng,ng, t tạạii sao? sao? Hạn chế về kích thước bộ nhớ cho các biến tĩnh  Tổng kích thước vùng nhớ dành cho tất cả các biến tĩnh chỉ là 64kb (1 segment bộ nhớ)  Nhu cầu thực tế: cần nhiều bộ nhớ hơn CTDL động giải quyết được vấn đề này. Nó giải quyết như thế nào? 9/16/2008 T.P.Tuấn - LTC 5
  6. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng Biến không động Kiểu con trỏ Biến động 9/16/2008 T.P.Tuấn - LTC 6
  7. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 7
  8. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng Biến không động  Được khai báo tường minh  Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này.  Đuợc cấp phát vùng nhớ trong vùng dữ liệu (data segment) hoặc là Stack (đối với biến nữa tĩnh – các biến cục bộ)  Kích thước không thay đổi trong suốt quá trình sống 9/16/2008 T.P.Tuấn - LTC 8
  9. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng Kiểu con trỏ  Một kiểu dữ liệu T được xác định bởi Tập giá trị mà nó có thể lưu trữ Tập các thao tác (phép toán) xử lý có thể thi hành trên tập giá trị đó.  Ví dụ: kiểu int (16) Tập giá trị [-32768, 32767] Tập các thao tác: +, -, *, /, %  Kiểu con trỏ (của 1 kiểu dữ liệu T) cũng vậy gồm: Tập giá trị là tập địa chỉ của kiểu dữ liệu T tương ứng Tập thao tác: tạo con trỏ đến đối tượng có kiểu T  Ví dụ: con trỏ số nguyên được khai báo như sau int *p; // có kích thước cố định 2 hay 4 byte tùy vào NNLT, loại con trỏ //Con trỏ kiểu int thì có thể lưu được địa chỉ của biến kiểu int. 9/16/2008 T.P.Tuấn - LTC 9
  10. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng  Biến động Biến động  Không được khai báo tường minh  Có thể được cấp pháp hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu.  Các biến này không theo quy tắc phạm vi (tĩnh)  Vùng nhớ của biến được cấp phát trong Heap.  Kích thước có thể thay đổi trong quá trình sống  Con trỏ làm nhiệm vụ quản lý các biến này bằng cách lưu địa chỉ vùng nhớ của chúng.  Ví dụ: int *p,*q; p=new int; //xin cấp phát vùng nhớ kiểu int q=new int[10]; //xin cấp phát 10 vùng kiểu int . //sử dụng các biến động ở đây delete p; //trả lại vùng nhớ cho hệ thống delete [ ]q; //trả lại vùng nhớ cho hệ thống 9/16/2008 T.P.Tuấn - LTC 10
  11. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 11
  12. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 12
  13. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 13
  14. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 14
  15. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng int x; int *p, *q; p=&x; q=&x; 9/16/2008 T.P.Tuấn - LTC 15
  16. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 16
  17. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 17
  18. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng 9/16/2008 T.P.Tuấn - LTC 18
  19. 2.2. ConCon tr trỏỏ vvàà kikiểểuu d dữữ liliệệuu đđộộngng Ví dụ về việc xin cấp phát biến động: #include void main() { int *p; p=new int; //xin cấp phát 1 vùng nhớ *p=4; printf(“Gia tri cua vung nho do p quan ly: %d”, *p); delete p; //trả lại vùng nhớ sau khi đã sử dụng xong } 9/16/2008 T.P.Tuấn - LTC 19
  20. 3.3. C Cấấuu tr trúúcc v vàà concon tr trỏỏ #include typedef struct PHANSO { int tu, mau; }PHANSO; void main() { PHANSO x; x.tu=3;x.mau=8; printf(“%d/%d”,x.tu,x.mau); PHANSO *a; a=new PHANSO; a->tu=5; // (*a).tu=5; a->mau=7; // (*a).mau=7; printf(“Phan so: %d/%d”,a->tu,a->mau); delete a; } 9/16/2008 T.P.Tuấn - LTC 20
  21. 4.4. DanhDanh s sááchch liên liên k kếếtt  Mảng là một hình thức liên kết ngầm  Các phần tử trong mảng được cấp phát vùng nhớ một cách liên tiếp nhau  Với T là kiểu dữ liệu cho trước, xét mảng các phần tử kiểu T. Ta có: Address(i)=Address(0)+(i-1)*sizeoof(T). 0 1 2 3 4 9 5 4 0 2 9/16/2008 T.P.Tuấn - LTC 21
  22. 4.4. DanhDanh s sááchch liên liên k kếếtt  Có nhiều loại danh sách liên kiết như:  Danh sách liên kết đơn  Danh sách liên kết kép  Danh sách liên kết vòng  .  Trong môn này ta tìm hiểu kỹ về danh sách liên kết đơn 9/16/2008 T.P.Tuấn - LTC 22
  23. 4.4. DanhDanh s sááchch liên liên k kếếtt 9/16/2008 T.P.Tuấn - LTC 23
  24. 4.4. DanhDanh s sááchch liên liên k kếếtt 9/16/2008 T.P.Tuấn - LTC 24
  25. 4.4. DanhDanh s sááchch liên liên k kếếtt 9/16/2008 T.P.Tuấn - LTC 25
  26. 4.4. DanhDanh s sááchch liên liên k kếếtt 9/16/2008 T.P.Tuấn - LTC 26
  27. 4.4. DanhDanh s sááchch liên liên k kếếtt 9/16/2008 T.P.Tuấn - LTC 27
  28. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn  Tạo danh sách  Khai báo danh sách liên kết  Khởi tạo danh sách liên kết  Tạo mới một phần tử để thêm vào danh sách liên kết  Thêm vào đầu danh sách  Thêm vào cuối danh sách  Xuất dữ liệu của toàn bộ danh sách liên kết  Thêm vào sau một phần tử cho trước  Tìm kiếm  Tìm một phần tử có khóa cho trước  Tìm một phần tử đứng trước một phần tử cho trước  Hủy danh sách  Hủy một phần tử đầu danh sách  Hủy một phần tử cuối danh sách  Hủy một phần tử sau một phần tử cho trước  Hủy một phần tử có khóa cho trước  Hủy toàn bộ danh sách 9/16/2008 T.P.Tuấn - LTC 28
  29. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn typedef struct NODE { int data; // 2 byte (dos) NODE* next; // 2 byte (dos) }NODE; typedef struct LIST { NODE* pHead; NODE* pTail; }LIST; 9/16/2008 Khai báo T.P.Tudanhấ nsách - LTC liên kết 29
  30. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void KhoiTao(LIST &l) { l.pHead=NULL; l.pTail=NULL; } Việc khởi tạo danh sách liên kết nhằm xác định danh sách ban đầu mới tạo ra là rỗng 9/16/2008 Khởi tạo T.P.Tudanhấ nsách - LTC liên kết 30
  31. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn NODE* GetNode(int x) { NODE* p; p=new NODE; p->next=NULL; p->data=x; return p; } 9/16/2008 Tạo mới một phầnT.P.Tu tử đấển -thêm LTC vào danh sách 31
  32. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Danh sách rỗng 2. Danh sách đã có phần tử 9/16/2008 Thêm một phần tửT.P.Tuvào ấđần -u LTC danh sách liên kết 32
  33. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void AddHead(LIST &l, NODE* add) { if(l.pHead==NULL) { l.pHead=l.pTail=add; } else { add->next=l.pHead; l.pHead=add; } } 9/16/2008 Thêm một phần tửT.P.Tuvào ấđần -u LTC danh sách liên kết 33
  34. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Danh sách rỗng 2. Danh sách đã có phần tử 9/16/2008 Thêm một phần tửT.P.Tuvào ấcun -ố LTCi danh sách liên kết 34
  35. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void AddTail(LIST &l, NODE* add) { if(l.pHead==NULL) { l.pHead=l.pTail=add; } else { l.pTail->next=add; l.pTail=add; } } 9/16/2008 Thêm một phần tửT.P.Tuvào ấcun -ố LTCi danh sách liên kết 35
  36. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void PrintfList(LIST l) { NODE* p; p=l.pHead; while(p!=NULL) { printf(“ >%d”,p->data); p=p->next; } } 9/16/2008 Xuất dữ liệu cT.P.Tuủa danhấn - LTC sách liên kết 36
  37. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Danh sách rỗng 2. Danh sách đã có phần tử q 9/16/2008 Thêm một phần tử vàoT.P.Tu sauấn -m LTCột phần tử cho trước 37
  38. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void AddAfter(LIST &l, NODE* q, NODE* add) { if(q!=NULL) { add->next=q->next; q->next=add; if(q==l.pTail) l.pTail=add; } else { AddHead(l,add); } } 9/16/2008 Thêm một phần tử vàoT.P.Tu sauấn -m LTCột phần tử cho trước 38
  39. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn Sử dụng 1 con trỏ phụ p để duyệt tất cả các phần tử trong danh sách liên kết 9/16/2008 Tìm một phần tử trong danhT.P.Tu sáchấn - LTCliên kết khi biết khóa (data) 39
  40. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn NODE* Search(LIST l, int data) { NODE* p=l.pHead; while((p!=NULL) && (p->data!=data)) p=p->next; return p; } Kết quả trả về là NULL tức là không tìm thấy phần tử có khóa data Ngược lại nếu tìm thấy thì nó sẽ trả về địa chỉ của phần tử đầu tiên có khóa data trong danh sách liên kết. 9/16/2008 Tìm một phần tử trong danhT.P.Tu sáchấn - LTCliên kết khi biết khóa (data) 40
  41. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn NODE* SearchPre(LIST l, NODE* s) { NODE* p=l.pHead; while((p!=NULL) && (p->next!=s)) p=p->next; return p; } 9/16/2008 Tìm một phần tử đứngT.P.Tu trướấnc - LTCmột phần tử cho trước 41
  42. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Tách phần tử đầu ra khỏi danh sách 2. Xóa phần tử này 9/16/2008 Hủy phần tử đầuT.P.Tu trongấn -danh LTC sách liên kết 42
  43. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void RemoveHead(LIST &l) { if(l.pHead!=NULL) { p=l.pHead; l.pHead=l.pHead->next; delete p; if(l.pHead==NULL) l.pTail=NULL; } } 9/16/2008 Hủy phần tử đầuT.P.Tu trongấn -danh LTC sách liên kết 43
  44. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Tách phần tử cuối ra khỏi danh sách 2. Gán pTail = địa chỉ của phần tử kế cuối 3. Xóa phần tử này 9/16/2008 Hủy phần tử cuốT.P.Tui trongấn -danh LTC sách liên kết 44
  45. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void RemoveTail(LIST &l) { if(l.pHead==NULL) return; NODE *p=l.pTail; l.pTail=SearchPre(l,l.pTail); delete p; if(l.pTail!=NULL) l.pTail->next=NULL; else l.pHead=NULL; } 9/16/2008 Hủy phần tử cuốT.P.Tui trongấn -danh LTC sách liên kết 45
  46. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Tách phần tử p ra khỏi danh sách liên kết 2. Xóa phần tử này q 9/16/2008 Hủy phần tử sau phầnT.P.Tu tử qấn trong- LTC danh sách liên kết 46
  47. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void RemoveAfter(LIST &l, NODE* q) { NODE* p; if(q!=NULL) Lưu ý: q là phần tử trong { danh sách liên kết p=q->next; if(p!=NULL) { if(p==l.pTail) l.pTail=q; q->next=p->next; delete p; } } else RemoveHead(l); } 9/16/2008 Hủy phần tử sau phầnT.P.Tu tử qấn trong- LTC danh sách liên kết 47
  48. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn 1. Tìm phần tử p có khóa k và phần tử q trước nó 2. Tách phần tử p ra khỏi danh sách liên kết 3. Xóa nó K=39 q 9/16/2008 Hủy phần tửT.P.Tucó khóấn - LTCa k cho trước 48
  49. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn void Remove (LIST &l, int k) { NODE* p=l.pHead,*q=NULL; while((p!=NULL)&&(p->data!=k)) { q=p; p=p->next; } if(p==NULL) return; if(q!=NULL) { if(p==l.pTail) { l.pTail=q; l.pTail->next=NULL; } q->next=p->next; delete p; } else // p là phần tử đầu tiên (pHead) RemoveHead(l); } 9/16/2008 Hủy phần tửT.P.Tucó khóấn - LTCa k cho trước 49
  50. 4.4. DanhDanh s sááchch liên liên k kếếtt đơđơnn Cách 1: void RemoveList (LIST &l, int k) { while(l.pHead!=NULL) RemoveHead(l); } Cách 2: void RemoveList (LIST &l) { while(l.pHead!=NULL) { p=l.pHead; l.pHead=l.pHead->next; delete p; } l.pTail=NULL; } 9/16/2008 Hủy toàn bộT.P.Tudanhấn - sách LTC liên kết 50
  51. 5.5. S Sắắpp x xếếpp trên trên danh danh s sááchch liên liên k kếếtt void ListSelectionSort (LIST &l) { NODE* min; //trỏ đến pt có data min NODE* i,*j; for(i = l.pHead;i->next!=NULL;i=i->next) { min=i; for(j=i->next;j!=NULL;j=j->next) if(j->data data) min=j; HoanVi(min->data,i->data); } } 9/16/2008 Selection Sort – Hoán T.P.Tuvị nộấin dung- LTC phần dữ liệu (data) 51
  52. 5.5. S Sắắpp x xếếpp trên trên danh danh s sááchch liên liên k kếếtt void ListSelectionSort (LIST &l) { NODE *i,*j,*min, *minpre=NULL; LIST lresult;KhoiTao(lresult); while(l.pHead!=NULL) //danh dách chưa hết { min=l.pHead;minpre=NULL; for(j=min,i=min->next;i!=NULL;j=i,i=i->next) if(i->data data) { min=i; minpre=j; } if(minpre==NULL) { l.pHead=l.pHead->next;if(min==l.pTail) l.pTail=NULL; } else { if(min==l.pTail) l.pTail=minpre;minpre->next=min->next; } min->next=NULL; AddTail(lresult,min); } l=lresult; } 1. Tìm pt min có data nhỏ nhất 2. Tách min ra khỏi danh sách 3. Thêm min vào đầu ds mới 9/16/2008 Selection SortT.P.Tu – Thayấn - LTCđổi mối liên kết 52
  53. 9/16/2008 T.P.Tuấn - LTC 53