#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct nodetype{ // 연결리스트 node를 만듭니다
int data;
struct nodetype *next_ptr;
// node(노드)는 자료 + 연결 이라고했죠?
// data라는 자료와 다음 노드를 연결하는 포인터 next_ptr로 구성했습니다
}node;
typedef struct listtype{ // 리스트의 형태를 구성합니다.
int count;
node headnode; // 해더 노드를 사용했습니다.
}list;
list *makelist(){ // 리스트를 생성하는 함수입니다.
list *returnlist;
returnlist = (list *)malloc(sizeof(list));
if ( returnlist != NULL ){ // 생성 후 반환할 리스트를 만들어 동적할당후 검사 단계
memset(returnlist,0,sizeof(list)); // 동적할당이 잘됬다면 list의 변수를 0으로 초기화!!
returnlist -> headnode.next_ptr = &returnlist -> headnode;
}else{
printf("Error\n");
return 0;
}
return returnlist; // 생성된 리스트를 반환합니다.
}
void Add(list *Plist,int p,node d){ // 리스트에 자료를 추가하는 함수입니다.
if ( p < 0 || p > Plist -> count ){ // 위치의 타당성을 검사합니다.
printf("Error!! value of position\n");
}else{
int i;
node *temp = &Plist -> headnode;
// temp라는 임시저장소를 만듭니다. 앞으로 temp는 자주 나올텐데...
// 리스트 형태에서 자료사이를 이동하는 역할을 해준다고 생각하면 됩니다.
node *newnode = (node *)malloc(sizeof(node)); // 받은 data노드를 저장하여 연결시키는 node입니다.
if ( newnode != NULL ){ // 동적할당이 잘되었는지 검사 후~
*newnode = d;
for( i = 0 ; i < p ; i++ ){
temp = temp -> next_ptr; // temp를 이용하여 원하는 위치로 이동 후~
}
newnode -> next_ptr = temp -> next_ptr; // 자료 값을 넣어 줍니다.
temp -> next_ptr = newnode; // 전에 리스트에서 설명한 순서에 의거합니다~!!
Plist -> count++; // 저장된 자료의 개수를 한단계 올립니다.
return ;
}else{
printf("Error!!\n");
return ;
}
}
}
void Del(list *Plist,int p){ // 리스트에서 자료를 제거하는 함수입니다
int i;
node *temp = &Plist -> headnode; // 역시나 temp를 생성했습니다.
node *free_node; // free_node는 나중에 삭제된 자료가 메모리상에서 남아있지 않게 하기 위해서 필요합니다.
if ( p < 0 || p >= Plist -> count ){ // 위치의 타당성을 점검한 후~
printf("Error!! value of positon\n");
return;
}else{
for ( i = 0 ; i < p ; i++ ){
temp = temp -> next_ptr; // 원하는 위치로 이동한 후~
}
free_node = temp -> next_ptr; // 삭제될 위치의 노드를 free_node에 저장합니다.
temp -> next_ptr = temp -> next_ptr -> next_ptr; // 후에 과감히 삭제되는 노드의 연결을 끈고,
Plist -> count--; // 저장된 자료의 개수를 한단계 내립니다.
if ( free_node != NULL ){ // free_node에 값이 잘들어있는지를 본후에
free(free_node); // 메모리상에서 삭제 시켜줍니다~
}
return;
}
}
void Seek(list *Plist, int p){ // 원하는 위치의 데이터를 찾는 함수입니다.
// 배열에서 구현한것과 비교해보면 줄수도 길어지고 복잡해보이죠?
int i;
node *temp = &Plist -> headnode; // 역시나 temp의 등장!!
if ( p < 0 || p >= Plist -> count ){ // 위치의 타당성을 점검한후~
printf("Error!! value of positon\n");
return;
}else{
for ( i = 0 ; i <= p ; i++ ){
temp = temp -> next_ptr; // 원하는 위치로 이동 후~
}
printf("%d번의 자료 : %d\n",p,temp -> data); // 출력해줍니다~
return ;
}
}
// 개인의 편의에 따라 return 타입을 정해줘 return해도 됩니다~
void Display(list *Plist){ // 모든 자료를 보는 함수입니다.
node *temp = NULL; // temp가 있죠?
int i = 0;
temp = &Plist -> headnode;
for ( i = 0 ; i <= Plist -> count ; i++ ){
temp = temp -> next_ptr; // 모든 데이터를 훑으면서 자료를 출력합니다.
if ( i == Plist -> count ){ // 순회시 해드노드에 도착하면 다음 노드로 이동...
temp = temp -> next_ptr;
}
printf("%d번째 자료 : %d\n",i % Plist->count,temp -> data);
}
}
//main은 언제나 그랬듯이.. 자신의 편이를 생각해서...
int main(){
list *LL;
LL = makelist();
while(1){
int select;
int position;
node datanode;
printf("\n\n\n현재 %d개의 자료 저장중\n",LL -> count);
printf("기능을 선택해주십시요.\n");
printf("1.자료저장\t2.자료삭제\t3.자료검색\t4.전체자료보기\t5.종료\n");
scanf("%d",&select);
switch(select){
case 1:
printf("저장 위치 : ");
scanf("%d",&position);
printf("저장 자료 : ");
scanf("%d",&datanode.data);
Add(LL,position,datanode);
break;
case 2:
printf("삭제할 자료 위치 : ");
scanf("%d",&position);
Del(LL,position);
break;
case 3:
printf("찾을 자료 위치 : ");
scanf("%d",&position);
Seek(LL,position);
break;
case 4:
Display(LL);
break;
case 5:
if( LL != NULL ){
free(LL); // 마지막 종류시에는 자료를 메모리에서도 지워줍니다.
}
return ;
default:
printf("You don't press colect number");
}
}
}
-------------------------------------------------------------------------------------------------
단순연결리스트와 다른 곳만을 하이라이트로 칠했다...
위의 구조는 다음과 같다...
원형 연결 리스트의 구조이다. 여기 또한 전에 단순연결리스트에서 했듯이 더미노드(해더노드)를 사용하였다.
이에 의해 추가와 삭제에서 이점이 생겼지만, 순환시 더미노드로왔을대 건너띄는 과정이 필요하다~
Display함수에서 잘 나타나 있을 것이다~!
여기서 끝나는 것이아니라... 한단계 더나아가 보자...
리스트 소개시 잠깐 소개했던
<<해더 포인터 vs 해더 노드>>
해더 노드를 이용했을때는 자료를 추가 삭제시 일정한 알고리즘에 의거하여 행동을 할 수가 있다.
만약, 더미노드가 아닌 해더포인터를 이용했다면..?? 자료의 구조는 다음과 같을 것이다.
위처럼 해더 포인터는 처음 노드를 지시할뿐 순환에 참가하지 않는다.
이에의해 추가, 삭제시 알고리즘이 경우의 수에 달라지게 된다.
일단 추가를 할때의 알고리즘을 알아보자...
ⓐ 첫 번째 자리(Index 0)에 자료를 추가하는가? ▷ No <Case 1>
YES ▽
ⓑ "ⓐ"의 경우일 때, 자료구조가 비어있는가(count = 0)? ▷ No <Case 2>
YES ▽
<Case 3>
자... 무려 3가지의 경우의 수가 나온다. 이것을 왜 다 따져야 하는가?
ⓐ의 경우는 마지막 노드의 처리문제가 상황에 따라 달라지고,
ⓑ의 경우는 해더 노드의 처리문제가 상황에 따라 달라지기 때문에 나눠서 생각해야 한다.
이번엔 삭제 할때의 알고리즘을 알아보자...
ⓐ 첫 번째 자리(Index 0)의 자료를 삭제하는가? ▷ No <Case 1>
YES ▽
ⓑ "ⓐ"의 경우일 때, 리스트의 마지막 노드인가? ▷ No <Case 2>
YES ▽
<Case 3>
자... 여기서도 3가지의 경우의 수가 나온다. 따지는 이유를 살피자면...
ⓐ 첫 번째 자리의 노드이냐 아니냐에 따라서 처리 문제가 달라지고,
ⓑ 마지막 노드냐 아니냐에 따라서 해더포인터의 처리 문제가 달라지기 때문에 나눠야한다.
이렇게 해더 포인터를 사용하면 해더 노드를 사용할때보다 추가/삭제시 생각해줘야 할 것이 많아진다.
----------------------------------------------------------------------------------------
흠... 이제와서 엄청난 오타를 발견했습니다.
프로그램을 돌리다보니 "5. 종류" 라고 써져 있더군요-_-;; 당황스럽지만... 전에 만들었던것이 다 그럴것 같다는...
므튼 이번엔 원형 연결리스트에 대해서 알아보고(실제로 새로한건 한줄뿐이잖아!!)
한개 별로 없다고 생각되어 해더노드와 해더포인터의 차이에 대해서 알아 봤습니다.
P.S : 헤더라고 쓰면서 Header라고 안하고 Head라고 쓰는건... =_= 제맘입니다.