연결리스트에서 포인터 교환으로 swap할 때..

alsrud의 이미지

명령어 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>
alsrud의 이미지

들여쓰기가 깨져서 캡쳐파일을 올립니다.

댓글 첨부 파일: 
첨부파일 크기
Image icon , 2014-11-12 14:01:25.png246.38 KB
twinwings의 이미지

{code}
코드 본문
{/code}
로 올리시면 깨지지 않고 올라갑니다. { 는 < 로 바꿔주세요.

alsrud의 이미지

조언 감사합니다 ^^

yhsuk의 이미지

일단 몇몇 가정들이 잘못되었습니다.

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 :) - "여유를 갖고 행동하되 게을러지지 말자"

alsrud의 이미지

C입문자라서 아직 너무 복잡하지만 링크 자료보고 좀 더 공부해야겠어요 : )
조언도 자료도 감사드립니다 !!

yhsuk의 이미지

시간이 좀 남길래, 한 번 작성해 보았습니다.
기본에 해당되는 것인데, 막상 해보면 복잡하네요.
링크들에도 해답들이 있는 것 같지만 참고하시라고 올려봅니다. (별로 잘 작성되진 않았습니다)

몇 가지 첨언하자면,

1. 링크드 리스트의 노드 교체시 노드의 데이터를 서로 교환하면 링크드 리스트를 쓰는 의미가 어느정도는 퇴색됩니다
노드의 포인터들만을 이동시켜, 노드의 데이터가 클 때, 데이터 복사를 막아 성능향상을 도모해야 합니다.

2. 전역 변수보다는 함수인자등을 사용하시고, 함수나 변수 네이밍에 신경 써서 작성하셔야 합니다.

3. sort_list 함수에서 사용된 malloc으로 추가한 임시노드는 함수를 빠져나가기 전에 꼭 free로 해제시켜주시구요.

댓글 첨부 파일: 
첨부파일 크기
Package icon main.zip1.39 KB

Signature :) - "여유를 갖고 행동하되 게을러지지 말자"

alsrud의 이미지

그런데 코드에서 dummy_head는 무엇을 의미하는 것인가요? :)
아울러 node1,2와 prev1,2를 따로 나누어 저장하는 것은 어떤 의미인지 궁금합니다 ~~

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.