Thực tập Kỹ thuật lập trình: Hướng dẫn thực hiện các chức năng sắp xếp hiệu quả

ự ậ

Ậ

Ỹ

Th c t p K THU T L P TRÌNH

ắ ế

ự

ứ

ệ

ầ Tu n 79

: Th c hi n các ch c năng s p x p

Yêu cầu:

Với dữ liệu sinh viên gồm các thông tin:

 Mã l pớ

 Mã sinh viên

 H và tên ọ

 Ngày sinh

ể

 Đi m trung bình tích lũy

đã nhập và lưu trữ trên file.

Ví dụ đã nhập được danh sách sinh viên như sau:

ọ

Mã l pớ Mã sinh viên

H và tên

ễ

13A 13C 13B

2014000001 Nguy n Đình Giang ị 2014000002 Tr nh Văn Anh 2014000003 Hoàng Xuân Đ tạ

Ngày sinh 02/12/1996 24/10/1996 15/06/1996

ĐTBTL 3.4 2.8 3.2

Hãy thực hiện các các yêu cầu sau:

- Sắp xếp danh sách sinh viên theo Mã lớp. Ví dụ danh sách trên

sau khi xếp theo mã lớp ta được:

ọ

Mã l pớ Mã sinh viên

H và tên

ễ

ị

13A 13B 13C

2014000001 Nguy n Đình Giang 2014000003 Hoàng Xuân Đ tạ 2014000002 Tr nh Văn Anh

Ngày sinh 02/12/1996 15/06/1996 24/10/1996

ĐTBTL 3.4 3.2 2.8

- Sắp xếp danh sách sinh viên theo Mã sinh viên (như sanh sách đã

cho).

- Sắp xếp danh sách sinh viên theo Họ và tên. Họ và tên sinh viên được so sánh theo tên rồi đến họ đệm. Ví dụ danh sách sinh viên ở trên đặc xếp lại theo họ tên là

ọ

Mã l pớ Mã sinh viên

H và tên

ị

13C 13B

2014000002 Tr nh Văn Anh 2014000003 Hoàng Xuân Đ tạ

Ngày sinh 24/10/1996 15/06/1996

ĐTBTL 2.8 3.2

ễ

13A

2014000001 Nguy n Đình Giang

02/12/1996

3.4

- Sắp xếp danh sách sinh viên theo Ngày sinh. Ngày sinh được so sánh theo năm, đến tháng, và cuối là đến ngày. Ví dụ danh sách trên sau khi sắp xếp ta được:

ọ

Mã l pớ Mã sinh viên

ễ

H và tên 2014000003 Hoàng Xuân Đ tạ ị 2014000002 Tr nh Văn Anh 2014000001 Nguy n Đình Giang

13B 13C 13A

Ngày sinh 15/06/1996 24/10/1996 02/12/1996

ĐTBTL 3.2 2.8 3.4

- Sắp xếp danh sách sinh viên theo mã lớp, cùng mã lớp sắp xếp

theo họ tên, cùng họ tên thì sắp xếp theo ngày sinh.

Kiến thức liên quan:

A. MỘT SỐ THUẬT TOÁN SẮP XẾP

ườ ượ ắ ả ư ng đ c mô t nh sau:

ế ế - Bài toán s p x p th - Cho danh sách X ch a ứ n ph n t ầ ử X[1], X[2], ..., X[n]. Gi

ơ ả thi ộ

ầ ướ ứ ự c a danh sách ượ ả i m ng ớ ế ạ ắ c, c n s p x p l X theo th t

ả ầ t là các ph n ể ử ủ X có th so sánh h n kém v i nhau theo m t tiêu chí nào đó. t ọ không c ch n tr Theo tiêu chí đ gi m (ho c không tăng).

- Trong m c này chúng ta xét tr

ợ ườ ố ự ng h p các ph n t

c a m ng ề

ả ế ắ

ế ổ ọ

ọ

ỗ ị ể ị i m i v trí tìm ph n t ừ 1 đ n ế n1, t

ầ ử ả ạ ớ ị ấ ợ

ứ ầ ử thích h p v i v trí th nh t ph i là ph n t ắ

ầ ử ứ ả

l n nh t trong dãy). ắ ế ợ thích h p và chuy n đ n. ấ ầ ử bé nh t trong danh ầ ả ầ ử ầ đ u tiên ph i là ph n ầ ử ấ bé nh t trong các ph n t ầ ả ầ ử ứ th hai ph i là ph n i (v i bài toán s p x p thành dãy không tăng thì ph n t

ừ ứ ả ử ợ ị s đã ch n đ

i c a dãy). ầ ử ợ ầ ử ả ạ ủ c các ph n t thích h p v i v trí th thích h p cho các v trí t ứ i ph i là ph n t

còn l ượ ầ ử ứ i1. Rõ ràng ph n t ấ ố ớ

ắ ệ ể ả ầ ử ứ i có th mô t th nh

