소개글
자체참조 구조(Self-referential Structure)를 이용하여 연결 리스트(Linked List)를 만들고,
연결 리스트를 조절하기 위한 Insert, Delete, Print 등의 함수 들을 구현해본다. 주어진
5개의 program function을 작성한다. 이 program function의 입력과 출력은 아래에 주어
져 있다. “main3.c”라는 file로 이 function들을 테스트할 프로그램이 주어질 것이다.
연결 리스트는 하나의 pointer에 의하여 전체 List가 대표된다. 그 이유는, root를 통하여
첫번째 node를 알 수 있고, 그 외의 node는 이전 node의 “link” field를 통하여 access
하기 때문이다.
그러나, 연결 리스트에 대한 operation을 효율적으로 수행하기 위하여 2개의 pointer로
대표하기도 한다. 하나는 첫번째 node에 pointer로, 다른 하나는 맨 뒤의 node에 대한
pointer로 사용된다. 첫번째 node에 대한 pointer를 “head”, 맨 뒤의 node에 대한
pointer를 “tail”이라 부르기로 한다. 이번 실습에서는 이러한 연결 리스트에 대하여 연습
한다.
목차
1. Introduction
2. Problem Statement
① Describe what is the problem.
② Describe how do you solve the problem.
③ Draw a flowchart of your algorithm
3. Implementation
4. Result
5. Conclusion & Evaluation
6. Source Code (with suitable comments)
본문내용
2. Problem Statement
① Describe what is the problem.
- 위 [그림2]의 연결 리스트를 구현하기 위해 아래와 같이 이미 언급되었던 데이터 구조
를 사용한다.
typedef struct list_node {
struct list_node *link; int data;
} NODE;
NODE *head = 0;
NODE *tail = 0;
- int headInsert(NODE **head_ptr, NODE **tail_ptr, int i_data);
이 function은 주어진 i_data (3 번째 argument)를 리스트의 맨 앞에 넣어 주는 기능을
수행하며, 새로운 node를 넣을 수 없는 경우에는 0을 return하고, 성공적으로 새로운
node를 넣었을 경우에는 1을 return한다. 다음에, 몇 개 의 예를 보였으며, S1은 이
function을 수행하기 이전의 모습이며, S2는 이 function을 수행한 이후의 모습이다. 단,
data는 “7”이라고 가정하였다.
(예1) S1 = { }, S2 = { 7 }
(예2) S1 = { 4 }, S2 = { 7, 4 }
(예3) S1 = {4, 8, 12}, S3 = {7, 4, 8, 12}
- int tailInsert(NODE **head_ptr, NODE **tail_ptr, int i_data)
이 function은 주어진 i_data (3 번째 argument)를 리스트의 맨 뒤에 넣어주는 기능을
수행하며, 새로운 node를 넣을 수 없는 경우에는 0을 return하고, 성공적으로 새로운
node를 넣었을 경우에는 1을 return한다. 다음에 예를 몇 개 보였으며, S1은 이 function
을 수행하기 이전의 모습이며, S2는 이 function을 수행한 이후의 모습이다. 단, data는
“7”이라고 가정하였다.
(예1) S1 = { }, S2 = { 7 }
(예2) S1 = { 4 }, S2 = { 4, 7 }
(예3) S1 = {4, 8, 12}, S3 = {4, 8, 12, 7}
참고 자료
없음