1. Python version ¶
- 개발자 : 나휘동
- 개발방식 : TestDrivenDevelopment
~cpp import copy import string class CrossReference: ## def __init__(self, aRoot): ## self.root = aRoot ## def find(self, aRoot, aWord): ## if aRoot.getWord() == aWord: ## return True ## elif string.lower(aRoot.getWord()) > aWord and aRoot.left != None: ## return self.find(aRoot.left, aWord) ## elif string.lower(aRoot.getWord()) < aWord and aRoot.right != None: ## return self.find(aRoot.right, aWord) ## return False def getNode(self, aRoot, aWord): if aRoot.getWord() == '' or aRoot.getWord() == aWord: return aRoot if aRoot.left == None: aRoot.left = Node('') return aRoot.left elif string.lower(aRoot.getWord()) > aWord: return self.getNode(aRoot.left, aWord) if aRoot.right == None: aRoot.right = Node('') return aRoot.right elif string.lower(aRoot.getWord()) < aWord: return self.getNode(aRoot.right, aWord) def setNode(self, aRoot, aWord, aLine = '1'): node = self.getNode(aRoot, aWord) if node == None: node = Node(aWord) else: node.setWord(aWord) node.increaseCount() node.addLines(aLine) def run(self): sentence =\ '''Twas brilling and the slithy toves did gtre and gimble in the wabe''' wordList = sentence.split(' ') root = Node('') for l in wordList: self.setNode(root, l) print 'Word\t\tCount\t\tLines' self.inorder(root) def inorder(self, aRoot): ## print 'start' if aRoot.left != None: ## print 'left' self.inorder(aRoot.left) if aRoot.word != '': ## print 'root' aRoot.show() if aRoot.right != None: ## print 'right' self.inorder(aRoot.right) class Node: def __init__(self, aWord = ''): self.setWord(aWord) self.left = None self.right = None self.count = 0 self.lines = '' def setWord(self, aWord): self.word = aWord def increaseCount(self): self.count += 1 def addLines(self, aLine): self.lines += aLine + ' ' def setLeftChild(self, aWord): self.left = Node(aWord) def setRightChild(self, aWord): self.right = Node(aWord) def getWord(self): return self.word def show(self): print self.getWord() + '\t\t' + str(self.count) + '\t\t' + self.lines ######################################################################### import unittest class CrossReferenceTestCase(unittest.TestCase): ## def testFind(self): ## t = Node('') ## t.setWord('Twas') ## t.setLeftChild('brilling') ## t.setRightChild('wabe') ## ## c = CrossReference() ## self.assertEqual(c.find(t, 'Twas'), True) ## self.assertEqual(c.find(t, 'brilling'), True) ## self.assertEqual(c.find(t, 'wabe'), True) ## self.assertEqual(c.find(t, 'and'), False) ## ## t.left.setLeftChild('and') ## self.assertEqual(c.find(t, 'and'), True) def testGetNode(self): t = Node() t.setWord('Twas') t.setLeftChild('brilling') t.setRightChild('wabe') c = CrossReference() self.assertEqual(c.getNode(t, 'Twas').getWord(), 'Twas') self.assertEqual(c.getNode(t, 'brilling').getWord(), 'brilling') self.assertEqual(c.getNode(t, 'wabe').getWord(), 'wabe') self.assertEqual(c.getNode(t, 'and').getWord(), '') t.left.setLeftChild('and') self.assertEqual(c.getNode(t, 'and').getWord(), 'and') def testSetNode(self): t = Node() c = CrossReference() c.setNode(t, 'Twas') self.assertEqual(c.getNode(t, 'Twas').getWord(), 'Twas') c.setNode(t, 'brilling') self.assertEqual(c.getNode(t, 'brilling').getWord(), 'brilling') c.setNode(t, 'wabe') self.assertEqual(c.getNode(t, 'wabe').getWord(), 'wabe') c.setNode(t, 'and') self.assertEqual(c.getNode(t, 'and').getWord(), 'and') self.assertEqual(c.getNode(t, 'and').count, 1) self.assertEqual(c.getNode(t, 'and').lines, '1 ') if __name__ == '__main__': unittest.main() c = CrossReference() c.run() ## t = Node() ## c = CrossReference() ## c.setNode(t, 'Twas') ## c.setNode(t, 'brilling') ## c.setNode(t, 'wabe') ## c.setNode(t, 'and') ## ## c.inorder(t)
2.1. 황재선 ¶
- 불필요한 부분 리펙토링 하는 중
- 배열 변수 제거. string과 동적 할당 이용.
~cpp #include <fstream> #include <iostream> #include <string> using namespace std; struct Line { int row; Line * next; }; struct Node { Node * left; string word; int wordCount; Line * line; Node * right; }; void makeRootNode(Node * aRoot, string aWord); void initNode(Node * aNewNode); Node * setNode(Node * ptr, string aWord, int aLineCount); void insertToNode(Node * ptr, string aWord, int aLineCount); void duplicatedWord(Node * ptr, string aWord, int aLineCount); void inorder(Node * aRoot); void printResult(Node * aRoot); void freeMem(Node * aRoot); int count = 0; int main() { Node * root = new Node; ifstream fin("lincoln.txt"); char word[150]; char split[] = " ,.;-"; char * p; int lineCount = 1; int start = true; while(!fin.eof()) { fin.getline(word, 150, '\n'); if(!strcmp(word, "")) continue; strlwr(word); p = strtok(word, split); strcpy(word, p); if (start) { makeRootNode(root, word); start = false; } else insertToNode(root, word, lineCount); while(p != NULL) { p = strtok(NULL, split); if (p) { strcpy(word, p); insertToNode(root, word, lineCount); } } lineCount++; } cout << "WORD\t\tCOUNT\t\tLINES" << endl; inorder(root); cout << "TOTAL\t\t" << count << endl; freeMem(root); fin.close(); return 0; } void insertToNode(Node * ptr, string aWord, int aLineCount) { bool isDuplicated = false; while(true) { if (ptr->word == aWord) { duplicatedWord(ptr, aWord, aLineCount); isDuplicated = true; break; } else if (ptr->word > aWord) { if (ptr->left != NULL) ptr = ptr->left; else break; } else if (ptr->word < aWord) { if (ptr->right != NULL) ptr = ptr->right; else break; } } if (!isDuplicated) { if (aWord < ptr->word) ptr->left = setNode(ptr, aWord, aLineCount); else if (aWord > ptr->word) ptr->right = setNode(ptr, aWord, aLineCount); } } void initNode(Node * aNewNode) { aNewNode->left = NULL; aNewNode->word = ""; aNewNode->wordCount = 0; Line * lp = new Line(); lp->row = 0; lp->next = NULL; aNewNode->line = lp; aNewNode->right = NULL; } void makeRootNode(Node * aRoot, string aWord) { initNode(aRoot); aRoot->word = aWord; aRoot->wordCount++; aRoot->line->row = 1; } Node * setNode(Node * ptr, string aWord, int aLineCount) { Node * newNode = new Node; initNode(newNode); newNode->word = aWord; newNode->wordCount++; newNode->line->row = aLineCount; return newNode; } void duplicatedWord(Node * ptr, string aWord, int aLineCount) { ptr->wordCount++; Line * temp = ptr->line; while (temp->next != NULL) temp = temp->next; Line * lp = new Line(); lp->row = aLineCount; lp->next = NULL; temp->next = lp; } void inorder(Node * aRoot) { if(aRoot) { inorder(aRoot->left); printResult(aRoot); inorder(aRoot->right); } } void printResult(Node * aRoot) { count++; cout.setf(ios_base::left, ios_base::adjustfield); cout.width(18); cout << aRoot->word; cout << aRoot->wordCount << "\t\t"; cout.width(3); while (aRoot->line->next != NULL) { cout.width(3); cout << aRoot->line->row; aRoot->line = aRoot->line->next; } cout.width(3); cout << aRoot->line->row; cout << "\n"; } void freeMem(Node * aRoot) { if (aRoot) { freeMem(aRoot->left); freeMem(aRoot->right); Line * temp = aRoot->line; while (temp->next != NULL) { temp = aRoot->line->next; delete aRoot->line; aRoot->line = temp; } delete aRoot->line; delete aRoot; } }
2.2. 나휘동 ¶
- 파이선 코드를 바탕으로 짜려고 했으나, 완전히 다르게 되어버려 시간이 더 오래걸렸다.
~cpp #include <iostream> #include <fstream> #include <cctype> #include <string> using namespace std; // Binary Tree를 구성하는 노드 #define Node_ptr struct Node * struct Node{ string word;// 노드에 들어있는 값 int count; string lines; Node_ptr left;// Left Child Node_ptr right;// Right Child }; ///////////////////////////////////////////////////// // Cross Reference를 작성하기 위한 함수 string toString(int aNum); Node_ptr * getNode( Node_ptr * aRoot, char aWord[]); void setNode( Node_ptr * aRoot, char aWord[], int aLine = 1); void show(ostream & aOs, Node_ptr aNode); void inorderTravel(ostream & aOs, Node_ptr aRoot); void showAll(ostream & aOs, Node_ptr aRoot); void deleteAllNode( Node_ptr aRoot ); ///////////////////////////////////////////////////// int num_of_node = 0; void main() { int line = 1; const int MAX_LEN = 20; char word[MAX_LEN]; Node_ptr root = NULL; ifstream fin("lincoln.txt"); char ch = fin.get(); while(!fin.eof()){ while ( ch == '\n' ){ line++; do ch = fin.get(); while ( ch == '\n' ); } if ( isalpha(ch) ){ for ( int i = 0 ; isalpha(ch) ; i++){ word[i] = (char)tolower(ch); ch = fin.get(); } word[i] = '\0'; setNode(&root, word, line); } else if ( isspace(ch) || ispunct(ch) == 16) // 공백이거나 ch = fin.get();// 알파벳이 아닌 문자일 경우 } fin.close(); //ofstream fout("result.txt", ios::app); // result.txt 라는 파일에 출력하는 경우 //showAll(fout, root); //fout.close(); showAll(cout, root); deleteAllNode(root); } Node_ptr * getNode( Node_ptr * aRoot, char aWord[]) { if ((*aRoot) == NULL || (*aRoot)->word == aWord ) return aRoot; // 루트에 있는 단어보다 새로 들어온 단어가 작으면 // 왼쪽 서브트리와 다시 비교한다. else if ( (*aRoot)->word > aWord) return getNode(&(*aRoot)->left, aWord); // 루트에 있는 단어보다 새로 들어온 단어가 크면 // 오른쪽 서브트리와 다시 비교한다. else if ( (*aRoot)->word < aWord ) return getNode(&(*aRoot)->right, aWord); return aRoot; } void setNode( Node_ptr * aRoot, char aWord[], int aLine ) { // 단어를 집어넣을 노드를 가져온다. Node_ptr * node = getNode(aRoot, aWord); if ((*node) == NULL){// 빈 노드일 경우 (*node) = new Node;// 노드를 새로 만들고 (*node)->left = NULL;// child 노드를 NULL로 초기화한다. (*node)->right = NULL; (*node)->word = aWord;// 노드에 값을 넣는다. (*node)->count = 1; (*node)->lines = toString(aLine); } else{ (*node)->count++; (*node)->lines += " "; (*node)->lines += toString(aLine); } } void inorderTravel(ostream & aOs, Node_ptr aRoot) { if ( aRoot->left != NULL ) inorderTravel(aOs, aRoot->left); if ( aRoot->count != 0 ){ show(aOs, aRoot); num_of_node++; } if ( aRoot->right != NULL ) inorderTravel(aOs, aRoot->right); } void show(ostream & aOs, Node_ptr aNode) { aOs << aNode->word << "\t\t"; if ( aNode->word.size() < 8)// 결과를 보기 좋게 탭 개수 조절 aOs << "\t"; if ( aNode->word.size() < 4) aOs << "\t"; aOs << aNode->count << "\t\t" << aNode->lines << endl; } void deleteAllNode( Node_ptr aRoot ) { if ( aRoot->left != NULL ) deleteAllNode( aRoot->left ); if ( aRoot->right != NULL ) deleteAllNode( aRoot->right ); delete aRoot; } string toString(int aNum) // 줄수를 string 객체로 바꾸는 함수 { char * temp; if ( aNum / 1000 != 0 ){ temp = new char[5]; temp[0] = aNum / 1000 + 48; temp[1] = aNum % 1000 / 100 + 48; temp[2] = aNum % 100 / 10 + 48; temp[3] = aNum % 10 + 48; temp[4] = '\0'; } else if ( aNum / 100 != 0 ){ temp = new char[4]; temp[0] = aNum / 100 + 48; temp[1] = aNum % 100 / 10 + 48; temp[2] = aNum % 10 + 48; temp[3] = '\0'; } else if ( aNum / 10 != 0 ){ temp = new char[3]; temp[0] = aNum / 10 + 48; temp[1] = aNum % 10 + 48; temp[2] = '\0'; } else if ( aNum > 0 ){ temp = new char[2]; temp[0] = aNum + 48; temp[1] = '\0'; } string number(temp); delete temp; return number; } void showAll(ostream & aOs, Node_ptr aRoot) { aOs << "WORD" << "\t\t\t" << "COUNT" << "\t\t" << "LINES" << endl << "--------------------------------------" << endl; inorderTravel(aOs, aRoot); aOs << "--------------------------------------" << endl << "TOTAL" << "\t\t" << num_of_node++ << endl; }