c·c++/c 프로그래밍

연결 리스트 - 선행노드를 모르고 삭제하기

바로이순간 2014. 6. 29. 15:49

보통 연결 리스트에서는 선행 노드를 알아야만 노드를 삭제할 수 있다. 

그러나 다음과 같이 하면 선행 노드를 모르고도 노드를 삭제할 수 있다. 


먼저 원형 연결 리스트라고 가정하자. 어떤 노드를 가리키는 포인터 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