[Binny's P1] Slang Filtering Project_단순 연결 리스트

***************************************************************************
문장을 입력하면 욕을 필터링하여 '*'로 출력되게 한다.
구현이 끝나면, 이 작업을 1만번, 10만번, 100만번 재실행하도록 반복문 안에 구현한다.

욕 데이터 파일은 해당 폴더의 data.txt 파일이다.

이 파일을 로딩해서 Linked list에 모두 저장하고, 위의 예와 같이 문자열을 입력한 후 엔터를 입력하면 data.txt에 등록되어 있는 단어들(가고거구, 하호버무, 등)이 모두 '*'로 Filtering된다. 마지막 줄에는 측정 시간을 잰다.

***************************************************************************

1. 필요한 자료구조를 위한 준비

단순 연결 리스트 구현 방법을 생각해본다. 단순 연결 리스트를 구현하기 위해 헤더 포인터만을 사용할 수도 있다. 하지만, 시작부분과 끝부분을 모두 기억해 놓으면, 노드 삽입 시 헤더에서부터 하나씩 찾아가서 노드를 추가하지 않고도 바로 맨 뒤쪽에 새 노드를 삽입할 수 있다. 

이를 위하여 Node 구조체 외에도 List 구조체 추가로 준비!!!

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

struct _Node {     struct _Node* pNext;     char* pData; };   struct _List {     struct _Node* pHead;     struct _Node* pTail; };   typedef struct _Node Node; typedef struct _List List;   List slang_list;

2. 필요한 함수들 준비

txt 파일로부터 욕 데이타들을 읽어들일 Load 함수, 읽어들인 데이타를 리스트로 저장할 List_Insert_Node 함수, 입력받은 문장을 걸러 줄 Filter함수, 그 외 리스트 처리 함수들 만든다.

List_Print 함수 : 리스트의 모든 노드들의 데이타를 출력 pHead에서 시작해서 NULL값이 아닌 동안 출력하고 다음 노드를 탐색해간다. Sleep(1000)은 1초동안 쉬라는 거!!!!

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void Load(char* pData); void List_Insert_Node(List* pList, char* pData); void Filter(List* pList, char* pStr); void List_Init(List* pList); void List_Clear(List* pList);   void List_Print(List* pList) {     Node* p = NULL;     for(p = pList->pHead; p != NULL; p = p->pNext)     {         printf("%s\n", p->pData);         Sleep(20);     } }

Tip. 이름 짓는 법

변수는 소문자로, 함수는 대문자로 시작하고, 멤버 변수일 경우 m_member, 포인터 변수일 경우는 pPointer, 이런 식으로 지어준다! 

3. Main 함수

전역 변수이자 사용할 리스트인 slang_list를 초기화 시켜주고, data.txt로 부터 욕 데이타들을 읽어 저장해준다.

문자열을 받아 필터링하여 새로 출력해준다. 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void main() {     int i;     char temp[128];     char ctemp[128];     unsigned int time;       //initialize     List_Init(&slang_list);     Load("data.txt");       scanf("%s" , &temp);       time = GetTickCount();     for(i=0; i<1000000; i++)     {         strcpy( ctemp, temp );         Filter(&slang_list, ctemp);     }     printf("%s\n%d.%d\n", ctemp, (GetTickCount()-time)/1000, (GetTickCount()-time)%1000);       List_Clear(&slang_list); }

Tip. GetTickCount 함수

지나간 시간을 밀리세컨드 단위로 돌려주는 함수. 경과 시간 측정을 위해서 사용!

4. 리스트 초기화와 삭제

처음엔 헤드와 테일 모두 NULL로 초기화. 삭제할 때는 p를 이용하여 헤드부터 테일까지 하나씩 이동하며 메모리 해제해 준다. 이 때, 현재 가리키던 데이터가 메모리 해제되어 다음 노드를 찾지 못하는 걸 막기 위해 임시 변수에 다음 노드의 주소 값을 넣어둔다. 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void List_Init(List* pList) {     pList->pHead = NULL;     pList->pTail = NULL; }   void List_Clear(List* pList) {     Node* tmp = NULL;     Node* p = NULL;     for(p = slang_list.pHead; p != NULL; )     {         tmp = p;         p = p->pNext;                  if (tmp != NULL)         {             if (tmp->pData != NULL)                 free(tmp->pData);             free(tmp);         }     } }

5. 필터링

욕 데이타를 하나씩 가지고 입력받은 문자열을 검색해서 욕이 있는지를 검사하여 욕이 있을 경우 별표(*)로 치환해준다. 사용한 함수는  char* strstr(char* _str, char* _substr) 이 함수는 주어진 문자열 안에 부분 문자열이 있으면, 부분 문자열이 시작하는 위치를 리턴해준다. 

검색될 문자열의 위치가 저장될 포인터 변수를 pResult로 두고 strstr으로 알아낸 위치값을 넣어준다. 그러면, 그 위치에서부터 문자열의 길이만큼 별표(*)로 바꿔 주기만 하면 됨!

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void Filter(List* pList, char* pStr ) {     Node* p = NULL;     char* pResult = NULL;     int i = 0;     for(p = pList->pHead; p != NULL; p = p->pNext)     {         while(1)         {             pResult = strstr(pStr, p->pData);               if(pResult != NULL)             {                 for(i = 0; i < strlen(p->pData); i++)                 {                     pResult[i] = '*';                 }             }             else                  break;         }     } }

Tip. 포인터, 배열, 문자열

char a[10] = "hello"

char* b = a; 

이렇게 있다고 하면 a를 이용하든,  b를 이용하든, 첨자로 각 문자에 접근 가능 

 a[1] = b[1] = *(b+1) = "hello"[1] = 'e'  ; 이건 모두 다 'e'를 가리킨다!

* 문자열을 가리키는 포인터는, 그 문자열이 있는 위치를 가리켜 주는 거니깐 배열로 표현한 거랑 같다!

6. 새로운 노드 삽입

새로운 노드를 동적할당하여 데이타를 넣어주고, 최초 한 번은 pHead(리스트의 첫부분)와 pTail(리스트의 끝부분)을 모두 새 노드의 값으로 동일하게 설정해준다. 그 외의 경우에는 pTail이 다음 노드를 연결하도록 하고, pTail을 방금 삽입된 그 노드로 바꿔준다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

void List_Insert_Node( List* pList, char* pData ) {     Node* newNode;     newNode = (Node*)malloc(sizeof(Node));     newNode->pData = (char*)malloc(strlen(pData) +1);     strcpy(newNode->pData, pData);     newNode->pNext = NULL;       if(pList->pHead == NULL)     {         pList->pHead = newNode;         pList->pTail = pList->pHead;     }     else      {         pList->pTail->pNext = newNode;         pList->pTail = pList->pTail->pNext;     } }

7. 데이타 파일입출력

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void Load(char* pData) {     char* temp;     char str[20];          //파일 오픈     FILE *fp = fopen(pData, "r");     if(fp == NULL)     {         printf("The following file could not be found.\n");     }          //불러들여서 링크드 리스트에 넣어주기     while(feof(fp) == NULL)     {         fscanf(fp, "%s", str);         List_Insert_Node(&slang_list, str);     }       //파일 클로즈     fclose(fp); }

8. 이중포인터를 사용하는 이유 (내 이해를 잊지 않기위한 나만의 설명!)

포인터를 사용해 이동하며 순회하는 리스트나 트리 같은 경우, 자료값을 변경하는 것이 아니라, 다음 노드를 연결하기위해 주소값을 저장한다. (예를 들어 리스트의 한 노드에는 데이타와 다음 연결 노드의 주소값이 들어가는 식). 

아래와 같은 함수의 원형을 보면, 노드의 이중포인터를 매개변수로 전달해준다. 이 때 이중포인터가 아닌 그냥 포인터를 사용하면 노드들의 주소들을 이용해 실제 노드들 사이를 직접 뛰어다니며 값을 바꾸고 집어 넣고 등을 해야하는데.. 그러면, 다음 노드로 연결되는 주소값 등을 바꿀 때마다 막히거나 갈곳을 잃을 수가 있다! 따라서, 한 차원 더 위에서 본단 생각으로 노드들의 주소값을 건너뛰어 다니며 처리할 수 있는 이중포인터를 사용하면 이런 걱정 없이 주소값들을 마음대로 연결하고 처리하기 편해진당!

Colored By Color Scripter™

1 2 3

void List_Insert_Node( Node** ppNode, char* pData ) { }