기능

1. 저장
   • 이름은 중복저장 가능하지만 전화번호는 불가
   • 이름에는 특수문자 등 모든 글자 허용, 64글자 허용
   • ㄱ,ㄴ,ㄷ / a,b,c 순으로 저장
2. 즐겨 찾기
   • 중복된 이름으로 즐찾 등록시 해당 이름, 전화번호 모두 출력 후 ‘mark 전화번호’로 등록 유도
   • 즐겨찾기 해제 기능도 제공되어야함.
3. 검색
   • 이름으로 검색할 수 있어야함.
   • 중복된 이름을 검색했을 시에도 이름과 전화번호 모두 출력돼야됨.
4. 삭제
   • 이름:전화번호 로 삭제해야됨.
   • 해당 연락처 삭제시 즐겨찾기도 같이 해제되어야됨.
5. 출력
   • 모든 목록과 즐겨찾기 목록이 각각 출력되어야함.
6. 매뉴얼
   • 프로그램 시작 시 매뉴얼이 제공되어야함.
   • 저장 → add 이름:전화번호
   • 즐겨찾기 → mark 이름:전화번호
   • 즐겨찾기 목록 → cmark
   • 즐겨찾기 해제 → unmark 이름:전화번호
   • 모든 목록 → c
   • 검색 → find 이름
   • 삭제 → rm 이름:전화번호

자료구조

• 이중 연결리스트
• 이진트리
• 각각 구현 후 성능 측정

성능 측정

• 100만개의 데이터를 넣어본 뒤 데이터 검색 시간 측정

예상되는 결과

• 이중연결리스트
  • insertAtTail을 했기 때문에 끝에 노드를 검색했을때 시간이 더 오래 걸릴것임.
  • 평균 탐색 시간은 n/2 이므로 이진트리보다는 성능이 떨어질 것으로 예상.
• 이진트리
  • 이중 연결리스트보다는 처음노드(루트노드)와 끝노드(리프노드)의 검색시간 차이가 별로 없을것임.
  • 평균탐색시간은 log(n)이므로 연결리스트 보다는 성능이 좋을 것으로 예상.

결과

• test1, test2 … test 999999 순으로 데이터 입력함.
• 연결 리스트
  • find → 중복되는것도 찾아야되서 처음부터 끝까지 찾기때문에 별차이 없음
    • test1 → 0.048111 sec
    • test100000 → 0.054231 sec
    • test500000→ 0.055835 sec
    • test999999 → 0.051343 sec
  • mark
    • test1 → 0.000406 sec
    • test100000 → 0.004472 sec
    • test500000→ 0.027875 sec
    • test999999 → 0.046094 sec
  • rm
    • test1 → 0.000466 sec
    • test100000 → 0.004519 sec
    • test500000 → 0.028431 sec
    • test999999 → 0.45959 sec
  • c → 131.200652sec
• 이진 트리
  • find → 중복되는것도 찾아야되서 처음부터 끝까지 찾기때문에 별차이 없음
    • test1 → 0.000114 sec
    • test100000 → 0.000107 sec
    • test500000→ 0.000152 sec
    • test999999 → 0.000113 sec
  • mark
    • test1 → 0.000156 sec
    • test100000 → 0.000333 sec
    • test500000→ 0.000340 sec
    • test999999 → 0.000278 sec
  • rm
    • test1 → 0.000483 sec
    • test100000 → 0.000527 sec
    • test500000 → 0.000603 sec
    • test999999 → 0.000737 sec
  • c → 116.017627 sec

최종결론

• 연결리스트로 구현한 주소록보다 이진트리로 구현한 주소록의 성능이 더 좋다.
• 연결리스트로 검색시 시작노드와 끝노드의 검색시간에서 차이가 많이 났다.
• 이진트리는 시작노드(루트)와 끝노드(리프)의 검색시간 차이가 많이 나지 않았다.

의의

• 연결리스트의 검색시간을 보면 일정한 수칙으로 증가하는것을 실제로 볼 수 있어서 추상적으로만 학습했던 자료구조의 특성을 실제로 체감할 수 있었다.
• 만약 데이터가 더 많이 쌓이게 됐을때를 고려하면 자료구조의 중요성을 다시 한번 느낄 수 있었다.
• 구현하면서 겪었던 에러들을 메모리 추적하면서 디버깅함으로써 디버깅 능력과 문제해결 능력을 기를 수 있었다.
• c언어의 이중포인터 등을 사용하면서 중요한 개념을 복습할 수 있었다.

나아갈 점

• ADT를 거의 고려하지 않고 코드를 짰기 때문에 모듈간의 결합도가 다소 높다.
• 코드의 가독성이 다소 떨어진다.
• 고민하는 시간을 좀 더 갖고 다른 의미있는 프로젝트를 하면서 실력을 키울 필요가 있다.