Linked list

소개

문제1> 아래와 같은 기능을 포함하는 List class를 정의하고 포인터를 사용하여 구현하시오.(즉, Linked-list로 구현하시오.)
문제2> 임의의 정수 값 100개를 랜덤하게 입력 받은 후에 위에서 정의 및 구현한 List 클래스를 사용하여 리스트로 구성한다. 그리고 리스트를 구성하는 값들을 오름차순으로 정렬(sorting)하여 출력하는 프로그램을 작성하시오.
소스 및 출력 파일은 문서 내에 있습니다.

목차

문제1> 아래와 같은 기능을 포함하는 List class를 정의하고 포인터를 사용하여 구현하시오.(즉, Linked-list로 구현하시오.)
문제2> 임의의 정수 값 100개를 랜덤하게 입력 받은 후에 위에서 정의 및 구현한 List 클래스를 사용하여 리스트로 구성한다. 그리고 리스트를 구성하는 값들을 오름차순으로 정렬(sorting)하여 출력하는 프로그램을 작성하시오

본문내용

문제1> 아래와 같은 기능을 포함하는 List class를 정의하고 포인터를 사용하여 구현하시오.(즉, Linked-list로 구현하시오.)

◈ 리스트 길이를 구하는 연산
◈ 리스트를 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 차례로 읽는 연산
◈ i 번째 항목을 찾는 연산
◈ 리스트에서 항목 elem을 찾는 연산
◈ i 번째 항목에 새로운 값을 저장시키는 연산
◈ i 번째 위치에 새로운 항목을 삽입시키는 연산
◈ i 번째 위치에 새로운 항목을 제거시키는 연산


문제2> 임의의 정수 값 100개를 랜덤하게 입력 받은 후에 위에서 정의 및 구현한 List 클래스를 사용하여 리스트로 구성한다. 그리고 리스트를 구성하는 값들을 오름차순으로 정렬(sorting)하여 출력하는 프로그램을 작성하시오.


<문제 해결>

우선 헤더파일에 링크드 클래스를 선언하였다. 이 부분에는 리스트에 필요한 문제에서 주어진 기본 함수들과 멤버 변수들을 선언하였다. 그리고 그 함수들의 구현은 cpp 파일 안에 구현을 하였는데, 우선 자료구조 책에 나온 표준적인 인터페이스로 구현하였고, ElementType을 별도로 typedef로 선언하여 여기에 중점을 두어 리스트에 들어갈 요소가 바뀔시 함수를 모두 고칠 필요 없이 typedef만 변경하면 요소 타입도 바꿀 수 있도록 하여 함수부분을 중점적으로 구현하였다.

그리고 각 함수마다 고려되어야 할 예외사항들을 최대한 고려하여 처리해주었다. 전체적으로 대부분의 함수에서 연결리스트라 head와 tail 부분에서
특수한 처리에 중점을 두어 구현하였다.
구현시 가장 어려웠던 것은 정렬부분인데, 선택정렬로 구성할시 모든 하나 하나 위치를 찾아갈 때 많은 시간 복잡도가 예상되므로 버블정렬로서 구현하였다. 정렬부분에서도 마찬가지로 첨에 버블 정렬시작할 때 head 부분의 특수한 코드 처리와 한번 for루프를 돌렸을때 맨 마지막 요소는 tail 처리를 해야되는 부분도 유의하여 문제를 풀어나갔다. (문제를 풀며 간단하게
주석처리로 설명을 달아 놓았다.)

참고자료

· 없음