2 단어별로읽어들이기 WORDTREE 2 2. 단어별로읽어들이기. 먼저입력스트림으로부터단어를선별하는함수부터작성하겠습니다. getword ( ) 함수는주어진입력을단어별로다루기위해서, 입력스트림으로부터단어를빼내는함수입니다. 여기서단어란글자 (letter) 로시작하면서글자와

Size: px

Start display at page:

Download "2 단어별로읽어들이기 WORDTREE 2 2. 단어별로읽어들이기. 먼저입력스트림으로부터단어를선별하는함수부터작성하겠습니다. getword ( ) 함수는주어진입력을단어별로다루기위해서, 입력스트림으로부터단어를빼내는함수입니다. 여기서단어란글자 (letter) 로시작하면서글자와"

광록 한
6 years ago
Views:

1 1. 단어출현횟수출력. 이프로그램은 The C Programming Language 책의 6.5 절 Self-referntial Structures 의첫번째예제프로그램을교육을목적으로자세한설명을곁들여 CWEB 으로다시작성한것으로파일을입력으로받아서그파일에있는모든단어의출현횟수를출력하는프로그램입니다. 입력파일에어떠한단어들이들어있는지미리알수없기때문에단어들을알파벳순으로나열할수는없어 서파일을읽어나가는중간중간에단어들을알파벳순으로정렬하기위해서대표적인자료구조인이진트리를이용해서문제를해결합니다. 이프로그램은놀랄정도로짧으며, 전체적인모양새는다음과같습니다. #include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> #define MAXWORD 100 이진트리노드구조정의 6 전역선언 4 프로그램에사용되는함수 3 main ( ) struct tnode root ; / 단어를저장할이진트리 / char word [MAXWORD]; / 단어, 단어의최대길이는 MAXWORD / root = Λ; while (getword (word, MAXWORD) EOF) / 단어를읽어들여라 / if (isalpha (word [0])) root = addtree (root, word ); / 단어를트리에적절하게저장하라 / treeprint (root ); / 트리에저장된단어를횟수와함께출력하라 / return 0;

2 2 단어별로읽어들이기 WORDTREE 2 2. 단어별로읽어들이기. 먼저입력스트림으로부터단어를선별하는함수부터작성하겠습니다. getword ( ) 함수는주어진입력을단어별로다루기위해서, 입력스트림으로부터단어를빼내는함수입니다. 여기서단어란글자 (letter) 로시작하면서글자와숫자로이루어진문자열이거나한자짜리공백문자가아닌문자 (character) 입니다. 이함수의반환값은방금읽어들인단어의맨앞문자이거나파일의끝을나타내는 EOF 혹은단어가한 문자로이루어졌을때, 그한문자자체입니다. 3. 함수 getword ( ) 는다음과같습니다 : 위의마디에서정의했듯이, 글자로시작한다는단어의정의에따라서단어의첫문자가글자인지아닌지를확인하기위해서우선입력스트림으로부터문자한개를읽어들입니다. 즉단어의첫문자가글자이면, 단어정의를만족하므로계속해서그다음문자를읽어들일것이며, 아니면방금읽어들인문자를반환할것입니다. 이때읽어들인문자공백문자이면무시하고공백문자가아닐때까지문자한개씩계속읽어들입니다. 그러 다가공백문자가아닌문자를만났을때, 그문자가파일의끝을나타내는문자, EOF 인지확인을하고, 파일의끝이면 EOF 를반환하고, 아니면일단그문자를단어 word 에저장합니다. 그런데방금단어에저장한문자가 글자가아니면, 더이상입력을받아들이지않고, 방금읽어들인글자가아닌문자를반환하고, 다음단어를읽어들일준비를합니다. 프로그램에사용되는함수 3 int getword (char word, int lim ) int c, getch (void); void ungetch (int); char w = word ; while (isspace (c = getch ( ))) / 공백문자는모두건너뛰어라 / ; if (c EOF) / 파일의끝이아니면 / w++ = c; / 일단한문자를읽어들여서단어에저장하라 / if ( isalpha (c)) / 방금단어버퍼로읽어들인문자가글자가아니면 / w = \0 ; / 그문자를이함수의반환값으로하여반환하라 / return c; for ( ; lim > 0; w++) / 단어의첫문자가글자이면, 그다음글자를계속입력받아라 / if ( isalnum ( w = getch ( ))) / 후속문자가글자나숫자가아니면 / ungetch ( w); / 방금읽어들인문자를다시버퍼에집어넣어라 / break; / 한단어입력이끝났다 / w = \0 ; return word [0]; 5, 7, 9, 10 번마디도살펴보라. 이코드는 1 번마디에서사용된다.

3 4 WORDTREE 단어별로읽어들이기 3 4. 함수 getword ( ) 에서입력스트림으로부터한문자씩읽어들이기위해서, 함수 getch ( ) 와 ungetch ( ) 가사 용되었습니다. 이프로그램은내부적으로 buf 라는충분한길이의버퍼를가지고있습니다. #define BUFSIZE 100 전역선언 4 char buf [BUFSIZE]; / ungetch 함수를위한버퍼 / int bufp = 0; / buf 를스캔하기위한변수 / 8 번마디도살펴보라. 이코드는 1 번마디에서사용된다. 5. 함수 getch ( ) 는우선 buf 버퍼에문자가들어있으면, 그버퍼에서문자를가져오고, 그렇지않으면, 표준 입출력함수인 getchar ( ) 를이용해서입력스트림으로부터한문자씩읽어들입니다. buf 와같은버퍼가왜필요 한것일까요? getword ( ) 함수는입력스트림에서한문자씩읽어들이면서단어를결정합니다. 충분한길이의문자열을읽어들인후에그것이단어인지아니지를결정합니다. 즉주어진단어의길이보다한문자더읽어 들여야방금읽어들인문자를보고현재까지읽어들인문자들이단어를구성하는지아닌지를알수있습니다. 따라서필요보다한문자를더읽어들였으므로이더읽어들인문자를 buf 버퍼에저장해두었다가다음문자를 읽어들일때, 그버퍼에저장된문자부터읽어들입니다. 사용하는함수가바로 ungetch ( ) 입니다. 프로그램에사용되는함수 3 + int getch (void) return (bufp > 0)? buf [ bufp] : getchar ( ); void ungetch (int c) if (bufp BUFSIZE) printf ("ungetch: too many characters\n"); else buf [bufp ++] = c; 필요이상으로읽어들인문자를버퍼에저장할때

