링크드리스트 버블소트...!
글쓴이: news4682 / 작성시간: 목, 2013/10/17 - 1:31오전
void sort()
{
NODE *p;
int changed = 1;
while(changed) {
changed = 0;
for(p = head; p->LINK != NULL; p = p->LINK) {
if((p->cgpa) < (p->LINK->cgpa)) {
p = switch_(p, p->LINK);
changed = 1;
}
}
}
printf("Success!\n");
functioncaller();
return;
}
NODE *switch_(NODE *l1, NODE *l2)
{
l1->LINK = l2->LINK;
l2->LINK = l1;
return l2;
}입력 받은 링크드리스트 노드들을 cgpa 값에 따라서 내림차순 정렬하려고 버블 소트를 사용했는데
정렬이 제대로 되지 않는군요...;;
조언 부탁드립니다.
Forums:
switch_()가 제 역할을 못하고 있는 것
switch_()가 제 역할을 못하고 있을 것입니다.
아래와 같이 수정하시면 될 것 같네요.
이전 제 답변은 완전히
이전 제 답변은 완전히 틀렸군요.
switch_()의 문제는 다른 곳에 있는 것 같습니다.
예를 들어 리스트 내용물이 아래와 같을 때,
만약 item1과 item2의 자리를 바꾸기 위해 switch_(item1, item1->LINK) 가 실행되면 리스트는 아래와 같이 될 것입니다.
... --> item0 --> item1 --> item3 --> ... ↑ item2 ───┘item0->LINK는 여전히 item1을 가리키고 있으니 item2는 미아가 됩니다.
switch_()에서 item0->LINK도 처리할 수 있게 변경하셔야 합니다.
item 두 개의 LINK를 치환하는 것이 아니고
item 세 개의 LINK가 서로 적절히 자리바꿈을 해야합니다.
코드를 수정해서 올리려고 했는데,
수정이 간단치 않은 것 같아 그냥 생각만 적어서 올립니다.
설명은 쉬운데 구현은 어렵네요. ㅇ_ㅇ;;
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
item0->LINK를 바로잡아서 아래와 같이 만들면
item0->LINK를 바로잡아서 아래와 같이 만들면 됩니다.
... --> item0 item1 --> item3 --> ... ↓ ↑ item2 ───┘코드를 수정해 봤습니다. 테스트는
코드를 수정해 봤습니다. 테스트는 안해봤고요.
switch_()에 두 노드의 포인터가 아닌 각각의 parent를 넘겨주는 식으로 바꾼 것입니다.
문득 코드를 보니까. 이런 생각이 드네요
이렇게하면 보기 좋을텐데... ㅇ_ㅇ??
맞는걸까 모르겠네요.
NODE *switch_(NODE *l1, NODE *l2) { NODE *t = l1->LINK = l2->LINK = t; return l2; }확인해보니 틀렸네요. ㅡ_ㅡ;;
이런 방식도 있습니다.
/* int *switch_(int *l1, int *l2) { 004113C0 push ebp 004113C1 mov ebp,esp 004113C3 sub esp,0D8h 004113C9 push ebx 004113CA push esi 004113CB push edi 004113CC lea edi,[ebp-0D8h] 004113D2 mov ecx,36h 004113D7 mov eax,0CCCCCCCCh 004113DC rep stos dword ptr es:[edi] 004113DE mov byte ptr [ebp-0D1h],0 int *t = l1 = l2 = t; 004113E5 cmp byte ptr [ebp-0D1h],0 004113EC jne switch_+3Bh (4113FBh) 004113EE push offset (41142Bh) 004113F3 call @ILT+175(__RTC_UninitUse) (4110B4h) 004113F8 add esp,4 004113FB mov eax,dword ptr [t] 004113FE mov dword ptr [l2],eax 00411401 mov ecx,dword ptr [l2] 00411404 mov dword ptr [l1],ecx 00411407 mov byte ptr [ebp-0D1h],1 0041140E mov edx,dword ptr [l1] 00411411 mov dword ptr [t],edx return l2; 00411414 mov eax,dword ptr [l2] } int *switch_(int *l1, int *l2) { 004113C0 push ebp 004113C1 mov ebp,esp 004113C3 sub esp,0CCh 004113C9 push ebx 004113CA push esi 004113CB push edi 004113CC lea edi,[ebp-0CCh] 004113D2 mov ecx,33h 004113D7 mov eax,0CCCCCCCCh 004113DC rep stos dword ptr es:[edi] int *t = l1; 004113DE mov eax,dword ptr [l1] 004113E1 mov dword ptr [t],eax l1 = l2; 004113E4 mov eax,dword ptr [l2] 004113E7 mov dword ptr [l1],eax l2 = t; 004113EA mov eax,dword ptr [t] 004113ED mov dword ptr [l2],eax return l2; 004113F0 mov eax,dword ptr [l2] } */ int *switch_(int *l1, int *l2) { int *t = l1; l1 = l2; l2 = t; printf("switch_() %d %d\n", *l1, *l2); //변수 정리된 내용 //https://www.google.com/url?q=http://kldp.org/files/chapter15.hwp&sa=U&ei=0kRfUprGDoPe2AWMjYHoBQ&ved=0CAoQFjAB&client=internal-uds-cse&usg=AFQjCNEmxVc40_OLS-rUI3JnFCZqiG2PJA //http://kldp.org/search/google?cx=partner-pub-6651292044448473%3Ajz430d1s80g&cof=FORID%3A11&query=%EB%B3%80%EC%88%98+%ED%95%98%EB%82%98%EB%A1%9C+%EC%8A%A4%EC%99%91&op=%EC%B0%BE%EA%B8%B0&hl=ko&safe=medium&form_build_id=form-0f3c4d0ac7a9a111308fe7536cb06d2e&form_token=39a7115ac3b1e39990bcedb79693aaf2&form_id=google_cse_results_searchbox_form&siteurl=http%3A%2F%2Fkldp.org%2Fnode%2F140372 //변수 하나로 스왑하는 방식 //https://kldp.org/node/105054 *l1 ^= *l2; *l2 ^= *l1; *l1 ^= *l2; printf("switch_() %d %d\n", *l1, *l2); return l2; }----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
찾아보니 XOR 교체 알고리즘에 잘 설명되어
찾아보니 XOR 교체 알고리즘에 잘 설명되어 있네요.
아래와 같은 장단점이 있다고 하니 알아두고 적시에 쓰면 도움이 될 것 같습니다.
글은 안보이고. 코드는 보이네요. ㅡ_ㅡ;;
알려주신 내용을 확인해 보니. 이런 방식입니다.
http://codepad.org/qtuEMK2v
#include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { int xx = 10; int yy = 20; xx ^= yy ^= xx ^= yy; printf("%d %d\n", xx, yy); return 0; }----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
뭔가... 무한루프를 돌고 있네요
솔팅 함수 부분에는 문제가 없는것 같은데 혹시 삽입이 잘못 된걸까요
void insertNode() { NODE *pNew; NODE *p; NODE *pre; int id; char name[20]; float cgpa; p = (NODE*)malloc(sizeof(NODE)); pre = (NODE*)malloc(sizeof(NODE)); pNew = (NODE*)malloc(sizeof(NODE)); printf("ID: "); scanf("%d",&id); printf("Name: "); scanf("%s",name); printf("CGPA: "); scanf("%f",&cgpa); pNew->id = id; pNew->name = name; pNew->cgpa = cgpa; pNew->LINK = NULL; if(head == NULL) { head = pNew; } else { pNew->LINK = head; head = pNew; } functioncaller(); return; }디버깅을 해보세요. ㅇ_ㅇ;;
이름에 주소를 확인해보시면 될거 같습니다.
#include <cstdlib> #include <iostream> using namespace std; typedef struct DF_NODE { int id; char* name; float cgpa; DF_NODE * LINK; }NODE; NODE *head = NULL; int max_cnt = 0; void functioncaller() { printf("-----------------------------------\n"); NODE* list = head; int i = 0; for(i=0; i<max_cnt; i++) { NODE* p = list; int id = p->id; char* name = p->name; float cgpa = p->cgpa; list = p->LINK; printf("%d %s %f\n", id, name, cgpa); } } void insertNode() { NODE *pNew; NODE *p; NODE *pre; int id; char name[20]; float cgpa; p = (NODE*)malloc(sizeof(NODE)); pre = (NODE*)malloc(sizeof(NODE)); pNew = (NODE*)malloc(sizeof(NODE)); printf("ID: "); scanf("%d",&id); printf("Name: "); scanf("%s",name); printf("CGPA: "); scanf("%f",&cgpa); pNew->id = id; pNew->name = name; pNew->cgpa = cgpa; pNew->LINK = NULL; if(head == NULL) { head = pNew; } else { pNew->LINK = head; head = pNew; } max_cnt++; functioncaller(); return; } /* int *switch_(int *l1, int *l2) { 004113C0 push ebp 004113C1 mov ebp,esp 004113C3 sub esp,0D8h 004113C9 push ebx 004113CA push esi 004113CB push edi 004113CC lea edi,[ebp-0D8h] 004113D2 mov ecx,36h 004113D7 mov eax,0CCCCCCCCh 004113DC rep stos dword ptr es:[edi] 004113DE mov byte ptr [ebp-0D1h],0 int *t = l1 = l2 = t; 004113E5 cmp byte ptr [ebp-0D1h],0 004113EC jne switch_+3Bh (4113FBh) 004113EE push offset (41142Bh) 004113F3 call @ILT+175(__RTC_UninitUse) (4110B4h) 004113F8 add esp,4 004113FB mov eax,dword ptr [t] 004113FE mov dword ptr [l2],eax 00411401 mov ecx,dword ptr [l2] 00411404 mov dword ptr [l1],ecx 00411407 mov byte ptr [ebp-0D1h],1 0041140E mov edx,dword ptr [l1] 00411411 mov dword ptr [t],edx return l2; 00411414 mov eax,dword ptr [l2] } int *switch_(int *l1, int *l2) { 004113C0 push ebp 004113C1 mov ebp,esp 004113C3 sub esp,0CCh 004113C9 push ebx 004113CA push esi 004113CB push edi 004113CC lea edi,[ebp-0CCh] 004113D2 mov ecx,33h 004113D7 mov eax,0CCCCCCCCh 004113DC rep stos dword ptr es:[edi] int *t = l1; 004113DE mov eax,dword ptr [l1] 004113E1 mov dword ptr [t],eax l1 = l2; 004113E4 mov eax,dword ptr [l2] 004113E7 mov dword ptr [l1],eax l2 = t; 004113EA mov eax,dword ptr [t] 004113ED mov dword ptr [l2],eax return l2; 004113F0 mov eax,dword ptr [l2] } */ int *switch_(int *l1, int *l2) { // int *t = l1 = l2 = t; // int *t = l1 = l2 = t; int *t = l1; l1 = l2; l2 = t; return l2; } int main(int argc, char *argv[]) { int n1 = 10; int n2 = 20; int n3 = *switch_(&n1, &n2); printf("%d %d %d\n", n1, n2, n3); insertNode(); insertNode(); insertNode(); system("PAUSE"); return EXIT_SUCCESS; } //10 20 10 //ID: 1 //Name: 1 //CGPA: 1 //----------------------------------- //1 1 1.000000 //ID: 2 //Name: 2 //CGPA: 2 //----------------------------------- //2 2 2.000000 //1 2 1.000000 //ID: 3 //Name: 3 //CGPA: 3 //----------------------------------- //3 3 3.000000 //2 3 2.000000 //1 3 1.000000 //계속하려면 아무 키나 누르십시오 . . .----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
시간이 없어서 답글의 다른 분들 코드는 못 본 상태로
시간이 없어서 답글의 다른 분들 코드는 못 본 상태로 작성하는 거라서 겹치는 얘기도 있겠습니다만,
애초에 링크드 리스트를 정렬하시려는 이유가
단지 공부 삼아서 하려는 거라면 : 답글 중에 언급이 있었지만 스왑하려는 두 노드 말고 그 앞 노드까지 고려해야 합니다.
저라면 노드의 연결 상태를 바꾸는 식으로 스왑하지 않고, 연결 상태는 그대로 두고 노드의 데이타들을 스왑하는 식으로
만들겠습니다. 그럼 그냥 스왑하려는 그 두 노드만 만지면 됩니다.
(다만 다른 포인터 변수가 특정 노드를 가리키고 있는상태로 사용되고 있다면 그 노드의 값이 어느 순간
바뀌어 있을 수 있으니 주의해야겠지요)
그게 아니고 실제로 필요해서 하는 거라면, 링크드 리스트는 정렬을 하기 편한 구조가 아니니까
1) 노드 포인터 타입의 배열을 만들어서 리스트의 노드를 순서대로 가리키게 한 다음에,
2) 그 배열을 정렬하고 - 배열의 정렬이니까 이젠 아무 알고리즘이든 편하게 다 쓸 수 있지요.
3) 이제 반대로 그 배열의 원소를 처음부터 끝까지 순회하면서 그에 맞춰서 리스트를 새로 만들거나
3') 아니면 굳이 새 리스트를 만들 필요도 없죠. 방금 정렬한 그 배열을 가지고 출력을 하든 뭘 하든 하면 그만이죠.
좋은 하루 되세요!
이게 정답인듯..
리스트 상태에서 정렬을 하는건 말이 안 됨..
차라리 데이터값을 정렬후 다시 리스트화시키는거랑 뭐가 다른건지..몰겠음
질문자께서는 아마 아래 페이지의 샘플을 가져다 고쳐
질문자께서는 아마 아래 페이지의 샘플을 가져다 고쳐 쓰신 것 같습니다.
8.5. Linked List Bubble Sort
(http://www.sal.ksu.edu/faculty/tim/CMST302/study_guide/topic7/bubble.html)
이 페이지의 샘플에는 버그가 좀 있습니다. 이미 여러 댓글을 통해 지적된 문제들입니다.
위 페이지 관리하시는 분에게 버그리포트를 보냈더니 TODO 목록에 올리겠다고 답장이 왔습니다.
질문자께서는 이미 문제를 해결하셨겠지만
누구에게든 참고가 될 것 같아 댓글 달아둡니다.
댓글 달기