ặ ả X là s th c và ầ ử ủ ụ ắ ậ ả ế X sao cho thành dãy không gi m. Có khá nhi u thu t toán s p ầ ắ yêu c u s p x p ế ế ể ả ộ ầ ế i quy t bài toán đã nêu. Trong ph n ti p theo chúng ta xem xét m t x p đ gi ế ọ ế ư ắ ơ ắ ậ ố s thu t toán s p x p đ n gi n nh s p x p ch n (selection sort) , s p x p ắ chèn (insertion sort) và s p x p n i b t (buble sort). ắ ế 5.2.1. S p x p ch n ngưở : Ý t ừ - Xét t ng v trí, t ư ậ Nh v y, ph n t ớ ế sách (v i bài toán s p x p thành dãy không tăng thì ph n t ấ ử ớ Ở ị t v trí th hai ph i là ph n t ớ ạ ế còn l ấ ử ớ ầ ử l n nh t trong các ph n t t ư ậ ọ ứ ấ - C nh v y, gi th nh t ị ế ấ ớ ị đ n v trí th bé nh t ặ ế ầ ử ớ l n nh t đ i v i bài toán s p x p thành dãy không tăng) trong các (ho c ph n t ư ọ ạ {X[i], X[i+1], ..., X[n]}. Vi c ch n ph n t ầ ử ph n t i còn l sau:

min {X[i], X[i+1], ..., X[n]};

ỗ ể ả ư ầ ử X[k] và X[i]; thu t toán nh sau: i t

(cid:0) ả Kí hi u ệ X[k] = N u ế k > i thì đ i ch hai ph n t ổ ậ ừ 1 nên có th mô t ị ể Do có th xét v trí ữ ệ : Dãy X[1], X[2], ...., X[n] D li u vào ữ ệ D li u ra Dãy X không gi m: X[1] : X[2] (cid:0) ....(cid:0) X[n];

(i = 1; i

for {

X[k] = min { X[i], ,..., X[n]}; if (k>i) swap (X[k], X[i]);

}

ỹ ậ ổ K thu t đ i ch ỗ X[k] và X[i]:

{

tg = X[k]; X[k]= X[i]; X[i] = tg;

ế ả ắ ố } Ví d 5.ụ 1 : S p x p dãy s sau thành không gi m:

13, 22, 30, 14, 21, 5, 21, 12, 15, 19 ắ ố ớ ụ ủ ế ầ ậ ị ọ Áp d ng thu t toán s p x p ch n đ i v i 3 v trí đ u c a dãy:

1) i = 1:

ị

V trí đang xét, i=1

k=6, X[6] = min {X[1], ..., X[10]}

13 22 30 14 21 5 21 12 15 19

ổ ỗ Đ i ch X[1], X[6]:

22 30 14 21 13 21 12 15 19 5

2) i = 2:

ị

V trí đang xét, i=2

k=8, X[8] = min {X[2], ..., X[10]}

5 22 30 14 21 13 21 12 15 19

ổ ỗ Đ i ch X[2], X[8]:

5 12 30 14 21 13 21 22 15 19

3) i = 3:

ị

V trí đang xét, i=3

k=6, X[6] = min {X[3], ..., X[10]}

5 12 30 14 21 13 21 22 15 19

ổ ỗ Đ i ch X[3], X[6]:

5 12 13 14 21 30 21 22 15 19

ự ư ậ ầ ử ầ ậ c c a thu t toán, dãy đã có 3 ph n t đ u tiên

ệ ứ ự ướ ủ ả không gi m).

(cid:0) ả ế : Dãy X[1], X[2], ...., X[n] Dãy X không gi m: X[1] X[2] (cid:0) ....(cid:0) X[n];

- Nh v y, sau khi th c hi n 3 b ị ứ đ ng đúng v trí (trong th t ậ t: Thu t toán chi ti ữ ệ D li u vào ữ ệ D li u ra : (i=1; i

k = 1; for (j=k+1; j<=n; j++) if (X[j]

if (k>i) {tg = X[k]; X[k]= X[i]; X[i] = tg;}

ứ ạ ộ n2), trong đó có (n1)(n+2) phép so sánh và nhi uề

} - Thu t toán có đ ph c t p O( ổ ị ầ ử . 3(n1) phép hoán đ i v trí các ph n t

- T i m i b

ắ ậ ủ c l n c a thu t toán s p x p n i b t m t ph n t

ậ ế ắ ộ ổ ọ ổ ọ ế ề cướ ư c đ a v n1 b

ọ ắ ậ ế

ể ố ở ầ ử ượ đ ư ậ ỉ đúng v trí c a nó. Nh v y, thu t toán s p x p n i b t cũng ch có ớ ớ l n. Đây là đi m gi ng v i thu t toán s p x p ch n. ỗ ậ ấ nh t là ắ ế ổ ọ 5.2.2. S p x p n i b t ỗ ướ ớ ạ ủ ị ể ệ - Đi m khác bi t là ch trong m i b

ị ậ ệ

c xét đ n t

ế ớ

ế ề ị ướ ặ ổ ủ ế ậ

ượ ọ ợ ứ i, 1 £ i £ n: c ề ướ i đ u đã đ

ầ ượ c ch n thích h p; ặ (X[j1], X[j]), j = n, ..., i+1, n u ế X[j1] > X[j] thì

Ví d 5.ụ

ỉ ế ọ ắ ỗ ướ ặ ủ c l p c a thu t toán s p x p ch n ch ầ ử ờ ủ ị ể thích thông qua các phép toán so sánh đ xác đ nh v trí hi n th i c a ph n t ổ ệ ể ự ượ ế ạ ướ ặ ớ ị ợ c l p, sau đó có th th c hi n phép đ i i b h p v i v trí đang đ ầ ử ề ị ỗ ể ư ổ ắ ậ ợ v v trí thích h p; trong khi đó, v i thu t toán s p x p n i ch đ đ a ph n t ỗ ể ư ệ ả ự ộ ố ẽ ọ b t, s ph i th c hi n liên ti p m t s phép toán so sánh và đ i ch đ đ a ợ ầ ử ượ c l p c a thu t toán. thích h p v v trí đang xét đ n trong b c ph n t đ ướ ạ ẳ c th Ch ng h n, xét b ầ ử ở ị a) Các ph n t v trí tr t các c p b) Xét l n l ỗ X[j1] và X[j]. ổ đ i ch 2 : Xét dãy có 10 ph n tầ ử 22 13 14 14 15 21 14 15 19 3