4 4 이진트리 WORDTREE 6 6. 이진트리. 지금까지입력스트림으로부터단어를만들어내는방법에대해서알았습니다. 이제부터는그 단어를저장하는이진트리의구조와이진트리에단어를저장하는방법을살펴보겠습니다. 트리의노드구조는다음과같습니다. 이진트리노드구조정의 6 struct tnode char word ; / 노드에저장되는단어를가리키는포인터 / int count ; / 노드에저장된단어의출현횟수 / struct tnode left ; / 왼쪽자식트리를가리킴 / struct tnode right ; / 오른쪽자식트리를가리킴 / ; 이코드는 1 번마디에서사용된다. 7. 함수 addtree ( ) 는읽어들인단어를트리에저장하는함수입니다. 이함수는트리를다루는대개의함수가그렇듯이재귀함수입니다. 새로들어오는단어가트리의루트에있는단어보다단어순으로작을때는왼쪽트 리에클때는오른쪽트리에저장합니다. 그러다가이미트리에있는단어일때는그단어노드의횟수를하나증가시킵니다. 이함수를잘보시면재귀함수의아름다움을느끼실수있습니다. 프로그램에사용되는함수 3 + struct tnode addtree (struct tnode p, char w) int cond ; if (p Λ) / 트리에없는새로운단어가들어왔을때 / p = talloc( ); / 단어를저장할새로운노드를만들어라 / p word = mystrdup(w); / 단어크기에해당하는공간을만들어라 / p count = 1; p left = p right = Λ; else if ((cond = strcmp(w, p word )) 0) / 단어를알파벳순으로비교 / p count ++; / 이미있는단어이면횟수를하나증가시켜라 / else if (cond < 0) p left = addtree (p left, w); / 왼쪽자식트리에저장하라 / else p right = addtree (p right, w); / 오른쪽자식트리에저장하라 / return p; 8. 단어를트리에저장하기위해서는그단어를포함하는트리노드를만들어야합니다. 노드를생성하는함수가 talloc( ) 이고, 트리에포함되는단어에해당하는공간을만드는함수가 mystrdup( ) 입니다. 이렇게생성된 단어는 p word 가가리키게됩니다. 전역선언 4 + struct tnode talloc(void); char mystrdup(char );

5 9 WORDTREE 이진트리 5 9. 프로그램에사용되는함수 3 + struct tnode talloc(void) return (struct tnode ) malloc(sizeof (struct tnode)); char mystrdup(char s) char p; p = (char ) malloc(strlen (s) + 1); if (p Λ) strcpy (p, s); return p; 10. 이제까지의과정으로파일의모든단어를단어의알파벳순위에맞게이진트리를구성하였습니다. 남은 것은이렇게완성된트리를순회하면서단어와그의출현횟수를출력하는것입니다. 함수 treeprint ( ) 가그일을하며, 이함수역시재귀함수이고, 트리의순회방법중에서 inorder 방법을택하고있습니다. 즉왼쪽 자식트리를방문하고, 자신의노드를방문하고마지막으로오른쪽자식트리를방문합니다. 이순회방법을택함으로써, 단어들을알파벳순으로나열할수있습니다. 프로그램에사용되는함수 3 + void treeprint (struct tnode p) if (p Λ) treeprint (p left ); printf ("%4d %s\n", p count, p word ); treeprint (p right );

6 6 프로그램실행 WORDTREE 프로그램실행. 명령행에서 gcc o wordtree wordtree.c 와같은명령으로, wordtree 라는실행 파일을만듭니다. 그리고 sample.txt 가다음과같은내용일때, Literate programming is a methodology that combines a programming language with a documentation language, thereby making programs more robust, more portable, more easily maintained, and arguably more fun to write than programs that are written only in a high-level language. The main idea is to treat a program as a piece of literature, addressed to human beings rather than to a computer. The program is also viewed as a hypertext document, rather like the World Wide Web. (Indeed, I used the word WEB for this purpose long before CERN grabbed it!) This book is an anthology of essays including my early papers on related topics such as structured programming, as well as the article in The Computer Journal that launched Literate Programming itself. The articles have been revised, extended, and brought up to date. 명령 cat sample.txt./wordtree 를실행하면, 아래와같은결과를얻습니다. 1 CERN 1 Computer 1 I 1 Indeed 1 Journal 2 Literate 1 Programming 4 The 1 This 1 WEB 1 Web 1 Wide 1 World 8 a 1 addressed 1 also 1 an 2 and 1 anthology 1 are 1 arguably 1 article 1 articles 5 as 1 been 1 before 1 beings 1 book 1 brought 1 combines 1 computer 1 date 1 document 1 documentation 1 early 1 easily 1 essays 1 extended 1 for 1 fun 1 grabbed 1 have 1 high 1 human 1 hypertext 1 idea 2 in...

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at