Xem mẫu

  1. Chủ đề tuần này thế nào để sử dụng công cụ gỡ lỗi  Làm (gdb)  Cấu trúc dữ liệu cây - Cây nhị fân - Cây nhị fân tìm kiếm  Đệ quy tiến trình trên cây. 1
  2. Gdb để gỡ lỗi (1) the Gnu DeBugger (công cụ gỡ lỗi  gdb: của Gnu).  http://www.cs.caltech.edu/courses/cs11/materi  Sử dụng khi lõi chương trình hỏng.  Hoặc khi ta muốn đi xuyên suốt sự thi hành của chương trình theo từng dòng 1. 2
  3. Gdb for Debugging (2)  Trước khi sử dụng gdb : - Phải biên dịch mã nguồn C với cờ phụ là -g . - Điều này sẽ giúp đặt tất cả mã nguồn vào dạng nhị fân có thể thực thi được. - Sau đó ta có thể thực thi chương trình như sau: gdb chuongtrinh - Nuôi dưỡng 1 môi trường dịch. 3
  4. Gdb for Debugging (3) Gdb> run  Chương trình chạy.  Nếu tất cả đều tốt, chương trình sẽ thoát thành công, trả bạn về dấu nhắc.  Nếu có lỗi thì gdb sẽ báo cho bạn biết và huỷ bỏ chương trình. 4
  5. Gdb – Các câu lệnh cơ bản (1) ngược ngăn xếp (“where”)  Dò - Chương trình bị lỗi - Đâu là dòng lệnh cuối cùng trong chương trình được thực thi trước khi gặp lỗi? - Đó là điều lệnh where sẽ chỉ ra cho bạn. 5
  6. Gdb – Các câu lệnh cơ bản (2) hình minh hoạ lệnh “where” trong  Xem slide tiếng anh tr7. Last call: lần gọi cuối. 6
  7. Gdb – Các câu lệnh cơ bản (3) kiếm vùng trên cùng của stack dò  Tìm ngược tương ứng với lỗi của bạn.  Đề fòng với: - Free vùng nhớ mà bạn không cấp phát trước đó. - Truy nhập mảng sau phần tử cuối cùng của nó. - Con trỏ quy chiếu ngược không trỏ tới phần của khối đã được malloc(). 7
  8. Gdb – Các câu lệnh cơ bản (4) câu lệnh break,continue,next, step  Các - break: dừng sự thi hành ở dòng được chỉ ra. gdb> break foo.c: 100(đặt điểm break). - continue: tiếp tục lại sự thi hành từ điểm đó. - next: thực thi dòng lệnh tiếp theo, sau đó dừng lại. - step: thực thi câu lệnh tiếp theo. Đi vào trong hàm nếu cần thiết (next thì • không). 8
  9. Gdb – Các câu lệnh cơ bản (5)  Lệnh print và display  print: in ra giá trị của bất cứ biểu thức nào trong chương trình. gdb> print i $1 = 100  display: in ra 1 gia trị cụ thể mỗi lần mà thi hành dừng lại. gdb> display i 9
  10. Gdb – in mảng (1) cũng có thể dùng để in ra mảng  print int arr[] = {1,2,3};  gdb> print arr $1 = {1,2,3}  ($1 chỉ là tên của kết quả) print $1 $2 = {1,2,3} 10
  11. Gdb – in mảng (2) xảy ra vấn đề với các mảng được cấp  gdb phát động. int*arr; arr= (int*)malloc(3 * sizeof(int)); arr[0] = 1; arr[1] = 2; arr[2] = 3; gdb> print arr $1 = (int*) 0x8094610  Nó không thực sự hữu dụng. 11
  12. Gdb – in mảng (3) thể in mảng này sử dụng @ (cú pháp gdb  Có đặc biệt). int*arr; arr = (int*)malloc(3 * sizeof(int)); arr[0] = 1; arr[1] = 2; arr[2] = 3; gdb> print *arr@3 $2 = {1, 2, 3} 12
  13. Gdb – các kí tự viết tắt câu lệnh gdb thông thường có các  Các viết tắt sau: - p (giống print) - c (giống continue) - n (giống next) - s (giống step)  Thuận tiện hơn để sử dụng khi gỡ lỗi. 13
  14. Cây,cây nhị fân,cây tìm kiếm nhị fân sách liên kết là 1 cấu trúc tuyến tính, và rất  Danh khó sử dụng nó để tổ chức biểu diễn các đối tượng phân cấp.  Mặc dù stack và queue cũng fản ánh đôi chút về cấp bậc, nhưng nó bị giới hạn chỉ 1 chiều duy nhất.  Để thoát khỏi giới hạn này, ta tạo 1 kiểu dữ liệu mới gọi là tree bao gồm các node và các arc (cạnh,cung). Không giống với cây tự nhiên, những cây này được vẽ từ trên xuống với root ở trên cùng và các lá (leaf) ở dưới cùng. 14
  15. Cây gia đình (family tree) hình minh hoạ trong slide tiếng anh  Xem tr17. 15
  16. Định nghĩa của tree cây là 1 tập hợp xác định của 1 hay 1 nhiều node mà: - Có 1 node đắc biệt gọi là root. - Các node còn lại chúng lại phân hoạch thành n>=0 tập T1,T2,…Tn, mà mỗi tập này lại là 1 cây. - Ta gọi T1,T2,…Tn là các subtree(cây con) của root. 16
  17. Định nghĩa đệ quy (recursive definition) hình minh hoạ slide tiếng anh tr19.  Xem 17
  18. Binary tree(cây nhị fân) nhị fân là 1 cây mà không node nào  Cây của nó có quá 2 con.  Mỗi node có 0,1 hoặc 2 con. 18
  19. Biểu diễn liên kết Mỗi node của cây được biểu diễn như là 1 đối tượng  có cùng kiểu dữ liệu. Không gian yêu cầu bởi n node cây nhị fân = n *  (không gian yêu cầu của 1 node) typedef ... elmType; //bất cứ kiểu phần tử nào Element (data) typedef struct nodeType { elmType element; struct nodeType *left, *right; }; Con fải Con trái typedef struct nodeType *treetype; 19
  20. 1 cây nhị fân liên kết hình minh hoạ slide tiếng anh tr22  Xem 20
nguon tai.lieu . vn