Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 강의 노트를 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)
The C Programming Language 2nd Ed. by Kerninghan & Ritchie ( Ch.6, list )
C언어의 자기 참조 구조체(self-referential structure)를 사용하여 리스트 프로그램을 작성하자. 리스트는 가변적인 원소를 다룰때 편리한 자료 구조이다. 편의상, 비어있는 리스트를 []로, 원소를 포함하고 있는 리스트를 [1, 2, 3]과 같이 표현하기로 한다. 또한 정수를 원소로 하는 리스트를 고려한다.
리스트의 노드는 구조체 struct Node 형으로 표현한다. 비어있는 리스트 []는 struct Node* 형의 NULL로 정의한다. 새로운 노드는 makeNode 함수를 사용해서 만든다. print 함수로 리스트의 모든 원소를 화면에 출력하고, insert와 del 함수로 새로운 원소를 리스트에 추가 삭제한다.
// list.h
#ifndef LIST_H
#define LIST_H
struct Node {
int v;
struct Node* next;
};
struct Node* makeNode(int v);
void print(struct Node* list);
struct Node* insert(int v, struct Node* list);
struct Node* del(int v, struct Node* list);
#endif // LIST_H
list.h에서 정의한 구조체 형과 선언한 함수를 이용하여 리스트를 새로 만들고, 원소를 추가 삭제하는 코드를 다음과 같이 작성할 수 있다.
// main.c
#include <stdio.h>
#include "list.h"
int main() {
struct Node* emptyList = NULL; // 비어있는 리스트 []
struct Node* l1 = makeNode(1); // 리스트 [ 1 ]
struct Node* l2 = makeNode(2); // 리스트 [ 2 ]
struct Node* l3 = insert(1, l2); // 리스트 [ 1, 2 ] insert함수는 리스트 앞에 원소를 추가
struct Node* l4;
struct Node* l5;
print(l3); // 1과 2를 출력
l4 = del( 2, l3 ); // l4 => [ 1 ]
l5 = del( 1, l4 ); // l5 => [ ]
return 0;
}
list.h에서 선언한 함수들을 작성한다. 간단한 makeNode 함수와 print 함수 부터 시작하자.
// list.h
#include <stdlib.h> // malloc
#include "list.h"
struct Node* makeNode( int v ) {
struct Node* p =
(struct Node*) malloc( sizeof(struct Node) );
p->v = v;
p->next = NULL;
return p;
}
void print( struct Node* list ) {
while ( list != null ) { // 주어진 list가 NULL이 아니면
printf("%d ", list->v); // 원소를 포함하고 있고, 이 원소를 출력
list = list->next; // list로 하여금 다음 노드를 가리키도록 이동
}
}
리스트와 추가할 정수를 인자로 받는 insert 함수에서 이 정수를 리스트의 맨 앞에 추가한다고 가정하자.
struct Node* insert( int v, struct Node* list ) {
struct Node* p;
p = makeNode(v); // 정수 v만을 포함하는 리스트 [ v ]를 만들어 p가 가리키도록 하고
p->next = list; // p의 next가 list를 가리키도록 하면 [ v ] + list가 된다.
return p;
}
delete 함수는 다소 복잡하다. 경우의 수를 따져 봐야 한다. 먼저, 비어있는 리스트와 비어있지 않은 경우로 분류한다. 비어있지 않은 경우는 첫번째 원소가 삭제하고자 하는 수와 일치하는지 여부에 따라 나누어 고려한다.
struct Node* del( int v, struct Node* list ) {
struct Node* p;
struct Node* q;
p = list;
if ( p == NULL ) return NULL; // list가 []
else if ( p->v == v ) { // list의 길이 >= 1 && 첫번째 원소가 v와 일치
q = p->next;
free( p );
return q;
}
else { // list의 길이 >= 1 && 첫번째 원소가 v와 일치하지 않는 경우
while ( p->next != NULL ) {
// p->next가 NULL이 아니면, list의 길이 >= 2
if ( p->next->v == v ) { // 다음 노드의 v가 삭제할 v와 일치하면
q = p->next->next; // 다음 노드가 가리키는 다음 리스트의 주소를 q에 저장
free ( p->next ); // 다음 노드를 삭제
p->next = q; // 현재 노드의 다음으로 q를 지정
break; // 리스트에 v가 여러번 나타나더라도 한번만 삭제
}
else {
p = p->next; // v와 일치하지 않으면 다음 노드로 이동
}
}
return list;
}
}
마지막으로 사용자의 명령을 받아 리스트에 원소를 추가하고 삭제하는 프로그램을 만든다. insert 10이라는 명령어를 입력하면 현재 리스트 (처음에는 비어있는 리스트로 가정)에 10을 추가하고, delete 7 명령어를 입력받으면 현재 리스트에서 7을 삭제한다. 만일 현재 리스트에 7이 여러 번 나타나면 제일 앞에 나타난 7만 삭제한다. 이 명령어들을 입력받아 리스트에 추가 삭제한 다음 결과 리스트를 화면에 출력한다. quit 명령을 입력하면 프로그램은 종료한다.
// main.c
#include <stdio.h>
#include "list.h"
int main() {
struct Node* list;
char cmd[100]; // insert, delete, quit
int n;
list = NULL; // list를 비어있는 리스트 []로 초기화
do {
printf("Enter insert n or delete n (or quit): ");
scanf("%s", cmd);
if ( strcmp(cmd, "insert") == 0 ) {
scanf("%d", &n);
list = insert(v, list);
} else
if ( strcmp(cmd, "delete") == 0 ) {
scanf("%d", &n);
list = del(v, list);
} else
if ( strcmp(cmd, "quit") == 0 ) {
break;
}
print( list );
} while ( 1 )
return 0;
}
이 프로그램은 다음과 같이 실행된다.
Enter insert n or delete n (or quit): insert 1 1 Enter insert n or delete n (or quit): insert 2 2 1 Enter insert n or delete n (or quit): insert 3 3 2 1 Enter insert n or delete n (or quit): delete 2 3 1 Enter insert n or delete n (or quit): delete 7 3 1 Enter insert n or delete n (or quit): delete 1 3 Enter insert n or delete n (or quit): delete 3 Enter insert n or delete n (or quit): quit