Appendix.ppt

1、L,L -1,Appendix,C / C+ / Java Library,L,L -2,Containers in Java,L,L -3,ArrayList,L,L -4,Example:public static void main(String args) Scanner cin = new Scanner(System.in);ArrayList list = new ArrayList();int x;while (x = cin.nextInt() != 0) list.add(x);System.out.println(“total “ + list.size() + “ in

2、put elements.“);System.out.println(list.toString();System.out.println(“2nd element = “ + list.get(2); ,ArrayList,3 5 7 1 0total 4 input elements. 3, 5, 7, 1 2nd element = 7,L,L -5,LinkedList,L,L -6,Set (TreeSet, HashSet)TreeSet can output a sorted iterator. O(log n)-time operators,L,L -7,Example:pub

3、lic static void main(String args) Scanner cin = new Scanner(System.in);Set s = new TreeSet();while (cin.hasNextInt() s.add(cin.nextInt();for (Iterator iter = s.iterator(); iter.hasNext();) System.out.print(iter.next() + “ “);System.out.println();System.out.println(s.toString();System.out.println(s.c

4、ontains(0); ,TreeSet,Input 3 5 7 1Output 1 3 5 7 1, 3, 5, 7 false,L,L -8,Map (TreeMap, HashMap)TreeMap can output a sorted iterator on key set. O(log n)-time operators,L,L -9,Example:public static void main(String args) Map map = new TreeMap();for (int i = 0; i iter = map.keySet().iterator(); iter.h

5、asNext();) String key = iter.next();System.out.println(key + “ - “ + map.get(key); ,TreeMap,C:myjavajava TestMap John Tom Mary Andy Andy - 3 John - 0 Mary - 2 Tom - 1,L,L -10,Containers in C+,Compare of Java and C+:,L,L -11,Example:vector v;int x;while (cin x)v.push_back(x);cout “total “ v.size() “

6、input elements.“ endl;reverse(v.begin(), v.end();for (int i = 0; i v.size(); i+)cout vi “, “;,#include ,3 5 7 1 0total 5 input elements. 0, 1, 7, 5, 3,L,L -12,Example:set s;s.insert(“xyz“);s.insert(“def“);s.insert(“abc“);s.insert(“bbb“);s.insert(“bbb“);set:iterator iter; for( iter = s.begin(); iter

7、!= s.end(); iter+ ) cout *iter endl;cout s.count(“aaa“) endl;cout s.count(“bbb“) endl;,#include ,abc bbb def xyz 0 1,L,L -13,Example:map stringCounts;string str; while (cin str) stringCountsstr+;map:iterator iter; for( iter = stringCounts.begin(); iter != stringCounts.end(); iter+ ) cout first secon

8、d endl;,#include ,here are some words and here are some more wordsand=1 are=2 here=2 more=1 some=2 words=2,L,L -14,Sorting / Searching in C,void qsort(void *base, size_t num, size_t width, _cdecl *compare); void *bsearch(void *key, void *base, size_t nelem, size_t size, _cdecl *compare);Prepare a co

9、mpare functionint compare (const void * elem1, const void * elem2 );,L,L -15,Example:int compare(const void *arg1, const void *arg2 ) char *a = (char *)arg1;char *b = (char *)arg2;return _strcmpi(*a, *b); int main( int argc, char *argv ) char *result;char *key = “DOG“;int i;qsort(argv, argc, sizeof(

10、char *), compare);for( i = 0; i argc; +i ) /* Output sorted list */printf( “%s “, argvi );result = bsearch( ,C:workmytest DOG PIG HORSE CAT HUMAN RAT COW GOAT CAT COW DOG GOAT HORSE HUMAN PIG RAT mytest DOG found at 003D2530 (2),L,L -16,Sorting / Searching in C+,Can be applied on both arrays and STL

11、 vectorstemplatevoid sort(RanIt first, RanIt last); templatevoid sort(RanIt first, RanIt last, Pr pred);templatebool binary_search(FwdIt first, FwdIt last, const Ty,L,L -17,Example:#include #include #include #include using namespace std;int main() int ia = 29,23,20,22,17,15,26,51,19,12,35,40; vector

12、 vec(ia, ia+12);sort( ,12 15 17 19 20 22 23 26 29 35 40 51 51 40 35 29 26 23 22 20 19 17 15 12 binary_search(): success!,L,L -18,Sorting / Searching in Java,Example:int arr1 = 5, 7, 1, 3, 9;Arrays.sort(arr1);System.out.println(Arrays.toString(arr1);System.out.printf(“index of %d is %dn“, 3, Arrays.b

13、inarySearch(arr1, 3);System.out.printf(“index of %d is %dn“, 4, Arrays.binarySearch(arr1, 4);,1, 3, 5, 7, 9 index of 3 is 1 index of 4 is -3 / -(-3 + 1) = 2,L,L -19,Example:String arr1 = “ABCD“, “BADC“, “DCBA“, “ADCB“; System.out.println(Arrays.toString(arr1);Arrays.sort(arr1); System.out.println(Ar

14、rays.toString(arr1);System.out.printf(“index of %s is %dn“, “BADC“, Arrays.binarySearch(arr1, “BADC“);Collections.reverse(Arrays.asList(arr1); System.out.println(Arrays.toString(arr1);System.out.printf(“index of %s is %dn“, “BADC“, Arrays.binarySearch(arr1, “BADC“);,ABCD, BADC, DCBA, ADCB ABCD, ADCB

15、, BADC, DCBA index of BADC is 2 DCBA, BADC, ADCB, ABCD index of BADC is 1,L,L -20,Example (10905):public static void main(String args) String data = “123“, “56“, “90“, “124“, “9“Arrays.sort(data, new Cmp();System.out.println(Arrays.toString(arr1); public static class Cmp implements Comparator public

16、 int compare(String s1, String s2) String new_s1 = s1 + s2;String new_s2 = s2 + s1;return - new_pareTo(new_s2); ,9 90 56 124 123,L,L -21,Very Big Integer (Java),L,L -22,Example:static BigInteger factorial(int n) BigInteger result = BigInteger.valueOf(1);for (int i = 2; i = n; i+) result = result.mul

17、tiply(BigInteger.valueOf(i);return result; public static void main(String args) System.out.printf(“%d! = %sn“, 100, factorial(100).toString(); ,100! = 93326215443944152681699238856266700490715968264381621468592963895217 599993229915608941463976156518286253697920827223758251185210916864000000000 0000

18、00000000000,L,L -23,Permutation in C+,#include bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare); bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare);,L,L -24,#include #include using namespace std;bool nameCompare(char * a, ch

19、ar * b) return strcmp(a, b) (cout, “ “), cout (cout, “ “), cout endl;while (next_permutation(words, words + 3, nameCompare); ,1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Alpha Beta Gamma Alpha Gamma Beta Beta Alpha Gamma Beta Gamma Alpha Gamma Alpha Beta Gamma Beta Alpha,L,L -25,#include #include #include u

20、sing namespace std;void main () vector word(4);word0 = b; word1 = e; word2 = l; word3 = a; docopy( word.begin(), word.end(), out_stream ), cout endl;while (prev_permutation(word.begin(), word.end();cout endl; ,b e l a b e a l b a l e b a e l a l e b a l b e a e l b a e b l a b l e a b e l,L,L -26,De

21、bug (C / C+ / Java),Assertion: Things that all team members should know and obey. Bugs made by inattention or stupid team members.,Example:int factorial(int n) int result = 1;for (int i = 2; i = n; i+) result = result * i;return result; ,(-3)! = ? 13! will overflow!,L,L -27,-1 means error occursint

22、factorial(int n) / 13! will overflowif (n = 0 ,Using assertion#include int factorial(int n) / 13! will overflowassert(n = 0 ,Assertion failed: n = 0 & n = 12, file C:test.cpp, line 11This application has requested the Runtime to terminate it in an unusual way. Please contact the applications support

23、 team for more information.,L,L -28,String (char) Number (C / C+),Example (C):char *s1 = “12345“; char s26;int n = atoi(s1); sscanf(s1, “%d“, ,Example (C+):string s1 = “12345“; char s26;int n = atoi(s1.c_str();itoa(n, s2, 10); s1 = s2; / string - char *,L,L -29,String Number (Java),Example:String s1

24、 = “123.45“; String s2;double n = Double.parseDouble(s1); s2 = String.valueOf(n);,L,L -30,I/O in C+,Example (good input):5 123 215 864 365 754 4 657 624 987 456 0,下列的輸入格式1. Test case 的數量未定 2. Test case 第一個為 N 3. 後面接著 N 個 integer (中間可任意換行) 4. 讀到 N=0 時結束N a1 a2 a3 aN,Example (bad input):5 123 215 864

25、365 754 4 657 624 987 456 0,L,L -31,Example:int N; int dataMAX; / view as integerwhile (cin N) for (int i = 0; i datai; ,Example:int N; string dataMAX; / view as stringwhile (cin N) for (int i = 0; i datai; ,L,L -32,Example:char name1256; string name2;cout d; cout fixd setprecision(3) setw(10) d; pr

26、intf(“%10.3f“, d);,L,L -33,String Manipulation in C,Example:#include #include void main() char s100 = “Hello!“;strcat(s, “ World!“);printf(“%s“, s); ,strcat : Append a string.#include char *strcat( char *strDestination, const char *strSource );,Hello! World!,L,L -34,Example:#include #include void ma

27、in() char *s = “This is a sample!“;char *p1 = strchr(s, s);char *p2 = strchr(p1 + 1, s);printf(“%sn%sn%s“, s, p1, p2); ,strchr : Find a character in a string.#include char *strchr( const char *string, int c );,This is a sample! s is a sample! s a sample!,L,L -35,Example:void main() char *s1 = “This

28、is a sample“;char *s2 = “This is another sample“;int result = strcmp(s1, s2);if (result 0)printf(“s1 s2“); ,strcmp : Compare strings.#include int strcmp( const char *string1, const char *string2 );,s1 s2,L,L -36,Example:#include #include void main() char s180 = “This is a sample“;char s280;strcpy(s2

29、, s1);printf(“s1 = %sns2 = %s“, s1, s2); ,strcpy : Copy a string.#include char *strcpy( char *strDestination, const char *strSource );,s1 = This is a sample s2 = This is a sample,L,L -37,Example:#include #include void main() char s180 = “This is a sample“;int len = strlen(s1);printf(“s1 = %snlength

30、of s1 = %d“, s1, len); ,strlen : Get the length of a string.#include size_t strlen( const char *string );,s1 = This is a sample length of s1 = 16,L,L -38,Example:#include #include void main() char *s = “This is a sample“;char *sub = “is a“;char *alt = “The“;char *sp = strstr(s, sub);char *ap = strst

31、r(s, alt);printf(“find %s : %sn“, sub, sp);printf(“find %s : %sn“, alt, ap); ,strstr : Find a substring.#include char *strstr( const char *string, const char *strCharSet );,find is a : is a sample find The : (null),L,L -39,Example:#include #include void main() char *s = “Thistis a sample“;char *toke

32、n;token = strtok(s, “ t“);while (token != NULL)printf(“%sn“, token);token = strtok(NULL, “ t“); ,strtok : Find the next token in a string.#include char *strtok( char *strToken, const char *strDelimit );,This is a sample,L,L -40,String Manipulation in C+,Compare of C and C+:,L,L -41,Example:#include

33、#include using namespace std;void main() string text, word;text = “This is a sample“;word = “very good “;text.insert(10,word,5,5);couttextendl; ,insert : insert a substring into a string.#include using namespace std; basic_string,This is a good sample,L,L -42,Example:#include #include using namespace std;void main() string text;text=“abcdefghi“;text.erase(4,3);couttextendl; ,erase : Remove some chars from a string.#include using namespace std; basic_string,abcdhi,