[OS] 자료구조(연결 리스트, 스택), include문과 포인터 변수

 

 

작년, 그러니까 3학년 2학기에 운영체제 강의를 들으며 주어졌던 C code 분석 과제를 다시 한번 정리해보려고 한다.

 

C 언어로 작성 된 코드를 주고 이를 분석하는 과제였는데, C 언어를 한 번도 사용해 본 적 없을 때라 (사실 현재까지도) 어려웠지만 흥미로웠던 기억이 있었다.

 

C 언어를 배우기 전이기도 하고, 구조에 대해 이해하고 코드를 분석해보는 데에 의의를 둔 것이기에,

분석하고 정리한 내용이 정확하지 않을 수도 있는 점,,🙏🏻

 

전체적인 코드를 분석하기 전, 기본적인 자료구조 등을 정확하게 알고 진행하는 것이 좋을 것 같아 이에 대해 먼저 공부했었다.

이 부분을 이번 게시글에 정리해보려 한다.

운영체제 C 코드 분석 과제 재정리 1탄!

 

 

 

 

1.   C 언어 자료 구조에 대한 간단한 설명

1.1  include 문

 

대부분 C 언어로 프로그램을 작성할 때 최상단에 작성한다.

프로그래밍 시 사용할 함수를 가져와서 사용할 수 있는 일종의 라이브러리와 같은 역할을 한다.

 

 

include문은 전처리기이다.

 

전처리기는 코드가 실행되기 전 미리 처리하는 문장인데,

일반적으로 C 언어에서는 #include와 #define을 가장 많이 사용한다고 한다.

 

#include는 파일 처리,  #define은 형태 정의를 위한 전처리기이다.

 

 

include 문

 

주어진 코드에는 이렇게 다섯개의 include문이 존재했다.

위에서부터 어떤 것을 불러오는 것인지 차근차근 찾아서 정리해 보았다.

 

코드	설명
stdio.h	현재 작성하고 있는 소스 코드에 표준 입출력과 관련 헤더파일을 호출하여 사용하겠다는 의미
conio.h	콘솔 입출력 함수를 제공하는 헤더
string.h	메모리 블록이나 문자열을 다룰 수 있는 함수 제공
stdlib.h	문자열 변환, 동적 메모리 관리 등의 함수 제공
ctype.h	아스키 코드 값이 문자/ 숫자인지 등을 판별하는 함수와 대/소문자로 변환하는 함수 제공

 

 

 

 

1.2 연결 리스트 ( Linked List )

 

열심히 만들어 본 연결리스트 그림

 

 

연결 리스트는 위 그림과 같이 여러 개의 node(노드)를 연결함으로써 데이터를 표현한다.

하나의 노드는 자료를 가진 data 부분과 다음 노드를 연결하는 link 부분으로 나뉜다.

 

위 그림에서 표시한 것과 같이 head와 tail 노드가 존재한다.

 

필요한 만큼 메모리를 동적으로 할당받아서 만들며, 유연하게 크기 변경이 가능한 자료구조이다.

데이터를 자유롭게 삽입, 삭제할 수 있다는 장점을 가지고 있다.

 

 

 

1.3 스택 ( Stack ) 

스택 그림

 

 

메모리의 스택 영역은 함수를 호출할 때 관련 되어있는 지역변수, 매개변수, 리턴 값 등의 데이터를 저장한다.

 

차곡차곡 쌓여 있는 더미라는 의미를 가지고 있으며 LIFO (Last In First Out), 즉 후입선출 구조라고도 불린다.

스택에서 데이터는 아래쪽부터 그 위에 하나하나 더미처럼 쌓여가는 형식으로 저장된다.

 

 

데이터 PUSH 하고 POP 할 때 일어나는 과정을 이해하기 쉽게 그림으로 그려보았다.

 

 

 

스택에서 Push 과정

 

 

새로운 데이터를 추가할 때의 과정이다.

이를 데이터를 PUSH 한다고 말하며, 기존 데이터 위에 차례대로 데이터가 쌓인다.

 

 

 

 

 

스택에서 Pop 과정

 

 

반대로 스택에 존재하고 있던 데이터를 다시 빼내는 것을 POP이라고 말한다.

가장 위에 있는 데이터부터 차례로 삭제되는 것을 볼 수 있다.

 

이것이 LIFO의 특징이다. 

입구가 하나이기 때문에, 먼저 들어간 것이 가장 마지막에 나오게 되는 구조인 것이다.

 

 

 

1.4 연결 리스트와 스택

 

연결 리스트를 스택 형식으로 변환해보았다.

 

 

코드에서 처음 연결리스트를 struct 문을 사용하여 생성을 하고, 이를 스택 형식으로 바꿔주었다.

 

이 부분을 이해하기 위해 공부를 해보았는데, 이 변환하는 과정을 찾아보아도 글로 읽는 것은 이해가 조금 어려웠다.

 

그래서 해당 과정을 시각적으로 바꿔 조금이나마 이해가 쉽도록 그려보았다.

나름.. 효과는 굉장했다..! ⭐

 

 

 

1.5 포인터 변수란?

출처:https://zapiro.tistory.com/entry/%ED%8F%AC%EC%9D%B8%ED%84%B0pointer-%EB%B3%80%EC%88%98%EC%9D%98-%EA%B0%9C%EB%85%90

 

 

포인터는 데이터의 주소를 가리키는 변수의 종류 중 하나이다.

int형은 정수를, char형은 문자를 저장하는 것과 같이 포인터는 변수의 주소 값을 저장한다.

선언할 때를 제외한 다른 곳에서의 *은 값을 참조하라는 의미를 가진다고 한다.

 

(위 사진의 출처인 블로그에 포인터 변수의 개념에 대해 아주 자세하고 이해하기 쉽게 정리가 잘 되어있다👍)

 

 

 

 

 

2.   연결 리스트와 스택, 포함하는 데이터 종류

 

코드에서 선언한 3가지의 연결 리스트와 이를 스택 형식으로 연결한 것을 모아보았다.

분석한 내용은 코드에 주석으로 정리를 해두었었다.