[자료구조/C언어] - ⑥ 리스트 - 원형연결리스트 삽입 삭제 추가

원형연결리스트

원형연결리스트는 마지막 노드의 링크가 첫 번쨰 노드를 가르키는 리스트 입니다.

 

 

 

원형연결리스트 추가 

 

#include <stdio.h> void add_node(Listnode* head,int num){ Listnode *p,*q,*temp; q=create_node(); q->data=num; p=head; if(p->link==NULL){ p->link=q; q->link=head->link; return; } //처음 링크에 아무 정보도 들어있지 않을 때 else{ /*링크의 마지막에 추가하기 때문에 끝으로 밀어줌 여기서 마지막 노드는 헤드의 링크를 가르키기 때문에 p->link!=head->link 일때 까지만 반복문을 돌려준다*/ do{ p=p->link; }while(p->link!=head->link); p->link=q; q->link=head->link; //마지막의 q의링크를 처음노드로 바꿔준다 } }

 

 

 

#include <stdio.h> void insert_node(Listnode* head,int num){ Listnode *p,*q,*temp; int data; p=head; q=create_node(); printf("집어넣을 data 입력 : "); scanf("%d",&data); q->data=data; if(head->link==NULL){ head->link=q; q->link=head->link; return; } //데이터가 없을때 else{ //앞에 삽입하려는 노드의 위치가 처음 노드일때 if(p->link->data==num){ q->link=p->link; do{ p=p->link; }while(p->link!=head->link); p->link=q; head->link=q; return; } //나머지 경우 do{temp=p; p=p->link; if(p->data==num){ q->link=temp->link; temp->link=q; return; } }while(p->link!=head->link); } printf("입력하신 데이터를 찾을 수 없습니다.\n"); }

넣고싶은 위치에 원형연결리스트  삽입

 

노드 앞에 삽입하는 경우는 3가지를 생각해줘야 합니다.

1. 헤드가 널일때

 

아무 정보도 없기 때문에 첫 노드가 된다

 

 

 

 

2. 앞에 삽입하려는 노드의 위치가 처음 노드일때

 

새로 생성 된 q는 p를 가르키고 마지막 노드가 q를 가르키게 하기위해

노드를 마지막까지 밀어준다. 헤드포인터가 가르키는 위치는 q로 바꿔준다

 

 

 

3. 가운데에 삽입

 

 

가운데에 추가하는 경우입니다.
데이터를 가져와 그 데이터와 일치하는 노드가 있다면 그 노드의 앞에 추가가 될 것 입니다.
그렇다면 찾는 값이 들어있는 노드와 그 전노드를 알아야합니다.
추가할 노드의 링크는 찾는 값이 있는 노드가 될 것이고,
그 전의노드의 링크는 추가할 노드가 될 것 입니다.

 

 

원형연결리스트 삭제

 

#include <stdio.h> void delete_node(Listnode* head,int num){ Listnode * p,*temp; p=head; if(head->link==NULL){ printf("삭제할 데이터가 없습니다\n"); return; } //데이터가 없을 경우 else{ if(p->link->data==num){ if(p->link->link==p->link){ p=p->link; head->link=NULL; free(p); return; } temp=p->link; do{ p=p->link; }while(p->link!=head->link); p->link=temp->link; head->link=temp->link; free(temp); return; } do{temp=p; p=p->link; if(p->data==num){ temp->link=p->link; free(p); return; } }while(p->link!=head->link); printf("입력하신 데이터를 찾을 수 없습니다.\n"); } }

 

 

 

이 함수들을 이용하여 메인에서 원형연결리스트를 만들어 보았습니다