ứ c th i = 1 Xét b

ướ j = 10

13 22 3 14 14 15 21 14 15 19

j = 9

j = 10 X[9] =15 < 19 = X[ 10] không đ i chổ 21

ỗ 14

ỗ

j = 9 X[8] =14 < 15 = X[ 9] không đ i chổ

13 22 3 14 14 15 19 15

j = 8

ỗ

j = 8 X[7] =21 > 14 = X[8] ổ đ i ch X[7] và X[8]

13 22 3 14 14 15 21 14 15 19

14 14 15 14 21 15 19 ả ế K t qu : 22 13 3

j = 7

ỗ

j = 7 X[6] =15 > 14 = X[ 7] ổ đ i ch X[6] và X[7]

3 13 22 14 14 15 14 21 15 19

ả ế K t qu : 22 13 3 14 14 14 15 21 15 19

j = 6

13 22 3 14 14 14 15 21 15 19

j = 5

j = 6 X[5] =14 = X[6] không đ i chổ 14

ỗ 21

13 22 3 14 14 15 19 12

j = 4

j = 5 X[4] =14 = X[5] không đ i chổ 14

ỗ 12

13 22 3 14 21 15 19 14

j = 4 X[3] =3 < 14 = X[4] ỗ ổ không đ i ch 14 14 14

j = 3

ỗ

j = 3 X[2] =22 > 3 = X[2] ổ đ i ch X[2] và X[3]

13 22 3 12 21 15 19

K t quế

ả 13 3 22 14 14 14 12 21 15 19

j = 2

ỗ

j = 2 X[1] =13 > 3 = X[2] ổ đ i ch X[1] và X[2]

13 3 22 14 14 14 12 21 15 19

K t quế

13 22 14 14 14 12 21 15 19 ả 3

- Trong ví d trên, sau khi ki m tra t

ể ổ ể ch s

ụ ế ị ể ượ ậ X[j1] > X[j], thu t toán đã chuy n đ

ứ ầ ử ở ướ b

ề ị ấ ằ ố ể ượ ừ ỉ ố j = 10 đ n ế j = 2 đ đ i ch các c p ỗ ặ ị ấ ỏ nh nh t vào v c ph n t ứ i nêu trên c th ứ c ph n t ể ầ ử ỏ nh nh t trong s các ph n t ầ ử {X[i], ..., X[n]} v v trí th

ế t:

(cid:0) ả : Dãy X[1], X[2], ...., X[n] Dãy X không gi m: X[1] X[2] (cid:0) ....(cid:0) X[n];

“ngh ch bi n", trí i=1. Không khó đ ch ng minh r ng phép toán b) chuy n đ i. ậ Thu t toán chi ti ữ ệ D li u vào ữ ệ D li u ra : for (i=1; i

for (j=n; j>i; j ) if (X[j1] >X[j]) {tg = X[j1]; X[j1]= X[j]; X[j] = tg;}

ậ ự } - Thu t toán có đ ph c t p O(

ộ ấ n2), trong đó ph i th c hi n ả ổ ị ệ (n1)(n+1) phép so ầ ử ề sánh và nhi u nh t là . ứ ạ 3n(n1)/2 phép hoán đ i v trí các ph n t

ắ ế 5.2.3. S p x p chèn Ý t

ầ ủ ả ầ ượ ắ ưở ng: - Gi s có ph n đ u c a m ng là ế c s p x p không B(i) = { X[1],...,X[i] } đã đ

ả ử gi m:ả

ư ợ ị X[1] ≤ ... ≤ X[i], th xét ph n t

- (5.1). Đ t ặ tg = X[i+1]. Có ba kh năng x y ra:

ả

(5.1) ầ ử ứ i+1. Đ a (chèn) X[i+1] vào v trí thích h p trong dãy ả ở ị v trí th ữ nguyên X[i+1] ứ i+1.

a) X[i] ≤ X[i+1]: Gi b) T n t

ộ ồ ạ ầ ử ừ t ỉ ố j, 1< j£ i, sao cho X[j1] ≤ tg < X[j]: Kéo toàn b các ph n t

ị i ch s ề

ứ j. ề ộ t Chèn giá X[j],..., X[i] v phía sau. Chèn giá tr c) X[i+1] < X[1]. Kéo toàn b các ph n t ị X[i+1] vào v trí th ầ ử ừ X[1],..., X[i] v phía sau.

ị tr ị X[i+1] vào v trí th

ườ ể Tr ng h p b) có th mô t ứ 1. ả ư nh sau:

ợ j = i+1; tg = X[i+1]; while (X[j1] > tg) { X[j] = X[j1]; j = j1;

ươ ớ ườ ứ ợ ng ng v i tr ng h p c). Vì ỉ ố j nh n giá tr 1 t

ả } X[j] = tg; ạ - Trong đo n mã trên, khi ch s ợ ườ ng h p b) và c) có th đ ậ v y, tr ậ ể ượ c mô t ị :

j = i+1; tg = X[i+1]; while ((j>1) && (X[j1] > tg)) { X[j] = X[j1];

j = j1;

ượ ế X[i] £ X[i+1], t c là ướ ự ệ ổ ứ c th c hi n b

ổ ị X[j1] £ tg ngay khi j = i+1 thì rõ ràng là ỉ ố j không thay đ i, nghĩa là phép c nào, ch s ầ X[i+1] cho chính nó, không làm thay đ i giá tr ph n

} X[j] = tg; ằ ể - Đ ý r ng n u ặ vòng l p không đ ự gán X[j] = tg th c ra là gán ử t

