›

Bài giảng Hệ điều hành - Chương 4: Khái quát về cáu trúc dữ liệu

pdf 32 trang huongle 6810
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 4: Khái quát về cáu trúc dữ liệu", để 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_he_dieu_hanh_chuong_4_khai_quat_ve_cau_truc_du_lie.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Khái quát về cáu trúc dữ liệu

  1. Kỹ thuật lập trình 1 g n 0101010101010101100001 ươ Chương 4: Khái01010101010101011000010101010101010101100001quát về cấu StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop()trúc110010110010001000001011001011001000100000101100101100100010000010dữ liệu 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 N 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; Ơ 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 9/8/2006 2004, HOÀNG MINH S ©
  2. Nộidung chương 4 4.1 Cấutrúcdữ liệulàgì? 4.2 Mảng và quảnlýbộ nhớ₫ộng 4.2 Xây dựng cấu trúc Vector 4.3 Xây dựng cấutrúcList N Ơ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 2 Ch ©
  3. 4.1 Giớithiệuchung ƒ Phầnlớn các bài toán trong thựctế liên quan tớicác dữ liệuphứchợp, những kiểudữ liệucơ bảntrong ngôn ngữ lập trình không ₫ủ biểudiễn ƒ Ví dụ: —Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV, —Môhìnhhàmtruyền: Đathứctử số, ₫athứcmẫusố —Môhìnhtrạng thái: Các ma trận A, B, C, D —Dữ liệuquátrình: Tên₫ạilượng, dải ₫o, giá trị, ₫ơnvị, thời gian, cấpsaisố, ngưỡng giá trị, N — Đốitượng ₫ồ họa: Kích thước, màu sắc, ₫ường nét, phông Ơ chữ, ƒ Phương pháp biểudiễndữ liệu: ₫ịnh nghĩakiểudữ liệumớisử dụng cấu trúc (struct, class, union, ) 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 3 Ch ©
  4. Vấn ₫ề: Biểudiễntậphợpdữ liệu ƒ Đasố những dữ liệuthuộcmột ứng dụng có liên quan với nhau => cầnbiểudiễntrongmộttậphợpcócấu trúc, ví dụ: — Danhsáchsinhviên: Cácdữ liệu sinh viên ₫ượcsắpxếptheo thứ tự Alphabet —Mộ hình tổng thể cho hệ thống ₫iều khiển: Bao gồm nhiều thành phầntương tác —Dữ liệuquátrình: Mộttậpdữ liệucóthể mang giá trị của một ₫ạilượng vào các thời ₫iểmgián₫oạn, các dữ liệu ₫ầu vào liên quan tớidữ liệu ₫ầura — Đốitượng ₫ồ họa: Mộtcửasổ bao gồm nhiều ₫ốitượng ₫ồ N họa, mộtbảnvẽ cũng bao gồm nhiều ₫ốitượng ₫ồ họa Ơ ƒ Thông thường, các dữ liệutrongmộttậphợpcócùng kiểu, hoặcítralàtương thích kiểuvớinhau ƒ Kiểumảng không phải bao giờ cũng phù hợp! 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 4 Ch ©
  5. Vấn ₫ề: Quảnlý(tậphợp) dữ liệu ƒ Sử dụng kếthợpmộtcáchkhéoléokiểucấutrúcvà kiểumảng ₫ủ ₫ể biểudiễncáctậphợpdữ liệubấtkỳ ƒ Các giảithuật (hàm) thao tác vớidữ liệu, nhằmquản lý dữ liệumộtcáchhiệuquả: —Bổ sung mộtmụcdữ liệumớivàomột danh sách, mộtbảng, mộttậphợp, —Xóamộtmụcdữ liệutrongmột danh sách, bảng, tậphợp, —Tìmmộtmụcdữ liệutrongmột danh sách, bảng tậphợp, theo mộttiêuchuẩncụ thể —Sắpxếpmột danh sách theo mộttiêuchuẩnnào₫ó N Ơ — 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 5 Ch ©
  6. QuảnlýDL thế nàolàhiệuquả? ƒ Tiếtkiệmbộ nhớ: Phần "overhead" không ₫áng kể so vớiphầndữ liệuthực ƒ Truy nhập nhanh, thuậntiện: Thờigiancầnchobổ sung, tìm kiếm và xóa bỏ các mụcdữ liệuphảingắn ƒ Linh hoạt: Số lượng các mụcdữ liệu không (hoặcít) bị hạnchế cố₫ịnh, không cầnbiếttrướckhitạocấu trúc, phù hợpvớicả bài toán nhỏ và lớn ƒ Hiệuquả quảnlýdữ liệuphụ thuộcvào —Cấutrúcdữ liệu ₫ượcsử dụng N —Giảithuật ₫ượcápdụng cho bổ sung, tìm kiếm, sắpxếp, xóa Ơ bỏ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 6 Ch ©
  7. Các cấutrúcdữ liệu thông dụng ƒ Mảng (nghĩarộng): Tậphợpcácdữ liệucóthể truy nhậptùyý theochỉ số ƒ Danh sách (list): Tậphợpcácdữ liệu ₫ược móc nối ₫ôi mộtvớinhauvàcóthể truy nhậptuầntự ƒ Cây (tree): Tậphợpcácdữ liệu ₫ược móc nốivới nhau theo cấutrúccây, cóthể truy nhậptuầntự từ gốc —Nếumỗi nút có tối ₫a hai nhánh: cây nhị phân (binary tree) ƒ Bìa, bảng (map): Tậphợpcácdữ liệucósắpxếp, có thể truy nhậprất nhanh theo mã khóa (key) N ƒƠ Hàng ₫ợi (queue): Tậphợpcácdữ liệucósắpxếp tuầntự, chỉ bổ sung vào từ một ₫ầuvàlấyratừ₫ầu còn lại 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 7 Ch ©
  8. Các cấutrúcdữ liệu thông dụng (tiếp) ƒ Tậphợp(set): Tậphợpcácdữ liệu ₫ượcsắpxếptùyý nhưng có thể truy nhậpmộtcáchhiệuquả ƒ Ngănxếp (stack): Tậphợpcácdữ liệu ₫ượcsắpxếp tuầntự, chỉ truy nhập ₫ượctừ một ₫ầu ƒ Bảng hash (hash table): Tậphợpcácdữ liệu ₫ượcsắp xếpdựatheomộtmãsố nguyên tạoratừ mộthàm ₫ặcbiệt ƒ Bộ nhớ vòng (ring buffer): Tương tự như hàng ₫ợi, nhưng dung lượng có hạn, nếuhếtchỗ sẽ₫ượcghi N Ơ quay vòng ƒ Trong toán họcvàtrong₫iềukhiển: vector, ma trận, ₫athức, phân thức, hàm truyền, 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 8 Ch ©
  9. 4.2 Mảng và quảnlýbộ nhớ₫ộng ƒ Mảng cho phép biểudiễnvàquảnlýdữ liệumộtcách khá hiệuquả: — Đọcvàghidữ liệurất nhanh qua chỉ số hoặcqua ₫ịachỉ —Tiếtkiệmbộ nhớ ƒ Các vấn ₫ề củamảng tĩnh: VD: Student student_list[100]; —Số phầntử phảilàhằng số (biếttrước khi biên dịch, ngườisử dụng không thể nhậpsố phầntử, không thể cho số phầntừ là mộtbiến) => kém linh hoạt N Ơ —Chiếmchỗ cứng trong ngănxếp(₫ốivớibiếncụcbộ) hoặc trong bộ nhớ dữ liệuchương trình (₫ốivớibiếntoàncục) => sử dụng bộ nhớ kém hiệuquả, kém linh hoạt 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 9 Ch ©
  10. Mảng ₫ộng ƒ Mảng ₫ộng là mộtmảng ₫ượccấpphátbộ nhớ theo yêu cầu, trong khi chương trình chạy #include /* C */ int n = 50; float* p1= (float*) malloc(n*sizeof(float)); /* C */ double* p2= new double[n]; // C++ ƒ Sử dụng con trỏ₫ểquảnlýmảng ₫ộng: Cách sử dụng không khác so vớimảng tĩnh p1[0] = 1.0f; N p2[0] = 2.0; Ơ ƒ Sau khi sử dụng xong => giải phóng bộ nhớ: free(p1); /* C */ delete [] p2; // C++ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 10 Ch ©
  11. Cấpphátvàgiải phóng bộ nhớ₫ộng ƒ C: —Hàmmalloc() yêu cầuthamsố là số byte, trả về con trỏ không kiểu(void*) mang ₫ịachỉ vùng nhớ mới ₫ượccấp phát (nằm trong heap), trả về 0 nếu không thành công. —Hàmfree() yêu cầuthamsố là con trỏ không kiểu(void*), giải phóng vùng nhớ có ₫ịachỉ₫ưavào ƒ C++: —Toántử new chấpnhậnkiểudữ liệuphầntử kèm theo số lượng phầntử củamảng cầncấpphátbộ nhớ (trong vùng heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công. N Ơ —Toántử delete[] yêu cầuthamsố là con trỏ có kiểu. —Toántử new và delete còn có thể áp dụng cho cấpphátvà giải phóng bộ nhớ cho mộtbiến ₫ơn, một ₫ốitượng chứ không nhấtthiếtphảimộtmảng. 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 11 Ch ©
  12. Mộtsố₫iềucầnlưuý ƒ Con trỏ có vai trò quảnlýmảng (₫ộng), chứ con trỏ không phải là mảng (₫ộng) ƒ Cấpphátbộ nhớ và giải phóng bộ nhớ chứ không phảicấpphát con trỏ và giải phóng con trỏ ƒ Chỉ giải phóng bộ nhớ mộtlần int* p; p[0] = 1; // never do it new(p); // access violation! p = new int[100]; // OK p[0] = 1; // OK int* p2=p; // OK delete[] p2; // OK N Ơ p[0] = 1; // access violation! delete[] p; // very bad! p = new int[50]; // OK, new array 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 12 Ch ©
  13. Cấpphátbộ nhớ₫ộng cho biến ₫ơn ƒ Ý nghĩa: Các ₫ốitượng có thể₫ượctạora₫ộng, trong khi chương trình chạy(bổ sung sinh viên vào danh sách, vẽ thêm mộthìnhtrongbảnvẽ, bổ sung mộtkhâutronghệ thống, ) ƒ Cú pháp int* p = new int; *p = 1; p[0]= 2; // the same as above p[1]= 1; // access violation! int* p2 = new int(1); // with initialization delete p; delete p2; N Student* ps = new Student; Ơ ps->code = 1000; delete ps; ƒ Mộtbiến ₫ơn khác vớimảng mộtphầntử! 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 13 Ch ©
  14. Ý nghĩacủasử dụng bộ nhớ₫ộng ƒ Hiệusuất: —Bộ nhớ₫ượccấpphát₫ủ dung lượng theo yêu cầuvàkhi ₫ượcyêucầutrongkhichương trình ₫ãchạy —Bộ nhớ₫ượccấpphátnằm trong vùng nhớ tự do còn lạicủa máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của máy tính —Bộ nhớ có thể₫ượcgiải phóng khi không sử dụng tiếp. ƒ Linh hoạt: —Thờigian"sống" củabộ nhớ₫ượccấpphát₫ộng có thể kéo dài hơnthời gian "sống" củathựcthể cấpphátnó. —Cóthể mộthàmgọilệnh cấpphátbộ nhớ, nhưng mộthàm N Ơ khác giải phóng bộ nhớ. —Sự linh hoạtcũng dễ dẫn ₫ếnnhững lỗi"ròrỉ bộ nhớ". 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 14 Ch ©
  15. Ví dụ sử dụng bộ nhớ₫ộng trong hàm Date* createDateList(int n) { Date* p = new Date[n]; return p; } void main() { int n; cout > n; Date* date_list = createDateList(n); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 15 Ch ©
  16. Tham số₫ầuralàcon trỏ? void createDateList(int n, Date* p) { p = new Date[n]; } void main() { int n; cout > n; Date* date_list; createDateList(n, date_list); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 16 Ch ©
  17. 4.3 Xây dựng cấutrúcVector ƒ Vấn ₫ề: Biểudiễnmột vector toán họctrongC/C++? ƒ Giải pháp chân phương: mảng ₫ộng thông thường, nhưng —Sử dụng không thuậntiện: Ngườisử dụng tự gọicáclệnh cấpphát và giải phóng bộ nhớ, trong các hàm luôn phải ₫ưathamsố là số chiều. —Sử dụng không an toàn: Nhầmlẫnnhỏ dẫn ₫ếnhậuquả nghiêm trọng int n = 10; double *v1,*v2, d; v1 = (double*) malloc(n*sizeof(double)); v2 = (double*) malloc(n*sizeof(double)); N Ơ d = scalarProd(v1,v2,n); // scalar_prod đãcó d = v1 * v2; // OOPS! v1.data[10] = 0; // OOPS! free(v1); free(v2); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 17 Ch ©
  18. Định nghĩacấutrúcVector ƒ Tên file: vector.h ƒ Cấutrúcdữ liệu: struct Vector { double *data; int nelem; }; ƒ Khai báo các hàm cơ bản: Vector createVector(int n, double init); void destroyVector(Vector); double getElem(Vector, int i); void putElem(Vector, int i, double d); N Vector addVector(Vector, Vector); Ơ Vector subVector(Vector, Vector); double scalarProd(Vector, Vector); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 18 Ch ©
  19. Định nghĩacáchàmcơ bản ƒ Tên file: vector.cpp #include #include "vector.h" Vector createVector(int n, double init) { Vector v; v.nelem = n; v.data = (double*) malloc(n*sizeof(double)); while (n ) v.data[n] = init; return v; } void destroyVector(Vector v) { free(v.data); }N doubleƠ getElem(Vector v, int i) { if (i = 0) return v.data[i]; return 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 19 Ch ©
  20. void putElem(Vector v, int i, double d) { if (i >=0 && i < v.nelem) v.data[i] = d; } Vector addVector(Vector a, Vector b) { Vector c = {0,0}; if (a.nelem == b.nelem) { c = createVector(a.nelem,0.0); for (int i=0; i < a.nelem; ++i) c.data[i] = a.data[i] + b.data[i]; } return c; } Vector subVector(Vector a, Vector b) { N Vector c = {0,0}; Ơ return c; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 20 Ch ©
  21. Ví dụ sử dụng #include "vector.h" void main() { int n = 10; Vector a,b,c; a = createVector(10,1.0); b = createVector(10,2.0); c = addVector(a,b); // destroyVector(a); N Ơ destroyVector(b); destroyVector(c); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 21 Ch ©
  22. 4.4 Xây dựng cấutrúcList ƒ Vấn ₫ề: Xây dựng mộtcấutrúc₫ể quảnlýmộtcách hiệuquả và linh hoạtcácdữ liệu ₫ộng, ví dụ: —Hộpthư₫iệntử — Danh sách những việccầnlàm —Các₫ốitượng ₫ồ họatrênhìnhvẽ — Các khâu ₫ộng họctrongsơ₫ồmô phỏng hệ thống (tương tự trong SIMULINK) ƒ Các yêu cầu ₫ặc thù: —Số lượng mụcdữ liệutrongdanhsáchcóthể thay ₫ổithường N Ơ xuyên — Các thao tác bổ sung hoặcxóadữ liệucần ₫ượcthựchiện nhanh, ₫ơngiản —Sử dụng tiếtkiệmbộ nhớ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 22 Ch ©
  23. Sử dụng kiểumảng? ƒ Số phầntử trong mộtmảng thựcchất không bao giờ thay ₫ổi ₫ược. Dung lượng bộ nhớ vào thời ₫iểmcấp phát phảibiếttrước, không thựcsự co giãn ₫ược. ƒ Nếu không thựcsự sử dụng hết dung lượng ₫ãcấp phát => lãng phí bộ nhớ ƒ Nếu ₫ãsử dụng hếtdung lượng và muốnbổ sung phầntử thì phảicấpphátlại và sao chép toàn bộ dữ liệusang mảng mới=> cần nhiềuthờigiannếusố phầntử lớn N Ơ ƒ Nếumuốnchènmộtphầntử/xóa mộtphầntửở₫ầu hoặcgiữamảng thì phải sao chép và dịch toàn bộ phầndữ liệucònlại => rấtmấtthờigian 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 23 Ch ©
  24. Danh sách móc nối (linked list) pHead Item A Dữ liệuA Item B Dữ liệuB Item C Dữ liệuC Item X Dữ liệuX N Ơ Item Y 0x00 Dữ liệuY 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 24 Ch ©
  25. Bổ sung dữ liệu pHead pHead pHead Dữ liệuT Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuT Dữ liệuC Dữ liệuC N Dữ liệuX Dữ liệuX Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Bổ sung vào ₫ầudanhsách Bổ sung vào giữa danh sách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 25 Ch ©
  26. Xóa bớtdữ liệu pHead pHead Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuC Dữ liệuC Dữ liệuX Dữ liệuX N Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Xóa dữ liệu ₫ầudanhsách Xóa dữ liệugiữadanhsách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 26 Ch ©
  27. Các ₫ặc ₫iểm chính ƒ Ưu ₫iểm: —Sử dụng rấtlinhhoạt, cấpphátbộ nhớ khi cần và xóa khi không cần —Bổ sung và xóa bỏ mộtdữ liệu ₫ượcthựchiện thông qua chuyểncon trỏ, thờigianthựchiệnlàhằng số, không phụ thuộcvàochiều dài và vị trí —Cóthể truy nhậpvàduyệtcácphầntử theo kiểutuầntự ƒ Nhược ₫iểm: —Mỗidữ liệubổ sung mới ₫ềuphải ₫ượccấpphátbộ nhớ₫ộng —Mỗidữ liệuxóabỏ₫i ₫ềuphải ₫ượcgiải phóng bộ nhớ tương N Ơ ứng —Nếukiểudữ liệu không lớnthìphần overhead chiếmtỉ lệ lớn —Tìmkiếmdữ liệutheokiểutuyến tính, mấtthờigian 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 27 Ch ©
  28. Ví dụ: Danh sách thông báo (hộpthư) #include using namespace std; struct MessageItem { string subject; string content; MessageItem* pNext; }; struct MessageList { MessageItem* pHead; }; void initMessageList(MessageList& l); void addMessage(MessageList&, const string& sj, N Ơ const string& ct); bool removeMessageBySubject(MessageList& l, const string& sj); void removeAllMessages(MessageList&); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 28 Ch ©
  29. #include "List.h" void initMessageList(MessageList& l) { l.pHead = 0; } void addMessage(MessageList& l, const string& sj, const string& ct) { MessageItem* pItem = new MessageItem; pItem->content = ct; pItem->subject = sj; pItem->pNext = l.pHead; l.pHead = pItem; } void removeAllMessages(MessageList& l) { MessageItem *pItem = l.pHead; while (pItem != 0) { MessageItem* pItemNext = pItem->pNext; N Ơ delete pItem; pItem = pItemNext; } l.pHead = 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 29 Ch ©
  30. bool removeMessageBySubject(MessageList& l, const string& sj) { MessageItem* pItem = l.pHead; MessageItem* pItemBefore; while (pItem != 0 && pItem->subject != sj) { pItemBefore = pItem; pItem = pItem->pNext; } if (pItem != 0) { if (pItem == l.pHead) l.pHead = 0; else pItemBefore->pNext = pItem->pNext; delete pItem; } N Ơ return pItem != 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 30 Ch ©
  31. Chương trình minh họa #include #include "list.h" using namespace std; void main() { MessageList myMailBox; initMessageList(myMailBox); addMessage(myMailBox,"Hi","Welcome, my friend!"); addMessage(myMailBox,"Test","Test my mailbox"); addMessage(myMailBox,"Lecture Notes","Programming Techniques"); removeMessageBySubject(myMailBox,"Test"); MessageItem* pItem = myMailBox.pHead; while (pItem != 0) { cout subject content pNext; N Ơ } char c; cin >> c; removeAllMessages(myMailBox); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 31 Ch ©
  32. Bài tậpvề nhà ƒ Xây dựng kiểu danh sách móc nốichứacácngàylễ trong nămvàý nghĩacủamỗi ngày (string), cho phép: —Bổ sung mộtngàylễ vào ₫ầudanhsách —Tìmý nghĩacủamộtngày(₫ưa ngày tháng là tham số) —Xóabỏ₫imộtngàylễở₫ầu danh sách —Xóabỏ₫imộtngàylễởgiữadanhsách(₫ưa ngày tháng là tham số) —Xóabỏ₫itoànbộ danh sách ƒ Viếtchương trình minh họacáchsử dụng N Ơ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 32 Ch ©