연결리스트에서 포인터 교환으로 swap할 때..
글쓴이: alsrud / 작성시간: 수, 2014/11/12 - 1:54오후
명령어 ls를 옵션과 함께 구현하고 있습니다.
-r옵션이 있을때는 memcpy해서 메모리 영역을 교환하는 식으로 바꿨습니다.
-r옵션이 없을경우는 포인터를 교환하고 싶어서 코드를 수정했는데ㅜ
값을 찍어보니 무한 루프를 돕니다..
단일연결리스트이기떄문에 교환하려면 head포인터 이전에 그것을 가리키는 prev노드가 있어야 할것
같아서 추가했구요~
어디가 문제일까요 ㅜㅜ?
//링크드리스트에 들어있는자료를 파일이름순으로 정렬 void sort_list(FILEINFO *list_head) { FILEINFO *tmp_list_left; FILEINFO *tmp_list_right; FILEINFO *prev; prev = (FILEINFO*)malloc(sizeof(FILEINFO)); prev->next = list_head; printf("%s\n", prev->next->filename); FILEINFO tmp_list; FILEINFO *tmp_listp; int change = 1; if(list_head == NULL || list_head->next == NULL) return ; tmp_list_left = list_head; //printf("%s\n", list_head->filename); tmp_list_right = list_head->next; while(change) { change = 0; while(tmp_list_right!= NULL) { //puts("================"); if(flag_r) { if(strcmp(tmp_list_left->filename, tmp_list_right->filename) < 0) { //데이터 교환 memcpy(&tmp_list, tmp_list_left, sizeof(FILEINFO)); memcpy(tmp_list_left, tmp_list_right, sizeof(FILEINFO)); memcpy(tmp_list_right, &tmp_list, sizeof(FILEINFO)); //포인터 교환 tmp_listp = tmp_list_left->next; tmp_list_left->next = tmp_list_right->next; tmp_list_right->next = tmp_listp; change = 1; } tmp_list_left = tmp_list_right; tmp_list_right = tmp_list_right->next; } else { if(strcmp(tmp_list_left->filename,tmp_list_right->filename) >0 ) { prev->next = tmp_list_left->next; tmp_list_left->next = tmp_list_right->next; tmp_list_right->next = tmp_list_left; change = 1; } if(change = 0) { tmp_list_left = tmp_list_right; tmp_list_right = tmp_list_left->next; }else { tmp_list_right = tmp_list_left->next; } } } prev ->next = list_head; printf("%s\n", list_head->filename); tmp_list_left = list_head; tmp_list_right = list_head->next; } } <//code>
Forums:
들여쓰기가 깨져서 캡쳐파일을 올립니다.
들여쓰기가 깨져서 캡쳐파일을 올립니다.
코드 올리실 때..
{code}
코드 본문
{/code}
로 올리시면 깨지지 않고 올라갑니다. { 는 < 로 바꿔주세요.
조언 감사합니다 ^^
조언 감사합니다 ^^
일단 몇몇 가정들이 잘못되었습니다. 1. head가
일단 몇몇 가정들이 잘못되었습니다.
1. head가 가리키는 노드도 sort 대상이 되어 뒤쪽으로 갈 수 있겠지요.
그렇게 되면 인자가 void sort_list(FILEINFO *list_head) 보다 void sort_list(FILEINFO **list_head)가 되어야 할 겁니다.
2. 단일 링크드 리스트에서 두 개의 노드를 swap한다는 것은 자신의 앞 쪽 노드에서의 포인터도 변경해야 합니다.
따라서, 2개의 임의의 노드를 교환하기 위해선 4개의 노드에서 포인터 교환이 있고, 2개의 인접한 노드를 교환하기 위해선 3개의 노드에서 포인터 교환이 있게 됩니다.
다음 링크들을 살펴보시면, 아실 수 있습니다.
http://stackoverflow.com/questions/15315914/swap-nodes-in-a-singly-linked-list
https://www.google.co.kr/search?num=20&newwindow=1&rlz=1C1ASRM_enKR557KR557&es_sm=122&q=single+linkedlist+sort+swap&oq=single+linkedlist+sort+swap&gs_l=serp.3..30i10.685950.689708.0.690012.17.15.2.0.0.0.145.1371.6j7.13.0....0...1c.1j4.58.serp..5.12.1183.pfcYm1hWzL8
Signature :) - "여유를 갖고 행동하되 게을러지지 말자"
C입문자라서 아직 너무 복잡하지만 링크 자료보고 좀
C입문자라서 아직 너무 복잡하지만 링크 자료보고 좀 더 공부해야겠어요 : )
조언도 자료도 감사드립니다 !!
시간이 좀 남길래, 한 번 작성해 보았습니다. 기본에
시간이 좀 남길래, 한 번 작성해 보았습니다.
기본에 해당되는 것인데, 막상 해보면 복잡하네요.
링크들에도 해답들이 있는 것 같지만 참고하시라고 올려봅니다. (별로 잘 작성되진 않았습니다)
몇 가지 첨언하자면,
1. 링크드 리스트의 노드 교체시 노드의 데이터를 서로 교환하면 링크드 리스트를 쓰는 의미가 어느정도는 퇴색됩니다
노드의 포인터들만을 이동시켜, 노드의 데이터가 클 때, 데이터 복사를 막아 성능향상을 도모해야 합니다.
2. 전역 변수보다는 함수인자등을 사용하시고, 함수나 변수 네이밍에 신경 써서 작성하셔야 합니다.
3. sort_list 함수에서 사용된 malloc으로 추가한 임시노드는 함수를 빠져나가기 전에 꼭 free로 해제시켜주시구요.
Signature :) - "여유를 갖고 행동하되 게을러지지 말자"
그런데 코드에서 dummy_head는 무엇을 의미하는
그런데 코드에서 dummy_head는 무엇을 의미하는 것인가요? :)
아울러 node1,2와 prev1,2를 따로 나누어 저장하는 것은 어떤 의미인지 궁금합니다 ~~
댓글 달기