c언어 이중연결리스트 이름순 정렬
글쓴이: myungwooBan@GitHub / 작성시간: 일, 2020/05/24 - 3:30오후
이중연결리스트를 이용해서 전화부를 만들고 있는데 삽입, 삭제, 검색을 모두 만들긴 했지만 삽입할때 이름순으로 삽입을 어떻게 해야 할지 잘 모르겠습니다. strcmp로 비교 해서 0보다 클때 앞뒤를 바꿔줘야 하는것은 알겠지만 이중연결리스트에서 구현을 하려니 어렵네요.. dinsert 함수 부분 이름순으로 삽입할 수 있게 도와주시면 감사하겠습니다.
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> //strcmp 및 strcpy_s 라이버러리 함수 사용하기 위해서 typedef struct PhoneBook { // PhoneBook 타입 char name[10]; char phone[20]; } PhoneBook; typedef struct DListNode { // 이중연결 노드 타입 PhoneBook data; struct DListNode* llink; //선행노드 struct DListNode* rlink; // 후속노드 } DListNode; // 이중 연결 리스트를 초기화 void init(DListNode* phead) { phead->llink = phead; phead->rlink = phead; } // 이중 연결 리스트의 노드를 출력 : 이름과 전화번호 출력 void dprint(DListNode* phead) { DListNode* p; for (p = phead->rlink; p != phead; p = p->rlink) printf("이름 : %s, 전화번호 : %s\n", p->data.name, p->data.phone); } // 새로운 노드 이름순으로 정렬된 위치에 삽입 void dinsert(DListNode* phead, PhoneBook in) { DListNode* newnode = (DListNode*)malloc(sizeof(DListNode)); DListNode* p; p = phead->rlink; newnode->data = in; newnode->llink = p; newnode->rlink = p->rlink; p->rlink->llink = newnode; p->rlink = newnode; } // 주어진 이름을 갖는 노드 삭제 void ddelete(DListNode* phead, char* name) { DListNode* p; for (p = phead->rlink; p != phead; p = p->rlink) { if (strcmp(p->data.name, name) == 0) { p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p); printf("%s이(가) 리스트에서 삭제되었습니다\n", name); return; } } if (strcmp(p->data.name, name) != 0) printf("%s이(가) 리스트에 존재하지 않습니다\n", name); } // 주어진 이름을 찾아 이름과 전화번호를 출력 void dsearch(DListNode* phead, char* name) { DListNode* p; for (p = phead->rlink; p != phead; p = p->rlink) { if (strcmp(p->data.name, name) == 0) { printf("이름 : %s, 전화번호 : %s\n", p->data.name, p->data.phone); return; } } if (strcmp(p->data.name, name) != 0) printf("%s이(가) 리스트에 존재하지 않습니다\n", name); } int main(void) { int menu; // 메뉴 선택 char name[10]; // 삭제, 검색시 입력받을 이름 PhoneBook in; // 삽입시 입력받을 연락처 DListNode* head = (DListNode*)malloc(sizeof(DListNode)); // 헤드노드 생성 init(head); // 헤드노드 초기화 for (;;) { printf("메뉴를 선택하시오.\n"); printf("1. 삽입 2. 삭제, 3, 검색, 4. 출력, 5. 종료 : "); scanf_s("%d", &menu); switch (menu) { case 1: // 삽입 printf("이름을 입력하시오: "); scanf_s("%s", in.name, sizeof(in.name)); printf("전화번호를 입력하시오: "); scanf_s("%s", in.phone, sizeof(in.phone)); dinsert(head, in); break; case 2: // 삭제 printf("이름을 입력하시오: "); scanf_s("%s", name, sizeof(name)); ddelete(head, name); break; case 3: // 검색 printf("이름을 입력하시오: "); scanf_s("%s", name, sizeof(name)); dsearch(head, name); break; case 4: // 출력 dprint(head); break; default: // 종료 exit(0); } } return 0; }
Forums:
핵심은 "삽입할 위치"를 찾는 것이죠.
핵심은 "삽입할 위치"를 찾는 것이죠.
strcmp를 쓸 줄 안다면 아주 그렇게 어려운 문제도 아닙니다.
이미 작성한 코드들처럼 리스트를 한 번 순회함으로써 찾을 수 있지요.
검색 조건은, 삽입할 노드보다 보다 앞에 있어야 하는 모든 노드들 뒤, 그리고 자기보다 뒤에 있어야 하는 모든 노드들 앞 위치를 찾는 것입니다.
그러고 나면, 그 위치에 추가하면 됩니다. 삽입은 삭제의 역순으로...
다만,
1. 리스트가 처음에 비어 있는 경우
2. 리스트 맨 앞에 삽입해야 하는 경우
3. 리스트 맨 뒤에 삽입해야 하는 경우
4. 리스트에 이미 같은 이름을 가진 항목이 있는 경우
등의 corner case를 제대로 처리할 수 있도록 신경써서 작성해야 하지요.
만일을 대비해서 질문 원본을 기록으로 남겨둡니다.
만일을 대비해서 질문 원본을 기록으로 남겨둡니다.
http://archive.is/b9JEh
댓글 달기