728x90
C언어로 쉽게 풀어쓴 자료구조: 6장
6.1 리스트 추상 데이터 타입
리스트란?
항목들이 순서 또는 위치를 갖고 차례대로 저장된 구조 ➡️스택, 큐도 리스트의 일종
리스트 ADT
insert(list, pos, item) = pos 위치에 요소를 추가한다.
insert_last(list, item) = 맨 끝에 요소를 추가한다.
insert_first(list, item) = 맨 처음에 요소를 추가한다.
delete(list, pos) = pos 위치의 요소를 제거한다.
clear(list) = 리스트의 모든 요소를 제거한다.
get_entry(list, pos) = pos 위치의 요소를 반환한다.
grt_length(list) = 리스트의 길이를 구한다.
is_empty(list) = 리스트가 비었는지 검사한다.
is_full(list) = 리스트가 꽉 찼는지 검사한다.
print_list(list) = 리스트의 모든 요소를 표시한다.
6.2 배열로 구현된 리스트
배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당된다.
➡️ 리스트의 순차적 표현이라고도 함
리스트 정의
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100 // 리스트의 최대크기
typedef int element; // 항목의 정의
typedef struct {
element array[MAX_LIST_SIZE]; // 배열 정의
int size; // 현재 리스트에 저장된 항목들의 개수
} ArrayListType;
기초 연산
// 오류 처리 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 리스트 초기화 함수
void init(ArrayListType *L)
{
L->size = 0;
}
// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType *L)
{
return L->size == 0;
}
// 리스트가 가득 차 있으면 1을 반환
// 그렇지 많으면 1을 반환
int is_full(ArrayListType *L)
{
return L->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType *L, int pos)
{
if (pos < 0 || pos >= L->size)
error("위치 오류");
return L->array[pos];
}
// 리스트 출력
void print_list(ArrayListType *L)
{
int i;
for (i = 0; i<L->size; i++)
printf("%d->", L->array[i]);
printf("\n");
}
항목 추가 연산
- insert_last() 함수에서는 리스트에 빈공간이 없으면 오류를 발생시킨다.
- 리스트의 pos 위치에 새로운 항목을 추가하기
- pos 번째부터 마지막 항목까지 한 칸씩 오른쪽으로 이동한다
- pos 번째에 생긴 빈자리에 새로운 항목을 저장한다.
void insert_last(ArrayListType *L, element item)
{
if( L->size >= MAX_LIST_SIZE ) {
error("리스트 오버플로우");
}
L->array[L->size++] = item;
}
void insert(ArrayListType *L, int pos, element item)
{
if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
for (int i = (L->size - 1); i >= pos; i--)
L->array[i + 1] = L->array[i];
L->array[pos] = item;
L->size++;
}
}
항목 삭제 연산
- 항목 삭제 후 array[pos + 1] 부터 array[size - 1]까지를 한 칸씩 앞으로 이동한다.
element delete(ArrayListType *L, int pos)
{
element item;
if (pos < 0 || pos >= L->size)
error("위치 오류");
item = L->array[pos];
for (int i = pos; i<(L->size - 1); i++)
L->array[i] = L->array[i + 1];
L->size--;
return item;
}
6.3 연결 리스트
동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없다.
6.4 단순 연결 리스트
- 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있다.
- 마지막 노드의 링크 필드 값은 NULL이다.
노드의 정의
- 노드는 자기 참조 구조체를 이용하여 정의된다.
- 자기 참조 구조체란 자기 자신을 참조하는 포인터를 포함하는 구조체이다.
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
이렇게 생긴 노드가 생성된다.
노드의 생성
- 연결 리스트에서는 필요할 때마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성
head = (ListNode *)malloc(sizeof(ListNode));
head->data = 10;
head->link = NULL;
요로캐 생긴 노드가 생성되고 data에는 10, link에는 Null 값이 들어간다.
노드의 연결
ListNode *p
p = (ListNode *)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;
p와 연결된 노드를 하나 더 생성하고
head->link = p;
head->link에 p를 저장하면 첫 번째 노드의 링크가 두 번째 노드를 가리키게 된다.
6.5 단순 연결 리스트의 연산 구현
insert_first(): 리스트의 시작 부분에 항목을 삽입하는 함수
insert(): 리스트의 중간 부분에 항목을 삽입하는 함수
delete_first(): 리스트의 첫 번째 항목을 삭제하는 함수
delete(): 리스트의 중간 항목을 삭제하는 함수
print_list(): 리스트를 방문하여 모든 항목을 출력하는 함수
삽입 연산
Insert_first 연산
- 동적 메모리 할당을 통해 새로운 노드 p를 생성한다.
- p->data에 value를 저장
- p->link를 현재의 head값으로 변경
- head를 p값으로 변경
- 반환
ListNode* insert_first(ListNode *head, int value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
p->data = value; // (2)
p->link = head; // 헤드 포인터의 값을 복사 //(3)
head = p; // 헤드 포인터 변경 //(4)
return head; // 변경된 헤드 포인터 반환
}
Insert 연산
- 새로운 노드를 생성하여 변수 p로 가리킨다.
- p의 데이터 필드에 value 저장
- p의 링크 필드가 노드 pre이 가리키던 노드를 가리키게 한다.
- per의 링크 필드가 p를 가리키게 한다.
// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode *head, ListNode *pre, element value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
p->data = value; //(2)
p->link = pre->link; //(3)
pre->link = p; //(4)
return head; //(5)
}
delete 연산
- 삭제할 노드를 찾는다
- per의 링크 필드가 삭제할 노드가 가리키는 노드를 가리키게 한다.
- 삭제할 노드의 동적 메모리를 반납한다.
- 변경된 헤드 포인터를 반환한다.
// pre가 가리키는 노드의 다음 노드를 삭제한다.
ListNode* delete(ListNode *head, ListNode *pre)
{
ListNode *removed;
removed = pre->link;
pre->link = removed->link; // (2)
free(removed); // (3)
return head; // (4)
}
전체 프로그램
#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);
exit(1);
}
ListNode* insert_first(ListNode *head, int value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
p->data = value; // (2)
p->link = head; // 헤드 포인터의 값을 복사 //(3)
head = p; // 헤드 포인터 변경 //(4)
return head; // 변경된 헤드 포인터 반환
}
// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode *head, ListNode *pre, element value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
p->data = value; //(2)
p->link = pre->link; //(3)
pre->link = p; //(4)
return head; //(5)
}
ListNode* delete_first(ListNode *head)
{
ListNode *removed;
if (head == NULL) return NULL;
removed = head; // (1)
head = removed->link; // (2)
free(removed); // (3)
return head; // (4)
}
// pre가 가리키는 노드의 다음 노드를 삭제한다.
ListNode* delete(ListNode *head, ListNode *pre)
{
ListNode *removed;
removed = pre->link;
pre->link = removed->link; // (2)
free(removed); // (3)
return head; // (4)
}
void print_list(ListNode *head)
{
for (ListNode *p = head; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL \n");
}
// 테스트 프로그램
int main(void)
{
ListNode *head = NULL;
for (int i = 0; i < 5; i++) {
head = insert_first(head, i);
print_list(head);
}
for (int i = 0; i < 5; i++) {
head = delete_first(head);
print_list(head);
}
return 0;
}
728x90
반응형
'C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 8장 트리 - Ⅰ (0) | 2024.11.24 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] 7장 연결리스트 - Ⅱ (0) | 2024.11.23 |
| [C언어로 쉽게 풀어쓴 자료구조] 5장 큐 (0) | 2024.11.16 |
| [C언어로 쉽게 풀어쓴 자료구조] 4장 스택 (0) | 2024.11.11 |
| [C언어로 쉽게 풀어쓴 자료구조] 3장 배열, 구조체, 포인터 (2) | 2024.11.06 |