아주대학교 자료구조 및 알고리즘 과제1- 전자공학과

소개

2016년 1학기 자료구조 A+받았습니다. 과제1은 보고서의 flow chart 작성 부분을 제외하고 만점을 받았기 때문에 작성시 flow chart를 함수별로 작성하세요.

목차

1. 문제분석
2. 배경지식
3. 자료구조/알고리즘의설명
4. 소스코드분석
5. 결과화면에대한분석

본문내용

① 문제분석
이번 과제는 자료구조 및 알고리즘의 이해 과목의 첫 과제로, C언어의 전반적인 지식 및 연결 리스트(Linked list)의 이해도를 묻는 과제이다. 단순한 int형 정수에 대해 2진법 형태의 연결 리스트를 구성하고, 이러한 결과물을 이용해 또 다른 결과물 즉, 이진합(Binary sum)을 얻음으로써 연결리스트에 대한 이해를 확인할 수 있었다.

-요구사항
main 함수에 대해 주어지는 입력은 단 하나, int형 정수 두 개이다. 첫 번째 기능은, 이 정수를 10진수 형태의 NumStruct로 변환(convert)하고, 두 번째 기능은 이러한 NumStruct를 2진수 형태로 다시 변환하는 것이다. 세 번째 기능은 2진수로 표현된 두 NumStruct에 대한 이진합을 구하고, 네 번째 기능은 이진합에 대한 리스트를 다시 10진법으로 변환하는 것이다. 마지막 기능은 위와 같은 NumStruct를 실제로 출력화면에 프린트하는 것이다.

-제약사항
이번 과제는 진법변환이기 때문에 제약은 모두 진법과 관련 있다. 2진수 입력이나 10진수 입력이 파라미터로 들어올 때 진법이 맞는지 확인해야하며, X진법으로 수를 표현 했을 때 각 자릿수는 X이상이 되면 안된다. 또한 Binary 합을 구하기 위해선 두 수 모두 2진수이어야 한다. 위 명시한 제약사항을 위반할 경우, exit(1)명령을 통해 프로그램을 종료하게 된다.

② 배경지식
- 기능적 배경지식
이번 과제에선 10진수 <-> 2진수간 변환만을 다룬다. 10진수를 2진수로 변환할 경우 우측 사진과 같이 원하는 정수를 2로 계속 나누어주고 그 몫과 나머지를 적어간다. 최종적으로 몫이 2보다 작아지게 되면, 아래서부터 최종 몫과 나머지를 순서대로 읽는다. 2진수를 10진수로 변환할 경우는 이와 반대로 곱셈을 해준다. 2진표현의 LSB부터 부터 의 가중치를 곱한 합이 10진 표현이 된다.

이진합의 경우 2진수 두 개에 대해 시행할 수 있다. LSB를 맞춰준 뒤, 각 자리를 더해준다. 아랫자리에서 올라온 Carry와 두 bit를 더한 합이 2 이상이라면 Carry를 출력하게 된다. 이에 대한 진리표를 작성하면 아래와 같다.

참고자료

· C언어로 쉽게 풀어쓴 자료구조, 천인국 외 2명, 생능출판, 2016년
· Digital Design, John F. Warkerly, Pearson, 2008년