Thuật toán và cấu trúc dữ liệu

0KỸ THUẬT LẬP TRÌNH THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU 1 NỘI DUNG ƒ Thuật toán ƒ Kiểu dữ liệu và cấu trúc dữ liệu ƒ Mối liên hệ giữa thuật toán và cấu trúc dữ liệu ƒ Kiểu con trỏ trong C ƒ Sử dụng kiểu array trong C ƒ Kiểu xâu kí tự trong C ƒ Sử dụng struct trong C 2 KHÁI NIỆM THUẬT TOÁN ƒ Thuật toán (giải thuật) là một quy tắc để với những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạn Bài toán Thuật toán Máy tính Dữ liệu vào Kết quả ra 3 ƒ Tính kết thúc (tính dừng) ƒ Tính xác định ƒ Tính phổ dụng ƒ Tính hiệu quả • Thực hiện nhanh • Tiêu phí ít tài nguyên máy tính (bộ nhớ) CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN 4CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN ƒ Thuật toán tìm UCLN của hai số nguyên dương 1. Nhập vào hai số nguyên dương a, b 2. So sánh hai số, chọn số nhỏ nhất gắn cho UCLN 3. Nếu một trong hai số a, b không chia hết cho UCLN thì thực hiện bước 4, ngược lại thì thực hiện bước 5 4. Giảm UCLN một đơn vị và quay lại bước 3 5. In UCLN. Kết thúc ? Các đặc trưng của thuật toán trên 5 TIÊU CHUẨN ĐÁNH GIÁ THUẬT TOÁN ƒ Lựa chọn thuật toán nào cho bài toán? ƒ Tiêu chuẩn 1: Thuật toán đơn giản, dễ hiểu, dễ cài đặt ƒ Tiêu chuẩn 2: Thuật toán sử dụng tiết kiệm tài nguyên máy tính (dung lượng không gian nhớ, thời gian) 6 NGÔN NGỮ THUẬT TOÁN ƒ Ngôn ngữ dùng để mô tả thuật toán ? Tại sao phải dùng ngôn ngữ diễn đạt thuật toán ? Đặc điểm của ngôn ngữ diễn đạt thuật toán • Ngôn ngữ liệt kê từng bước (Ngôn ngữ tự nhiên) • Sơ đồ khối • Ngôn ngữ “giả code”: Tựa Pascal, tựa C, … – Các bước trong chương trình nên được đánh số thứ tự – Có thể bỏ qua phần khai báo dữ liệu, thay vào đó là đặc tả cấu trúc dữ liệu trước khi viết giải thuật ƒ Mô tả thuật toán • Thuật toán: • Vào (Input): • Ra (Output): 7 NGÔN NGỮ THUẬT TOÁN ƒ Ngôn ngữ liệt kê từng bước • Thuật toán: Euclid • Vào: m,n nguyên dương (m > n) • Ra: gcd là ước chung lớn nhất của m và n r: số nguyên dương Bước 1. Nhập vào m, n Bước 2. Nếu m, n >0 thì chuyển sang bước 3, ngược lại thì thông báo “Dữ liệu vào không hợp lệ” và kết thúc thuật toán Bước 3. Nếu m > n thì chuyển sang bước 4. Ngược lại, hoán chuyển giá trị của m, n Bước 4. Nếu n = 0 thì gcd = m, in giá trị của gcd và kết thúc. Ngược lại, chuyển sang bước 5. Bước 5. Tính r là phần dư của phép chia m cho n Bước 6. Gán giá trị của n cho m và của r cho n. Quay lại bước 4. 8NGÔN NGỮ THUẬT TOÁN ƒ Sơ đồ khối Điều kiện Lệnh Nút thao tác Chỉ hướng truyền thông tin Nút điều kiện Nút bắt đấu, nút kết thúc 9 NGÔN NGỮ THUẬT TOÁN ƒ Thuật toán Euclid Sai Sai Đúng Đúng Bắt đầu Nhập m, n m, n >0 m >= n n = 0 gcd = m In gcd r = m mod n m = n n = r r = m m = n n = r Kết thúc Thông báo Dữ liệu vào không hợp lệ Sai Đúng 10 NGÔN NGỮ THUẬT TOÁN ƒ Ngôn ngữ Tựa Pascal • Khai báo: Program Begin ……. End. • Chú thích {….} • Phép toán số học: +, - *, /, ↑(luỹ thừa) • Phép toán so sánh: >, >=, <, <=, =, ≠ • Giá trị logic: true, false • Phép toán logic: and, or, not 11 NGÔN NGỮ THUẬT TOÁN ƒ Các câu lệnh • Câu lệnh gán V := E; – V: biến, E: biểu thức – Phép gán chung: V1 := V2 := E; • Câu lệnh điều kiện if B then S1 [else S2]; • Câu lệnh tuyển Case B1: S1; B2: S2; …. Bn: Sn; else Sn+1 end case; 12 NGÔN NGỮ THUẬT TOÁN • Câu lệnh lặp – Số lần lặp biết trước for i := m to n do …. for i := n down to m do…. – Số lần lặp không biết trước while B do S; repeat S until B; (B: biểu thức logic; S: dãy lệnh) • Câu lệnh chuyển go to n; (n:số hiệu của một bước trong chương trình) • Câu lệnh vào ra read(); write() 13 NGÔN NGỮ THUẬT TOÁN • Chương trình con – Hàm function (): S return – Thủ tục Procedure: không có kết quả ra – Sử dụng Var đặt trước tham số cần giữ lại sự thay đổi giá trị sau khi kết thúc thực hiện hàm/thủ tục – Lời gọi Hàm Tên_hàm() – Lời gọi thủ tục Call () 14 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Giải thuật nào hiệu quả nhất cho một bài toán? • Độ phức tạp thời gian • Độ phức tạp không gian ? Đánh giá giải thuật khi chạy chương trình ??? ƒ Các yếu tố ảnh hưởng đến thời gian thực hiện thuật toán • Môi trường phần cứng: tốc độ xử lý, bộ nhớ,… • Môi trường phần mềm: kiểu lệnh, ngôn ngữ, trình biên dịch • Kích thước dữ liệu vào ƒ Đánh giá độ phức tạp thời gian T(n) bằng tổng số phép tính cần phải thực hiện. 15 ƒ Độ tăng của hàm • Cho hai hàm f(x), g(x) xác định từ tập các số nguyên dương hoặc tập số thực vào tập số thực. Ta nói f(x) là O(g(x)) nếu tồn tại hai hằng số C và k sao cho: |f(x)| ≤ C.|g(x)|, với mọi x > k. ƒ Ví dụ 1 • f(x) = an xn +…. +a0, với ai là các số thực. Khi đó f(x) = O(xn). • với x > 1 ta có • Đặt C = |an| + |an−1| + … + |a0| và k = 1, suy ra f(x) = O(xn). ƒ Ví dụ 2. • f(x) = 1+ 2+ 3 + … + n = n(n+1)/2 nên là O(n2). ĐỘ PHỨC TẠP THUẬT TOÁN )....( ...( ...)( 01 01 0 1 1 aaax x a x a ax axaxaxf nn n n n n n n n n n +++≤ +++≤ +++≤ − − − − 16 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Các thuật ngữ thường dùng • Độ phức tạp O(1) gọi là độ phức tạp hằng số • Độ phức tạp O(log(n)) gọi là độ phức tạp logarit • Độ phức tạp O(n) gọi là độ phức tạp tuyến tính • Độ phức tạp O(nlogn) gọi là độ phức tạp nlogn • Độ phức tạp O(nk) gọi là độ phức tạp đa thức • Độ phức tạp O(bn) , b>1, gọi là độ phức tạp hàm mũ • Độ phức tạp O(n!) gọi là độ phức tạp giai thừa 17 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Ví dụ 1 K:=0; For i:=1 to n do Begin K:=K+i; End; ƒ Ví dụ 2 K:=0; For i:=1 to n do For j:= 1 to n do Begin K := K + i * j ; End; 18 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Ví dụ 3 i :=1; K:=0; while i <= n do begin K:= K+ i*i; i := i * 2; end; ƒ Số phép toán cần thực hiện: (1 so sánh + 2 nhân + 1 cộng) * (1 + |log2n|) = 4 + 4 |log2n| là O(log2n). 19 ƒ Ví dụ 4 Searching(A[]: array of integer, n: integer, integer K): Boolean Begin i := 1; found := false; while (i <=n and !found) do begin if A[i] = K then found:=true; else i := i+1; end; return found; end; ĐỘ PHỨC TẠP THUẬT TOÁN 20 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Độ phức tạp xấu nhất ƒ Độ phức tạp trường hợp tốt nhất ƒ Độ phức tạp trung bình 21 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Độ phức tạp trường hợp xấu nhất của A là số lớn nhất các phép toán cơ bản được thực hiện trong A trên bất kỳ dữ liệu vào có kích cỡ xác định. ƒ Độ phức tạp trường hợp tốt nhất của A là số bé nhất các phép toán cơ bản được thực hiện trong A trên bất kỳ dữ liệu vào có kích cỡ xác định. ƒ Độ phức tạp trung bình của A là giá trị trung bình của số các phép toán cơ bản được thực hiện trong A trên bất kỳ dữ liệu vào có kích thước xác định. 22 ĐỘ PHỨC TẠP THUẬT TOÁN ƒ Ví dụ hàm Searching ở trên: • Độ phức tạp trong trường hợp xấu nhất là O(n) • Độ phức tạp trong trường hợp tốt nhất là:O(1) khi K chính là phần tử đầu tiên của mảng. • Độ phức tạp trung bình là: cỡ n/2 (khoảng ½ các phần tử của mảng được duyệt). Việc tính toán rất phức tạp dựa vào xác suất K xuất hiện trong A. ƒ Thường đánh giá thuật toán theo độ phức tạp thời gian xấu nhất. Hiệu quả sử dụng của thuật toán lại thể hiện thông qua độ phức tạp trung bình. 23 ƒ Kiểu dữ liệu: • Trong ngôn ngữ bậc cao • Là sự trừu tượng hóa các thuộc tính bản chất của các đối tượng trong thực tế và phù hợp với cách tổ chức thông tin trên máy tính • Kiểu số nguyên, số thực, kí tự,… • Kiểu dữ liệu T = , V là tập các giá trị hợp lệ của T và O là tập các phép toán trên kiểu T. KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU 24 KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU ƒ Cấu trúc dữ liệu: • Là các lưu trữ dữ liệu trên máy tính sao cho việc sử dụng dữ liệu đó được hiệu quả. Đó chính là tổ chức các khái niệm toán học và logic về dữ liệu. • Kiểu dữ liệu có cấu trúc được kết hợp nên từ các kiểu dữ liệu cơ sở • Ví dụ: Kiểu mảng, xâu kí tự, Bản ghi, File,… ƒ Mối liên hệ giữa cấu trúc dữ liệu và Thuật toán Chương trình = Cấu trúc dữ liệu + Thuật toán 25 KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU ƒ Mô hình dữ liệu • Là mô hình toán học, có thể biểu diễn được trên máy tính, để biểu diễn các đối tượng của bài toán và mối liên hệ giữa các đối tượng • Mô hình dữ liệu muốn cài đặt được trên máy tính phải có cách tổ chức dữ liệu phù hợp. • Ví dụ: Danh sách, Cây, Đồ thị, Quan hệ,. … ƒ Các tiêu chuẩn chọn cấu trúc dữ liệu • Phản ánh đúng thực tế: quan trọng nhất, đảm bảo tính đúng đắn của phương án giải quyết • Các thao tác phù hợp • Tiết kiệm tài nguyên hệ thống 26 KIỂU DỮ LIỆU TRONG C ƒ Kiểu dữ liệu cơ sở • Kí tự (char, unsigned char) • Số nguyên (int, unsigned int, long (int), unsigned long (int)) • Số thực, độ chính xác đơn (float) • Số thực, độ chính xác kép (double) – Lưu ý: Kích thước và phạm vi biểu diễn của các kiểu dữ liệu ƒ Kiểu con trỏ ƒ Kiểu enum ƒ Kiểu mảng (array) ƒ Kiểu cấu trúc (struct) 9 Kiểm tra kích thước của kiểu dữ liệu: dùng toán tử sizeof(), ví dụ: sizeof(int),… 27 KIỂU CON TRỎ ƒ Biến con trỏ (Pointer) • Địa chỉ bộ nhớ của biến được gán cho con trỏ là giá trị của biến con trỏ. • Biến thông thường chứa giá trị một cụ thể (count = 7). • Các con trỏ chứa địa chỉ của biến: biến được trỏ chứa giá trị cụ thể (tham chiếu gián tiếp) Con trỏ countPtr trỏ đến biến count, giá trị của biến con trỏ countPtr là địa chỉ của biến count, giá trị của biến count là 7. count 7 count 7 countPtr 28 Biến con trỏ trong ngôn ngữ C ƒ Con trỏ - Pointer • Sức mạnh của ngôn ngữ lập trình C • Tạo ra khả năng mềm dẻo khi lập trình • Thuận lợi truyền tham số cho hàm (tham biến), xử lý mảng, xâu, bộ nhớ • Con trỏ có quan hệ mật thiết giữa arrays và strings • Lưu ý, thận trọng trong cách sử dụng: can thiệp vào bộ nhớ. 29 ƒ Định nghĩa và khởi tạo biến con trỏ • * được sử dụng định nghĩa biến pointer int *myPtr; • Định nghĩa biến con trỏ, trỏ tới vùng nhớ kiểu int • Định nghĩa nhiều con trỏ yêu cầu sử dụng * trước mỗi biến con trỏ int *myPtr1, *myPtr2; • Có thể định nghĩa con trỏ kiểu dữ liệu bất kỳ • Khởi tạo con trỏ là 0, NULL (con trỏ rỗng) hoặc một địa chỉ của một biến cùng kiểu dữ liệu Biến con trỏ trong C 30 ƒ &Tenbien (trả về địa chỉ của tenbien) • Phép gán trả về địa chỉ của biến dữ liệu int y = 5; int *yPtr; yPtr = &y; /* yPtr lấy địa chỉcủa y */ yPtr “trỏ tới” y yPtr y 5 yptr 500000 600000 y 600000 5 địa chỉ của y là giá trị của yptr Biến con trỏ trong ngôn ngữ C 31 ƒ Sử dụng dấu * để tham chiếu giá trị trong vùng nhớ trỏ bởi con trỏ • *yptr trả về giá trị của biến y (bởi vì yptr trỏ tới y) • Dấu * có thể sử dụng trong lệnh gán làm thay đổi giá trị của biến dữ liệu. *yptr = 7; /* thay đổi y bằng 7 */ ƒ * và & quan hệ đối ngược nhau - *p là dữ liệu được chứa trong vùng nhớ có địa chỉ là p - &x là địa chỉ của biến x int x; int *xptr; xptr = &x; Khi đó, *xptr = x; &*xptr = *&xptr Biến con trỏ trong ngôn ngữ C 1 /* Fig. 7.4: fig07_04.c 2 Using the & and * operators */ 3 #include 4 5 int main() 6 { 7 int a; /* a is an integer */ 8 int *aPtr; /* aPtr is a pointer to an integer */ 9 10 a = 7; 11 aPtr = &a; /* aPtr set to address of a */ 12 13 printf( "The address of a is %p" 14 "\nThe value of aPtr is %p", &a, aPtr ); 15 16 printf( "\n\nThe value of a is %d" 17 "\nThe value of *aPtr is %d", a, *aPtr ); 18 19 printf( "\n\nShowing that * and & are complements of " 20 "each other\n&*aPtr = %p" 21 "\n*&aPtr = %p\n", &*aPtr, *&aPtr ); 22 23 return 0; /* indicates successful termination */ 24 25 } /* end main */ Địa chỉ của biến a là giá trị của con trỏ aPtr * aPtr là giá trị của biến Quan hệ giữa * và & là bổ sung The address of a is 0012FF7C The value of aPtr is 0012FF7C The value of a is 7 The value of *aPtr is 7 Showing that * and & are complements of each other. &*aPtr = 0012FF7C *&aPtr = 0012FF7C 33 Operators Associativity Type () [] left to right highest + - ++ -- ! * & (type) right to left unary * / % left to right multiplicative + - left to right additive >= left to right relational == != left to right equality && left to right logical and || left to right logical or ?: right to left conditional = += -= *= /= %= right to left assignment , left to right comma Fig. 7.5 Operator precedence. Toán tử trên con trỏ Biến con trỏ trong ngôn ngữ C 34 SỬ DỤNG KIỂU MẢNG TRONG C ƒ Các mảng • Là cấu trúc gồm các phần tử dữ liệu có liên quan với nhau • Các thực thể tĩnh (Static) – kích thước không thay đổi trong suốt chương trình (Phân biệt với: Cấu trúc dữ liệu động (Dynamic) 35 ƒ Khái niệm mảng • Nhóm của định vị bộ nhớ liên tiếp nhau • Cùng chung tên và kiểu dữ liệu ƒ Tham chiếu đến phần tử, cụ thể • Tên mảng • Số vị trí ƒ Định dạng: arrayname[ position number ] • phần tử đầu tiên có vị trí 0 • n phần tử mảng với tên c: – c[ 0 ], c[ 1 ]...c[ n – 1 ] Tên của mảng (tất cả các phần tử có chung tên c) Số vị trí của phần tử trong mảng c c[6] -45 6 0 72 1543 -89 0 62 -3 1 6453 78 c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] 36 ƒ Các phần tử trong mảng giống như các biến c[ 0 ] = 3; printf( "%d", c[ 0 ] ); • Thực hiện thao tác trong ngoặc [] để xác định chỉ số. + Nếu x = 3 thì c[ 5 - 2 ] == c[ 3 ] == c[ x ] + Chỉ số của mảng có thể xác định bằng biểu thức toán học 37 Khai báo mảng ƒ Khi khai báo mảng • Tên mảng • Kiểu mảng • Số phần tử Cú pháp: arrayType arrayName[ numberOfElements ]; • Ví dụ: int c[ 10 ]; float myArray[ 3284 ]; ƒ Khai báo nhiều mảng có cùng kiểu • Cú pháp tương tự như khai báo biến • Ví dụ: int b[ 100 ], x[ 27 ]; 38 Khai báo và khởi tạo mảng ƒ Khởi tạo mảng: khai báo và gắn giá trị các phần tử int n[ 5 ] = { 1, 2, 3, 4, 5 }; • Nếu không đủ các biến thì các phần tử bên phải nhất bằng 0 int n[ 5 ] = { 0 } // Tất cả các phần tử bằng 0 • Nếu quá nhiều phần tử thì báo lỗi cú pháp • C không kiểm tra giới hạn của mảng • Nếu bỏ qua kích thước, sử dụng mặc định số phần tử khởi tạo int n[ ] = { 1, 2, 3, 4, 5 }; . Khởi tạo 5 phần tử, do đó mảng có 5 phần tử 1 /* Fig. 6.4: fig06_04.c 2 Initializing an array with an initializer list */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 /* use initializer list to initialize array n */ 9 int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 10 int i; /* counter */ 11 12 printf( "%s%13s\n", "Element", "Value" ); 13 14 /* output contents of array in tabular format */ 15 for ( i = 0; i < 10; i++ ) { 16 printf( "%7d%13d\n", i, n[ i ] ); 17 } /* end for */ 18 19 return 0; /* indicates successful termination */ 20 21 } /* end main */ Element Value 0 32 1 27 2 64 3 18 4 95 5 14 6 90 7 70 8 60 9 37 Program Output Ví dụ: Khai báo và khởi tạo mảng array = 0012FF78 &array[0] = 0012FF78 &array = 0012FF78 1 /* Fig. 6.12: fig06_12.c 2 The name of an array is the same as &array[ 0 ] */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 char array[ 5 ]; /* define an array of size 5 */ 9 10 printf( " array = %p\n&array[0] = %p\n" 11 " &array = %p\n", 12 array, &array[ 0 ], &array ); 13 14 return 0; /* indicates successful termination */ 15 16 } /* end main */ Ví dụ: Tên của array chính là &array[ 0 ] (địa chỉ của phần tử đầu tiên trong mảng) Mối liên hệ giữa mảng và con trỏ trong C 41 Mảng nhiều chiều ƒ Mảng nhiều chiều • Bảng với các hàng và các cột (m hàng và n cột) • Giống như ma trận: chỉ số đầu là hàng (row), sau đó là cột (column) Row 0 Row 1 Row 2 Column 0 Column 1 Column 2 Column 3 a[ 0 ][ 0 ] a[ 1 ][ 0 ] a[ 2 ][ 0 ] a[ 0 ][ 1 ] a[ 1 ][ 1 ] a[ 2 ][ 1 ] a[ 0 ][ 2 ] a[ 1 ][ 2 ] a[ 2 ][ 2 ] a[ 0 ][ 3 ] a[ 1 ][ 3 ] a[ 2 ][ 3 ] Chỉ sô hàng-Row Tên mảng Chỉ số cột-Column 42 Mảng nhiều chiều ƒ Khởi tạo • int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; • Khởi tạo theo hàng trong dấu {} • Nếu không đủ, các phần tử còn lại nhận giá trị 0 int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; ƒ Tham chiếu các phần tử • Chỉ ra hàng và cột printf( "%d", b[ 0 ][ 1 ] ); • Nhập giá trị cho phần tử (i,j) của mảng scanf(“%d”, &b[i][j]); 1 2 3 4 1 0 3 4 1 /* Fig. 6.21: fig06_21.c 2 Initializing multidimensional arrays */ 3 #include 4 5 void printArray( const int a[][ 3 ] ); /* function prototype */ 6 7 /* function main begins program execution */ 8 int main() 9 { 10 /* initialize array1, array2, array3 */ 11 int array1[ 2 ][ 3 ] = { { 1, 2, 3 }, { 4, 5, 6 } }; 12 int array2[ 2 ][ 3 ] = { 1, 2, 3, 4, 5 }; 13 int array3[ 2 ][ 3 ] = { { 1, 2 }, { 4 } }; 14 15 printf( "Values in array1 by row are:\n" ); 16 printArray( array1 ); 17 18 printf( "Values in array2 by row are:\n" ); 19 printArray( array2 ); 20 21 printf( "Values in array3 by row are:\n" ); 22 printArray( array3 ); 23 24 return 0; /* indicates successful termination */ 25 26 } /* end main */ 27 Ví dụ: Khởi tạo mảng đa chiều Program Output Values in array1 by row are: 1 2 3 4 5 6 Values in array2 by row are: 1 2 3 4 5 0 Values in array3 by row are: 1 2 0 4 0 0 28 /* function to output array with two rows and three columns */ 29 void printArray( const int a[][ 3 ] ) 30 { 31 int i; /* counter */ 32 int j; /* counter */ 33 34 /* loop through rows */ 35 for ( i = 0; i <= 1; i++ ) { 36 37 /* output column values */ 38 for ( j = 0; j <= 2; j++ ) { 39 printf( "%d ", a[ i ][ j ] ); 40 } /* end inner for */ 41 42 printf( "\n" ); /* start new line of output */ 43 } /* end outer for */ 44 45 } /* end function printArray */ 45 Xâu kí tự trong C ƒ Mảng ký tự • Xâu “first” là một mảng các ký tự • Mảng các ký tự có thể được khởi tạo bởi một xâu char string1[ ] = "first" – Kết thúc của xâu ký tự '\0' (Null) – string1 thực tế có 6 phần tử – Có thể viết tương ứng như sau: char string1[ ] = { 'f', 'i', 'r', 's', 't', '\0' }; • Có thể truy cập đến từng ký tự : string1[ 3 ] là ký tự ‘s’ • Tên mảng thể hiện địa chỉ của mảng, vì vậy không cần sử dụng ký tự “&” trong lệnh scanf scanf( "%s", string2 ); – Đọc các ký tự đến khi gặp ký tự trắng / dấu cách 1 /* Fig. 6.10: fig06_10.c 2 Treating character arrays as strings */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 char string1[ 20 ]; /* reserves 20 characters */ 9 char string2[] = "string literal"; /* reserves 15 characters */ 10 int i; /* counter */ 11 12 /* read string from user into array string2 */ 13 printf("Enter a string: "); 14 scanf( "%s", string1 ); 15 16 /* output strings */ 17 printf( "string1 is: %s\nstring2 is: %s\n" 18 "string1 with spaces between characters is:\n", 19 string1, string2 ); 20 21 /* output characters until null character is reached */ 22 for ( i = 0; string1[ i ] != '\0'; i++ ) { 23 printf( "%c ", string1[ i ] ); 24 } /* end for */ 25 47 Xâu kí tự trong C ƒ Khai báo String • Giống như khai báo một mảng ký tự hoặc một biến kiểu char * char color[] = "blue"; char *colorPtr = "blue"; ƒ Đọc vào xâu • Sử dụng scanf() scanf("%s", word); – Sao chép vào word[] – Không cần & (vì tên xâu là con trỏ) • Sử dụng gets( ) ƒ Xác định độ dài xâu: size_t strlen( const char *s ): Trả về số ký tự trong xâu s 48 Kí tự và xâu kí tự trong C ƒ Thư viện các hàm về kí tự và xâu kí tự • Thư viện xử lý ký tự: • Sử dụng các hàm vào/ra ký tự và xâu (thư viện stdio.h). • Sử dụng các hàm chuyển đổi xâu (thư viện stdlib.h). • Sử dụng các hàm xử lý string (thư viện string.h). 49 Thư viện chuẩn các hàm xử lý ký tự Prototype Description int isdigit( int c ); Returns true if c is a digit and false otherwise. int isalpha( int c ); Returns true if c is a letter and false otherwise. int isalnum( int c ); Returns true if c is a digit or a letter and false otherwise. int isxdigit( int c ); Returns true if c is a hexadecimal digit character and false otherwise. int islower( int c ); Returns true if c is a lowercase letter and false otherwise. int isupper( int