보통 연결 리스트에서는 선행 노드를 알아야만 노드를 삭제할 수 있다.
그러나 다음과 같이 하면 선행 노드를 모르고도 노드를 삭제할 수 있다.
먼저 원형 연결 리스트라고 가정하자. 어떤 노드를 가리키는 포인터 x가 주어진 경우,
그 노드의 후속 노드를 쉽게 찾을 수 있다. 후속 노드를 y라고 하면 x에 y의 데이터
필드 값을 복사한다. 그리고 y를 삭제한다. 그러면 실질적으로는 x가 삭제된것처럼된다.
이런식으로 노드를 삭제하는 함수 remove_node2를 작성하고 구현, 테스트하라.
================================================================
//리스트의 헤더가 시작노드를 가리키는 경우
//void insert_first(ListNode **, ListNode *)
#include<stdio.h>
#include<stdlib.h>
typedef int element;
typedef struct ListNode{
element data;
struct ListNode *link;
}ListNode;
void error(char *message){
fprintf(stderr, "%s",message);
exit(1);
}
ListNode *create_node(element data, ListNode *link){
ListNode *new_node;
new_node = (ListNode*)malloc(sizeof(ListNode));
if(new_node == NULL) error("메모리 할당 에러");
new_node -> data= data;
new_node->link =link; // NULL
return new_node;
}
// head가 dummy노드를 가리키도록 해야
// 제대로 구현이 된다.
ListNode *create_list(){
ListNode *new_node;
new_node = (ListNode*)malloc(sizeof(ListNode));
if(new_node == NULL) error("메모리 할당 에러");
new_node -> data= 0;
new_node->link =new_node;
return new_node;
}
void insert_first(ListNode **phead, ListNode *node){
node->link = (*phead)->link ;
(*phead) ->link = node;
}
void display(ListNode *head) {
ListNode *p;
// p는 더미노드 다음 노드를 가리킨다.
p=head->link;
//head가 아닐때까지!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 찍어
while(p!=head) {
printf("%d->", p->data);
p=p->link;
//getchar();
}
printf("\n");
}
void remove_node2(ListNode **phead, element value) {
ListNode *p;
ListNode *t;
// p는 더미노드 다음 노드를 가리킨다.
p=(*phead)->link;
// 끝이 나올 때 까지
while(p!=*phead) {
// 지금 노드의 data가 vlaue와 같다면 지울 노드를 찾은 것이다.
if(p->data==value) {
break;
}
// 아니면 다음 노드로 간다.
p=p->link;
}
// 만약 한바퀴 돌아도 value를 찾지 못했다면
if(p==*phead) {
printf("There is no value %d\n", value);
return;
// 만약 value를 가진 노드가 마지막 노드라면
// 이 노드를 더미 노드로 만들어 주고 더미 노드를 삭제해 준다.
} else if(p->link==*phead) {
// t는 더미 노드이다.
t=*phead;
// 이 노드를 삭제하는 대신 더미 노드로 만들어 준다.
p->data=0;
// 더미 노드의 다음위치를 복사해준다.
p->link=t->link;
// head가 이 노드를 가리키도록 해준다. (p노드가 더미노드로 바뀐다.)
*phead=p;
// 원래 더미노드 t를 삭제해 준다.
free(t);
// 만약 value를 가진 노드가 마지막 노드가 아니라면
} else {
// 다음 노드를 t라고 하자.
t=p->link;
// t의 값과 link를 p에 복사한 다음
p->data=t->data;
p->link=t->link;
// t를 삭제해 주면 된다.
free(t);
}
}
int main(){
// 더미 노드를 가진 리스트를 만들어 준다.
ListNode *list1 = create_list();
// 10, 20, 30, 40, 50의 순서대로 삽입을 한다.
insert_first(&list1, create_node(10, NULL));
insert_first(&list1, create_node(20, NULL));
insert_first(&list1, create_node(30, NULL));
insert_first(&list1, create_node(40, NULL));
insert_first(&list1, create_node(50, NULL));
display(list1);
remove_node2(&list1, 20);
display(list1);
remove_node2(&list1, 50);
display(list1);
remove_node2(&list1, 10);
display(list1);
remove_node2(&list1, 20);
display(list1);
remove_node2(&list1, 30);
display(list1);
remove_node2(&list1, 40);
display(list1);
return 0;
}
'c·c++ > c 프로그래밍' 카테고리의 다른 글
rgb2hsv (0) | 2014.08.02 |
---|---|
next_permutation (0) | 2014.07.21 |
3x3 행렬의 determinant 와 역행렬 (0) | 2014.06.27 |
c/c++ 언어 공부 (0) | 2014.06.26 |
pseudo random number generator (0) | 2014.06.20 |