반응형
리스트 ADT
1. insert(list, pos, item) ::= pos 위치에 요소를 추가
2. insert_last(list, item) ::= 맨 끝에 요소를 추가
3. insert_first(list, item) ::= 맨 처음에 요소를 추가
4. delete(list, pos) ::= pos 위치의 요소를 제거
5. clear(list) ::= 리스트 전체를 삭제
6. get_entry(list, pos) ::= pos 위치의 요소를 반환
7. get_length(list) ::= 리스트의 길이를 반환
8. is_empty(list) ::= 리스트가 비었는지 검사
9. is_full(list) ::= 리스트가 다 찼는지 검사
10. print_list(list) ::= 리스트의 모든 요소 표시
배열은 ADT를 가장 간단하게 구현이 가능하나 고정된 크기가 단점이다.
연결리스트는 크기가 제한되지는 않으나, 구현이 복잡하고, 배열에 비해 임의의 항목을 추출하려 했을 때 시간이 많이 걸린다.
배열로 구현된 리스트
#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");
}
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++;
}
}
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;
}
int main(void)
{
// ArrayListType를 정적으로 생성하고 ArrayListType를
// 가리키는 포인터를 함수의 매개변수로 전달한다.
ArrayListType list;
init(&list);
insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
insert(&list, 0, 20); print_list(&list); // 0번째 위치에 20 추가
insert(&list, 0, 30); print_list(&list); // 0번째 위치에 30 추가
insert_last(&list, 40); print_list(&list); // 맨 끝에 40 추가
delete(&list, 0); print_list(&list); // 0번째 항목 삭제
return 0;
}10이 리스트의 0번째 위치에 추가된다. 이어서 20이 0번째 위치에 추가되므로 기존의 10은 뒤로 밀리게 된다. 30이 0번째 위치에 추가되면 "30->20->10"과 같이 저장된다. insert_last()를 호출하여 40을 맨 끝에 추가하면 "30->20->10->40"이 된다. delete()를 호출하여서 0번째 항목을 삭제하면 "20->10->40"이 된다.
연결 리스트
노드 = 데이터 필드 + 링크 필드
리스트를 역순으로 만드는 연산
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
ListNode* insert_first(ListNode *head, element value)
{
ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //(1)
p->data = value; // (2)
p->link = head; // 헤드 포인터의 값을 복사 //(3)
head = p; // 헤드 포인터 변경 //(4)
return head;
}
void print_list(ListNode *head)
{
for (ListNode *p = head; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL \n");
}
ListNode* reverse(ListNode *head)
{
// 순회 포인터로 p, q, r을 사용
ListNode *p, *q, *r;
p = head; // p는 역순으로 만들 리스트
q = NULL; // q는 역순으로 만들 노드
while (p != NULL) {
r = q; // r은 역순으로 된 리스트.
// r은 q, q는 p를 차례로 따라간다.
q = p;
p = p->link;
q->link = r; // q의 링크 방향을 바꾼다.
}
return q;
}
// 테스트 프로그램
int main(void)
{
ListNode* head1 = NULL;
ListNode* head2 = NULL;
head1 = insert_first(head1, 10);
head1 = insert_first(head1, 20);
head1 = insert_first(head1, 30);
print_list(head1);
head2 = reverse(head1);
print_list(head2);
return 0;
}
연결 리스트로 구현한 다항식 덧셈 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode { // 노드 타입
int coef;
int expon;
struct ListNode *link;
} ListNode;
// 연결 리스트 헤더
typedef struct ListType { // 리스트 헤더 타입
int size;
ListNode *head;
ListNode *tail;
} ListType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 리스트 헤더 생성 함수
ListType* create()
{
ListType *plist = (ListType *)malloc(sizeof(ListType));
plist->size = 0;
plist->head = plist->tail = NULL;
return plist;
}
// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수,
// expon는 지수
void insert_last(ListType* plist, int coef, int expon)
{
ListNode* temp =
(ListNode *)malloc(sizeof(ListNode));
if (temp == NULL) error("메모리 할당 에러");
temp->coef = coef;
temp->expon = expon;
temp->link = NULL;
if (plist->tail == NULL) {
plist->head = plist->tail = temp;
}
else {
plist->tail->link = temp;
plist->tail = temp;
}
plist->size++;
}
// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
ListNode* a = plist1->head;
ListNode* b = plist2->head;
int sum;
while (a && b) {
if (a->expon == b->expon) { // a의 차수 > b의 차수
sum = a->coef + b->coef;
if (sum != 0) insert_last(plist3, sum, a->expon);
a = a->link; b = b->link;
}
else if (a->expon > b->expon) { // a의 차수 == b의 차수
insert_last(plist3, a->coef, a->expon);
a = a->link;
}
else { // a의 차수 < b의 차수
insert_last(plist3, b->coef, b->expon);
b = b->link;
}
}
// a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두
// 결과 다항식으로 복사
for (; a != NULL; a = a->link)
insert_last(plist3, a->coef, a->expon);
for (; b != NULL; b = b->link)
insert_last(plist3, b->coef, b->expon);
}
//
//
void poly_print(ListType* plist)
{
ListNode* p = plist->head;
printf("polynomial = ");
for (; p; p = p->link) {
printf("%d^%d + ", p->coef, p->expon);
}
printf("\n");
}
//
int main(void)
{
ListType *list1, *list2, *list3;
// 연결 리스트 헤더 생성
list1 = create();
list2 = create();
list3 = create();
// 다항식 1을 생성
insert_last(list1, 3, 12);
insert_last(list1, 2, 8);
insert_last(list1, 1, 0);
// 다항식 2를 생성
insert_last(list2, 8, 12);
insert_last(list2, -3, 10);
insert_last(list2, 10, 6);
poly_print(list1);
poly_print(list2);
// 다항식 3 = 다항식 1 + 다항식 2
poly_add(list1, list2, list3);
poly_print(list3);
free(list1); free(list2); free(list3);
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 6장 연습문제 해설을 가져오도록 하겠습니다.
반응형