지난 6장에서는 연결 리스트의 구현과 몇 가지 함수를 추가해 보았다.
이번 7장에서는 아래 링크의 가장 하단에 있는 연결 리스트로 구현한 스택과 큐를 리뷰하도록 해보자.
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode{
element data;
struct ListNode *link;
} ListNode;
void error(char *message){
fprintf(stderr, "%s\n", message);
}
ListNode *create_node(element data, ListNode *link){
ListNode *new_node;
new_node = (ListNode *)malloc(sizeof(ListNode));
if(new_node ==NULL) error("메모리 할당 에러");
new_node->data = data;
new_node->link = link;
return new_node;
}
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node){
if (*phead == NULL){
new_node->link = NULL;
*phead = new_node;
}
else if(p == NULL){
new_node->link = *phead;
*phead = new_node;
}
else {
new_node->link = p->link;
p->link = new_node;
}
}
void remove_node(ListNode **phead, ListNode *p, ListNode *removed){
if( p == NULL )
*phead = (*phead)->link;
else
p->link = removed->link;
free(removed);
}
void display(ListNode *head){
ListNode *p = head;
if(head == NULL)
printf("List is empty\n");
else{
while(p != NULL){
printf("%d->", p->data);
p = p->link;
}
printf("\n");
}
}
ListNode *search(ListNode *head, element x){
ListNode *p;
p = head;
while(p!=NULL){
if(p->data == x) return p;
p = p->link;
}
return p;
}
ListNode *concat(ListNode *head1, ListNode *head2){
ListNode *p;
if(head1 == NULL) return head2;
else if(head2 == NULL) return head1;
else{
p = head1;
while(p->link != NULL){
p = p->link;
}
p->link = head2;
return head1;
}
}
ListNode *reverse(ListNode *head){
ListNode *p, *q, *r;
p = head;
q = NULL;
while(p!=NULL){
r = q;
q = p;
p = p->link;
q->link = r;
}
return q;
}
void add_last(ListNode **head, ListNode *new_node){
ListNode *pNode = *head;
while(pNode->link != NULL){
pNode = pNode->link;
}
pNode->link = new_node;
}
void add_first(ListNode **head, ListNode *new_node){
ListNode *pNode = *head;
*head = new_node;
(*head)->link = pNode;
}
void clear(ListNode **head){
ListNode *pNode = *head;
ListNode *pPrev;
if(pNode->link != NULL){
while(pNode->link != NULL){
pPrev = pNode;
pNode = pNode->link;
}
free(pNode);
pPrev->link = NULL;
clear(head);
}
else{
free(*head);
*head = NULL;
}
}
void replace(ListNode *pNode, int pos, int data){
int i;
for(i=1;i<pos;i++){
pNode = pNode->link;
}
pNode->data = data;
}
int get_entry(ListNode *pNode, int pos){
int i;
for(i=1;i<pos;i++){
pNode = pNode->link;
}
return pNode->data;
}
int is_empty(ListNode *head){
if(head == NULL)
return 1;
return 0;
}
int get_length(ListNode *pNode){
int i;
for(i=1;pNode->link != NULL;i++, pNode=pNode->link){}
return i;
}
void main(){
ListNode *list1 = NULL;
printf("list1 insert -> 10, 20, 30\n");
insert_node(&list1, NULL, create_node(10, NULL));
insert_node(&list1, NULL, create_node(20, NULL));
insert_node(&list1, NULL, create_node(30, NULL));
display(list1);
printf("list1 remove\n");
remove_node(&list1, NULL, list1);
display(list1);
printf("add_first (list1,123)\n");
add_first(&list1, create_node(123, NULL));
display(list1);
printf("add_last (list1,456)\n");
add_last(&list1, create_node(456, NULL));
display(list1);
printf("list1_replace (789), position_2\n");
replace(list1, 2, 789);
display(list1);
printf("list1_position_1 : %d\n", get_entry(list1, 1));
printf("list1_length : %d\n", get_length(list1));
clear(&list1);
}
[4장] 스택
스택에 대한 문제풀이 내용이다. 스택(Stack)이란? - 한마디로 표현하면 선입후출, FILO(First In, Last Out) 형태의 자료구조이다. - 주로 컴파일러에서 괄호검사를 시행할 때, '{' 중괄호는 '}' 중괄호, '('소괄..
ngkim.tistory.com
[5장] 큐
큐에 대한 문제풀이 내용이다. 큐(Queue)란? - 한마디로 표현하면 선입선출, FIFO(First In, First Out) 형태의 자료구조이다. - 자동차로 비유하면 각 지방도로에서 톨게이트를 거쳐서 인라인하게 데이터가 줄지..
ngkim.tistory.com
'학습공간 > C, 자료구조와 알고리즘' 카테고리의 다른 글
| [8장] 트리 (0) | 2019.11.25 |
|---|---|
| [6장] 연결 리스트 I (0) | 2019.11.23 |
| [5장] 큐 (0) | 2019.11.22 |
| [4장] 스택 (0) | 2019.11.22 |
| [3장] 배열, 구조체, 포인터 (0) | 2019.11.21 |
