imported>Unknown at 05:29, 7 February 2021

2021-02-07T05:29:28Z

New page

{| class="wikitable"
|-
| __TOC__
|}
== Python version ==
* 개발자 : 나휘동
* 개발방식 : TestDrivenDevelopment
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)

== C++ version ==
=== [[황재선]] ===
* 불필요한 부분 리펙토링 하는 중
* 배열 변수 제거. string과 동적 할당 이용.
#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;
}
}
=== 나휘동 ===
* 파이선 코드를 바탕으로 짜려고 했으나, 완전히 다르게 되어버려 시간이 더 오래걸렸다.

#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;
}
----
[[몸짱프로젝트]]

몸짱프로젝트/CrossReference - Revision history

imported>Unknown at 05:29, 7 February 2021