#include<stdio.h>
#include<stdlib.h>
// element 타입의 정의
// element 타입은 필요에 따라 다른 타입으로 대체 할수 있음.
typedef int element;
// ListNode 타입의 정의
typedef struct _ListNode {
element data; // 데이터 필드
struct _ListNode *link; // 링크 필드
} ListNode;
// List 타입의 정의
typedef struct _List {
ListNode *head; // 연결 리스트로 구현
} List;
////////////////////////////////////////////////////////
// element 관련 연산
void print_element(element e); // element 타입의 값을 모니터에 출력
// ListNode 관련 연산
void insert_node(ListNode **phead, ListNode *prior, ListNode *new_node);
void remove_node(ListNode **phead, ListNode *prior, ListNode *removed);
// List 관련 연산
void list_init(List *pList); // 빈 list로 초기화
int list_is_empty(List *pList); // list가 비어 있는지...
int list_get_length(List *pList); // list의 길이를 반환
int list_get_pos(List *pList, element item); // item을 찾아서 위치를 반환
element list_get_entry(List *pList, int pos); // list의 pos위치의 항목을 반환
void list_add(List *pList, int pos, element item); // pos위치에 item을 추가
void list_add_last(List *pList, element item); // 맨끝에 item을 추가
void list_add_first(List *pList, element item); // 맨앞에 item을 추가
element list_delete(List *pList, int pos); // pos위치의 item을 삭제
element list_delete_last(List *pList); // 맨 끝의 항목을 삭제
element list_delete_first(List *pList); // 맨 처음의 항목을 삭제
void list_delete_all(List *pList); // 모든 항목을 삭제
void list_replace(List *pList, int pos, element item); // pos위치의 항목을 교체
void print_list(List *pList); // list를 모니터에 출력
// 에러처리 함수
void error_msg(char *strMsg);
///////////////////////////////////////////////////////////
// print_element
// element타입의 값을 적당한 형식으로 화면에 출력한다.
// 현재는 element는 int 로 정의되어 있으나, 추후 변경 될 경우,
// 상황에 맞게 이 함수를 수정하여 사용할 수 있다.
void print_element(element e)
{
int n = (int) e; // 현재 element는 int타입임.
printf("%d", n);
}
// error_msg
// 에러메시지를 출력한 후 프로그램을 끝내버린다.
// parameter: char *strMsg
// 에러메시지 strMsg를 표준에러스트림으로 출력하고
// exit함수를 호출하여 프로그램을 죽인다.
void error_msg(char *strMsg)
{
fprintf(stderr, "%s", strMsg);
exit(1);
}
// ListNode 관련 연산
// insert_node
// 리스트에 새 노드를 삽입
// parameters: ListNode **phead, ListNode *prior, ListNode *new_node
// return value: 없음
// 설명: phead는 head pointer의 포인터.
// prior가 가리키는 노드의 다음에 new_node를 삽입한다.
// 단, prior == NULL일 경우, new_node가 가장 앞에 추가된다.
void insert_node(ListNode **phead, ListNode *prior, ListNode *new_node)
{
if( *phead == NULL ) // 빈 리스트인 경우
{
new_node->link = NULL; // 새 노드 다음은 없음
*phead = new_node; // head pointer는 새 노드를 가리키도록 조정
}
else if( prior == NULL ) // prior 가 NULL이면 첫번째 노드로 삽입
{
new_node->link = *phead; // 현재 맨 앞 노드는 새 노드 다음으로
*phead = new_node; // head pointer는 새 노드를 가리키도록 조정
}
else
{
new_node->link = prior->link; // 새 노드의 다음은 현재 prior의 다음으로
prior->link = new_node; // prior의 다음은 새노드로
}
}
// remove_node
// 리스트에서 노드를 삭제
// parameters: ListNode **phead, ListNode *prior, ListNode *removed
// return value: 없음
// 설명: phead는 head pointer의 포인터.
// 리스트로부터 removed를 삭제한다. prior는 removed의 선행 노드를 의미
// 단, removed가 리스트의 만 앞 노드인 경우, prior는 NULL이어야 한다.
// 주의! 이 함수에서 삭제되는 노드를 메모리에 반환하지는 않는다.
void remove_node(ListNode **phead, ListNode *prior, ListNode *removed)
{
if( prior == NULL ) // 맨 앞 노드이면
*phead = (*phead)->link; // head pointer를 그 다음 노드로
else
prior->link = removed->link; // prior의 다음을 removed의 다음으로
}
// List 관련 연산
// list_init
// 빈 list로 초기화한다.
// 이 함수는 List 타입의 변수를 선언한 후 최초에 한번만 호출되어야 한다.
// parameters: List *pList
// return value: 없음
// 단, pList==NULL 인 경우 에러메시지를 출력하고 프로그램을 끝낸다.
void list_init(List *pList)
{
if (pList==NULL) // 입력받은 리스트가 NULL이면 프로그램 종료
error_msg("list_init: pList == NULL");
pList->head = NULL;
}
// list_get_pos
// item을 찾아서 위치를 반환
// parameters: List *pList, element item
// return value: pList가 가리키는 리스트에서 item의 위치 (맨 앞이 0번)
// item이 존재하지 않는 경우 -1을 리턴한다.
// 단, pList==NULL 인 경우 에러메시지를 출력하고 프로그램을 끝낸다.
int list_get_pos(List *pList, element item)
{
// 여기에 코드를 기입하세요
return -1;
}
// list_get_length
// 리스트의 길이를 계산하여 반환
// parameter: List *pList
// return value: pList의 항목 개수를 계산하여 리턴
// 단, pList==NULL 인 경우 에러메시지를 출력하고 프로그램을 끝낸다.
int list_get_length(List *pList)
{
int cnt = 0;
// 여기에 코드를 기입하세요
return cnt;
}
// list_is_empty
// 리스트가 비어있는지를 판별
// parameter: List *pList
// return value: pList가 NULL이거나 빈 리스트이면 1 아니면 0을 리턴
//
int list_is_empty(List *pList)
{
// 여기에 코드를 기입하세요
return 0;
}
// list_get_item
// 리스트에서 pos위치의 항목을 반환
// parameters: List *pList, int pos
// return value: pList의 pos 위치의 항목 (element 타입)
// 단, pos가 적절한 값이 아닌 경우에는 에러 메시지를 출력하고 프로그램을 끝낸다.
element list_get_entry(List *pList, int pos)
{
// 여기에 코드를 기입하세요
return 0;
}
// list_add
// 리스트의 pos위치에 항목 item을 삽입한다.
// parameter: List *pList, int pos, element item
// return value: 없음
// pos==0이면 맨 앞에, pos==list_get_length(pList)이면 맨 뒤에 추가된다.
// 단, 삽입에 실패할 경우, (pos 값이 부적절하거나) 에러메시지를 출력하고 프로그램을 끝낸다.
void list_add(List *pList, int pos, element item)
{
// 여기에 코드를 기입하세요
}
// list_add_last
// 리스트의 맨 끝에 항목 item을 삽입한다.
// parameter: List *pList, element item
// return value: 없음
// 단, 삽입에 실패할 경우, 적당한 에러메시지를 출력하고 프로그램을 끝낸다.
void list_add_last(List *pList, element item)
{
// 여기에 코드를 기입하세요
ListNode *new_node = NULL;
ListNode *last_node = NULL;
ListNode *p = NULL;
if(pList == NULL)
{ error_msg("list_add_first pList == NULL");}
new_node = (ListNode *)malloc(sizeof(ListNode));
if(new_node == NULL)
{ error_msg("list_add_first pList == NULL");}
last_node->data=item;
if(pList->head == NULL)
{
pList->head = new_node;
new_node->link=NULL;
}
else
{
p=pList->head;
while(p->link !=NULL) //*
{ p= p->link;}
// for(pList->head; p->link != NULL; p=p->link ) ;
last_node = p;
last_node->link = new_node;
new_node->link = NULL;
}
}
// list_add_first
// 리스트의 맨 앞에 항목 item을 삽입한다.
// parameter: List *pList, element item
// return value: 없음
// 단, 삽입에 실패할 경우, 적당한 에러메시지를 출력하고 프로그램을 끝낸다.
void list_add_first(List *pList, element item)
{
// 여기에 코드를 기입하세요
ListNode *new_node = NULL;
if(pList == NULL)
{ error_msg("list_add_first pList == NULL");}
new_node = (ListNode *)malloc(sizeof(ListNode));
if(new_node == NULL)
{ error_msg("list_add_first pList == NULL");}
new_node-> data= item;
new_node->link = pList->head;
pList-> head = new_node;
// list_delete
// 리스트에서 pos위치의 항목을 삭제한다.
// parameter: List *pList, int pos, element item
// return value: 리스트에서 삭제된 항목
// 단, 삭제에 실패할 경우, (pos 값이 부적절하거나) 에러메시지를 출력하고 프로그램을 끝낸다.
element list_delete(List *pList, int pos)
{
// 여기에 코드를 기입하세요
return 0;
}
// list_delete_last
// 리스트의 맨 끝의 항목 삭제한다.
// parameter: List *pList
// return value: 리스트에서 삭제된 항목
// 단, 삭제에 실패할 경우, 에러메시지를 출력하고 프로그램을 끝낸다.
// 예) pList가 NULL이거나 빈 리스트인 경우
element list_delete_last(List *pList)
{
return list_delete(pList, list_get_length(pList)-1);
}
// list_delete_first
// 리스트의 맨 앞의 항목 삭제한다.
// parameter: List *pList
// return value: 리스트에서 삭제된 항목
// 단, 삭제에 실패할 경우, 에러메시지를 출력하고 프로그램을 끝낸다.
// 예) pList가 NULL이거나 빈 리스트인 경우
element list_delete_first(List *pList)
{
return list_delete(pList, 0);
}
// list_delete_all
// 리스트안의 항목을 모두 삭제한다.
// parameter: List *pList
// return value: 없음
void list_delete_all(List *pList)
{
ListNode *cur_node = NULL;
// pList==NULL 이면 에러메시지 출력후 프로그램 종료
if(pList == NULL)
error_msg("list_delete_all: pList == NULL");
// cur_node를 head pointer로 초기화
cur_node = pList->head;
// 현재 노드(cur_node)가 NULL이 아닌 동안...
while(cur_node != NULL)
{
ListNode *to_be_deleted = cur_node; //임시로 저장->곧 삭제됨
cur_node = cur_node->link; //cur_node는 다음 노드로
free(to_be_deleted); //to_be_deleted는 메모리 반환->삭제
}
pList->head = NULL; // 초기화 (pList->head = NULL을 실행)
}
// list_replace
// 리스트에서 pos 위치의 항목을 item으로 대체한다.
// parameter: List *pList, int pos, element item
// return value: 없음
// 단, pos가 적절한 값이 아닌 경우에는 에러메시지를 출력하고 프로그램을 끝낸다.
void list_replace(List *pList, int pos, element item)
{
// 여기에 코드를 기입하세요
}
// print_list
// 리스트의 내용을 모니터에 출력한다.
// parameter: List *pList, char *strLink
// return value: 없음
// 리스트의 내용은 순서대로 화면에 출력된다.
// strLink는 항목 사이에 들어갈 문자열이다.
// element 타입인 각 항목은 print_element를 호출하여 출력한다.
// 예) print_list(pList, "-->"); 형태로 호출하면 각항목 사이에 --> 가 그려진다.
// 단, pList==NULL 일 경우, 에러메시지를 출력하고 프로그램을 끝낸다.
void print_list(List *pList, char *strLink)
{
ListNode *cur_node = NULL;
if(pList == NULL)
error_msg("print_list: pList==NULL");
cur_node = pList->head;
if(cur_node == NULL) // 만약 빈 리스트라면...
{
printf("空\n");
return;
}
// 하나라도 있다면...
// 먼저 맨 앞 항목을 출력
printf("[");
print_element(cur_node->data);
printf("]");
cur_node = cur_node->link;
// 그 다음의 모든 항목들에 대하여..
while(cur_node != NULL)
{
printf(" %s ", strLink); // strLink를 출력한 후,
printf("[");
print_element(cur_node->data); // 현재 노드의 데이터를 출력
printf("]");
cur_node = cur_node->link; // 다음 노드로 이동
}
printf("\n");
}
////////////////////////////////////////////////////////////////////////////////////
// main
int main()
{
// Linked List 연습
List L; // List 타입의 변수 선언
list_init(&L); // List 초기화, 현재 빈 리스트
print_list(&L, "-->"); // 출력해본다
//////////////////////////////////////////////////////////
// HW#4. list_add_first와 list_add_last를 구현한 후
// 아래의 작업을 수행하는 코드를 쓰시오.
// (1) 1을 L의 맨앞에 추가
// (2) 2를 L의 맨앞에 추가
// (3) L을 모니터에 출력해본다
// (4) 3을 L의 맨뒤에 추가
// (5) 4를 L의 맨뒤에 추가
// (6) L을 모니터에 출력해본다
// (7) L의 모든 항목을 삭제한다
// (8) L을 모니터에 출력해본다
// 여기에 코드를 기입하세요
list_add_first(&L, 1);
list_add_last(&L, 2);
return 0;
}