내 소식

오르비

태그

내 태그

입시

학습

생활

클럽

직업·취업

Epioptimus

Centurion

✨컴공주✨ [1052682] · MS 2021 (수정됨) · 쪽지

2022-10-12 22:51:23
조회수 6,709
2

컴공 일기193

게시글 주소: https://orbi.kr/00058764625

오랜만에 일기 씁니다.

요새 재미삼아 만들어 보는 탐색 예제입니다.

특정 교수님을 사용자가 검색하면 검색할수록 연관검색어에 가장 끝에 위치하도록 하는 프로그램이지요.

선형 탐색이기 때문에, 자료구조는 당연히 리스트를 사용해야 합니다.

알고리즘은 이래서 자료구조에 의존적이지요. 만약, 이진 탐색을 하고 싶다면,

알고리즘을 손 댈 것이 아니라 자료구조를 바꿔야 합니다.

알고리즘보다 자료구조가 더 중요한 이유지요.

+) 박준상 교수님 사랑해용 근데 F폭격은 좀... ㅠㅠ

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct Node

{

char szData[64];

struct Node* NextNode;

}Node;

/*전역변수로 더미헤드를 선언해준다*/

Node* g_Head;

Node* g_pTail;

void InitList(void)

{

g_Head = (Node*)malloc(sizeof(Node));

g_pTail = (Node*)malloc(sizeof(Node));

memset(g_Head, 0, sizeof(Node));

memset(g_pTail, 0, sizeof(Node));

strcpy_s(g_Head->szData, sizeof(g_Head->szData), "DUMMY HEAD");

strcpy_s(g_pTail->szData, sizeof(g_pTail->szData), "DUMMY TAIL");

//기본적인 교통정리

g_Head->NextNode = g_pTail;

}

int IsEmpty()

{

if (g_Head->NextNode == NULL )

return 1;

else

return 0;

}

int InsertAtHead(char* pszData)

{

Node* pNode = (Node*)malloc(sizeof(Node));

memset(pNode, 0, sizeof(Node));

strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);

if (IsEmpty())

{

g_Head->NextNode = pNode;

g_pTail = pNode;

}

//리스트에 추가된 첫 번째 데이터 처리

else

{

pNode->NextNode = g_Head->NextNode;

g_Head->NextNode = pNode;

}

g_pTail = pNode;

return 1;

}

int InsertAtTail(char* pszData)

{

Node* pNode = (Node*)malloc(sizeof(Node));

memset(pNode, 0, sizeof(Node));

strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);

if (IsEmpty())

g_Head->NextNode = pNode;

//리스트에 추가된 첫 번째 데이터 처리

else

g_pTail->NextNode = pNode;

g_pTail = pNode;

return 1;

}

/*연결리스트 전체 노드 출력 함수*/

void PrintList(void)

{

Node* Head = g_Head;

while (Head != NULL)

{

printf("[%p] %s, next[%p]\n",

Head, Head->szData, Head->NextNode);

Head = Head->NextNode;

}

putchar('\n');

}

/*노드를 추가하는 함수*/

int InsertNewNode(char* pszData)

{

Node* pNode = (Node*)malloc(sizeof(Node));

/*기본적으로 memset으로 메모리 초기화를 꾀했다*/

memset(pNode, 0, sizeof(Node));

strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);

if (g_Head->NextNode == NULL)

g_Head->NextNode = pNode;

else {

pNode->NextNode = g_Head->NextNode;

g_Head->NextNode = pNode;

}

return 1;

}

int FindData(char* pszData)

{

Node* pCur = g_Head->NextNode;

Node* pPrev = g_Head;

while (pCur != NULL)

{

//찾은 노드의 앞 노드 주소를 반환하는 패턴.

//더미헤드의 미학 ; 이렇게 해도 문제 없음.

if (strcmp(pCur->szData, pszData) == 0)

return pPrev;

pCur = pCur->NextNode;

pPrev = pPrev->NextNode;

}

return 0;

}

Node* Transpose(char* pszData)

