1. 자료구조

1. 프로그램의 동작

1. 변수 (자료형, 범위, 할당)

2. 제어문

3. 부 프로그램 호출

위와같은 세가지로 프로그램이 동작하게 된다.

2. 자료구조

1. 선형구조 - 선형리스트(배열), 연결리스트(단순, 원형, 이중, 이중원형), 스택, 큐, 데크

2. 비선형 구조 - 트리, 그래프

3. 정렬

4. 검색

3. 리스트(LIST)

3.1 선형 리스트

- 장점

가장 간단한 구조

기억 메모리 밀도가 1 (제일 높음)

검색 효율이 좋다.

- 단점

삽입 삭제의 단점(중간에 삽입하려면 그 뒤의 모든것을 한칸씩 뒤로 미루어야하기 때문)

낭비가 심함

3.2 단순연결 리스트

한 노드가 데이터와, 링크 부분으로 구성되어있다.

시작과 끝이있고, 한 방향으로 진행하는것이 단순연결 리스트라고한다.

시작을 Head Pointer, 끝을 Tail Pointer라고 한다. 그런데 Tail Pointer는 개발자에 따라 쓰이기도, 쓰이지 않기도 한다.

삽입 알고리즘

Insert (HEAD, X, ITEM)

// HEAD = 단순열결 리스트의 시작지점

// X = 삽입노드의 전 노드를 가리키는 포인터

// ITEM = 삽입하려는 값

CALL GET NODE(I) // 새로운 노드를 동적할당하여 I 포인터에 연결

I->Data = ITEM; // 동적할당된 I 포인터의 Data 부분에 ITEM을 삽입

이후 연결리스트에 삽입시킬 알고리즘을 생각한다.

1. 기존 연결리스트가 존재하지 않을 때

2. 맨 앞에 INSERT 시킬때

3. 맨 뒤에 INSERT 시킬때

4. 중간에 삽입할 때

1. if (head == NULL)

I->link=NULL

head=I

2. if(X == NULL)

I->link=head

head=I

3. if(X->link == NULL)

I->link=NULL

X->link=I

4. else

I->link=X->link

X->link=I

잘 살펴보면 중복되는 부분이 존재한다.

1, 2 번이 비슷한 코드로 되어있고

3, 4 번이 비슷한 코드로 되어있다.

1, 2 if (X == NULL)

I->link=head

head=I

3, 4 else

I->link=X->link

X->link=I