dustn9401   2년 전

일단 해시테이블에 듣도 못한 사람의 명단을 넣고

보도 못한 사람을 테이블에서 검색하여 테이블에 존재하면 결과를 저장하는 배열인 res에 넣는 방식으로 만들어 봤습니다.

그런데 런타임 에러가 떠 버렸습니다............ 이름도 널문자까지 고려하여 21크기의 배열로 잡았고, 정답이 50만 개 일 경우를 고려하여

듣도 보도 못한 놈을 저장하는 배열의 크기도 50만 으로 하였습니다......

도대체 어디서 문제가 생기는 것인지 도무지 모르겠어서 질문 올립니다...

chogahui05   2년 전

어떤 것 때문에 런타임이 뜨는지는.. 흐음.. 자세히 안 봤지만요.

제가 봤을 때는 insert 과정에서.. 끝에 null을 안 붙여서

seek 과정에서 런타임 뜨는 거 같은데요.


24번째 줄에서 hash 값을 얻어와요. 이걸 버킷에다가 넣잖아요.

그게 table[idx] = n;

이 문장인 거 같은데요.


만약에 해당 버킷에 단 1개의 원소만 추가되었다면 어떤 일이 벌어지나요?

제가 봤을 때는

사이클이 생겨서 무한루프 돌 거 같은데요.


차라리 head와 tail 포인터를 둬서 따로 관리하시는 게 좋을 거 같네요.

chogahui05   2년 전

malloc으로 생성한 것은 힙에 할당되기도 하고요..

초기화 될 때 랜덤한 값으로 되어버려요. 그렇기 때문에 next 같은 경우도 초기화를 안 해주면

이상한 어느 공간을 가르키고 있겠죠..


링크드 리스트 같은 경우.

새 노드를 할당한 다음에 끝에 추가하는 경우 next에 null을 할당시켜버리는 게 보통입니다.

dustn9401   2년 전

답글 감사합니다. 참고해서 해보겠습니다

dustn9401   2년 전

혹시 조금만 더 자세히 설명 해 주실 수 있으신가요..?ㅠㅠ

처음에 모든 헤드를 NULL로 초기화 하고 새로 들어오는 데이터는 무조건 헤드 앞에 넣어서

리스트의 마지막 데이터는 항상 NULL을 가리키게 하였는데... 

무한 루프가 돌 수가 있는지요..ㅠㅠ

chogahui05   2년 전

링크드 리스트 먼저 구현해 보시는 게 좋아보입니다..

경험이 없으면 어려울 수도 있어서요..


dust님의 의도대로 하시려면 먼저

Bucket[uu] = null로 초기화를 먼저 해 놓고요.

아마 이 경우 Bucket[uu]의 head도 null이겠죠??


만약에 이 값이 null인 경우

새로 hashcode가 uu인 데이터가 들어왔을 경우 (주소가 new_node일 경우)

Bucket[uu] = new_node; new_node->next = null; 이렇게 초기화를 해 주시면 되겠네요..

Bucket[uu].head = new_node가 될 거고요.


만약에 이미 Bucket[uu]에 데이터가 있을 경우..

new_node -> next = Bucket[uu]가 될 거고요.

Bucket[uu] = new_node 이래 하시면 될 거 같네요..


끝에 붙어있는 노드가 null이 아니라면 무한 루프를 돌아버릴 수 있어요~

그림을 그려보시면서 천천히 구현해 보세요.

chogahui05   2년 전

의도대로 구현하시려면 이런 식으로 구현하시는 게 맞아보입니다.


new_node = (~)malloc(sizeof(~));

new_node -> data = ??

new_node -> next = NULL;

if(Bucket[~]==NULL)

{

    Bucket[~] = new_node;

}

else

{

    new_node -> next = Bucket[~];

    Bucket[~] = new_node;

}

dustn9401   2년 전

해결했습니다. 처음에 res_idx가 char로 선언되어있는데 int로 바꾸니 됬습니다.

댓글을 작성하려면 로그인해야 합니다.