자료구조 기초 (1)

자료구조 : 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는것

단순구조

: 정수, 실수, 문자, 문자열 등의 기본 자료형

선형구조

: 자료들 사이의 관계가 1:1 관계

순차 리스트, 연결 리스트, 스택, 큐, 데크

비선형구조

:자료들 사이의 관계가 1:다 또는

다:다 관계

트리, 그래프

파일구조

:서로 관련있는 필드로 구성된 레코드의 집합인 파일에 대한 구조

순차파일, 색인파일, 직접파일

 

컴퓨터에서의 자료 표현

2진수 코드

 

디지털 시스템에서의 자료 표현

n개의 비트로 2^n개의 상태 표현

 

10진수의 표현

- 존 형식의 표현

10진수 한자리를 표현하기 위해서 1바이트를 사용하는 형식

마지막 자리의 존 영역에 부호를 표시

양수 1100 음수 1101

ex :

1일때는 1111 0001

2일때는 1111 0010

3일때는 1100 0011

 

팩 형식의 표현

10진수 한자리를 표현하기 위해서 존 영역없이 4비트를 표현하는 형식

최 하위 4비트에 부호를 표시

양수 1100 음수 1101

ex : 0010 0001 0011 1100

        2      1      3      +

 

2진수의 정수 표현

-n비트의 부호와 절댓값 형식

양수이면 0 음수이면 1

최상위 비트에 표현함

ex : 10010101

 

- 1의 보수형식

음수 표현에서 부호비트를 사용하는 대신 1의 보수를 사용

n비트의 2진수를 1의 보수로 만드는방법

-> n비트를 모두 1로 만든 이진수에서 변환하고자 하는 이진수를 뺌

- 예) 10진수 21을 1의 보수로 만듦!

왜 배웠는데 기억을 못할까..

 

  그냥 반대로 생각하면됨

예컨대 

10101111

이면 1의 보수는

01010000

반대임

 

 

-2의보수는

1의 보수 만들고 + 1

---

+52와 -52를 1바이트를 사용하여 다음 3가지 형식으로 표현하시오.

ƒ 부호와 절댓값 형식

• +52: 32+16+4 = 00110100

• -52: 10110100

음.. 이렇게 하는거군

 

ƒ 1의 보수1’ Complement 형식

• +52: 00110100

• -52:  11001011

ƒ 2의 보수2’ Complement 형식

• +52: 2의 보수의 1의 보수 + 1 하면 00110100

• -52: 11001011 +1 = 11001100

 

---

2진수의 정수 뺄셈

ƒ 1 바이트를 사용하여 16-8을 위 3가지 형식으로 계산하면?

ƒ n비트의 부호와 절대값 형식

• 16에서 8을 빼는 감산기 회로 사용

• 8-16은 절대값이 큰 16에서 작은 8을 빼고 – 부호를 표시

ƒ 1의 보수1’ Complement 형식

• 16에서 (-8)의 1의 보수를 더하는 가산기 회로 사용

• Carry bit 생기면 1을 더해줌

ƒ 2의 보수2’ Complement 형식

• 16에서 (-8)의 2의 보수를 더하는 가산기 회로 사용

• Carry bit 생기면 무시함

ƒ 1의 보수와 2의 보수 형식은 감산기 회로가 없어도 됨

 

---

63 - 28을 8비트 1의 보수와 2의 보수 방식으로 계산하시오.

단, 가산기를 이용해서 계산하며, 과정을 설명하시오.

 

00111111(64-1)

00011100(28)

1의 보수

11100011

 

63 + 28의 1의 보수 하면

캐리비트 생김

더해줌

--------------------------------------

1의보수 +1 = 2의 보수

11100100

캐리비트는 버림