[C언어 자료구조] 3.3 연결리스트 테스트
연결리스트를 사용하는 방법은 순차적으로 보관하거나 원하는 위치를 찾아 보관하는 방법이 대표적입니다. 동적 배열에서는 이 외에도 인덱스를 사용하는 방법이 있었지만 연결리스트를 사용할 때는 이 방법은 사용하지 않습니다.
따라서 테스트 코드는 크게 순차 보관하는 시뮬레이션과 원하는 순서로 보관하는 예로 구성할게요.
int main()
{
Simul_Seq();
Simul_Order();
return 0;
}
먼저 순차적으로 보관하는 테스트 코드를 작성합시다.
void Simul_Seq()
{
먼저 연결리스트를 동적으로 생성합니다.
LinkedList *linkedlist = New_LinkedList();
그리고 도서 개체를 생성하여 연결리스트에 순차 보관합니다. 순차 보관할 때는 LinkedList_PushBack 함수를 이용합니다.
LinkedList_PushBack(linkedlist,New_Book("C언어","홍길동",10));
LinkedList_PushBack(linkedlist,New_Book("C++언어","강감찬",20));
LinkedList_PushBack(linkedlist,New_Book("자료구조","김구",5));
LinkedList_PushBack(linkedlist,New_Book("알고리즘","이순신",9));
LinkedList_PushBack(linkedlist,New_Book("디자인패턴","정약용",13));
원하는 순서로 보관하였는지 테스트하기 위해 보관한 전체 자료를 출력합니다. 이 부분은 별도의 함수로 작성합시다.
View_LinkedList(linkedlist);
도서 제목으로 검색도 테스트 해 봅시다. 테스트를 위해 연결리스트에 보관한 도서와 보관하지 않은 도서의 제목으로 검색을 테스트합시다. 이 부분도 별도의 함수로 작성합시다.
Simul_Find(linkedlist,"C언어");
Simul_Find(linkedlist,"이데아이론");
그리고 도서 제목으로 보관한 자료를 삭제하는 것도 테스트합시다. 이 부분도 별도의 함수로 작성합시다.
Simul_Remove(linkedlist,"자료구조");
원하는대로 삭제가 이루어졌는지 확하기 위해 보관한 전체 자료를 출력합니다.
View_LinkedList(linkedlist);
시뮬레이션에 사용한 개체를 정리합니다. 이 부분도 별도의 함수로 작성합시다.
SimulEnd(linkedlist);
}
연결리스트에 보관한 모든 도서 정보를 출력하는 함수를 작성합시다.
void View_LinkedList(LinkedList *linkedlist)
{
Book *book = 0;
연결리스트의 시작 부분과 끝 부분을 얻어옵니다. 참고로 시작 부분은 보관한 자료 중에 맨 앞에 있는 노드의 위치 정보이고 끝 부분은 마지막 자료를 보관한 노드의 다음 노드 위치입니다.
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
순차적으로 이동하여 마지막 끝 위치에 도달할 때까지 보관한 도서를 얻어옵니다.
printf("-----보유 도서 목록-----\n");
for( ;seek!=end;seek = seek->next)
{
book = (Book *)(seek->data);
얻어온 도서 개체가 존재하면 도서 정보를 출력합니다.
if(book){ Book_View(book); }
}
}
도서 제목으로 검색하는 함수를 작성합시다.
void Simul_Find(LinkedList *linkedlist,const char *title)
{
Book *book = 0;
마찬가지로 연결리스트의 시작과 끝부분을 얻어옵니다.
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
순차적으로 이동하면서 끝부분까지 도서 정보를 얻어옵니다.
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
얻어온 도서가 유효할 때 입력 인자로 받은 도서 제목과 일치하면 도서 개체 정보를 출력하고 함수를 종료합니다.
if(book && (Book_CompareTitle(book,title)==0))
{
printf("검색 결과:");
Book_View(book);
return;
}
}
끝까지 탐색해도 원하는 도서를 찾지 못하면 이를 출력합니다.
printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
도서 제목으로 삭제하는 함수를 작성합시다. 검색 기능과 전체적인 흐름은 비슷하면 단지 찾고 난 후의 동작만 차이가 있습니다.
void Simul_Remove(LinkedList *linkedlist,const char *title)
{
Book *book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
if(book && (Book_CompareTitle(book,title)==0))
{
일치하면 연결리스트에서 해당 위치의 노드를 제거하고 도서 개체를 소멸한 후 함수를 종료합니다.
LinkedList_Erase(linkedlist,seek);
Delete_Book(book);
printf("삭제 성공!\n");
return;
}
}
존재하는 책이 없을 때 이 정보를 출력합니다.
printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
시뮬레이션을 마치고 자원을 해제하는 함수를 작성합시다.
void SimulEnd(LinkedList *linkedlist)
{
Book *book = 0;
연결리스트의 시작과 끝 부분을 얻어옵니다.
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
순차적으로 이동하면서 보관한 도서 개체를 얻어옵니다.
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
도서 개체가 유효하면 시뮬레이션에 사용한 해당 도서 개체를 소멸합니다.
if(book)
{
Delete_Book(book);
}
}
마지막으로 연결리스트를 소멸합니다.
Delete_LinkedList(linkedlist);
}
이제 특정 키 순으로 자료를 보관하는 시뮬레이션 함수를 작성합시다.
void Simul_Order()
{
먼저 연결리스트를 동적으로 생성합니다.
LinkedList *linkedlist = New_LinkedList();
그리고 지은이 순으로 도서 개체를 보관합니다. 이 부분은 별도의 함수로 작성합시다.
Simul_OrderAdd(linkedlist,New_Book("C언어","홍길동",10));
Simul_OrderAdd(linkedlist,New_Book("C++언어","강감찬",20));
Simul_OrderAdd(linkedlist,New_Book("자료구조","김구",5));
Simul_OrderAdd(linkedlist,New_Book("알고리즘","이순신",9));
Simul_OrderAdd(linkedlist,New_Book("디자인패턴","정약용",13));
원하는 순서대로 보관하였는지 확인하기 위해 연결리스트에 보관한 전체 도서 정보를 출력합니다.
View_LinkedList(linkedlist);
도서 검색에 관한 테스트와 삭제에 관한 테스트를 수행한 후에 시뮬레이션을 종료합니다.
Simul_Find(linkedlist,"C언어");
Simul_Find(linkedlist,"이데아이론");
Simul_Remove(linkedlist,"자료구조");
View_LinkedList(linkedlist);
SimulEnd(linkedlist);
}
지은이 순으로 도서 개체를 보관하는 함수를 작성합시다.
void Simul_OrderAdd(LinkedList *linkedlist,Book *book)
{
Book *stored_book = 0;
연결리스트의 시작과 끝 부분을 얻어옵니다.
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
순차적으로 이동하면서 보관한 도서 개체를 얻어옵니다.
for( ;seek!=end;seek=seek->next)
{
stored_book = (Book *)(seek->next);
만약 보관한 도서의 지은이 이름이 입력 인자로 받은 도서의 이름보다 크거나 같으면 보관할 위치를 찾은 것입니다.
if(stored_book && (Book_CompareAuthor(stored_book,book->author)>=0))
{
break;
}
}
찾은 위치 뒤에 도서를 보관합니다.
LinkedList_Insert(linkedlist,seek,book);
}
//Program.c
#include "LinkedList.h"
#include "Book.h"
void View_LinkedList(LinkedList *linkedlist)
{
Book *book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
printf("-----보유 도서 목록-----\n");
for( ;seek!=end;seek = seek->next)
{
book = (Book *)(seek->data);
if(book)
{
Book_View(book);
}
}
}
void SimulEnd(LinkedList *linkedlist)
{
Book *book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
if(book)
{
Delete_Book(book);
}
}
Delete_LinkedList(linkedlist);
}
void Simul_Find(LinkedList *linkedlist,const char *title)
{
Book *book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
if(book && (Book_CompareTitle(book,title)==0))
{
printf("검색 결과:");
Book_View(book);
return;
}
}
printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
void Simul_Remove(LinkedList *linkedlist,const char *title)
{
Book *book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
for( ;seek!=end;seek=seek->next)
{
book = (Book *)(seek->data);
if(book && (Book_CompareTitle(book,title)==0))
{
LinkedList_Erase(linkedlist,seek);
Delete_Book(book);
printf("삭제 성공!\n");
return;
}
}
printf("<%s> 책을 찾을 수 없습니다.\n",title);
}
void Simul_Seq()
{
LinkedList *linkedlist = New_LinkedList();
LinkedList_PushBack(linkedlist,New_Book("C언어","홍길동",10));
LinkedList_PushBack(linkedlist,New_Book("C++언어","강감찬",20));
LinkedList_PushBack(linkedlist,New_Book("자료구조","김구",5));
LinkedList_PushBack(linkedlist,New_Book("알고리즘","이순신",9));
LinkedList_PushBack(linkedlist,New_Book("디자인패턴","정약용",13));
View_LinkedList(linkedlist);
Simul_Find(linkedlist,"C언어");
Simul_Find(linkedlist,"이데아이론");
Simul_Remove(linkedlist,"자료구조");
View_LinkedList(linkedlist);
SimulEnd(linkedlist);
}
void Simul_OrderAdd(LinkedList *linkedlist,Book *book)
{
Book *stored_book = 0;
Link seek = LinkedList_Begin(linkedlist);
Link end = LinkedList_End(linkedlist);
for( ;seek!=end;seek=seek->next)
{
stored_book = (Book *)(seek->next);
if(stored_book && (Book_CompareAuthor(stored_book,book->author)>=0))
{
break;
}
}
LinkedList_Insert(linkedlist,seek,book);
}
void Simul_Order()
{
LinkedList *linkedlist = New_LinkedList();
Simul_OrderAdd(linkedlist,New_Book("C언어","홍길동",10));
Simul_OrderAdd(linkedlist,New_Book("C++언어","강감찬",20));
Simul_OrderAdd(linkedlist,New_Book("자료구조","김구",5));
Simul_OrderAdd(linkedlist,New_Book("알고리즘","이순신",9));
Simul_OrderAdd(linkedlist,New_Book("디자인패턴","정약용",13));
View_LinkedList(linkedlist);
Simul_Find(linkedlist,"C언어");
Simul_Find(linkedlist,"이데아이론");
Simul_Remove(linkedlist,"자료구조");
View_LinkedList(linkedlist);
SimulEnd(linkedlist);
}
int main()
{
Simul_Seq();
Simul_Order();
return 0;
}
동적 배열과 연결리스트를 설계 및 구현하고 이를 테스트해 보았습니다. 동적 배열은 자료를 보관하는 저장소가 하나의 메모리여서 시작 위치에서 상대적 거리에 있는 원소를 참조하는 기능을 제공한다는 점을 제외하면 대부분 사용 방법이 비슷하다는 것을 알 수 있습니다. 좀 더 세부적으로 비교한다면 동적 배열에 원하는 위치에 자료를 보관하면 최악의 경우 보관한 자료 전체를 이동하지만 연결리스트에서는 네 개의 링크만 조절하면 가능함을 알 수 있습니다. 마찬가지로 자료를 삭제할 때 배열에서는 최악의 경우 보관한 자료 전체를 이동하지만 연결리스트에서는 두 개의 링크만 조절하면 가능합니다.
이 외에도 보관한 자료를 통합하거나 분리하는 등의 기능을 제공한다면 연결리스트가 보다 효과적으로 제공할 수 있음을 알 수 있는데 이 부분은 이 책에서는 논하지 않겠습니다. 여러분 스스로 해결해 보세요.
'언어 자료구조 알고리즘 > 디딤돌 자료구조 (C언어)' 카테고리의 다른 글
| [C언어 자료구조] 4.3 큐 테스트 (0) | 2016.11.26 |
|---|---|
| [C언어 자료구조] 4.2 큐 구현 (0) | 2016.11.26 |
| [C언어 자료구조] 4.1 큐 설계 (0) | 2016.11.26 |
| [C언어 자료구조] 4. 큐(Queue) (0) | 2016.11.26 |
| [C언어 자료구조] 3.4 연결리스트 소스 코드 (0) | 2016.11.26 |
| [C언어 자료구조] 3.2 연결리스트 구현 (0) | 2016.11.26 |
| [C언어 자료구조] 3.1 연결리스트 설계 (0) | 2016.11.26 |
| [C언어 자료구조] 3. 연결리스트 (0) | 2016.11.26 |
| [C언어 자료구조] 2.4 동적 배열 소스 코드 (0) | 2016.11.26 |
| [C언어 자료구조] 2.3 동적 배열 테스트 (0) | 2016.11.26 |