연결리스트 명령 프로그램
연결리스트의 기본을 이해하고 나면 다양한 연산을 구현해 보아야 한다. 파이썬에 있는 리스트 명령을 전부 구현해 볼 수 있는데, 연결리스트는 자꾸 연습하다 보면 어느 순간에 편안해지는데, 그 시간이 빨리 오지는 않는다. 프로그램이 중지되거나 포인터가 말썽을 일으키는 긴 시간을 견디어낸 사람에게만 그 편안해지는 순간이 올 수 있다.
이를 위해 연결리스트의 여러 가지 기능을 연습할 수 있는 명령문 기반의 프로그램을 만들어보려고 한다. 이 프로그램은 append, extend, contains, compare 등 다양한 연산을 내맘대로 정의하여 실행해 볼 수 있다. 간단하게 하기 위해 리스트에는 int 정수값만 들어있다고 보자. 예시 실행화면은 아래와 같다.
(1) append (2) extend (3) contains (4) let
(5) compare (6) print (7) end
>> let a 1 2 3 0 // a 리스트 만들어 등록
>> let b 6 7 8 9 0 // b 리스트 만들어 등록
>> print a // a 리스트 출력하기
[ 1 2 3 ]
>> append 5 a // a 리스트에 5 추가하기
[ 1 2 3 5 ]
>> extend a b // a에 b 리스트 붙이기
[ 1 2 3 5 6 7 8 9] // a를 출력
>> contains 4 a // a 리스트에 4가 있는지 검사
false
>> append 4 b // b 리스트에 4를 추가하기
[6 7 8 9 4]
>> contains 4 a // a에 4가 들어있는가?
false
>> let c 0 // 빈 리스트를 만들어 c로 등록여기에 reverse, count, remove 등 추가 연산을 얼마든지 더해볼 수 있다.
그럼 먼저 리스트 구조체와 기본 연산을 몇가지 정의하자.
typedef int element;
typedef struct ListNode { // 노드 타입을 구조체로 정의한다. element data;
struct ListNode* link;
element data;
} ListNode;다음은 리스트에 요소를 맨뒤에 추가하는 insert_last 함수와 print_list 함수를 구현한다. 이것은 여러분에게 맡기겠다.
ListNode* insert_last(ListNode* head, int value);
void print_list(ListNode* head);이제 명령문 기반의 리스트 처리를 위한 기본 틀을 만들어 보자. 먼저 리스트에 이름을 붙여 생성하는 것이 필요하다. 위의 실행 예제에서 let 명령문이 여기에 해당한다. 새로운 리스트를 만들고 이름을 붙이면 그 이름으로 이후에 리스트에 대한 연산을 수행할 수 있게 된다.
기본 자료구조는 이름 이차원 배열과 리스트 포인터 배열이다. let 명령으로 새로운 이름의 리스트가 생성되면 그것을 이름 배열과 리스트 포인터 배열의 같은 위치(cc번째)에 저장한다.
char names[20][10];
ListNode* namelist[20] = { 0 };
int cc = 0;이것은 전통적인 C 언어의 이름과 값을 연결하여 저장하는 방법이다. 이 배열을 이용해서 이름에 해당하는 리스트를 찾는 것은 다음과 같다.
int find_namelist(char* buf) {
for (int i = 0; i < cc; i++)
if (strcmp(names[i], buf) == 0)
return i;
return -1;
}이름으로 그 리스트를 출력하게 하는 함수도 다음과 같이 작성할 수 있다.
void print_namelist(char* name) {
int index = find_namelist(name);
if (index == -1)
printf("없는 이름입니다.\n");
printf("%s = ", name);
print_list(namelist[index]);
}그럼 이제 "let" 명령을 구현해 보자. let 명령은 다음과 같이 사용하게 된다.
>> let a 1 2 3 4 0
그럼 [1, 2, 3, 4] 배열을 만들어 a라는 이름으로 저장하게 된다.
// 이름과 0으로 끝나는 숫자 여러 개를 입력받아 리스트를 만들고
// 이름으로 namelist에 저장한다.
// names[cc]번째에 이름, namelist[cc]번째에 리스트 포인터를 저장
void let() {
int num;
scanf_s("%s", names[cc], 10);
ListNode* head = NULL, *p;
while (1) {
scanf_s("%d", &num);
if (num == 0) break;
head = insert_last(head, num);
}
namelist[cc] = head;
cc++;
}단, 이코드는 같은 이름으로 let 명령이 다시 들어왔을 때 새로운 것을 제일 끝에 추가하므로 나중에 실행된 let 명령문의 효과를 잃게 된다. (찾을 때는 앞에서부터 이름이 같은 것을 찾으므로) 이것을 해결하기 위해서는 같은 이름이 있는지 찾고 있으면 그 리스트 포인터를 바꾸어 주어야 한다. 이 때 이전에 있던 리스트는 모두 메모리 해제해 주어야 한다. (C 언어와 같이 사는 것이 쉽지만은 않다!!)
그럼 이제 기본적인 준비를 마쳤으니 명령문을 처리하는 부분을 생각해 보자. 명령문은 모두 7개인데, 명령을 받아서 그에 대응하는 번호로 바꾸어 취급하게 된다.
명령문을 받으면 그것에 대응하는 메뉴의 번호를 돌려주는 부분을 다음과 같이 구현할 수 있다.
const char* menu[] = { "append", "extend", "contains", "let", "compare", "print", "end"};
int readmenu() {
char buf[10];
printf(">> ");
scanf_s("%s", buf, 9);
for (int i = 0; i < 6; i++) {
if (strcmp(buf, menu[i]) == 0)
return i;
}
return -1;
}위 함수는 7개의 명령문을 배열로 만들어두고 입력된 문자열을 비교하여 몇번 명령인지를 돌려준다. 이 때 명령이 잘못 들어왔다면 -1을 돌려준다. 이제 명령 기반으로 입력과 연산을 수행하는 부분을 만들 준비가 되었다. 기본 구조는 아래와 같다.
char buf[10];
printf("(1) append (2) extend (3) contains (4) let\n(5) compare (6) print (7) end\n\n");
int m = readmenu();
while (1) {
switch (m) {
case 0: // (1) append 3 a
break;
case 1: // (2) extend a b
break;
case 2: // (3) contains 3 a
break;
case 3: // (4) let a 1 2 3 4 0
break;
case 4: // (5) compare a b
break;
case 5: // (6) print a
break;
default: gets_s(buf, 10);
}
if (m == 7) // (7) end
break;
m = readmenu();
}그럼 이제 리스트 연산을 구현해 볼 준비가 모두 되었다. 추가되어야 할 함수는 다음과 같다.
// head가 가리키는 리스트를 그대로 복사한 새로운 리스트를 만들어 리턴
// -- 차례로 같은 값을 가지는 노드 만들어 insert_last 함
ListNode* copy(ListNode* head) {
}
// left 리스트 끝에 right 리스트를 복사하여 붙인다
ListNode* extend(ListNode* left, ListNode* right) {
}
// head 리스트에 num이 들어있으면 1, 아니면 0을 반환
int contains(int num, ListNode* head) {
}
// left와 right가 가리키는 리스트가 같으면 1, 다르면 0을 리턴
int compare(ListNode* left, ListNode* right) {
}이외에도 다양한 명령을 추가하여 구현해 보기 바란다. 이상에서 설명된 전체 코드는 다음 링크에서 찾을 수 있다.