{

Node* Current = g_Head->NextNode;

Node* Previous = g_Head;

Node* PPrevious = g_Head;

Node* Match = NULL;

while (Current != NULL)

{

if (strcmp(Current->szData, pszData) == 0)

{

Match = Current;

if (Previous != NULL)

{

if (PPrevious != g_Head)

PPrevious->NextNode = Current;

else

g_Head->NextNode = Current;

Previous->NextNode = Current->NextNode;

Current->NextNode = Previous;

}

break;

}

else

{

if(Previous != NULL)

PPrevious = Previous;

Previous = Current;

Current = Current->NextNode;

}

return Match;

}

//전반적 소감 : 더미 헤드를 추가하지 않으면 삭제할 노드의 전 노드를 찾아야 하는 노가다가 발생한다.

int DeleteData(char* pszData)

{

Node* pPrev = FindData(pszData);

if (pPrev != 0)

{

Node* pDelete = pPrev->NextNode;

pPrev->NextNode = pDelete->NextNode;

printf("DeleteData(): %s\n", pDelete->szData);

if (pDelete == g_pTail)

g_pTail = 0;

free(pDelete);

return 1;

}

void ReleaseList(void)

{

Node* pTmp = g_Head;

while (pTmp != NULL)

{

/*반복문 안에서 변수 선언하면 안 되지 않아? -> 최근엔 조금 애매해지긴 해졌다. 컴파일러 최적화 과정!*/

Node* pDelete = pTmp;

pTmp = pTmp->NextNode;

printf("Delete: [%p] %s\n", pDelete, pDelete->szData);

free(pDelete);

}

//g_Head.NextNode가 아예 메모리 해제가 되었으므로 다시 NULL로 초기화를 해주어야 한다.

g_Head = 0;

g_pTail = 0;

}

void Push(char* pszData)

{

InsertAtHead(pszData);

}

int Pop(Node* pPopNode)

{

Node* sp = g_Head->NextNode;

if (IsEmpty())

return 0;

memcpy(pPopNode, sp, sizeof(Node));

g_Head->NextNode = sp->NextNode;

free(sp);

return 1;

}

int Enqueue(char* pszData)

{

InsertAtTail(pszData);

return 1;

}

int Dequeue(char* pszData)

{

Pop(pszData);

return 1;

}

int main()

{

InitList();

//링크드 리스트를 위한 테스트 코드

InsertNewNode("박준상");

InsertNewNode("표창우");

InsertNewNode("권건우");

InsertNewNode("하란");

//사용자가 만약 박준상 교수를 계속 탐색하려 든다면, 박준상 교수의 인덱스를 계속 앞으로 당겨오는 것이다.

Transpose("박준상");

//원래 박준상 교수는 4번째에 위치해 있지만, 2번을 탐색했으므로 index = 1이 된다.

PrintList();

ReleaseList();

}

실행결과 :

[0000025C86533500] DUMMY HEAD, next[0000025C8653A680]

[0000025C8653A680] 하란, next[0000025C8653A4D0]

[0000025C8653A4D0] 박준상, next[0000025C8653A5F0]

[0000025C8653A5F0] 권건우, next[0000025C8653A560]

[0000025C8653A560] 표창우, next[0000025C86535700]

[0000025C86535700] DUMMY TAIL, next[0000000000000000]

Delete: [0000025C86533500] DUMMY HEAD

Delete: [0000025C8653A680] 하란

Delete: [0000025C8653A4D0] 박준상

Delete: [0000025C8653A5F0] 권건우

Delete: [0000025C8653A560] 표창우

Delete: [0000025C86535700] DUMMY TAIL

팔로우 156

0 XDK (+0)

유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

✨컴공주✨ [1052682]

쪽지 보내기

최근 게시글 · 더보기
9 4 06/10 22:14 근데 원래 오르비는 부정선거를 음모론이라고 생각하지 않았었나요?
3 1 05/13 00:54 한화이글스 팬입니다.
4 1 04/11 01:39 컴공 무물
14 0 02/18 12:41 컴공 무물
15 1 25/12/16 14:09 컴공 일기279

알림
스크랩
신고

대학가자!!!!!!!! · 1051001 · 22/10/17 19:55 · MS 2021

혹시 군대는 어디로 가실 예정인가요?? 다른 일기 보니깐 군대에서도 공부하신다길래 궁금해서 여쭈어봅니다.

좋아요 0 답글 달기 신고
✨컴공주✨ · 1052682 · 22/10/18 00:22 · MS 2021

공군 갈 것 같습니다 ㅎㅎ

좋아요 0 답글 달기 신고
대학가자!!!!!!!! · 1051001 · 22/10/21 02:05 · MS 2021

저도 공군 생각 중인데 혹시 뭐 자격증 같은 거 준비하는게 좋나요..? ㅎㅎ

좋아요 0 답글 달기 신고