ể nào. - Trong m i tr ế c s p x p không B(1) = { X[1] } đã đ

ng h p, luôn có th coi ắ ợ ậ ế ể ượ ả ư c mô t ượ ắ nh sau:

(cid:0) ả ọ ườ ư ậ gi m. Nh v y, thu t toán s p x p chèn có th đ : Dãy X[1], X[2], ...., X[n] Dãy X không gi m: X[1] X[2] (cid:0) ....(cid:0) X[n];

ả ữ ệ D li u vào ữ ệ D li u ra : for (i=2; i<=n;i++) {

j = i+1; tg = X[i+1]; while ((j>1) && (X[j1] > tg)) {

X[j] = X[j1]; j = j1;

}

X[j] = tg;

} Ví d 5.ụ 3 : Xét dãy X:

5 21 21 12 15 19 X 13 22 30 14

ả i = 4.

ặ ạ Ta có đo n B(3) = {X[1], X[2], X[3]} = {13, 22, 30} không gi m. Xét Đ t tg = 14, j= 4.

21 21 12 15 19 5

X 13 22 30 j

ặ 14 4 X[j1] = 30 > tg =14. Đ t X[j] = X[j1], t c là X[4] = X[3], j =j 1= 3.

30 21 21 12 15 19 ứ 5

30 3 X 13 22 j

ặ X[j1] = 22 > tg=14. Đ t X[j] = X[j1], t c là X[3] = X[2], j =j 1= 2.

22 30 21 21 12 15 19 ứ 5

X 13 22 2 j

ặ ượ ắ ả X[j1] = 13 < tg=14. Đ t X[j] = tg. Ta có dãy con B(4) đ c s p không gi m.

5 21 21 12 15 19 22 30

- Thu t toán s p x p chèn có đ ph c t p O(n

ậ ứ ạ ườ ộ

2), trong đó, trong tr ổ

X 13 14 2 j ắ ự ấ ả nh tph i th c hi n ế ấ ợ ng h p x u ỗ ệ (n1)(n+1) phép so sánh và n(n+1)/2 phép đ i ch .

B. MỘT SỐ KỸ THUẬT XỬ LÝ XÂU

ễ ự x y ra th

ị ế ỗ ể ữ ệ ự ả ệ

- Trong th c ti n vi c x lý chu i các ký t ặ ữ ậ

ệ ế

ư ệ ữ ậ ặ ự

ỗ

ườ ệ ử ng xuyên trên máy tính, ầ ự ượ ặ ỗ c đ t ra cho đ vì th nhu c u đ nh nghĩa ki u d li u đ c bi t cho chu i ký t ữ ậ ả ừ ỗ là m ng các ký các ngôn ng l p trình. Trong ngôn ng l p trình C, chu i ký t ự ặ ự ớ ư ấ đ c bi v i ký t t t đánh d u k t thúc – mã là 0. Do đ c tr ng riêng và nhu ườ ử ầ ng xuyên nên các ngôn ng l p trình xây d ng th vi n các hàm c u x lý th ự ử . x lý chu i ký t ậ ấ ữ ệ

- Cú pháp:

2.2.1. Khai báo và nh p xu t d li u 1. Khai báo

- Trong đó:

ử ử ế ế ầ ầ ố ố char Tên_bi n_1[S _ph n_t _1], … ,Tên_bi n_n[S _ph n_t _n];

ừ khóa ki u d li u cho chu i

ể ữ ệ ế ư i s d ng t - char: là t ế - Tên_bi n_1, …, Tên_bi n_n

ỗ . ườ ử ụ ế : Tên bi n do ng ở ị

ố ầ ươ ố ự ị đ nh nghĩa, l u ý ữ ậ ị ố ắ ặ ử : H ng s nguyên d ng xác đ nh s ph n t

ế ử ỗ ả ầ - S _ph n_t _1,…, S _ph n_t _n ỗ ợ ủ ằ ệ ề ị ầ ử ố ượ ng

ầ ử ủ

ỗ c a chu i là khác nhau. 1 : Khai báo chu iỗ

ỉ ố ể ấ ế ự ề ấ , ch s đ truy xu t đ n các ký t ự ằ r ng tên bi n ph i tuân theo qui t c đ t tên qui đ nh b i ngôn ng l p trình. ố ủ ủ c a c a chu i. Tùy theo h tr c a h đi u hành và trình biên d ch mà s l ph n t Ví d 2.ụ char x[10]; - Khai báo chu i ỗ x có nhi u nh t là 10 ký t

trong chu i ỗ x là t ừ 0 đ n ế 9.

ấ ả ả ộ ự ế k t thúc là ‘\0’ vì thế

ỗ ả ệ ẫ ớ ỗ

ỗ ớ ở ạ

ự ớ : B n ch t chu i là m t m ng các ký t - Chú ý v i ký t ự . các quan ni m trên m ng v n đúng v i chu i ký t ị - Khai báo chu i v i giá tr kh i t o theo cú pháp sau. - Cú pháp:

- Trong đó:

ở ạ ở ạ ỗ ỗ ế ế ầ ầ ố ố ử char Tên_bi n_1[ S _ph n_t _1 ] = {chu i_kh i_t o_1}, … ử Tên_bi n_n[ S _ph n_t _n ] = {chu i_kh i_t o_n};

ử ế ầ ầ ố ố ượ ử đ ể c hi u - Tên_bi n_1, …, Tên_bi n_n, S _ph n_t _1, …, S _ph n_t _n

