1. 추상자료형 (Abstract Data Type)
- 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것
- 예시 - wallet 이라는 구조체를 정의하였다면, 이를 기반으로 ADT를 정의 할 수 있다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
typedef struct _wallet
{
int coint100Num; //100원짜리 동전의 수
int bill5000Num; //5000원짜리 지폐의 수
} Wallet;
//Wallet의 ADT
int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
// 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다
// 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달
// 꺼내고자 하는 돈의 총액이 반환, 그만큼 돈이 차감
int PutMoney(Wallet * pw, int coinNum, int billNum)
// 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다
// 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달
// 넣은 만큼 동전과 지폐의 수가 증가
|
cs |
2. 리스트 자료구조 - 데이터를 나란히 저장한다 / 중복된 데이터의 저장을 막지 않는다
- 순차리스트 - 배열을 기반으로 구현된 리스트
- 연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트
- 리스트 자료구조의 ADT 정의 예시
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
//리스트 자료구조의 ADT
void ListInit(List * plist);
//초기화할 리스트의 주소 값을 인자로 전달
//리스트 생성 후 제일 먼저 호출되어야 하는 함수
void LInsert(List * plist, LData data);
//리스트에 데이터를 저장
//매개변수 data에 전달된 값을 저장
void LFirst(List * plist, LData * pdata);
//첫 번째 데이터를 pdata가 가리키는 메모리에 저장
//데이터의 참조를 위한 초기화가 진행
//참조 성공 시 True(1), 실패 시 False(0) qksghks
void LNext(List * plist, LData * pdata);
//참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장됨
//순차적인 참조를 위해서 반복 호출이 가능
//참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야함
//참조 성공 시 True(1), 실패 시 False(0) 반환
void LData(List * plist);
//LFirst 혹은 LNext 함수의 마지막 반환 데이터를 삭제
//삭제된 데이터는 반환됨
//마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다
void LCount(List * plist);
//리스트에 저장되어 있는 데이터의 수를 반환
//리스트 ADT를 기반으로 정의된 main 함수 예시
#include <stdio.h>
#include "ArrayList.h"
int main(void)
{
//ArrayList의 생성 및 초기화
List list;
int data;
ListInit(&list);
//5개의 데이터 저장
LInsert(&list, 11); LInsert(&list, 11);
LInsert(&list, 22); LInsert(&list, 22);
LInsert(&list, 33);
//저장된 데이터의 전체 출력
printf("현재 데이터의 수: %d \n", LCount(&list));
if (LFirst(&list, &data)
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n")
if(LFirst(&list, &data))
{
if(data == 22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data == 22)
LRemove(&list);
}
}
return 0;
}
|
cs |
3. 순차 리스트 - 배열 기반의 리스트 자료구조
- 배열 기반 리스트 구현을 위한 헤더파일
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
#define LIST_LEN 100
typedef int LData;
typedef struct __ArrayList // 배열 기반 리스트를 정의한 구조체
{
LData arr[LIST_LEN]; // 리스트의 저장소인 배열
int numOfData; // 저장된 데이터의 수
int curPosition; // 데이터 참조위치를 기록
} ArrayList;
typedef ArrayList List;
void ListInit(List * plist);
void LInsert(List * plist, LData data);
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
LData LRemove(List * plist);
int LCount(List * plist);
#endif
|
cs |
- 배열 기반 리스트의 단점: 1. 배열의 길이가 초기에 결정되어야 하고 변경이 불가능 2. 삭제의 과정에서 데이터의 이동이 매우 빈번히 일어난다
- 배열 기반 리스트의 장점: 1. 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능
4. 연결 리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 자료구조
- 노드를 표현한 구조체의 정의
|
1
2
3
4
5
6
7
8
|
typedef int LData // 상황에 따라 변경
typedef struct _node
{
LData data; // 데이터를 담을 공간
struct _node * next; // 연결의 도구
} Node;
|
cs |
- 단순 연결 리스트 - 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재
- 머리에 새로운 노드를 추가하는 경우
- 장점: 포인터 변수 tail이 불필요
- 단점: 저장된 순서를 유지하지 않는다
- 꼬리에 새로운 노드를 추가하는 경우
- 장점: 저장된 순서가 유지된다
- 단점: 포인터 변수 tail이 필요
- 머리에 새로운 노드를 추가하되 맨 앞에 더미 노드가 존재하는 구조
- 장점: 노드를 추가, 삭제, 조회하는 방법에 있어서 첫 번째 노드와 두 번째 이후의 노드에 차이가 없어진다 - 일관된 형태로 구성할 수 있다
- 머리에 새로운 노드를 추가하는 경우
--> 포인터 변수 tail을 유지하기 위해 넣어야 할 부가적인 코드가 번거로울 뿐만아니라 리스트 자료구조는 저장된 순서를 유지해야 하는 자료구조가 아니므로 1번의 방식을 많이 사용한다. 또한, 더미 노드를 추 가하면 장점이 더 커지므로 3번을 구현해 보겠음
- 더미 노드 기반의 단순 연결 리스트 (3번) 구조 헤더파일 정의
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int LData;
typedef struct _node
{
LData data;
struct _node * next;
} Node;
typedef struct __Linkedlist
{
Node * head;
Node * cur;
Node * before;
int numofData;
int (*comp)(LData d1, LData d2);
} LinkedList;
typedef LinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, LData data);
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
LData LRemove(List * plist);
int LCount(List * plist);
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2)); // 데이터 정렬 순서를 정하기 위한 함수가 추가됨
#endif
|
cs |
- 더미 노드 기반의 단순 연결 리스트 (3번) 구조 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"
void ListInit(List * plist)
{
plist->head = (Node*)malloc(sizeof(Node)); // 더미 노드의 생성
plist->head->next = NULL;
plist->comp = NULL;
plist->numOfData = 0;
}
void LInsert(List * plist, LData data)
{
Node * newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드의 생성
newNode->data = data;
newNode->next = plist->head->next;
plist->head->next = newNode;
(plist->numOfData)++;
}
int LFirst(List * plist, LData * pdata)
{
if (plist->head->next == NULL) // 더미 노드가 NULL을 가리킨다면, 반환할 데이터가 없다
return FALSE;
plist->before = plist->head; // before는 더미 노드를 가리키게 함
plist->cur = plist->head->next; // cur은 첫 번째 노드를 가리키게 함
*pdata = plist->cur->data; // 첫 번째 노드의 데이터를 전달
return TRUE; // 데이터 반환 성공
}
int LNext(List * plist, LData * pdata)
{
if (plist->cur->next == NULL) // cur이 NULL을 가리킨다면
return FALSE; // 반환할 데이터가 없다
plist->before = plist->cur; // cur이 가리키던 것을 before가 가리키게 함
plist->cur = plist->cur->next; // cur은 그 다음 노드를 가리킴
*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 전달
return TRUE; // 데이터 반환 성공
}
LData LRemove(List * plist)
{
// cur의 위치 재조정에 주목, 삭제 노드 이전 노드를 가리켜야 LNext 함수를 이용했을 시
// 그 다음 노드를 참조할 수 있다
Node * delNode = plist->cur; // 소멸 대상의 주소 값을 delNode에 저장
LData removeData = delNode->data; // 소멸 대상의 데이터를 removeData에 저장
plist->before->next = plist->cur->next; // 소멸 대상을 리스트에서 제거
plist->cur = plist->before; // cur이 가리키는 위치를 재조정
free(delNode); // 리스트에서 제거된 노드 소멸
(plist->numOfData)--; // 저장된 데이터의 수 하나 감소
return removeData; // 제거된 노드의 데이터 반환
}
int LCount(List * plist)
{
return plist->numOfData;
}
|
cs |
LRemove 함수 관련 이미지
- 연결 리스트에서 정렬기준 설정과 구현
- 연결 리스트의 정렬기준이 되는 함수를 등록하는 SetSortRule 함수
- SetSortRule 함수를 통해서 전달된 함수정보를 저장하기 위한 LinkedList의 멤버 comp
- comp에 등록된 정렬기준을 근거로 데이터를 저장하는 LInsert 함수
- SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, LInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다
123456789101112131415161718192021222324252627282930313233343536373839404142//어떤 함수건 SetSortRule의 인자가 될 수 있다int WhoIsPrecede(int d1, int d2){if(d1 < d2)return 0; //d1이 정렬 순서상 앞선다elsereturn 1; //d2가 정렬 순서상 앞서거나 같다}void SetSortRule(List * plist, int (*comp)(LData d1, LData d2){plist->comp = comp;}//정렬 기준 추가 전void LInsert(List * plist, LData data){Node * newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드의 생성newNode->data = data;newNode->next = plist->head->next;plist->head->next = newNode;(plist->numOfData)++;}//정렬 기준 추가 후void LInsert(List * plist, LData data){Node * newNode = (Node*)malloc(sizeof(Node));newNode->data = data; // 새 노드에 데이터 저장Node * pred = plist->head; // pred는 더미 노드를 가리킴while(pred->next != NULL && plist->comp(data, pred->next->data) !=0){pred = pred->next; // 다음 노드로 이동}newNode->next = pred->next; // 새 노드의 오른쪽을 연결pred->next = newNode; // 새 노드의 왼쪽을 연결(plist->numOfData)++; // 저장된 데이터의 수 하나}cs
- 원형 연결 리스트 (Circular Linked List)
- 단순 연결 리스트의 마지막 노드는 NULL을 가리켰다. 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다
- 단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다
- 기본 형태에 대한 그림
- 변형 원형 연결 리스트
- 위의 그림을 보면 head에 포인트가 있는 상황에서 꼬리에 새로운 노드를 추가하는 방식은 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야 한다.
- 따라서, 이 포인터 변수를 머리가 아닌 꼬리를 가리키게 하면 이야기는 쉬워진다
- 꼬리를 가리키는 포인터 변수는? tail
- 머리를 가리키는 포인터 변수는? tail->next
3. 원형 연결 리스트의 자료구조 헤더파일 정의
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
}Node;
typedef struct _CLL
{
Node * tail;
Node * cur;
Node * before;
int numOfData;
}CList;
typedef CList List;
void ListInit(List * plist);
void LInsert(List * plist, Data data); // 꼬리에 노드 추가
void LInsertFront(List * plist, Data data); // 머리에 노드 추가
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);
#endif
|
cs |
- 양방향 연결 리스트 (doubly Linked List) 또는 이중 연결 리스트
- 하나의 노드가 자신의 왼쪽과 오른쪽 노드를 동시에 가리키는 구조
- 양방향으로 조회가 가능하기 때문에, 한쪽 방향으로만 이동할 때 필요한 포인터 변수 before가 불필요 해진다.
- 양방향 연결리스트 타입 예시
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
//그림 5-17 기본적인 양방향 연결리스트 헤더 파일 및 구현 예시
#ifndef __DB_LINKED_LIST_H__ #define __DB_LIKNED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next; //오른쪽 노드를 가리키는 포인터 변수
struct _node * prev; //왼쪽 노드를 가리키는 포인터 변수
}Node;
typedef struct _DLinkedList
{
Node * head;
Node * cur;
int numOfData;
} DBLinkedList;
typedef DBLinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, Data data);
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata); //왼쪽 노드로 이동하며 조회할 수 있는 함수
int LCount(List * plist);
#endif
void ListInit(List * plist)
{
plist->head = NULL;
plist->numOfData = 0;
}
void LInsert(List * plist, Data data)
{
//더미노드가 존재하지 않기 때문에,
//첫 번째 노드를 추가하는 과정과, 두 번째 노드 이후를 추가하는 과정을
//나누어서 생각해야 한다
Node * newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = plist->head; //새 노드의 next를 NULL로 초기화
newNode->prev = NULL; //새 노드의 prev를 NULL로 초기화
if (plist->head != NULL)
{
plist->head->prev = newNode;
}
plist->head = newNode; //포인터 변수 head가 새 노드를 가리키게 함
(plist->numOfData)++;
}
int LFirst(List * plist, Data * pdata)
{
if(plist->head == NULL)
return FALSE;
plist->cur = plist->head;
*pdata = plist->cur->data;
return TRUE;
}
int LNext(List * plist, Data * pdata)
{
if(plist->cur->next == NULL)
return FALSE;
plist->cur=plist->cur->next;
*pdata = plist->cur->data;
return TRUE;
}
int LPrevious(List * plist, Data * pdata)
{
if(plist->cur->prev == NULL)
return FALSE;
plist->cur=plist->cur->prev;
*pdata = plist->cur->data;
return TRUE;
}
|
cs |
728x90
'Data Structures & Algorithms' 카테고리의 다른 글
| [Data Structures] 트리 (Tree) (0) | 2022.05.07 |
|---|---|
| [Data Structures] 큐 (Queue)와 덱 (Deque) (0) | 2022.05.06 |
| [Data Structures] 스택 (Stack) (0) | 2022.05.06 |
| [Data Structures] 재귀 (Recursion)의 이해 (0) | 2022.05.04 |
| [Data Structures] 자료구조와 알고리즘에 대한 기본 이해 (0) | 2022.05.04 |