항해99 5기 CS Study - 7장 데이터 구조와 처리

4. 문자열

• 정의: 여러 문자로 이뤄진 시퀀스
• 문자열을 연산할 때도 길이를 알아야 함
• 길이가 변할 수 있는 가변 문자열 데이터에 작용하는 프로그램이 많기 때문
• 접근 방법
  • 문자열 안에 길이를 저장
    • 첫번째 바이트에 길이를 넣는다 -> 문자열 길이가 255자로 제한되는 단점
    • 더 긴 문자열을 지원하다보면 길이를 저장하기 위한 바이트 수가 문자열 길이를 넘어설 수 있다
    • 문자열은 바이트라서 메모리 정렬이 그때그때 다를 수도
  • C 언어
    • 문자 배열에 들어 있는 문자열 데이터 끝에 바이트를 하나 추가하고, 문자열의 끝을 표시하는 문자로 NUL을 넣는다
    • 저장이 쉽다는 장점
    • 부가 비용이 들지 않음
    • 문자열 길이를 알아내려면 문자열을 스캔하면서 문자 수를 세야 한다는 단점
      

5. 복합 데이터 타입

• 구조체: 원하는 대로 데이터 타입 (=스위트) 을 만들 수 있는 방법
• 멤버: 구조체 스위트 안에 있는 여러 방
• 월, 일, 시, 분, 초는 1 바이트인 unsigned char로
• 2바이트인 unsigned short를 사용한 C의 일시 표현 구조체:
  

6. 단일 연결 리스트

• 데이터 양이 정해져 있지 않는 경우에는 배열이 적합 X

• 연결 리스트: 목록에 들엉갈 원소 개수를 모르는 경우, 배열보다 BETTER!!

  • next: 리스트의 다음 원소 주소를 저장하는 포인터

  • 헤드: 리스트 맨 앞

  • 테일: 리스트 마지막

  • 원소 위치: 메모리의 아무 위치! 배열의 원소는 메모리에서 연속적으로 위치)
    

  • 새 원소 헤드 앞에 쉽게 추가 가능!
    

  • "삭제할 리스트 원소의 바로 앞 원소의 next 포인터가 삭제할 원소의 next 포인터가 가리키는 원소를 가리키게 해야 한다"
    

  • 포인터를 한 쌍으로 유지하여 단일 연결 리스트의 원소 삭제 가능

  • 리스트의 각 원소 방문 -> previous 포인터를 통해 current.next 포인터 조정 -> 원소 삭제
    

  • 이중 간접 주소 지정을 통해 보다 효율적인 단인 연결 리스트 원소 삭제 가능
    
    

    1. current0 을 head 주소 설정 -> current1 은 head를 가리킨다 -> head는 리스트 원소 A의 노드를 가리킨다
    2. 삭제할 원소가 D가 아니기 때문에 다음으로 진행
    3. 점선 화살표가 나타내는 것처럼 방금 전 current (=A)의 next값을 나타낸다 -> current2는 A.next 가리킨다 -> 삭제할 원소가 아니라서 다음 진행
    4. 삭제할 원소를 찾을 때까지 반복하고 D를 찾았을 때, C.next를 D.next값으로 덮어쓴다 -> D.next인 E로 진행

• 두 가지 단일 연결 리스트 원소 삭제 방법을 C코드로 비교하면

  • 두 포인터 사용 코드
    
    
  • 이중 간접 주소 지정 사용 코드