ỗ ỗ ở ạ ở ạ

ỗ ở ạ ườ - chu i_kh i_t o_1, …, chu i_kh i_t o_n ợ là chu i kh i t o cho các giá tr bi n. ủ ị ế ng h p khai báo có kh i t o các giá tr , đ dài c a chu i có th đ ế nh trên; ỗ - Trong tr

ộ ỗ ẽ ệ ố ở ạ ị ị ộ ủ

ở ạ ị 2 : Khai báo m ng có kh i t o giá tr

ầ ộ ố i đa là ể ượ c ở ỗ ộ ể ố đ tr ng, lúc đó h th ng s xác đ nh đ dài c a chu i theo đ dài chu i kh i t o.ạ ả - Ví d 2.ụ char s[100]= "Xin chao den voi ky thua lap trinh"; char a[]="Ky thuat lap trinh co ban"; - Khai báo chu i ỗ s có đ dài t 100 ký t

ỗ

ự ớ ớ ộ : Cách khai báo chu i ký t

ỏ ể ỗ ộ ố ợ ị ứ ở ạ ủ và kh i t o c a con tr ng trình. Vì là h ng s ỏ ố

ỏ ế ỉ ổ ở ỗ ằ i. ự ươ ẽ ả ỏ b s n y sinh l

ỗ ở ạ ự ượ c kh i t o chu i ban đ u là , đ ở ạ ượ “Xin chao den voi ky thua lap trinh”. Chu i ỗ a đ “Ky thuat lap c kh i t o là ủ ở ạ ỗ ủ ộ ố trinh co ban” v i đ dài t i đa c a chu i chính là đ dài c a chu i kh i t o. ỗ trên hoàn toàn khác v i khai báo - Chú ý char *b="Con tro den hang so chuoi"; ườ ng h p này khai báo m t con tr ki u ký t tr - ằ ượ ỏ ế c tr đ n đ a ch ch a h ng s là chu i trong ch đ ữ ệ ọ ỗ chu i nên m i thay đ i trên d li u tr đ n b i con tr ầ ử ấ 2. Truy xu t ph n t ấ ư ặ ấ ỗ ặ ầ ử

c a chu i thông qua c p ngo c [, ] nh truy xu t ph n t ầ ử ủ ự .

ụ - Truy xu t ph n t ỗ ả ầ ử ủ 2 . 3 : Ví d truy xu t ph n t ộ c a chu i là m t ký t ỗ ấ c a chu i

ầ ử ủ ỗ ủ c a m ng. M i ph n t - Ví d ụ char s[100]= "Xin chao den voi ky thua lap trinh"; s[0]='x';

ậ 3. Nh p xu t d li u xâu

ể ữ ệ ư ấ ữ ệ ỗ ặ ữ ể - Chu i là ki u m ng đ c bi

ả ỗ ợ ệ ượ t đ ậ c xem nh là ki u d li u nên trong ngôn ng ấ

a) Nh p ậ xâu

ố %s

ậ ằ - S d ng hàm - ớ scanf() v i tham s 4 : Nh p xâu b ng hàm scanf()

ử ụ ậ l p trình C h tr các hàm nh p xu t xâu. - ử ụ Ví d 2.ụ char s[100]; scanf("%s",s); gets()

- S d ng hàm Cú pháp: -

ị ả ề ỏ ế ỏ ủ char *gets(char *s); ố ầ Tham s đ u vào s là con tr c a xâu. Giá tr tr v : con tr đ n xâu đã

- ượ đ Ví d ụ

ậ ằ gets()

ậ c nh p vào. 2 . 5 : Nh p xâu b ng hàm char a[100];

ố %s.

char *b; b=gets(a); ỗ ấ b) Xu t chu i ằ ằ ấ Ví d 2.ụ ớ printf() v i tham s printf()

- Xu t ấ xâu lên màn hình b ng hàm 6 : Xu t xâu b ng hàm - char s[100]= "Xin chao den voi ky thua lap trinh"; printf("Loi chao: %s",s);

ử ụ hàm puts() - Xu t ấ xâu lên màn hình s d ng

Cú pháp:

ẽ ư ự c đ a lên màn hình, s đ a các ký t

int puts(const char *s); ầ ự ế ị ả ề ủ ượ ư k t thúc có mã lên màn ASCII là 0. Giá tr tr v c a hàm trên là

ặ ấ ấ ằ Trong đó s là xâu c n đ - ế hình đ n khi g p ký t ự ố s ký t đã xu t lên màn hình. Ví d 2.ụ 7 : Xu t xâu b ng hàm puts()

char s[100]= "Xin chao den voi ky thua lap trinh"; int c; c=puts(s);

ừ hàm sprintf()

- Xây d ng ự xâu t - Cú pháp:

hàm Trong đó buffer là xâu nh n k t qu . Hàm sprintf() t printf()

ả ẽ ư ế int sprintf (char *buffer, const char *format [, argument, ...]); ự ế ng t buffer.

ươ ậ - ư nh ng k t qu thay v đ a lên màn hình s đ a vào trong xâu Ví d 2.ụ 8 : Xu t xâu b ng hàm sprintf()

ề ư ả ằ ấ #include #include int main() {

char s[100]; int a=5, b=7; sprintf(s,"Tich cua %d va %d la %d",a,b,a*b); puts(s); getch(); return 0;

}

ữ ệ ử 2.2.2. Các hàm x lý d li u xâu

- Trong ngôn ng l p trình C các hàm x lý xâu đ

ữ ậ ử ượ ị ư ệ c đ nh nghĩa trong th vi n

