際際滷
Submit Search
Ctdl 2005 chuong 5
0 likes
123 views
H畛 L畛i
Follow
1 of 16
Download now
Download to read offline
More Related Content
Ctdl 2005 chuong 5
1.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 75 Ch旦担ng 5 CHUOI KY T Trong phan na淡y chu湛ng ta se探 hie辰n th旦誰c mo辰t l担湛p bie奪u die達n mo辰t chuo達i no叩i tie叩p ca湛c ky湛 t旦誰. V鱈 du誰 ta co湛 ca湛c chuo達i ky湛 t旦誰: a但y la淡 mo辰t chuo達i ky湛 t旦誰, Te但n? trong 単o湛 ca谷p da叩u kho但ng pha短i la淡 bo辰 pha辰n cu短a chuo達i ky湛 t旦誰. Mo辰t chuo達i ky湛 t旦誰 ro達ng 単旦担誰c ky湛 hie辰u . Chuo達i ky湛 t旦誰 cu探ng la淡 mo辰t danh sa湛ch ca湛c ky湛 t旦誰. Tuy nhie但n, ca湛c ta湛c vu誰 tre但n chuo達i ky湛 t旦誰 co湛 h担i 単a谷c bie辰t va淡 kha湛c v担湛i ca湛c ta湛c vu誰 tre但n mo辰t danh sa湛ch tr旦淡u t旦担誰ng ma淡 chu湛ng ta 単a探 単嘆nh ngh坦a, chu湛ng ta se探 kho但ng da達n xua叩t l担湛p chuo達i ky湛 t旦誰 t旦淡 mo辰t l担湛p List na淡o tr旦担湛c 単a但y. Trong ca湛c ta湛c vu誰 thao ta湛c tre但n chuo達i ky湛 t旦誰, ta湛c vu誰 t狸m kie叩m la淡 kho湛 kha棚n nha叩t. Chu湛ng ta se探 t狸m hie奪u hai gia短i thua辰t t狸m kie叩m va淡o cuo叩i ch旦担ng na淡y. Trong phan 単au, chu湛ng ta 単a谷c bie辰t quan ta但m 単e叩n vie辰c kha辿c phu誰c t鱈nh thie叩u an toa淡n cu短a chuo達i ky湛 t旦誰 trong ngo但n ng旦探 C ma淡 単a so叩 ng旦担淡i la辰p tr狸nh 単a探 t旦淡ng s旦短 du誰ng. Do 単o湛 phan tr狸nh ba淡y tie叩p theo 単a但y lie但n quan cha谷t che探 単e叩n ngo但n ng旦探 C va淡 C++. 5.1. Chuo達i ky湛 t旦誰 trong C va淡 trong C++ Ngo但n ng旦探 C++ cung ca叩p hai ca湛ch hie辰n th旦誰c chuo達i ky湛 t旦誰. Ca湛ch nguye但n thu短y la淡 hie辰n th旦誰c string cu短a C. Gio叩ng nh旦 nh旦探ng phan kha湛c, hie辰n th旦誰c string cu短a ngo但n ng旦探 C co湛 the奪 cha誰y trong mo誰i hie辰n th旦誰c cu短a C++. Chu湛ng ta se探 go誰i ca湛c 単o叩i t旦担誰ng string cung ca叩p b担短i C la淡 C-String. C-String the奪 hie辰n ca短 ca湛c 単ie奪m ma誰nh va淡 ca短 ca湛c 単ie奪m ye叩u cu短a ngo但n ng旦探 C: chu湛ng ra叩t pho奪 bie叩n, ra叩t hie辰u qua短 nh旦ng cu探ng ra叩t hay b嘆 du淡ng sai. C-String lie但n quan 単e叩n mo辰t loa誰t ca湛c ta辰p qua湛n ma淡 chu湛ng ta se探 xem la誰i d旦担湛i 単a但y. Mo辰t C-String co湛 kie奪u char*. Do 単o湛, mo辰t C-String tham chie叩u 単e叩n mo辰t 単嘆a ch脱 trong bo辰 nh担湛; 単嘆a ch脱 na淡y la淡 単ie奪m ba辿t 単au cu短a ta辰p ca湛c bytes ch旦湛a ca湛c ky湛 t旦誰 trong chuo達i ky湛 t旦誰. Vu淡ng nh担湛 chie叩m b担短i mo辰t chuo達i ky湛 t旦誰 pha短i 単旦担誰c ke叩t thu湛c ba竪ng mo辰t ky湛 t旦誰 単a谷c bie辰t 0. Tr狸nh bie但n d嘆ch kho但ng the奪 kie奪m tra giu湛p quy 単嘆nh na淡y, s旦誰 thie叩u so湛t se探 ga但y lo達i th担淡i gian cha誰y. No湛i ca湛ch kha湛c, C-String kho但ng co湛 t鱈nh 単o湛ng k鱈n va淡 thie叩u an toa淡n. Ta辰p tin chua奪n <cstring> ch旦湛a th旦 vie辰n ca湛c ha淡m x旦短 ly湛 C-String. Trong ca湛c tr狸nh bie但n d嘆ch C++ cu探, ta辰p tin na淡y th旦担淡ng co湛 te但n la淡 <string.h>. Ca湛c ha淡m th旦 vie辰n na淡y ra叩t tie辰n l担誰i, hie辰u qua短 va淡 ch旦湛a hau he叩t ca湛c ta湛c vu誰 tre但n chuo達i ky湛 t旦誰 ma淡 chu湛ng ta can. Gia短 s旦短 s va淡 t la淡 ca湛c C-String. Ta湛c vu誰 strlen(s) tra短 ve chieu da淡i cu短a s, strcmp(s,t) so sa湛nh t旦淡ng ky湛 t旦誰 cu短a s va淡 t, va淡 strstr(s,t) tra短 ve con tro短 tham chie叩u 単e叩n v嘆 tr鱈 ba辿t 単au cu短a t trong s. Ngoa淡i ra, trong C++ ta湛c vu誰 xua叩t << 単旦担誰c 単嘆nh ngh坦a la誰i cho C-String, nh担淡 va辰y, le辰nh 単担n gia短n << s se探 in chuo達i ky湛 t旦誰 s.
2.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 76 Ma谷c du淡 hie辰n th旦誰c C-String co湛 nhieu 旦u 単ie奪m tuye辰t v担淡i, nh旦ng no湛 cu探ng co湛 nh旦探ng nh旦担誰c 単ie奪m nghie但m tro誰ng. Th旦誰c va辰y, no湛 co湛 nh旦探ng va叩n 単e ma淡 chu湛ng ta 単a探 ga谷p pha短i khi nghie但n c旦湛u CTDL nga棚n xe叩p lie但n ke叩t trong ch旦担ng 2 cu探ng nh旦 ca湛c CTDL co湛 ch旦湛a thuo辰c t鱈nh con tro短 no湛i chung. Tha辰t de達 da淡ng khi ng旦担淡i s旦短 du誰ng co湛 the奪 ta誰o b鱈 danh cho chuo達i ky湛 t旦誰, cu探ng nh旦 ga但y ne但n ra湛c. Trong h狸nh 5.1, chu湛ng ta tha叩y ro探 phe湛p ga湛n s = t da達n 単e叩n ca短 hai va叩n 単e tre但n. Mo辰t va叩n 単e kha湛c cu探ng th旦担淡ng na短y sinh trong ca湛c 旦湛ng du誰ng co湛 s旦短 du誰ng C- String. Mo辰t C-String ch旦a kh担短i ta誰o can 単旦担誰c ga湛n NULL. Tuy nhie但n, ra叩t nhieu ha淡m th旦 vie辰n cu短a C-String se探 ga谷p s旦誰 co叩 trong th担淡i gian cha誰y khi ga谷p 単o叩i t旦担誰ng C-String la淡 NULL. Cha炭ng ha誰n, le辰nh char* x = NULL; cout << strlen(x); 単旦担誰c mo辰t so叩 tr狸nh bie但n d嘆ch cha叩p nha辰n, nh旦ng v担湛i nhieu hie辰n th旦誰c kha湛c cu短a th旦 vie辰n C-String, th狸 ga谷p lo達i trong th担淡i gian cha誰y. Do 単o湛, ng旦担淡i s旦短 du誰ng pha短i kie奪m tra ky探 l旦担探ng 単ieu kie辰n tr旦担湛c khi go誰i ca湛c ha淡m th旦 vie辰n. Trong C++, vie辰c 単o湛ng go湛i string va淡o mo辰t l担湛p co湛 t鱈nh 単o湛ng k鱈n va淡 an toa淡n 単旦担誰c th旦誰c hie辰n de達 da淡ng. Th旦 vie辰n chua奪n STL co湛 l担湛p String an toa淡n ch旦湛a trong ta辰p tin <string>. Th旦 vie辰n na淡y hie辰n th旦誰c l担湛p co湛 te但n std::String v旦淡a tie辰n l担誰i, an toa淡n v旦淡a hie辰u qua短. Trong phan na淡y chu湛ng ta se探 t旦誰 xa但y d旦誰ng mo辰t l担湛p String 単e奪 co湛 d嘆p hie奪u ky探 ve ca湛ch ta誰o ne但n mo辰t CTDL co湛 t鱈nh 単o湛ng k鱈n va淡 an toa淡n cao. Chu湛ng ta se探 kho但ng pha短i vie叩t la誰i toa淡n bo辰 ma淡 ch脱 s旦短 du誰ng la誰i th旦 vie辰n 単a探 co湛 C-String. H狸nh 5.1- S旦誰 thie叩u an toa淡n cu短a C-String.
3.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 77 5.2. a谷c ta短 cu短a l担湛p String e奪 ta誰o mo辰t hie辰n th旦誰c l担湛p String an toa淡n, chu湛ng ta 単o湛ng go湛i C-String nh旦 mo辰t thuo辰c t鱈nh tha淡nh phan cu短a no湛 va淡 単e奪 thua辰n tie辰n h担n, chu湛ng ta the但m mo辰t thuo辰c t鱈nh chieu da淡i cho chuo達i ky湛 t旦誰. Do thuo辰c t鱈nh char* la淡 mo辰t con tro短, chu湛ng ta can the但m ca湛c ta湛c vu誰 ga湛n 単嘆nh ngh坦a la誰i (overloaded assignment), copy constructor, destructor, 単e奪 l担湛p String cu短a chu湛ng ta tra湛nh 単旦担誰c ca湛c va叩n 単e b鱈 danh, ta誰o ra湛c, hoa谷c vie辰c s旦短 du誰ng 単o叩i t旦担誰ng ma淡 ch旦a 単旦担誰c kh担短i ta誰o. 5.2.1. Ca湛c phe湛p so sa湛nh V担湛i mo辰t so叩 旦湛ng du誰ng, se探 he叩t s旦湛c thua辰n tie辰n ne叩u chu湛ng ta bo奪 sung the但m ca湛c ta湛c vu誰 so sa湛nh <, >, <=, >=, ==, != 単e奪 so sa湛nh t旦淡ng ca谷p 単o叩i t旦担誰ng String theo t旦淡ng ky湛 t旦誰. V狸 the叩, l担湛p String cu短a chu湛ng ta se探 ch旦湛a ca湛c ta湛c vu誰 so sa湛nh 単旦担誰c 単嘆nh ngh坦a la誰i (overloaded comparison operators). 5.2.2. Mo辰t so叩 constructor tie辰n du誰ng Ta誰o 単o叩i t旦担誰ng String t旦淡 mo辰t C-String Chu湛ng ta se探 xa但y d旦誰ng constructor v担湛i tho但ng so叩 char* cho l担湛p String. Constructor na淡y cung ca叩p mo辰t ca湛ch chuye奪n 単o奪i thua辰n tie辰n mo辰t 単o叩i t旦担誰ng C- String sang 単o叩i t旦担誰ng String. Vie辰c chuye奪n 単o奪i tho但ng qua ca湛ch go誰i t旦担淡ng minh nh旦 sau: String s(some_string); Trong le辰nh na淡y, 単o叩i t旦担誰ng String s 単旦担誰c ta誰o ra ch旦湛a d旦探 lie辰u la淡 some_string. Constructor na淡y 単o但i khi co淡n 単旦担誰c go誰i mo辰t ca湛ch kho但ng t旦担淡ng minh b担短i tr狸nh bie但n d嘆ch mo達i khi ch旦担ng tr狸nh can 単e叩n s旦誰 e湛p kie奪u (type cast) t旦淡 kie奪u char* sang String. La叩y v鱈 du誰, String s; s = some_string; e奪 cha誰y le辰nh th旦湛 hai, tr狸nh bie但n d嘆ch C++ tr旦担湛c he叩t go誰i constructor cu短a chu湛ng ta 単e奪 chuye奪n some_string tha淡nh mo辰t 単o叩i t旦担誰ng String ta誰m. Sau 単o湛 phe湛p ga湛n 単嘆nh ngh坦a la誰i cu短a String 単旦担誰c go誰i 単e奪 che湛p 単o叩i t旦担誰ng ta誰m na淡y va淡o s. Cuo叩i cu淡ng destructor cho 単o叩i t旦担誰ng ta誰m 単旦担誰c th旦誰c hie辰n. Ta誰o 単o叩i t旦担誰ng String t旦淡 mo辰t danh sa湛ch ca湛c ky湛 t旦誰 T旦担ng t旦誰, chu湛ng ta cu探ng ne但n co湛 constructor 単e奪 chuye奪n mo辰t danh sa湛ch ca湛c ky湛 t旦誰 sang mo辰t 単o叩i t旦担誰ng String. Cha炭ng ha誰n, khi 単o誰c mo辰t chuo達i ky湛 t旦誰 t旦淡 ng旦担淡i s旦短 du誰ng, chu湛ng ta ne但n 単o誰c t旦淡ng ky湛 t旦誰 va淡o mo辰t danh sa湛ch ca湛c ky湛 t旦誰 do ch旦a bie叩t tr旦担湛c
4.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 78 chieu da淡i cu短a no湛. Sau 単o湛 chu湛ng ta se探 chuye奪n 単o奪i danh sa湛ch na淡y sang mo辰t 単o叩i t旦担誰ng String. Chuye奪n t旦淡 mo辰t 単o叩i t旦担誰ng String sang mo辰t C-String Cuo叩i cu淡ng, ne叩u co湛 the奪 chuye奪n 単o奪i ng旦担誰c t旦淡 mo辰t 単o叩i t旦担誰ng String sang mo辰t 単o叩i t旦担誰ng C-String th狸 se探 ra叩t co湛 l担誰i cho nh旦探ng tr旦担淡ng h担誰p string can 単旦担誰c xem la淡 char*. o湛 la淡 nh旦探ng lu湛c chu湛ng ta can s旦短 du誰ng la誰i ca湛c ha淡m th旦 vie辰n cu短a C-String cho ca湛c 単o叩i t旦担誰ng String. Ph旦担ng th旦湛c na淡y se探 単旦担誰c go誰i la淡 c_str() va淡 pha短i tra短 ve const char* la淡 mo辰t con tro短 tham chie叩u 単e叩n d旦探 lie辰u bie奪u die達n String. Ph旦担ng th旦湛c c_str() co湛 the奪 単旦担誰c go誰i nh旦 sau: String s = some_String; const char* new_s = s.c_str(); ieu quan tro誰ng 担短 単a但y la淡 c_str() tra短 ve mo辰t C-String nh旦 la淡 ca湛c ky湛 t旦誰 ha竪ng. Chu湛ng ta co湛 the奪 tha叩y 単旦担誰c s旦誰 can thie叩t na淡y ne叩u chu湛ng ta xem xe湛t 単e叩n vu淡ng nh担湛 chie叩m b担短i chuo達i ky湛 t旦誰 new_s. Vu淡ng nh担湛 na淡y ro探 ra淡ng la淡 thuo辰c 単o叩i t旦担誰ng cu短a l担湛p String. Chu湛ng ta tha叩y ra竪ng l担湛p String ne但n ch嘆u tra湛ch nhie辰m ve vu淡ng nh担湛 na淡y, v狸 単ieu 単o湛 cho phe湛p chu湛ng ta hie辰n th旦誰c ha淡m chuye奪n 単o奪i mo辰t ca湛ch hie辰u qua短, 単ong th担淡i tra湛nh 単旦担誰c cho ng旦担淡i s旦短 du誰ng kho短i pha短i ch嘆u tra湛ch nhie辰m ve vie辰c que但n xo湛a mo辰t C-String 単a探 単旦担誰c chuye奪n 単o奪i t旦淡 mo辰t 単o叩i t旦担誰ng String. Do 単o湛, chu湛ng ta khai ba湛o c_str() tra短 ve const char* 単e奪 ng旦担淡i s旦短 du誰ng kho但ng the奪 s旦短 du誰ng con tro短 tra短 ve na淡y ma淡 thay 単o奪i ca湛c ky湛 t旦誰 d旦探 lie辰u 単旦担誰c tham chie叩u 単e叩n, s旦誰 thay 単o奪i na淡y ch脱 thuo辰c quyen cu短a l担湛p String ma淡 tho但i. V担湛i mo辰t so叩 鱈t 単a谷c t鱈nh 単旦担誰c mo但 ta短 tre但n chu湛ng ta co湛 単旦担誰c mo辰t ca湛ch x旦短 ly湛 chuo達i ky湛 t旦誰 vo但 cu淡ng linh hoa誰t, hie辰u qua短 va淡 an toa淡n. L担湛p String cu短a chu湛ng ta la淡 mo辰t ADT 単o湛ng k鱈n hoa淡n toa淡n, nh旦ng no湛 cung ca叩p mo辰t giao die辰n tha辰t 単ay 単u短. Chu湛ng ta co湛 単a谷c ta短 l担湛p String nh旦 sau: class String { public: String(); ~String(); String (const String ©); // copy constructor String (const char * copy); // Chuye奪n 単o奪i t旦淡 C-string String (List<char> ©); // Chuye奪n 単o奪i t旦淡 List ca湛c ky湛 t旦誰 void operator =(const String ©); const char *c_str() const; // Chuye奪n 単o奪i sang C-string protected: char *entries; int length; };
5.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 79 bool operator ==(const String &first, const String &second); bool operator >(const String &first, const String &second); bool operator <(const String &first, const String &second); bool operator >=(const String &first, const String &second); bool operator <=(const String &first, const String &second); bool operator !=(const String &first, const String &second); 5.3. Hie辰n th旦誰c l担湛p String Ca湛c constructor chuye奪n 単o奪i C-String va淡 danh sa湛ch ca湛c ky湛 t旦誰 sang 単o叩i t旦担誰ng String: String::String (const char *in_string) /* pre: Con tro短 in_string tham chie叩u 単e叩n mo辰t C-string. post: o叩i t旦担誰ng String 単旦担誰c kh担短i ta誰o t旦淡 chuo達i ky湛 t旦誰 C-string in_string, va淡 no湛 na辿m gi旦探 mo辰t ba短n sao cu短a in_string, chuo達i ky湛 t旦誰 trong in_string kho但ng thay 単o奪i. */ { length = strlen(in_string); entries = new char[length + 1]; strcpy(entries, in_string); } String::String (List<char> in_list) /* post: o叩i t旦担誰ng String 単旦担誰c kh担短i ta誰o t旦淡 danh sa湛ch ca湛c ky湛 t旦誰 trong 単o叩i t旦担誰ng List, va淡 no湛 na辿m gi旦探 mo辰t ba短n sao kha湛c, 単o叩i t旦担誰ng in_list kho但ng thay 単o奪i. */ { length = in_list.size(); entries = new char[length + 1]; for (int i = 0; i < length; i++) in_list.retrieve(i,entries[i]); entries[length] = '0'; } Chu湛ng ta cho誰n ca湛ch hie辰n th旦誰c ph旦担ng th旦湛c chuye奪n 単o奪i 単o叩i t旦担誰ng String sang const char* nh旦 sau: const char*String::c_str() const /* post: tra短 ve con tro短 ch脱 ky湛 t旦誰 単au tie但n cu短a chuo達i ky湛 t旦誰 trong 単o叩i t旦担誰ng String. L旦u y湛 ra竪ng 担短 単a但y co湛 vie辰c chia se短 cu淡ng mo辰t chuo達i ky湛 t旦誰. */ { return (const char *) entries; } Ca湛ch hie辰n th旦誰c na淡y cu探ng kho但ng hoa淡n toa淡n th鱈ch 単a湛ng do no湛 cho phe湛p truy xua叩t d旦探 lie辰u be但n trong cu短a 単o叩i t旦担誰ng String. Tuy nhie但n chu湛ng ta se探 tha叩y nh旦探ng
6.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 80 ca湛ch gia短i quye叩t kha湛c cu探ng ga谷p mo辰t so叩 va叩n 単e. Ca湛ch gia短i quye叩t na淡y co淡n co湛 単旦担誰c 旦u 単ie奪m la淡 t鱈nh hie辰u qua短. Ph旦担ng th旦湛c c_str() tra短 ve con tro短 ch脱 単e叩n ma短ng ca湛c ky湛 t旦誰 ch脱 co湛 the奪 単o誰c ch旦湛 kho但ng the奪 s旦短a 単o奪i do chu湛ng ta 単a探 e湛p kie奪u sang const char*. Tuy nhie但n ng旦担淡i la辰p tr狸nh co湛 the奪 e湛p kie奪u ng旦担誰c tr担短 la誰i va淡 ga湛n va淡o mo辰t con tro短 kha湛c la淡m pha湛 v担探 t鱈nh 単o湛ng k鱈n cu短a d旦探 lie辰u cu短a chu湛ng ta. Mo辰t va叩n 単e nghie但m tro誰ng h担n ch鱈nh la淡 b鱈 danh 単旦担誰c ta誰o b担短i ph旦担ng th旦湛c na淡y. Chu湛ng ta tha叩y ra竪ng ng旦担淡i la辰p tr狸nh ne但n s旦短 du誰ng con tro短 tra短 ve ngay sau khi v旦淡a go誰i ph旦担ng th旦湛c, ne叩u kho但ng nh旦探ng g狸 xa短y ra se探 kho但ng l旦担淡ng tr旦担湛c 単旦担誰c. La叩y v鱈 du誰 sau: String s = "abc"; const char *new_string = s.c_str(); s = "def"; cout << new_string; Le辰nh s = "def" 単a探 la淡m thay 単o奪i d旦探 lie辰u ma淡 new_string ch脱 単e叩n. Mo辰t chie叩n l旦担誰c kha湛c cho ph旦担ng th旦湛c c_str() co湛 the奪 la淡 単嘆nh v嘆 vu淡ng nh担湛 単o辰ng m担湛i 単e奪 che湛p d旦探 lie辰u cu短a 単o叩i t旦担誰ng String sang. Ca湛ch hie辰n th旦誰c na淡y ro探 ra淡ng la淡 ke湛m hie辰u qua短 h担n, 単a谷c bie辰t 単o叩i v担湛i String da淡i. Ngoa淡i ra no湛 co淡n co湛 mo辰t nh旦担誰c 単ie奪m nghie但m tro誰ng, 単o湛 la淡 kha短 na棚ng ta誰o ra湛c. String ma淡 c_str() tra短 ve kho但ng co淡n chia se短 d旦探 lie辰u v担湛i 単o叩i t旦担誰ng String n旦探a, va淡 nh旦 va辰y ng旦担淡i la辰p tr狸nh pha短i nh担湛 delete no湛 khi kho但ng co淡n s旦短 du誰ng. Cha炭ng ha誰n, ne叩u ch脱 vie辰c in ra nh旦 d旦担湛i 単a但y th狸 trong bo辰 nh担湛 単a探 単e奪 la誰i ra湛c do ca湛ch hie辰n th旦誰c v旦淡a ne但u. String s = "Some very long string"; cout << s.c_str(); To湛m la誰i, tuy chu湛ng ta va達n gi旦探 ph旦担ng a湛n 単au tie但n cho ph旦担ng th旦湛c c_str(), nh旦ng ng旦担淡i la辰p tr狸nh kho但ng ne但n s旦短 du誰ng ph旦担ng th旦湛c na淡y v狸 no湛 pha湛 v担探 t鱈nh 単o湛ng k鱈n cu短a 単o叩i t旦担誰ng String, tr旦淡 khi muo叩n s旦短 du誰ng la誰i ca湛c ha淡m th旦 vie辰n cu短a C- String va淡 単a探 hie奪u tha辰t ro探 ve ba短n cha叩t cu短a s旦誰 vie辰c. Cuo叩i cu淡ng, chu湛ng ta xem xe湛t ca湛c ta湛c vu誰 so sa湛nh 単旦担誰c 単嘆nh ngh坦a la誰i. Hie辰n th旦誰c sau 単a但y cu短a phe湛p so sa湛nh ba竪ng 単旦担誰c 単嘆nh ngh坦a la誰i tha辰t nga辿n go誰n va淡 hie辰u qua短 nh担淡 ph旦担ng th旦湛c c_str(). bool operator ==(const String &first, const String &second) /* post: Tra短 ve true ne叩u 単o叩i t旦担誰ng first gio叩ng 単o叩i t旦担誰ng second. Ng旦担誰c la誰i tra短 ve false. */ { return strcmp(first.c_str(), second.c_str()) == 0; } Ca湛c ta湛c vu誰 so sa湛nh 単嘆nh ngh坦a la誰i kha湛c co湛 hie辰n th旦誰c hau nh旦 t旦担ng t旦誰.
7.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 81 5.4. Ca湛c ta湛c vu誰 tre但n String Chu湛ng ta se探 pha湛t trie奪n mo辰t so叩 ta湛c vu誰 la淡m vie辰c tre但n ca湛c 単o叩i t旦担誰ng String. Trong nhieu tr旦担淡ng h担誰p, ca湛c ha淡m cu短a C-String co湛 the奪 単旦担誰c go誰i tr旦誰c tie叩p cho ca湛c 単o叩i t旦担誰ng String 単a探 chuye奪n 単o奪i: String s = "some_string"; cout << s.c_str() << endl; cout << strlen(s.c_str()) << endl; o叩i v担湛i nh旦探ng ha淡m kho但ng thay 単o奪i ca湛c tho但ng so叩 String nh旦 strcpy, chu湛ng ta se探 vie叩t ca湛c phie但n ba短n 単嘆nh ngh坦a la誰i co湛 tho但ng so叩 la淡 単o叩i t旦担誰ng String thay v狸 char*. Nh旦 chu湛ng ta 単a探 bie叩t, trong C++, mo辰t ha淡m 単旦担誰c go誰i la淡 co湛 単嘆nh ngh坦a la誰i ne叩u hai hoa谷c ba phie但n ba短n kha湛c nhau cu短a no湛 co湛 trong cu淡ng mo辰t ch旦担ng tr狸nh. Chu湛ng ta 単a探 co湛 ca湛c constructor va淡 ca湛c ta湛c vu誰 ga湛n 単嘆nh ngh坦a la誰i. Khi mo辰t ha淡m 単旦担誰c 単嘆nh ngh坦a la誰i, chu湛ng pha短i co湛 ca湛c tho但ng so叩 kha湛c nhau. Ca棚n c旦湛 va淡o ca湛c tho但ng so叩 単旦担誰c g担短i khi go誰i ha淡m, tr狸nh bie但n d嘆ch bie叩t 単旦担誰c can pha短i s旦短 du誰ng phie但n ba短n na淡o. Phie但n ba短n 単嘆nh ngh坦a la誰i cho strcat co湛 khai ba湛o nh旦 sau: void strcat(String &add_to, const String &add_on) Ng旦担淡i s旦短 du誰ng co湛 the奪 go誰i strcat(s,t) 単e奪 no叩i chuo達i ky湛 t旦誰 t va淡o chuo達i ky湛 t旦誰 s. s la淡 mo辰t String, t co湛 the奪 la淡 String hoa谷c C-String. Ne叩u t la淡 C-String th狸 tr旦担湛c he叩t constructor co湛 tho但ng so叩 char* se探 th旦誰c hie辰n 単e奪 chuye奪n t tha淡nh mo辰t 単o叩i t旦担誰ng String cho h担誰p kie奪u tho但ng so叩 ma淡 strcat ye但u cau. void strcat(String &add_to, const String &add_on) /* post: String add_on 単旦担誰c no叩i va淡o sau String add_to. */ { const char *cfirst = add_to.c_str(); const char *csecond = add_on.c_str(); char *copy = new char[strlen(cfirst) + strlen(csecond) + 1]; strcpy(copy, cfirst); strcat(copy, csecond); add_to = copy; delete []copy; } Trong ph旦担ng th旦湛c tre但n co湛 go誰i strcat v担湛i hai tho但ng so叩 la淡 char* va淡 const char*, ta誰i 単a但y tr狸nh bie但n d嘆ch se探 go誰i 単u湛ng ha淡m th旦 vie辰n cu短a C-String ch旦湛 kho但ng pha短i go誰i 単e辰 quy ch鱈nh ph旦担ng th旦湛c na淡y. Do add_to la淡 単o叩i t旦担誰ng String, le辰nh add_to = copy tr旦担湛c he叩t go誰i constructor 単e奪 chuye奪n copy kie奪u char* sang 単o叩i t旦担誰ng String, sau 単o湛 m担湛i go誰i phe湛p ga湛n 単嘆nh ngh坦a la誰i cu短a l担湛p String. No湛i ca湛ch kha湛c, 単ieu na淡y da達n 単e叩n vie辰c
8.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 82 che湛p chuo達i ky湛 t旦誰 hai lan. e奪 tra湛nh 単ieu na淡y chu湛ng ta ha探y th旦短 thay 単o奪i do淡ng le辰nh. Cha炭ng ha誰n, mo辰t ca湛ch 単担n gia短n chu湛ng ta khai ba湛o strcat la淡 mo辰t ha淡m friend cu短a l担湛p String. Khi 単o湛 chu湛ng ta co湛 the奪 truy ca辰p 単e叩n thuo辰c t鱈nh entries cu短a l担湛p String: add_to.entries = copy. Chu湛ng ta can ha淡m 単e奪 単o誰c ca湛c 単o叩i t旦担誰ng String. Chu湛ng ta co湛 the奪 th旦誰c hie辰n t旦担ng t旦誰 nh旦 単o叩i v担湛i C-String, ta湛c vu誰 << se探 単旦担誰c 単嘆nh ngh坦a la誰i 単e奪 nha辰n tho但ng so叩 la淡 mo辰t String. Tuy nhie但n, chu湛ng ta cu探ng co湛 the奪 du淡ng ca湛ch kha湛c 単e奪 xa但y d旦誰ng ha淡m read_in nh旦 sau: String read_in(istream &input) /* post: Tra短 ve mo辰t 単o叩i t旦担誰ng String 単o誰c t旦淡 tho但ng so叩 istream (ky湛 t旦誰 ke叩t thu湛c chuo達i ky湛 t旦誰 単旦担誰c quy 旦担湛c la淡 ky湛 t旦誰 xuo叩ng ha淡ng hoa谷c ke叩t thu湛c ta辰p tin) */ { List<char> temp; int size = 0; char c; while ((c = input.peek()) != EOF && (c = input.get()) != 'n') temp.insert(size++, c); String answer(temp); return answer; } Ha淡m tre但n s旦短 du誰ng mo辰t 単o叩i t旦担誰ng temp 単e奪 gom ca湛c ky湛 t旦誰 t旦淡 tho但ng so叩 input, sau 単o湛 go誰i constructor 単e奪 chuye奪n 単o奪i temp na淡y tha淡nh 単o叩i t旦担誰ng String. Ky湛 t旦誰 ke叩t thu湛c chuo達i ky湛 t旦誰 la淡 ky湛 t旦誰 xuo叩ng ha淡ng hoa谷c ky湛 t旦誰 ke叩t thu湛c ta辰p tin. Mo辰t phie但n ba短n 単旦担誰c 単e ngh嘆 kha湛c cho ha淡m read_in la淡 the但m tho但ng so叩 th旦湛 hai 単e奪 ch脱 ra ky湛 t旦誰 ke叩t thu湛c chuo達i ky湛 t旦誰 mong muo叩n: String read_in(istream &input, int &terminator); post: Tra短 ve mo辰t 単o叩i t旦担誰ng String 単o誰c t旦淡 tho但ng so叩 istream (ky湛 t旦誰 ke叩t thu湛c chuo達i ky湛 t旦誰 単旦担誰c quy 旦担湛c la淡 ky湛 t旦誰 xuo叩ng ha淡ng hoa谷c ke叩t thu湛c ta辰p tin, ky湛 t旦誰 na淡y cu探ng 単旦担誰c tra短 ve tho但ng qua tham bie叩n terminator.) T旦担ng t旦誰 chu湛ng ta co湛 ph旦担ng th旦湛c 単e奪 in mo辰t 単o叩i t旦担誰ng String: void write(String &s) /* post: o叩i t旦担誰ng String s 単旦担誰c in ra cout. */ { if (strlen(s.c_str())>0) cout << s.c_str() << endl; }
9.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 83 Trong ca湛c phan tie叩p theo chu湛ng ta se探 s旦短 du誰ng ca湛c ha淡m th旦 vie辰n cho l担湛p String nh旦 sau: void strcpy(String ©, const String &original); post: Ha淡m che湛p String original sang String copy. void strncpy(String ©, const String &original, int n); post: Ha淡m che湛p nhieu nha叩t la淡 n ky湛 t旦誰 t旦淡 String original sang String copy. int strstr(const String &text, const String &target); post: Ne叩u String target la淡 chuo達i con (subtring) cu短a String text, ha淡m tra短 ve v嘆 tr鱈 xua叩t hie辰n 単au tie但n cu短a target trong text; ng旦担誰c la誰i, ha淡m tra短 ve -1. Ca湛c hie辰n th旦誰c cu短a ca湛c ha淡m na淡y theo ca湛ch s旦短 du誰ng la誰i th旦 vie辰n C-String 単旦担誰c xem nh旦 ba淡i ta辰p. 5.5. Ca湛c gia短i thua辰t t狸m mo辰t chuo達i con trong mo辰t chuo達i Phan sau 単a但y chu湛ng ta se探 t狸m hie奪u la誰i ca湛ch hie辰n th旦誰c cu短a mo辰t va淡i ha淡m th旦 vie辰n cu短a C-String. Ca湛c phe湛p x旦短 ly湛 c担 ba短n tre但n chuo達i ky湛 t旦誰 bao gom: t狸m mo辰t chuo達i con trong mo辰t chuo達i, thay the叩 mo辰t chuo達i con ba竪ng mo辰t chuo達i kha湛c, che淡n mo辰t chuo達i con va淡o mo辰t chuo達i, loa誰i mo辰t chuo達i con trong mo辰t chuo達i, Trong 単o湛 phe湛p t狸m mo辰t chuo達i con trong mo辰t chuo達i co湛 the奪 xem la淡 phe湛p c担 ba短n nha叩t, nh旦探ng phe湛p co淡n la誰i co湛 the奪 単旦担誰c th旦誰c hie辰n de達 da淡ng sau khi 単a探 xa湛c 単嘆nh 単旦担誰c v嘆 tr鱈 cu短a chuo達i con. Chu湛ng ta se探 t狸m hie奪u hai gia短i thua辰t t狸m chuo達i con trong mo辰t chuo達i cho tr旦担湛c. 5.5.1. Gia短i thua辰t Brute-Force Y t旦担短ng gia短i thua辰t na淡y vo但 cu淡ng 単担n gia短n, 単o湛 la淡 th旦短 so tru淡ng chuo達i con ta誰i mo誰i v嘆 tr鱈 ba辿t 単au trong chuo達i 単a探 cho (H狸nh 5.2). Gia短 s旦短 chu湛ng ta can t狸m v嘆 tr鱈 cu短a chuo達i a trong chuo達i s. Ca湛c v嘆 tr鱈 ba辿t 単au so tru淡ng a tre但n s la淡 0, 1, 2, Mo達i lan so tru淡ng, chu湛ng ta lan l旦担誰t so sa湛nh t旦淡ng ca谷p ky湛 t旦誰 cu短a a va淡 s t旦淡 tra湛i sang pha短i. Khi ga谷p hai ky湛 t旦誰 kha湛c nhau, chu湛ng ta la誰i pha短i ba辿t 単au so tru淡ng t旦淡 単au chuo達i a v担湛i v嘆 tr鱈 m担湛i. V嘆 tr鱈 ba辿t 単au so tru淡ng tre但n s lan th旦湛 i se探 la淡 v嘆 tr鱈 ba辿t 単au so tru淡ng tre但n s lan th旦湛 i-1 co辰ng the但m 1. Ca湛c ky湛 t旦誰 in nghie但ng trong h狸nh ve探 be但n d旦担湛i la淡 v嘆 tr鱈 tha叩t ba誰i trong mo辰t lan so tru淡ng, phan co湛 nen xa湛m be但n tra湛i chu湛ng la淡 nh旦探ng ky湛 t旦誰 so tru淡ng 単a探 tha淡nh co但ng. Mo辰t lan so tru淡ng na淡o 単o湛 ma淡 chu湛ng ta 単a探 duye辰t qua 単旦担誰c he叩t chieu da淡i cu短a a xem nh旦 単a探 t狸m tha叩y a trong s va淡 gia短i thua辰t d旦淡ng. Cho i la淡 ch脱 so叩 cha誰y tre但n s va淡 j la淡 ch脱 so叩 cha誰y tre但n a, j luo但n 単旦担誰c ga湛n ve 0 khi ba辿t 単au mo辰t lan so tru淡ng. Khi ga谷p tha叩t ba誰i trong mo辰t lan so tru淡ng na淡o 単o湛 th狸 ca短 i va淡 j 単eu 単a探 tie叩n 単旦担誰c j b旦担湛c so v担湛i lu湛c ba辿t 単au so tru淡ng. Do 単o湛 単e奪短 ba辿t 単au so tru淡ng cho lan sau, i can lu淡i ve j-1 b旦担湛c.
10.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 84 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 s 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 H狸nh 5.2- Minh ho誰a gia短i thua辰t Brute-Force Tr旦担淡ng h担誰p xa叩u nha叩t cu短a gia短i thua辰t Brute-Force la淡 chuo達i con a tru淡ng v担湛i phan cuo叩i cu淡ng cu短a chuo達i s. Khi 単o湛 chu湛ng ta 単a探 pha短i la辰p la誰i lsla+1 lan so tru淡ng, v担湛i // Gia短i thua辰t Brute-Force int strstr(const String &s, const String &a); /* post: Ne叩u chuo達i a la淡 chuo達i con cu短a chuo達i s, ha淡m tra短 ve v嘆 tr鱈 xua叩t hie辰n 単au tie但n cu短a a trong s; ng旦担誰c la誰i, ha淡m tra短 ve -1. */ { int i = 0, // Ch脱 so叩 cha誰y tre但n s. j = 0, // Ch脱 so叩 cha誰y tre但n a. ls = s.strlen(); // So叩 ky湛 t旦誰 cu短a s. la = a.strlen(), // So叩 ky湛 t旦誰 cu短a a. const char* pa = a.c_str(); //嘆a ch脱 ky湛 t旦誰 単au tie但n cu短a a. const char* ps = s.c_str(); //嘆a ch脱 ky湛 t旦誰 単au tie但n cu短a s. do { if (pa[j] == ps[i]){ i++; j++; }; else { i = i (j 1); // Lu淡i ve cho lan so tru淡ng ke叩 tie叩p. j = 0; } } while ((j<la) && (i<ls)); if (j>=la) return i la; else return 1; }
11.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 85 ls va淡 la la淡 chieu da淡i cu短a chuo達i s va淡 chuo達i a. Mo達i lan so tru淡ng 単a探 pha短i so sa湛nh la ky湛 t旦誰. So叩 lan so sa湛nh to叩i 単a la淡 la*(ls-la+1) la*ls. 5.5.2. Gia短i thua辰t Knuth-Morris-Pratt Gia短i thua辰t na淡y do Knuth, Morris va淡 Pratt 単旦a ra, co淡n go誰i la淡 gia短i thua辰t KMP- Search. Trong v鱈 du誰 tre但n chu湛ng ta tha叩y gia短i thua辰t Brute-Force pha短i so tru淡ng 単e叩n lan th旦湛 11 m担湛i pha湛t hie辰n 単旦担誰c v嘆 tr鱈 can t狸m. Gia短i thua辰t KMP-Search d旦担湛i 単a但y tie叩t kie辰m 単旦担誰c mo辰t so叩 lan so tru淡ng va淡 ch脱 pha短i so tru淡ng 単e叩n lan th旦湛 5. H担n the叩 n旦探a, ch脱 so叩 i cha誰y tre但n s cu探ng kho但ng bao gi担淡 pha短i lu淡i la誰i. e奪 co湛 単旦担誰c 単ieu na淡y, chu湛ng ta ha探y co叩 ga辿ng ru湛t ra nha辰n xe湛t t旦淡 h狸nh 5.3 be但n d旦担湛i. Trong lan so tru淡ng th旦湛 nha叩t, khi i=4 th狸 aj si, khi 単o湛 a se探 単旦担誰c d嘆ch chuye奪n ve ph鱈a pha短i sao cho 単oa誰n 単au cu短a a tru淡ng kh担湛p v担湛i 単oa誰n cuo叩i cu短a a trong phan 単a探 単旦担誰c duye辰t qua (ch脱 t鱈nh phan ma淡u xa湛m). Trong h狸nh ve探 la淡 hai ky湛 t旦誰 1 va淡 0 co湛 ga誰ch d旦担湛i. Lan so tru淡ng ke叩 tie叩p ch鱈nh la淡 t旦淡 v嘆 tr鱈 na淡y, va淡 nh旦探ng lan so tru淡ng trung gian gi旦探a hai lan na淡y co湛 the奪 bo短 qua. ieu na淡y co湛 the奪 ly湛 gia短i nh旦 sau: ne叩u phan 単au cu短a a tru淡ng v担湛i phan cuo叩i cu短a a th狸 no湛 cu探ng tru淡ng v担湛i phan t旦担ng 旦湛ng cu短a s be但n tre但n, do phan cuo叩i cu短a a v旦淡a m担湛i 単旦担誰c so tru淡ng tha淡nh co但ng v担湛i phan t旦担ng 旦湛ng cu短a s. 旦担誰c nh旦 va辰y th狸 i m担湛i hoa淡n toa淡n kho但ng pha短i lu淡i la誰i. Trong lan so tru淡ng m担湛i, ch鱈nh si na淡y se探 単旦担誰c so sa湛nh v担湛i aj, v担湛i j se探 単旦担誰c t鱈nh toa湛n th鱈ch h担誰p ma淡 chu湛ng ta se探 ba淡n 単e叩n sau. Trong v鱈 du誰 chu湛ng ta tha叩y j = 2, lan so sa湛nh 単au tie但n cu短a lan so tru淡ng th旦湛 hai la淡 so sa湛nh gi旦探a s4 va淡 a2. T旦担ng t旦誰, khi lan so tru淡ng th旦湛 hai tha叩t ba誰i ta誰i s8, chuo達i con a se探 単旦担誰c d嘆ch chuye奪n ra叩t xa, tie叩t kie辰m 単旦担誰c ra叩t nhieu lan so tru淡ng. Chu湛ng ta de達 da淡ng kie奪m ch旦湛ng, v担湛i nh旦探ng v嘆 tr鱈 trung gian kha湛c, phan 単au cu短a a kho但ng tru淡ng v担湛i phan cuo叩i (ch脱 t鱈nh phan ma淡u xa湛m) cu短a a, ne但n cu探ng kho但ng the奪 tru淡ng v担湛i phan t旦担ng 旦湛ng tre但n s, co湛 th旦誰c hie辰n so tru淡ng cu探ng se探 tha叩t ba誰i ma淡 tho但i. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 s 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 H狸nh 5.3- Minh ho誰a gia短i thua辰t Knuth-Morris-Pratt Ba辿t 単au lan so tru淡ng th旦湛 hai (i = 4, j = 2) Ba辿t 単au lan so tru淡ng th旦湛 ba (i = 8, j = 1)
12.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 86 H狸nh ve探 d旦担湛i 単a但y giu湛p chu湛ng ta hie奪u 単旦担誰c ca湛ch t鱈nh ch脱 so叩 j th鱈ch h担誰p cho 単au mo達i lan so tru淡ng (trong khi i kho但ng lu淡i ve ma淡 gi旦探 nguye但n 単e奪 tie叩p tu誰c tie叩n t担湛i). Tr鱈ch t旦淡 h狸nh ve探 tre但n, chu湛ng ta co湛 単旦担誰c ke叩t qua短 sau 単a但y. Xe湛t v嘆 tr鱈 i = 4, j = 4, do so sa湛nh si v担湛i aj tha叩t ba誰i, chu湛ng ta 単ang muo叩n bie叩t phan cuo叩i cu短a a ke奪 t旦淡 単ie奪m na淡y tr担短 ve tr旦担湛c (t旦湛c ch脱 t鱈nh phan ma淡u xa湛m) va淡 phan 単au cu短a a tru淡ng 単旦担誰c bao nhie但u ky湛 t旦誰. Go誰i a = a. Chu湛ng ta se探 nh狸n que湛t t旦淡 cuo叩i phan ma淡u xa湛m cu短a a va淡 t旦淡 単au cu短a a, chu湛ng ta se探 bie叩t 単旦担誰c co湛 bao nhie但u ky湛 t旦誰 tru淡ng. o湛 la淡 hai ky湛 t旦誰 1 va淡 0 単旦担誰c ga誰ch d旦担湛i. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 s 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 Nh旦 va辰y, 単ieu na淡y hoa淡n toa淡n kho但ng co淡n phu誰 thuo辰c va淡o s n旦探a. Chu湛ng ta co湛 the奪 t鱈nh so叩 ky湛 t旦誰 tru淡ng theo j d旦誰a tre但n a va淡 a. ong th担淡i ta tha叩y so叩 ky湛 t旦誰 tru淡ng na淡y cu探ng la淡 ch脱 so叩 ma淡 j pha短i lu淡i ve cho lan so tru淡ng ke叩 tie叩p aj v担湛i si, i kho但ng 単o奪i. Chu湛ng ta ba辿t 単au v担湛i j = 1 va淡 xem h狸nh 5.4 sau 単a但y. j=4, so叩 ky湛 t旦誰 tru淡ng la淡 2 i
13.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 87 a 1 0 1 0 0 1 1 1 next1 = 0 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next2 = 0 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next3 = 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next4 = 2 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next5 = 0 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next6 = 1 a 1 0 1 0 0 1 1 1 a 1 0 1 0 0 1 1 1 next7 = 1 a 1 0 1 0 0 1 1 1 H狸nh 5.4- Minh ho誰a gia短i thua辰t Knuth-Morris-Pratt Gia短 s旦短 chu湛ng ta 単a探 ta誰o 単旦担誰c danh sa湛ch next ma淡 phan t旦短 th旦湛 j ch旦湛a tr嘆 ma淡 j pha短i lu淡i ve khi 単ang so sa湛nh aj v担湛i si ma淡 tha叩t ba誰i (aj si), 単e奪 ba辿t 単au lan so tru淡ng ke叩 tie叩p (i gi旦探 nguye但n kho但ng 単o奪i). H狸nh 5.4 cho tha叩y next1 luo但n ba竪ng 0 v担湛i mo誰i a. Chu湛ng ta co湛 gia短i thua辰t KMP-Search nh旦 d旦担湛i 単a但y. Lan so tru淡ng th旦湛 nha叩t luo但n ba辿t 単au t旦淡 ky湛 t旦誰 単au cu短a s va淡 a, ne但n hai ch脱 so叩 i va淡 j 単eu la淡 0. Tr旦担淡ng h担誰p de達 hie奪u nha叩t la淡 trong khi ma淡 aj=si th狸 i va淡 j 単eu 単旦担誰c nh鱈ch t担湛i. ieu kie辰n d旦淡ng cu短a vo淡ng la谷p hoa淡n toa淡n nh旦 gia短i thua辰t Brute-Force tre但n, co湛 ngh坦a la淡 j 単i 単旦担誰c he叩t chieu da淡i cu短a a (t狸m tha叩y a trong s), hoa谷c i 単i qua湛 chieu da淡i cu短a s (vie辰c t狸m ke叩t thu湛c tha叩t ba誰i). j=1, so叩 ky湛 t旦誰 tru淡ng la淡 0 (khi 単e叩m so叩 ky湛 t旦誰 tru淡ng, luo但n pha短i d嘆ch chuye奪n a sang pha短i so v担湛i a, t旦湛c ch脱 so sa湛nh phan cuo叩i cu短a a v担湛i phan 単au cu短a a, tr旦担淡ng h担誰p na淡y xem nh旦 kho但ng co湛 ky湛 t旦誰 tru淡ng). j=2, so叩 ky湛 t旦誰 tru淡ng la淡 0 j=3, so叩 ky湛 t旦誰 tru淡ng la淡 1 j=4, so叩 ky湛 t旦誰 tru淡ng la淡 2 j=5, so叩 ky湛 t旦誰 tru淡ng la淡 0 j=6, so叩 ky湛 t旦誰 tru淡ng la淡 1 j=7, so叩 ky湛 t旦誰 tru淡ng la淡 1
14.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 88 Tr旦担淡ng h担誰p ajsi (v担湛i j0) trong mo辰t lan so tru淡ng na淡o 単o湛 th狸 nh旦 単a探 no湛i 担短 tre但n, ch脱 vie辰c cho j lu淡i ve v嘆 tr鱈 単a探 単旦担誰c ch旦湛a trong phan t旦短 th旦湛 j trong danh sa湛ch next. Nh担淡 va辰y trong lan la谷p ke叩 tie叩p se探 tie叩p tu誰c so sa湛nh aj na淡y v担湛i si ma淡 i kho但ng 単o奪i. Rie但ng tr旦担淡ng h担誰p 単a谷c bie辰t, v担湛i j = 0 ma淡 ajsi, ta xem h狸nh d旦担湛i 単a但y s 1 1 0 0 1 0 0 1 1 1 0 1 1 a 1 0 1 0 0 1 1 1 Ba叩t c旦湛 mo辰t lan so sa湛nh si na淡o 単o湛 v担湛i a0 ma淡 tha叩t ba誰i th狸 chuo達i a cu探ng pha短i d嘆ch chuye奪n sang pha短i mo辰t b旦担湛c, 単e奪 lan so sa湛nh ke叩 tie叩p (cu探ng la淡 lan so tru淡ng m担湛i) co湛 the奪 so sa湛nh a0 v担湛i si+1. Nh旦 va辰y ta ch脱 can ta棚ng i va淡 gi旦探 nguye但n j ma淡 tho但i. j=0, so叩 ky湛 t旦誰 tru淡ng la淡 0 i // Gia短i thua辰t Knuth- Morris Pratt int strstr(const String &s, const String &a); /* post: Ne叩u a la淡 chuo達i con cu短a s, ha淡m tra短 ve v嘆 tr鱈 xua叩t hie辰n 単au tie但n cu短a a trong s; ng旦担誰c la誰i, ha淡m tra短 ve -1. */ { List<int> next; int i = 0, // Ch脱 so叩 cha誰y tre但n s. j = 0, // Ch脱 so叩 cha誰y tre但n a. ls = s.strlen(); // So叩 ky湛 t旦誰 cu短a s. la = a.strlen(), // So叩 ky湛 t旦誰 cu短a a. const char* pa = a.c_str(); //嘆a ch脱 ky湛 t旦誰 単au tie但n cu短a a. const char* ps = s.c_str(); //嘆a ch脱 ky湛 t旦誰 単au tie但n cu短a s. InitNext(a, next); // Kh担短i ga湛n ca湛c phan t旦短 next1, next2,,nextla-1. // Kho但ng s旦短 du誰ng next0. do { if (pa[j]==ps[i]){// Va達n co淡n ky湛 t旦誰 tru淡ng trong mo辰t lan so tru淡ng i++; // na淡o 単o湛, i va淡 j 単旦担誰c quyen nh鱈ch t担湛i. j++; } else if (j == 0) // a但y la淡 tr旦担淡ng h担誰p 単a谷c bie辰t, pha短i d嘆ch a sang pha短i i++; // mo辰t b旦担湛c, co湛 ngh坦a la淡 cho i nh鱈ch t担湛i. else next.retrieve(j, j); // Cho j lu淡i ve tr嘆 単a探 ch旦湛a trong nextj. } while ((j<la) && (i<ls)); if (j>=la) return i la; else return 1; }
15.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 89 Sau 単a但y chu湛ng ta se探 vie叩t ha淡m InitNext ga湛n ca湛c tr嘆 cho ca湛c phan t旦短 cu短a next, t旦湛c la淡 t狸m so叩 phan t旦短 tru淡ng theo h狸nh ve探 5.4. Co湛 mo辰t 単ieu kha湛 thu湛 v嘆 trong gia短i thua辰t na淡y, 単o湛 ch鱈nh la淡 ha淡m ta誰o danh sa湛ch next la誰i s旦短 du誰ng ngay ch鱈nh danh sa湛ch na淡y. Chu湛ng ta tha叩y ra竪ng 単e奪 t狸m so叩 phan t旦短 tru淡ng nh旦 単a探 no湛i, chu湛ng ta can d嘆ch chuye奪n a ve be但n pha短i so v担湛i a, ma淡 vie辰c d嘆ch chuye奪n a tre但n a cu探ng hoa淡n toa淡n gio叩ng nh旦 vie辰c d嘆ch chuye奪n a tre但n s trong khi 単i t狸m a trong s. Ha淡m ta誰o next 単旦担誰c che湛p la誰i t旦淡 gia短i thua辰t KMP-Search tre但n, ch脱 co湛 va淡i 単ie奪m bo奪 sung nh旦 sau: v担湛i i cha誰y tre但n a va淡 j cha誰y tre但n a, va淡 a luo但n pha短i d嘆ch pha短i so v担湛i a, chu湛ng ta kh担短i ga湛n i=1 va淡 j=0. Do i ta棚ng 単e叩n 単a但u la淡 chu湛ng ta xem nh旦 単a探 so tru淡ng xong phan cuo叩i cu短a a (ke奪 t旦淡 v嘆 tr鱈 i na淡y tr担短 ve tr旦担湛c) v担湛i phan 単au cu短a a, ne但n nexti 単a探 単旦担誰c xa湛c 単嘆nh. Trong qua湛 tr狸nh so tru淡ng, trong khi ma淡 ai va達n co淡n ba竪ng aj, i va淡 j 単eu nh鱈ch t担湛i. V狸 va辰y, chu湛ng ta de達 tha叩y ra竪ng j ch鱈nh la淡 so叩 phan t旦短 単a探 tru淡ng 単旦担誰c cu短a a so v担湛i a, chu湛ng ta co湛 phe湛p ga湛n nexti=j. // Ha淡m phu誰 tr担誰 ga湛n ca湛c phan t旦短 cho danh sa湛ch next. void InitNext(const String &a, List<int> &next); /* post: Ga湛n ca湛c tr嘆 cho ca湛c phan t旦短 cu短a next d旦誰a tre但n chuo達i ky湛 t旦誰 a. */ { int i = 1, // Ch脱 so叩 cha誰y tre但n a. j = 0, // Ch脱 so叩 cha誰y tre但n a. la = a.strlen(), // So叩 ky湛 t旦誰 cu短a a (cu探ng la淡 cu短a a). const char* pa = a.c_str(); //嘆a ch脱 ky湛 t旦誰 単au tie但n cu短a a (cu探ng la淡 cu短a a). next.clear(); next.insert(1, 0); // Luo但n 単u湛ng v担湛i mo誰i a. do { if (pa[j]==pa[i]){ // Va達n co淡n ky湛 t旦誰 tru淡ng trong mo辰t lan so tru淡ng i++; // na淡o 単o湛, i va淡 j 単旦担誰c quyen nh鱈ch t担湛i. j++; // T旦淡 v嘆 tr鱈 i tre但n a tr担短 ve tr旦担湛c, j xem nh旦 単a探 next.insert(i, j);// que湛t 単旦担誰c so叩 phan t旦短 tru淡ng cu短a a so v担湛i a. } else if (j == 0){ // Tr旦担淡ng h担誰p 単a谷c bie辰t, pha短i d嘆ch a sang pha短i i++; // mo辰t b旦担湛c, co湛 ngh坦a la淡 cho i nh鱈ch t担湛i. next.insert(i, j); }; else next.retrieve(j, j); // Cho j lu淡i ve tr嘆 単a探 ch旦湛a trong nextj. } while (i<la); // i=la la淡 単a探 ga湛n xong la phan t旦短 cu短a next, // kho但ng s旦短 du誰ng next0. }
16.
Ch旦担ng 5
Chuo達i ky湛 t旦誰 Gia湛o tr狸nh Ca叩u tru湛c d旦探 lie辰u va淡 Gia短i thua辰t 90 Khi ai aj, chu湛ng ta s旦短 du誰ng y湛 t旦担短ng cu短a KMP-Search la淡 cho j lu淡i ve nextj. Va叩n 単e co淡n la誰i can kie奪m ch旦湛ng la淡 gia湛 tr嘆 cu短a nextj pha短i co湛 tr旦担湛c khi no湛 単旦担誰c s旦短 du誰ng. Do chu湛ng ta 単a探 ga湛n va淡o nexti va淡 単a探 s旦短 du誰ng nextj, ma淡 i luo但n luo但n 単i tr旦担湛c j, ne但n chu湛ng ta hoa淡n toa淡n ye但n ta但m ve 単ieu na淡y. Cuo叩i cu淡ng, ch脱 co淡n mo辰t 単ieu nho短 ma淡 chu湛ng ta can xem xe湛t. o湛 la淡 tr旦担淡ng h担誰p co湛 nhieu ph旦担g a湛n cho so叩 ky湛 t旦誰 tru淡ng nhau. Cha炭ng ha誰n v担湛i a la淡 10101010111 va淡 j=8, so叩 ky湛 t旦誰 tru淡ng khi d嘆ch a=a ve be但n pha短i so v担湛i a la淡: a 1 0101010111... So叩 ky湛 t旦誰 tru淡ng la淡 6 a 10101 010111... a 1 0101010111... a 10101010111... So叩 ky湛 t旦誰 tru淡ng la淡 4 a 1 010101 0111... a 10101010111... So叩 ky湛 t旦誰 tru淡ng la淡 2 Sinh vie但n ha探y t旦誰 suy ngh坦 xem ca湛ch cho誰n ph旦担ng a湛n na淡o la淡 単u湛ng 単a辿n nha叩t va淡 kie奪m tra la誰i ca湛c 単oa誰n ch旦担ng tr狸nh tre但n xem chu湛ng co湛 can pha短i 単旦担誰c s旦短a 単o奪i g狸 hay kho但ng. Ngoa淡i ra, gia短i thua辰t KMP-Search co淡n co湛 the奪 ca短i tie叩n mo辰t 単ie奪m nho短, 単o湛 la淡 tr旦担湛c khi ga湛n nexti=j trong InitNext, chu湛ng ta kie奪m tra ne叩u paj=pai th狸 se探 ga湛n nexti=nextj. Do khi so tru淡ng pai ma淡 tha叩t ba誰i th狸 co湛 lu淡i ve panexti=paj cu探ng se探 tha叩t ba誰i, chu湛ng ta ne但n lu淡i ha炭n ve panextj. So叩 lan so sa湛nh to叩i 単a trong KMP-Search la淡 ls+la. V嘆 tr鱈 j 単ang xe湛t
Download