KỸ THUẬT LẬP TRÌNH (p3)

Chia sẻ: Nguyễn Văn Cường | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

154
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 . 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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: KỸ THUẬT LẬP TRÌNH (p3)

KỸ THUẬT LẬP TRÌNH NỘI DUNG Thuật toán Kiểu dữ liệu và cấu trúc dữ liệu THUẬT TOÁN Mối liên hệ giữa thuật toán và cấu trúc dữ liệu 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 0 1 KHÁI NIỆM THUẬT TOÁN CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN Thuật toán (giải thuật) là một quy tắc để với những dữ Tính kết thúc (tính dừng) liệu ban đầu đã cho, tìm được lời giải sau một khoảng Tính xác định thời gian hữu hạn Tính phổ dụng Bài toán Tính hiệu quả • Thực hiện nhanh Thuật toán • Tiêu phí ít tài nguyên máy tính (bộ nhớ) Dữ liệu vào Kết quả ra Máy tính 2 3
CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN TIÊU CHUẨN ĐÁNH GIÁ THUẬT TOÁN Thuật toán tìm UCLN của hai số nguyên dương Lựa chọn thuật toán nào cho bài toán? 1. Nhập vào hai số nguyên dương a, b Tiêu chuẩn 1: Thuật toán đơn giản, dễ hiểu, dễ cài đặt 2. So sánh hai số, chọn số nhỏ nhất gắn cho UCLN Tiêu chuẩn 2: Thuật toán sử dụng tiết kiệm tài nguyên 3. Nếu một trong hai số a, b không chia hết cho UCLN thì thực máy tính (dung lượng không gian nhớ, thời gian) 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 4 5 NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN Ngôn ngữ dùng để mô tả thuật toán Ngôn ngữ liệt kê từng bước ? Tại sao phải dùng ngôn ngữ diễn đạt thuật toán • Thuật toán: Euclid ? Đặc điểm của ngôn ngữ diễn đạt thuật toán • Vào: m,n nguyên dương (m > n) • Ngôn ngữ liệt kê từng bước (Ngôn ngữ tự nhiên) • Ra: gcd là ước chung lớn nhất của m và n • Sơ đồ khối r: số nguyên dương • Ngôn ngữ “giả code”: Tựa Pascal, tựa C, … Bước 1. Nhập vào m, n – Các bước trong chương trình nên được đánh số thứ tự 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 – 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 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 Mô tả thuật toá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, • Thuật toán: chuyển sang bước 5. • Vào (Input): Bước 5. Tính r là phần dư của phép chia m cho n • Ra (Output): Bước 6. Gán giá trị của n cho m và của r cho n. Quay lại bước 4. 6 7
NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN Sơ đồ khối Thuật toán Euclid Bắt đầu Nút thao tác Lệnh Nhập m, n Thông báo Dữ liệu vào m, n >0 Sai không hợp lệ Chỉ hướng truyền thông tin ướ Đúng r=m Sai m=n m >= n n=r Đúng Điều kiện Nút điều kiện n=0 Đúng Sai r = m mod n gcd = m m=n In gcd n=r Nút bắt đấu, nút kết thúc thú Kết thúc 8 9 NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN Các câu lệnh Ngôn ngữ Tựa Pascal • Câu lệnh gán V := E; • Khai báo: Program < Tên chương trình> – V: biến, E: biểu thức Begin ……. – Phép gán chung: V1 := V2 := E; End. • Câu lệnh điều kiện if B then S1 [else S2]; • Chú thích {….} • Câu lệnh tuyển Case • Phép toán số học: +, - *, /, ↑(luỹ thừa) B1: S1; • Phép toán so sánh: >, >=,
NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN • Câu lệnh lặp • Chương trình con – Số lần lặp biết trước for i := m to n do …. – Hàm for i := n down to m do…. function (): – Số lần lặp không biết trước while B do S; S repeat S until B; return (B: biểu thức logic; S: dãy lệnh) – Thủ tục Procedure: không có kết quả ra • Câu lệnh chuyển – Sử dụng Var đặt trước tham số cần giữ lại sự thay đổi giá trị sau go to n; (n:số hiệu của một bước trong chương trình) khi kết thúc thực hiện hàm/thủ tục • Câu lệnh vào ra – Lời gọi Hàm Tên_hàm() read(); – Lời gọi thủ tục Call () write() 12 13 ĐỘ PHỨC TẠP THUẬT TOÁN ĐỘ PHỨC TẠP THUẬT TOÁN Độ tăng của hàm Giải thuật nào hiệu quả nhất cho một bài toán? • 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 • Độ phức tạp thời gian 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. • Độ phức tạp không gian Ví dụ 1 Đánh giá giải thuật khi chạy chương trình ??? ? • f(x) = an xn +…. +a0, với ai là các số thực. Khi đó f(x) = O(xn). Các yếu tố ảnh hưởng đến thời gian thực hiện thuật toán • với x > 1 ta có f ( x ) ≤ a n x n + a n −1 x n −1 + ... + a 0 • Môi trường phần cứng: tốc độ xử lý, bộ nhớ,… a n −1 a0 ≤ x n ( an + + ... + xn x • Môi trường phần mềm: kiểu lệnh, ngôn ngữ, trình biên dịch ≤ x ( a n + a n −1 + .... + a 0 ) n • Kích thước dữ liệu vào • Đặt C = |an| + |an−1| + … + |a0| và k = 1, suy ra f(x) = O(xn). Đánh giá độ phức tạp thời gian T(n) bằng tổng số phép Ví dụ 2. tính cần phải thực hiện. • f(x) = 1+ 2+ 3 + … + n = n(n+1)/2 nên là O(n2). 14 15
ĐỘ PHỨC TẠP THUẬT TOÁN ĐỘ PHỨC TẠP THUẬT TOÁN Ví dụ 1 Các thuật ngữ thường dùng K:=0; • Độ phức tạp O(1) gọi là độ phức tạp hằng số For i:=1 to n do • Độ phức tạp O(log(n)) gọi là độ phức tạp logarit Begin K:=K+i; • Độ phức tạp O(n) gọi là độ phức tạp tuyến tính End; • Độ phức tạp O(nlogn) gọi là độ phức tạp nlogn Ví dụ 2 • Độ phức tạp O(nk) gọi là độ phức tạp đa thức K:=0; • Độ phức tạp O(bn) , b>1, gọi là độ phức tạp hàm mũ For i:=1 to n do For j:= 1 to n do • Độ phức tạp O(n!) gọi là độ phức tạp giai thừa Begin K := K + i * j ; End; 16 17 ĐỘ PHỨC TẠP THUẬT TOÁN ĐỘ PHỨC TẠP THUẬT TOÁN Ví dụ 4 Ví dụ 3 Searching(A[]: array of integer, n: integer, integer K): Boolean i :=1; K:=0; Begin while i
ĐỘ PHỨC TẠP THUẬT TOÁN ĐỘ PHỨC TẠP THUẬT TOÁN Độ phức tạp xấu nhất Độ 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 Độ phức tạp trường hợp tốt nhất kỳ dữ liệu vào có kích cỡ xác định. Độ phức tạp trung bì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. 20 21 ĐỘ PHỨC TẠP THUẬT TOÁN KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU Ví dụ hàm Searching ở trên: Kiểu dữ liệu: • Độ phức tạp trong trường hợp xấu nhất là O(n) • Trong ngôn ngữ bậc cao • Độ phức tạp trong trường hợp tốt nhất là:O(1) khi K chính là • Là sự trừu tượng hóa các thuộc tính bản chất của các đối phần tử đầu tiên của mảng. 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 • Độ 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 • Kiểu số nguyên, số thực, kí tự,… suất K xuất hiện trong A. • 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. 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. 22 23
KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU Mô hình dữ liệu Cấu trúc dữ liệu: • Là mô hình toán học, có thể biểu diễn được trên máy tính, để • Là các lưu trữ dữ liệu trên máy tính sao cho việc sử dụng 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 dữ liệu đó được hiệu quả. Đó chính là tổ chức các khái đối tượng niệm toán học và logic về dữ liệu. • Mô hình dữ liệu muốn cài đặt được trên máy tính phải có cách • 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 tổ chức dữ liệu phù hợp. cơ sở • Ví dụ: Danh sách, Cây, Đồ thị, Quan hệ,. … • Ví dụ: Kiểu mảng, xâu kí tự, Bản ghi, File,… Các tiêu chuẩn chọn cấu trúc dữ liệu Mối liên hệ giữa cấu trúc dữ liệu và Thuật toán • 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 Chương trình = Cấu trúc dữ liệu + Thuật toán • Tiết kiệm tài nguyên hệ thống 24 25 KIỂU DỮ LIỆU TRONG C KIỂU CON TRỎ Kiểu dữ liệu cơ sở Biến con trỏ (Pointer) • Kí tự (char, unsigned char) • Địa chỉ bộ nhớ của biến được gán cho con trỏ là giá trị của • Số nguyên (int, unsigned int, long (int), unsigned long (int)) biến con trỏ. • Số thực, độ chính xác đơn (float) • Biến thông thường chứa giá trị một cụ thể (count = 7). • Số thực, độ chính xác kép (double) count – Lưu ý: Kích thước và phạm vi biểu diễn của các kiểu dữ liệu 7 Kiểu con trỏ • Các con trỏ chứa địa chỉ của biến: biến được trỏ chứa giá trị cụ Kiểu enum thể (tham chiếu gián tiếp) Kiểu mảng (array) Con trỏ countPtr trỏ đến biến count, giá trị countPtr count Kiểu cấu trúc (struct) của biến con trỏ countPtr là địa chỉ của 7 Kiểm tra kích thước của kiểu dữ liệu: dùng toán tử sizeof(), ví biến count, giá trị của biến count là 7. dụ: sizeof(int),… 26 27
Biến con trỏ trong C Biến con trỏ trong ngôn ngữ C Định nghĩa và khởi tạo biến con trỏ Con trỏ - Pointer • * được sử dụng định nghĩa biến pointer • Sức mạnh của ngôn ngữ lập trình C int *myPtr; • Tạo ra khả năng mềm dẻo khi lập trình • Định nghĩa biến con trỏ, trỏ tới vùng nhớ kiểu int • Thuận lợi truyền tham số cho hàm (tham biến), xử lý • Định nghĩa nhiều con trỏ yêu cầu sử dụng * trước mỗi biến con trỏ mảng, xâu, bộ nhớ int *myPtr1, *myPtr2; • Con trỏ có quan hệ mật thiết giữa arrays và strings • Có thể định nghĩa con trỏ kiểu dữ liệu bất kỳ • Lưu ý, thận trọng trong cách sử dụng: can thiệp vào • 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 bộ nhớ. 28 29 Biến con trỏ trong ngôn ngữ C Biến con trỏ trong ngôn ngữ C Sử dụng dấu * để tham chiếu giá trị trong vùng nhớ trỏ bởi &Tenbien (trả về địa chỉ của tenbien) con trỏ • Phép gán trả về địa chỉ của biến dữ liệu • *yptr trả về giá trị của biến y (bởi vì yptr trỏ tới y) int y = 5; • 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. int *yPtr; *yptr = 7; /* thay đổi y bằng 7 */ yPtr = &y; /* yPtr lấy địa chỉcủa y */ * và & quan hệ đối ngược nhau yPtr “trỏ tới” y - *p là dữ liệu được chứa trong vùng nhớ có địa chỉ là p yptr y y 5 500000 600000 600000 5 - &x là địa chỉ của biến x yPtr int x; int *xptr; xptr = &x; Khi đó, *xptr = x; &*xptr = *&xptr địa chỉ của y là giá trị của yptr 30 31
The address of a is 0012FF7C Biến con trỏ trong ngôn ngữ C The value of aPtr is 0012FF7C 1 /* Fig. 7.4: fig07_04.c The value of a is 7 2 Using the & and * operators */ The value of *aPtr is 7 3 #include Showing that * and & are complements of each other. 4 Toán tử trên con trỏ To &*aPtr = 0012FF7C 5 int main() *&aPtr = 0012FF7C 6 { Operators Associativity Type 7 int a; /* a is an integer */ 8 int *aPtr; /* aPtr is a pointer to an integer */ () [] left to right highest 9 10 a = 7; + - ++ -- ! * & (type) right to left unary 11 aPtr = &a; /* aPtr set to address of a */ * / % left to right multiplicative 12 + - left to right additive 13 printf( "The address of a is %p" Địa chỉ của biến a là giá trị của 14 < >= left to right relational "\nThe value of aPtr is %p", &a, aPtr ); con trỏ aPtr 15 == != left to right equality 16 printf( "\n\nThe value of a is %d" && left to right logical and 17 "\nThe value of *aPtr is %d", a, *aPtr ); * aPtr là giá trị 18 || left to right logical or của biến 19 printf( "\n\nShowing that * and & are complements of " ?: right to left conditional 20 "each other\n&*aPtr = %p" = += -= *= /= %= right to left assignment 21 "\n*&aPtr = %p\n", &*aPtr, *&aPtr ); Quan hệ giữa * 22 , left to right comma và & là bổ sung 23 return 0; /* indicates successful termination */ Operator precedence. Fig. 7.5 24 33 25 } /* end main */ Tên của mảng (tất SỬ DỤNG KIỂU MẢNG TRONG C cả các phần tử có chung tên c) Khái niệm mảng Các mảng c[0] -45 • Nhóm của định vị bộ nhớ liên tiếp nhau • Là cấu trúc gồm các phần tử dữ liệu có liên quan c[1] 6 c[2] 0 • Cùng chung tên và kiểu dữ liệu với nhau c[3] 72 c[4] 1543 Tham chiếu đến phần tử, cụ thể • Các thực thể tĩnh (Static) – kích thước không thay c[5] -89 c[6] 0 • Tên mảng đổi trong suốt chương trình c[7] 62 • Số vị trí c[8] -3 (Phân biệt với: Cấu trúc dữ liệu động (Dynamic) c[9] 1 Định dạng: c[10] 6453 c[11] 78 arrayname[ position number ] • phần tử đầu tiên có vị trí 0 Số vị trí của phần tử trong • n phần tử mảng với tên c: mảng c 34 35 – c[ 0 ], c[ 1 ]...c[ n – 1 ]
Khai báo mảng Khi khai báo mảng Các phần tử trong mảng giống như các biến • Tên mảng c[ 0 ] = 3; • Kiểu mảng printf( "%d", c[ 0 ] ); • Số phần tử • Thực hiện thao tác trong ngoặc [] để xác định chỉ số. Cú pháp: arrayType arrayName[ numberOfElements ]; + Nếu x = 3 thì c[ 5 - 2 ] == c[ 3 ] == c[ x ] • Ví dụ: + Chỉ số của mảng có thể xác định bằng biểu thức int c[ 10 ]; toán học 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 ]; 36 37 Ví dụ: Khai báo và khởi tạo mảng Khai báo và khởi tạo mảng 1 /* Fig. 6.4: fig06_04.c Program Output 2 Initializing an array with an initializer list */ Khởi tạo mảng: khai báo và gắn giá trị các phần tử 3 #include 4 int n[ 5 ] = { 1, 2, 3, 4, 5 }; Element Value 5 /* function main begins program execution */ • Nếu không đủ các biến thì các phần tử bên phải nhất bằng 0 0 32 6 int main() 7{ int n[ 5 ] = { 0 } // Tất cả các phần tử bằng 0 1 27 8 /* use initializer list to initialize array n */ • Nếu quá nhiều phần tử thì báo lỗi cú pháp 2 64 9 int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 10 int i; /* counter */ • C không kiểm tra giới hạn của mảng 3 18 11 • Nếu bỏ qua kích thước, sử dụng mặc định số phần tử khởi tạo 4 95 12 printf( "%s%13s\n", "Element", "Value" ); 13 int n[ ] = { 1, 2, 3, 4, 5 }; 5 14 14 /* output contents of array in tabular format */ . Khởi tạo 5 phần tử, do đó mảng có 5 phần tử 6 90 15 for ( i = 0; i < 10; i++ ) { 16 printf( "%7d%13d\n", i, n[ i ] ); 7 70 17 } /* end for */ 8 60 18 19 return 0; /* indicates successful termination */ 9 37 20 21 } /* end main */ 38
Mảng nhiều chiều Mối liên hệ giữa mảng và con trỏ trong C 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ảng nhiều chiều 1 /* Fig. 6.12: fig06_12.c • Bảng với các hàng và các cột (m hàng và n cột) 2 The name of an array is the same as &array[ 0 ] */ 3 #include • Giống như ma trận: chỉ số đầu là hàng (row), sau đó là cột 4 5 /* function main begins program execution */ (column) 6 int main() 7{ 8 char array[ 5 ]; /* define an array of size 5 */ Column 1 Column 2 Column 0 Column 3 9 a[ 0 ][ 0 ] a[ 0 ][ 1 ] a[ 0 ][ 2 ] a[ 0 ][ 3 ] Row 0 10 printf( " array = %p\n&array[0] = %p\n" Row 1 11 " &array = %p\n", a[ 1 ][ 0 ] a[ 1 ][ 1 ] a[ 1 ][ 2 ] a[ 1 ][ 3 ] 12 Row 2 array, &array[ 0 ], &array ); a[ 2 ][ 0 ] a[ 2 ][ 1 ] a[ 2 ][ 2 ] a[ 2 ][ 3 ] 13 14 return 0; /* indicates successful termination */ Chỉ số cột-Column 15 Tên mảng 16 } /* end main */ Chỉ sô hàng-Row array = 0012FF78 &array[0] = 0012FF78 &array = 0012FF78 41 Ví dụ: Khởi tạo mảng đa chiều Mảng nhiều chiều 1 / * Fig. 6.21: fig06_21.c 2 I nitializing multidimensional arrays */ 3 # include 4 Khởi tạo 5 v oid printArray( const int a[][ 3 ] ); /* function prototype */ 1 2 6 3 4 7 / * function main begins program execution */ • int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; 8 i nt main() 9 { • Khởi tạo theo hàng trong dấu {} 10 / * initialize array1, array2, array3 */ 11 i nt array1[ 2 ][ 3 ] = { { 1, 2, 3 }, { 4, 5, 6 } }; 1 0 • Nếu không đủ, các phần tử còn lại nhận giá trị 0 12 i nt array2[ 2 ][ 3 ] = { 1, 2, 3, 4, 5 }; 3 4 13 i nt array3[ 2 ][ 3 ] = { { 1, 2 }, { 4 } }; int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; 14 15 p rintf( "Values in array1 by row are:\n" ); Tham chiếu các phần tử 16 p rintArray( array1 ); 17 • Chỉ ra hàng và cột 18 p rintf( "Values in array2 by row are:\n" ); 19 p rintArray( array2 ); printf( "%d", b[ 0 ][ 1 ] ); 20 21 p rintf( "Values in array3 by row are:\n" ); • Nhập giá trị cho phần tử (i,j) của mảng 22 p rintArray( array3 ); 23 scanf(“%d”, &b[i][j]); 24 r eturn 0; /* indicates successful termination */ 25 26 } / * end main */ 42 27
28 /* function to output array with two rows and three columns */ Xâu kí tự trong C 29 void printArray( const int a[][ 3 ] ) 30 { Program Output Program 31 int i; /* counter */ 32 int j; /* counter */ Mảng ký tự 33 34 /* loop through rows */ • Xâu “first” là một mảng các ký tự 35 for ( i = 0; i
Kí tự và xâu kí tự trong C Thư viện chuẩn các hàm xử lý ký tự Thư viện các hàm về kí tự và xâu kí tự Prototype Description int isdigit( int c ); Returns true if c is a digit and false otherwise. • Thư viện xử lý ký tự: int isalpha( int c ); Returns true if c is a letter and false otherwise. • Sử dụng các hàm vào/ra ký tự và xâu (thư viện stdio.h). 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. • Sử dụng các hàm chuyển đổi xâu (thư viện stdlib.h). int islower( int c ); Returns true if c is a lowercase letter and false otherwise. int isupper( int c ); Returns true if c is an uppercase letter; false otherwise. • Sử dụng các hàm xử lý string (thư viện string.h). int tolower( int c ); If c is an uppercase letter, tolower returns c as a lowercase letter. Otherwise, tolower returns the argument unchanged. int toupper( int c ); If c is a lowercase letter, toupper returns c as an uppercase letter. Otherwise, toupper returns the argument unchanged. int isspace( int c ); Returns true if c is a white-space character—newline ('\n'), space (' '), form feed ('\f'), carriage return ('\r'), horizontal tab ('\t'), or vertical tab ('\v')—and false otherwise int iscntrl( int c ); Returns true if c is a control character and false otherwise. int ispunct( int c ); Returns true if c is a printing character other than a space, a digit, or a letter and false otherwise. int isprint( int c ); Returns true value if c is a printing character including space (' ') and false otherwise. int isgraph( int c ); Returns true if c is a printing character other than space (' ') and false otherwise. 48 49 Các hàm chuyển đổi Các hàm thư viện I/O chuẩn • Trong (thư viện chuẩn) Function prototype Function description int getchar( void ); Inputs the next character fromthe standard input and re- Chuyển đổi string của các số thành các số nguyên (int) turns it as an integer. và số thực (float) char *gets( char *s ); Inputs characters from the standard input into the array s Function prototype Function description until a newline or end-of-file character is encountered. A double atof( const char *nPtr ); Converts the stringnPtr todouble. terminating null character is appended to the array. int putchar( int c ); Prints the character stored in c. int atoi( const char *nPtr ); Converts the stringnPtr to int. int puts( const char *s ); Prints the string s followed by a newline character. long atol( const char *nPtr ); Converts the stringnPtr tolong int. int sprintf( char *s, const Equivalent to printf, except the output is stored in the double strtod( const char *nPtr, char Converts the string nPtr to double. char *format, ... ); array s instead of printing it on the screen. **endPtr ); long strtol( const char *nPtr, char Converts the string nPtr to long. int sscanf( char *s, const Equivalent to scanf, except the input is read fromthe array **endPtr, int base ); char *format, ... ); s instead of reading it from the keyboard. unsigned long strtoul( const char Converts the string nPtr to unsigned long. *nPtr, char **endPtr, int base ); 50 51
Thư viện điều khiển string có các hàm: So sánh các string • Thao tác dữ liệu string • Máy tính so sánh mã số ASCII của ký tự trong xâu • Tìm kiếm trên string • Xem bảng mã các ký tự (sách lập trình C) • Xác định độ dài string int strcmp( const char *s1, const char *s2 ); Function prototype Function description • So sánh xâu s1 với s2 char *strcpy( char Copies string s2 into array s1. The value of s1 is returned. *s1, const char *s2 ) • Kết quả trả về của hàm là số âm nếu s1 < s2, 0 nếu s1 == s2 char *strncpy( char Copies at most n characters of string s2 into array s1. The value of s1 hoặc số dương nếu s1 > s2 *s1, const char *s2, is returned. size_t n ) char *strcat( char Appends string s2 to array s1. The first character of s2 overwrites the *s1, const char *s2 ) terminating null character of s1. The value of s1 is returned. int strncmp(const char *s1, const char *s2, size_t n ); char *strncat( char Appends at most n characters of string s2 to array s1. The first • So sánh n ký tự của xâu s1 với s2 *s1, const char *s2, character of s2 overwrites the terminating null character of s1. The size_t n ) value of s1 is returned. • Giá trị kết quả trả về giống hàm strcmp() 52 53 Các hàm tìm kiếm String từ thư viện chuẩn Hàm Memory • Trong F unction prototype F unction description • Thao tác, so sánh, tìm kiếm khối của memory Locates the first occurrence of character c in string s . If c is found, a c har *strchr( const char *s, int c ); pointer to c in s is returned. Otherwise, a N ULL p ointer is returned. • Có thể thao tác bất kỳ khối dữ liệu nào D etermines and returns the length of the initial segment of string s 1 s ize_t strcspn( const char Function prototype Function description *s1, const char *s2 ); consisting of characters not contained in string s 2 . Copies n characters from the object pointed to by s2 into the object void *memcpy( void D etermines and returns the length of the initial segment of string s 1 s ize_t strspn( const char *s1, const void *s2, *s1, const char *s2 ); pointed to by s1. A pointer to the resulting object is returned. consisting only of characters contained in string s 2 . size_t n ); Locates the first occurrence in string s 1 o f any character in string s 2 . Copies n characters from the object pointed to by s2 into the object void *memmove( void c har *strpbrk( const char *s1, const char *s2 ); *s1, const void *s2, If a character from string s 2 is found, a pointer to the character in pointed to by s1. The copy is performed as if the characters were first size_t n ); string s 1 is returned. Otherwise, a N ULL p ointer is returned. copied from the object pointed to by s2 into a temporary array and Locates the last occurrence of c in string s . If c is found, a pointer to c c har *strrchr( const char *s, then from the temporary array into the object pointed to by s1. A int c ); in string s is returned. Otherwise, a N ULL p ointer is returned. pointer to the resulting object is returned. Locates the first occurrence in string s 1 o f string s 2 . If the string is c har *strstr( const char *s1, Compares the first n characters of the objects pointed to by s1 and s2. int memcmp( const const char *s2 ); found, a pointer to the string in s 1 is returned. Otherwise, a N ULL void *s1, const void The function returns 0, less than 0 or greater than 0 if s1 is equal to, p ointer is returned. *s2, size_t n ); less than or greater than s2. A s equence of calls to s trtok b reaks string s 1 into “tokens”—logical c har *strtok( char *s1, const Locates the first occurrence of c (converted to unsigned char) in the void *memchr( const char *s2 ); pieces such as words in a line of text—separated by characters void *s, int c, contained in string s 2 . The first call contains s 1 a s the first argument, first n characters of the object pointed to by s. If c is found, a pointer size_t n ); and subsequent calls to continue tokenizing the same string contain to c in the object is returned. Otherwise, NULL is returned. N ULL a s the first argument. A pointer to the current token is returned Copies c (converted to unsigned char) into the first n characters of void *memset( void by each call. If there are no more tokens when the function is called, *s, int c, size_t n the object pointed to by s. A pointer to the result is returned. N ULL i s returned. ); 54 55
Mảng , Con trỏ và Xâu kí tự Con trỏ và mảng Các phần tử của array có thể là con trỏ Cấp phát động cho mảng () Ví dụ: array của các xâu (strings) • Hàm cấp phát vùng bộ nhớ gồm n byte: char *suit[ 4 ] = { "Hearts", "Diamonds", "Clubs", "Spades" }; • Strings là các con trỏ tới ký tự đầu tiên void *malloc(unsigned n) • char * : mỗi phần tử của suit là một con trỏ char • Giải phóng vùng nhớ Các string được lưu trữ là mảng suit • void free(void *ptr) suit[0] ’H’ ’e’ ’a’ ’r’ ’t’ ’s’ ’\0’ Ví dụ: ’D’ ’i’ ’a’ ’m’ ’o’ ’n’ ’d’ ’s’ ’\0’ suit[1] int *IntArray; ’C’ ’l’ ’u’ ’b’ ’s’ ’\0’ suit[2] ’S’ ’p’ ’a’ ’d’ ’e’ ’s’ ’\0’ suit[3] printf(“Size of array:”); scanf(“%d”, &n); IntArray = (int*) malloc(n*sizeof(int)); • Mảng suit có kích thước cố định, nhưng con trỏ string có thể là kích thước bất k ỳ 56 57 Kiểu bản ghi Kiểu bản ghi trong C Dữ liệu kiểu bản ghi: Ví dụ: • Tập hợp các biến có liên quan sử dụng chung 1 tên struct Student { – Tên biến “chung” có thể chứa các biến với các kiểu dữ liệu char name[40]; khác nhau int grade; • Nhiều trường dữ liệu • Kết hợp với con trỏ để tạo các danh sách liên kết, ngăn xếp, }; hàng đợi và cây • struct mô tả định nghĩa cấu trúc Student • Student là tên cấu trúc và được sử dụng để khai báo biến dữ liệu có kiểu là cấu trúc • chứa 2 trường dữ liệu 58 59
Các thao tác hợp lệ trên cấu trúc Cách định nghĩa: • Gán một cấu trúc cho một cấu trúc cùng kiểu • Khai báo biến: • Lấy địa chỉ (&) của một cấu trúc struct Student oneStudent, Class[ 50 ], *sPtr; • Truy cập các thành phần của 1 cấu trúc • Kết hợp định nghĩa và khai báo biến: • Sử dụng hàm sizeof để xác định kích thước của cấu trúc struct Student { char name[40]; int grade; } oneStudent, Class[ 50 ], *sPtr; 60 61 Truy cập các thành phần của cấu trúc Khởi tạo cấu trúc sử dụng danh sách • Sử dụng dấu (.) đi kèm với tên biến cấu trúc • Ví dụ: struct Student myFriend; struct Student oneStudent = { “Hoang Lan", 8 }; printf( "%s", myFriend.name ); Các lệnh gán • Mũi tên (->) được sử dụng cho con trỏ trỏ đến • Ví dụ: biến cấu trúc struct Student myFriend = oneStudent; struct Student *sPtr = &myFriend; • Có thể định nghĩa và khởi tạo biến myFriend như sau: struct Student myFriend; printf( "%s",sPtr->name ); myFriend.name = “Hoang Lan”; • myFriend.name tương đương với myFriend.grade = 8; ( *sPtr ).name 62 63
typedef : Định nghĩa kiểu Đọc thêm: Kiểu union, kiểu enum trong ngôn ngữ lập • Tạo ra tên khác (bí danh) cho một kiểu dữ liệu đã định trình C nghĩa • typedef không tạo ra kiểu dữ liệu mới • Ví dụ: typedef struct Student * StudentPtr; StudentPtr sPtr; > Định nghĩa tên kiểu mới StudentPtr có cùng kiểu với kiểu struct Student * • Ví dụ: typedef char line[80]; line str; // tương ứng char str[80]; 64 65 Bài tập Nhập vào một danh sách lớp sinh viên gồm 2 thông tin: Tên và điểm. Hiển thị danh sách sinh viên Tính điểm trung bình cộng điểm của các sinh viên. Tìm và hiển thị tên các sinh viên đạt điểm lớn hơn hoặc bằng giá trị trung bình cộng vừa tính được. Tìm và hiển thị tên sinh viên có điểm cao nhất lớp. Yêu cầu: • Sử dụng kết hợp kiểu mảng và kiểu struct • Cấp phát động cho mảng 66