ể ổ ứ ự ể ổ ể ữ a) Các hàm chuy n đ i ki u ch , chuy n đ i th t

ể ữ ườ thành ch th ng

string.h. - ự - Chuy n ký t Cú pháp: -

char *strlwr(char *s);

ự ể ữ ườ

trong xâu ượ ng. ữ ườ s thành ch th ể c chuy n thành ch th ng.

ữ ể Trong đó: ầ s là xâu đ u vào, hàm chuy n các ký t ị ả ề ủ ỏ ứ Giá tr tr v c a hàm là con tr ch a xâu đã đ ự thành ch hoa - Chuy n ký t

Cú pháp:

char *strupr(char *s);

Trong đó:

ự ầ ữ trong xâu s thành ch hoa.

ữ ể

- Tham s ố s là xâu đ u vào, hàm chuy n các ký t ể ỏ ứ ị ả ề ủ Giá tr tr v c a hàm là con tr ch a xâu đã chuy n thành ch hoa. ự ả - Đ o các ký t Cú pháp: -

trong xâu

char *strrev(char *s);

Trong đó:

ẽ ả ự .

- Tham s ố s là xâu đ u vào, hàm s đ o ng ượ ầ Giá tr tr v c a hàm là con tr đ n xâu đã đ

c th t ượ ả ượ ứ ự ấ c đ o ng ệ xu t hi n các ký t c.

- Ví d 2.ụ #include #include #include int main(void) {

ể ự ỏ ế ổ 9 : Hàm chuy n đ i ký t ị ả ề ủ

char a[]="Chuyen Thanh Chu Hoa"; char b[]="Chuyen Thanh Chu Thuong"; char c[]="Dao nguoc thu tu"; strupr(a); strlwr(b); strrev(c); puts(a); puts(b); puts(c); getch(); getch(); return 0; }

ề - b) Hàm xác đ nh chi u dài xâu

- Xác đ nh chi u dài c a xâu văn b n. Chi u dài c a xâu văn b n k t thúc b i ký

ị ủ ủ ề ề ế ả ả ở

ự t 0.

ị có mã - Cú pháp:

- Trong đó:

size_t strlen(const char *s);

ể

ị ả ề ủ ộ ủ ộ - Tham s ố s là xâu c n ki m tra đ dài. ầ - Giá tr tr v c a hàm là đ dài c a xâu

c) Hàm sao chép, ghép xâu

- - Sao chép xâu Cú pháp: -

char *strcpy(char *dest, const char *src);

Trong đó:

ẽ ỉ

- Tham s ố dest là đ a ch xâu s nh n giá tr sao chép. ậ ị ồ ượ ị Tham s ố src là đ a ch xâu ngu n đ

ỉ ị c sao chép.

ị ả ề ủ ượ ỏ Giá tr tr v c a hàm là con tr xâu đ

ế ự ừ t xâu c sao chép. Hàm strcpy ti n hành sao chép các ký t src sang xâu dest đ n khi

- ặ g p ký t

ự ự ế ả ự ế có mã là k t thúc xâu). Hàm sao chép c ký t k t thúc xâu. ế 0 (ký t

ố - N i xâu - Cú pháp:

char *strcat(char *dest, const char *src);

src vào cu i.ố

ẽ ượ ộ ộ c c ng thêm xâu dest.

ớ ượ ộ c c ng vào.

ệ ị ả ề ủ ự Hàm strcat th c hi n n i xâu src vào xâu dest.

ạ

Trong đó: - Tham s ố dest là xâu s đ Tham s ố src là xâu c ng thêm vào xâu ỏ ỉ ế Giá tr tr v c a hàm là con tr ch đ n vùng nh xâu đ ố - ớ ả - T o b n sao xâu m i Cú pháp: -

char *strdup(const char *s);

ẽ ượ ạ

ộ ớ ớ ượ ấ ể ư c c p phát đ l u tr ữ

Trong đó: - ả Tham s ố s là xâu s đ c t o b n sao. ỏ ỏ ế ị ả ề ủ Giá tr tr v c a hàm là con tr tr đ n vùng b nh m i đ xâu.

ự ớ ớ ệ ấ

ộ ớ ộ ớ ấ ằ Hàm strdup th c hi n vi c c p pháp m t vùng nh m i có đ l n b ng ộ

- ộ đ dài xâu, và ti n hành b n sao sang vùng m i này. Vì hàm này c p phát b ớ nh nên sau khi s d ng ph i s d ng hàm : Các hàm strcpy(), strcat() không gi ớ

ế ử ụ ệ ả ả ử ụ ể ả

free() đ gi ớ ạ ố ượ i h n s l ẽ ạ src l n s t o ra hi n t

ợ ng h p xâu ế ủ ượ ợ ớ i phóng vùng nh . ự ẽ ư s đ a vào xâu ộ ệ ng tràn b đ m ớ ạ c xâu i h n đ ng ký t ệ ượ ng h p không gi

ườ strncpy(), strncat() thay th .ế

- Ví d 2.ụ

- Chú ý ườ ế dest vì th trong tr ớ ư ữ (vùng nh l u tr không đ ) vì th trong tr ử ụ ầ đ u vào nên s d ng các hàm ố 10 : Copy và n i xâu

#include #include #include int main(void) {

char t[100]; char a[10]; char b[20]= "Thu"; char c[10]= "123456789"; char d[]="Chuoi dai hon vung dem"; strcpy(a,b); puts(a); strcat(b,c); puts(b); strncpy(a,d,10); a[9]=0; puts(a); strncat(b,d,20); b[19]=0;

puts(b); //loi tran bo dem printf("\nLoi\n"); strcpy(a,d); strcat(b,d); puts(a); puts(b); getch(); return 0; }

ệ ữ ườ ữ - d) Hàm so sánh hai xâu phân bi t ch hoa ch th ng

- Cú pháp:

- Trong đó:

int strcmp(const char *s1, const char*s2);

ế s2, b ng ằ 0 n u xâu s1 b ngằ ơ s1 bé h n xâu ứ ấ - Tham s ố s1 xâu c n so sánh th nh t. ầ - Tham s ố s2 xâu c n so sánh th hai. ứ ầ - Giá tr tr v c a hàm bé h n

ế ơ 0 n u xâu s1 l n h n xâu

ằ ừ ớ ả s2. ủ ế ơ ơ 0 n u xâu trái sang ph i theo mã c a các ký t

ị ả ề ủ ớ xâu s2, l n h n - Hàm so sánh t ằ ộ ầ ự ừ t . Hai xâu b ng nhau khi xâu ự ả ặ trái sang ph i g p ký t s2 thì chu iố xâu s1 có mã l n ký t

ị ố ộ ự thu c xâu ượ ạ c l i.

ự ế ừ có đ dài b ng nhau, các giá tr gi ng nhau. N u t ớ ế khác nhau đ u tiên n u ký t ặ ơ ớ s2 ho c ng s1 l n h n xâu - Ví d 2.ụ 11 : So sánh xâu char a[]="xin chao"; char b[]="xin chao"; char c[]="xin don mung cac ban"; int i1, i2; i1=strcmp(a,b); i2=strcmp(a,c);

ự ị

ế ự ứ ơ ị 0 (xâu a bàng xâu b), i2 có giá tr bé h n ẽ ự 'd' s có mã th 4 thì ký t

ệ i1 có giá tr là ừ c xét t ớ ơ 0 (xâu a bé h n xâu ơ ớ l n h n ký t trái sang khi đ n ký t a).

- Sau khi th c hi n: ơ ự 'c' nên xâu c l n h n xâu - Ngoài ra, đ so sánh hai xâu không phân bi

ể ệ ữ ườ ữ t ch hoa, ch th ng có th ể

ử ụ s d ng cú pháp sau đây. - Cú pháp:

int stricmp(const char *s1, const char *s2);

ư ệ ữ t ch hoa và

ữ ườ ố ơ ả - Hàm này c b n gi ng hàm ng có nghĩa hai ký t so sánh.

ư 'A' và 'a' là nh nhau v th t ủ ệ ự ấ ự ầ ch th - strcmp nh ng khi so sánh thì không bi ự e) Hàm tìm s xu t hi n đ u tiên c a ký t ề ứ ự trong xâu

- Cú pháp:

- Trong đó:

char *strchr(const char *s, int c);

ự trên đó.

ế

ệ ế ừ ả ề ỏ ỏ ế trái qua) thì hàm tr v con tr tr đ n ẽ - Tham s ố s là xâu s tìm ki m ký t ế - Tham s ố c là ký t ự ầ c n tìm ki m. ế ự ầ ấ - N u xu t hi n ký t c n tìm ki m (tính t

ệ ệ ấ ầ ự ầ ế xu t hi n đ u tiên; n u không xu t hi n ký t ế c n tìm ki m thì con

ự ể ử ụ ệ ầ ấ ể ả xu t hi n đ u tiên bên ph i có th s d ng cú pháp sau ị ự ấ ủ v trí c a ký t ỏ ỏ ế NULL. tr tr đ n - Ngoài ra, đ tìm ký t

đây. - Cú pháp:

char *strrchr(const char *s, int c);

- Hàm làm vi c t

ự ướ ế ừ ả ng t hàm ng tìm ki m là t ph i sang.

ệ ươ ế strchr() h ệ - ấ f) Tìm ki m xâu con xu t hi n trong xâu khác

- Cú pháp:

- Trong đó:

char *strstr(const char *s1, const char *s2);

ế ế s1.

ẽ ượ ầ ệ ủ ỏ ỏ ế s2 trên xâu s1 thì hàm s tr v con tr tr đ n - Tham s ố s1 là xâu s đ c tìm ki m trên đó. - Tham s ố s2 là xâu con c n tìm ki m trên xâu ấ ự ấ - N u tìm th y s xu t hi n c a xâu

ệ ủ ấ ượ ạ ả ạ đ u tiên xu t hi n c a xâu con; ng c l i giá tr ẽ ả ề ị NULL.

i tr l ố ế ự ầ ký t - ế ổ ể g) Các hàm bi n đ i ki u xâu thành s

ể ố

- Chuy n xâu thành s nguyên - Cú pháp:

int atoi(const char *s); long atol(const char *s);

ị

ị ả ề ủ atoi() tr v ki u ả ề ể int,

ế ị 0.

- Trong đó: ạ ể ố - Tham s ố s là xâu có đ nh d ng ki u s . ớ ố ươ ứ ng ng v i xâu. N u hàm - Giá tr tr v c a hàm là s t ế ỗ ẽ ả ạ ả ề ể long. N u l i giá tr i s tr l ố ự - Chuy n đ i xâu thành s th c - Cú pháp:

atol() tr v ki u ổ ể

- Trong đó:

double atof(const char *s);

ị

ạ ố ế ỗ ẽ ả ạ i s tr l i giá tr ị 0.

ạ ỏ ạ ầ - Tham s ố s là xâu có đ nh d ng ki u s . ể ố ị ả ề ủ - Giá tr tr v c a hàm là s . N u có l ụ ộ ố 2.2.3. M t s ví d ự ắ 1. Lo i b các ký t

ố tr ng (spacebar) c nh nhau, và đ u xâu, cu i xâu ạ ỏ ấ

ả ỉ ể ạ ộ ế ộ ấ ộ ạ ạ - Bài toán: Cho m t xâu là m t đo n văn b n hãy lo i b các d u cách ạ ỏ i m t d u cách), lo i b

ả

ngưở : Tìm ký t ự ắ

ờ ự ế ấ ạ c nh nhau (n u có nhi u d u cách c nh nhau ch đ l ố ủ ở ầ ấ đ u, và cu i c a văn b n. các d u cách ự ắ ự ầ - Ý t đ u tiên khác ký t ể en. Chuy n các ký t tr ng là ự ắ ồ đó không đ ng th i là ký t ố ị st. Tìm v trí cu i cùng tr ng là ả ế ự ừ st đ n en sang kho ng t ự ướ c đó cũng là tr tr ng và ký t

ư ừ ự ắ

: Xâu c n lo i b ký t ượ ự ắ ầ : Xâu đã đ ạ ỏ ạ ỏ c lo i b ký t tr ng d th a tr ng.

ủ c a xâu là khác ký t ớ ế xâu m i n u ký t ự ắ tr ng. ký t ậ Thu t toán: ữ ệ D li u vào ữ ệ D li u ra len=strlen(s); st=0; en=len1;

while(st

st++;

while(en>st && s[en]==' ')

en; mo=1; s[0]=s[st];

for(i=st+1 > en)

if(!(s[i]==' ' && s[i1]==' ')) {

s[mo]=s[i]; mo++;

}

s[mo]=0;

- Cài đ t ch #include #include #include int main(void) {

ươ ặ ng trình :

char s[]=" chuoi co du nhieu dau trang "; int st=0, len, en, mo=1,i; len=strlen(s); en=len; while(st

st++;

while(en>st && s[en]==' ')

en;

s[0]=s[st]; for(i=st+1;i

if(!(s[i]==' ' && s[i1]==' ')) {

s[mo]=s[i]; mo++;

}

} s[mo]=0; puts(s); getch(); return 0; }

ẩ 2. Chu n hóa tên

ữ ầ ế ả ắ ả ữ t hoa, các ch cái khác

ế vi

- Bài toán: Tên đ m b o qui t c ch đ u tên là vi ườ t th - Ý t

ự ổ ữ ườ ể ng. ể ngưở : Chuy n đ i các ký t trong xâu thành ch th ổ ng. Chuy n đ i

ầ ữ ữ ữ ứ ấ

ượ ể ch cái đ u tiên thành ch hoa. Tìm các ch cái đ ng sau d u cách chuy n ữ thành ch hoa. ậ Thu t toán: ữ ệ D li u vào ữ ệ D li u ra : Xâu tên : Xâu tên đã đ ẩ c chu n hóa.

s=strlwr(s); s[0]=toupper(s[0]); for(i=1 > N)

if(s[i1]==' ')

s[i]=toupper(s[i]);

- Cài đ t ch #include #include #include #include int main(void) {

ươ ặ ng trình :

char s[]="nguyen LAN ANH"; int i; strlwr(s); s[0]=toupper(s[0]); for(i=1;i

if(s[i1]==' ')

s[i]=toupper(s[i]);

} puts(s); getch(); return 0; }

ố ớ ộ 3. Phép toán c ng cho hai xâu s l n

ư ố ớ ự ệ ộ ố ớ ố - Bài toán: L u s l n trong hai xâu s , th c hi n phép c ng cho hai s l n

trên.

- Ý t

ớ ủ ố ố

ộ ộ 0. Duy t theo đ dài c a hai s l y t

ị ộ ủ ố ấ

c cùng v i s nh hi n t ổ

ố ế ẫ

ượ ả ượ ế ngưở : Tìm đ dài c a hai l n nh t c a hai xâu s . S nh ban đ u ầ ớ ấ ủ ộ ả ố ấ ừ ẽ ế ph i sang n u không thu c xâu s ố ệ ạ ớ ệ ạ ớ ố ượ i i. S hi n t ố ớ ế 10. 10. S nh ti p theo là t ng chia cho ế ố ư ộ ng h p sau khi c ng xong v n còn s d thì tính ti p cho s ti p theo. Do ị hi n th xâu là ng c ti n hành đ o ng c xâu.

ố ứ ấ : Xâu s th c nh t s1 và xâu s th 2 s2.

ố ổ ố ứ : Xâu s t ng.

b ng ằ ệ ậ 0. C ng hai s l y đ nh n giá tr là ủ ố ư ủ ổ c a xâu là s d c a t ng chia cho ườ ợ Tr ứ ự ể th t ậ Thu t toán: ữ ệ D li u vào ữ ệ D li u ra cl1=strlen(s1); cl2=strlen(s2); clm=timmax(cl1,cl2);

sd=0; for(i=0 >cml) {

i1=0; i2=0; if(i

i1=chuyensangso(s1[cl1i1];

if(i

i2=chuyensangso(s2[cl2i1];

t=sd+i1+i2; s[i]=chuyensangkytu(t%10); sd=t/10; } if(sd>0) {

s[i]=chuyensangkytu(sd); i++;

} s[i]=0; s=strrev(s);

- Cài đ t ch #include #include #include int main(void) {

ặ ươ ng trình :

char s1[]="12345678"; char s2[]="362435444545344678"; char s[100],sd=0,t,i1,i2; int i, cl1, cl2, cml; cl1=strlen(s1); cl2=strlen(s2); cml=cl1; if(cml

cml=cl2;