가자미의 개발이야기

C언어로 구현한 리스트 자료구조(ArrayList) 본문

Computer Science/자료구조

C언어로 구현한 리스트 자료구조(ArrayList)

가자미 2021. 2. 3. 16:55

1. 헤더파일(ArrayList.h)

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
//전처리 지시자
#ifndef _ARRAYLIST_
#define _ARRAYLIST_
 
typedef struct ArrayListNodeType {
    int data;
}ArrayListNode;
 
typedef struct ArrayListType {
    int maxElementCount;//최대원소갯수
    int currentElementCount;//현재 원소의 개수
    ArrayListNode* pElement;//원소 저장을 위한 1차원 배열
}ArrayList;
 
//함수 선언
ArrayList* createArrayList(int maxElementCount);
void deleteArrayList(ArrayList* pList);
int isArrayListFull(ArrayList* pList);
int addALElement(ArrayList* pList, int position, ArrayListNode element);
int removeALElement(ArrayList* pList, int position);
ArrayListNode* getALElement(ArrayList* pList, int position);
void displayArrayList(ArrayList* pList);
void clearArrayList(ArrayList* pList);
int getArrayListLength(ArrayList* pList);
 
#endif
 
//상수값 선언
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
 
#define TRUE    1
#define FALSE    0
 
#endif
 cs

2.함수정의 파일(ArrayList.c)

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arraylist.h"
 
ArrayList* createArrayList(int maxElementCount) {    //배열리스트를 생상하는 함수
    ArrayList* pReturn = NULL;
    int i = 0;
 
    if (maxElementCount > 0) {    //최대 원소크기 0이상인지 확인
        pReturn = (ArrayList*)malloc(sizeof(ArrayList));//구조체만큼 메모리 할당
 
        if (pReturn != NULL) {    //메모리 할당 성공 확인
            pReturn->maxElementCount = maxElementCount;
            pReturn->currentElementCount = 0;
            pReturn->pElement = NULL;
        }
        else {
            printf("오류, 메모리할당 createArrayList()\n");
        }
    }
    else {
        printf("오류, 원소의 최대 개수는 0 이상이어야 합니다.\n");
    }
 
    pReturn->pElement = (ArrayListNode*)malloc(sizeof(ArrayListNode)*maxElementCount);//구조체 요소에 메모리 할당
    if (pReturn->pElement == NULL) {//할당 성공 확인
        printf("오류, 2번째 메모리 할당 createArrayList()\n");
        free(pReturn); return NULL;
    }
    memset(pReturn->pElement, 0, sizeof(ArrayListNode) * maxElementCount);//요소를 0으로 초기화
    return pReturn;
}
int addALElement(ArrayList* pList, int position, ArrayListNode element) {
    int ret = FALSE;
    int i = 0;
 
    if (pList != NULL) {
        if(isArrayListFull(pList) != TRUE) {    //배열에 자리 있는 지 확인
            if (position >= 0 && position <= pList->currentElementCount) {    //놓으려는 위치가 적절한지 확인
                for (i = pList->currentElementCount - 1; i >= position; i--) {   
                    pList->pElement[i + 1] = pList->pElement[i];
                }
                pList->pElement[position] = element;
                pList->currentElementCount++;
                ret = TRUE;
            }
            else {
                printf("오류, 위치인덱스-[%d] 범위 초과, addALElement()\n",position);
            }
        }
        else {
            printf("오류, 리스트 용량 초과-[%d]/[%d]\n", position, pList->maxElementCount);
        }
    }
    return ret;
}
int removeALElement(ArrayList* pList, int position) {
    int ret = FALSE;
    int i = 0;
 
    if (pList != NULL) {
        if (position >= 0 && position < pList->currentElementCount) {    //인덱스 값이 적절한지 확인
            for (i = position; i < pList->currentElementCount - 1; i++) {
                pList->pElement[i] = pList->pElement[i + 1];
            }
            pList->currentElementCount--;
            ret = TRUE;
        }
        else {
            printf("오류, 위치 인덱스-[%d] 범위 초과, removeALElement().", position);
        }
        return ret;
    }
}
ArrayListNode* getALElement(ArrayList* pList, int position) {
    ArrayListNode* pReturn = NULL;
    if (pList != NULL) {
        if (position >= 0 && position < getArrayListLength(pList)) {
            pReturn=&(pList->pElement[position]);
        }
        else {
            printf("오류, 위치 인덱스-[%d] 범위 초과, getALElement()\n", position);
        }
        return pReturn;
    }
}
void displayArrayList(ArrayList* pList) {
    int i = 0;
    if (pList != NULL) {
        printf("최대 원소 개수: %d\n", pList->maxElementCount);
        printf("현재 원소 개수: %d\n", pList->currentElementCount);
 
        for (i = 0; i <= pList->currentElementCount - 1; i++) {    //내용물 출력
            printf("[%d],%d\n", i, getALElement(pList, i)->data);
        }
        i = pList->currentElementCount;
        for (; i < pList->maxElementCount; i++) {    //비어있는 공간 출력
            printf("[%d], Empty\n", i);
        }
    }
    else {
            printf("ArrayList is NULL");
    }
}
int isArrayListFull(ArrayList* pList) {
    int ret = FALSE;
    if (pList != NULL) {
        if (pList->currentElementCount == pList->maxElementCount) {
            ret = TRUE;
        }
    }
    return ret;
}
int getArrayListLength(ArrayList* pList) {
    int ret = 0;
    if (pList != NULL) {
        ret = pList->currentElementCount;
    }
    return ret;
}
void clearArrayList(ArrayList* pList) {
    int ret = 0;
    ArrayListNode node;
    node.data = 0;
    if (pList != NULL) {
        for (int i = pList->currentElementCount - 1; i >= 0; i--) {
            pList->pElement[i] = node;
        }
    }
}
void deleteArrayList(ArrayList* pList) {
    int i = 0;
    if (pList != NULL) {
        free(pList->pElement);    //리스트에 내용을 저장한 메모리를 해제
        free(pList);    //리스트 구조체 내용을 저장한 메모리를 해제
    }
}
int addALElementFirst(ArrayList* pList, int element) {
    int position = 0;
    ArrayListNode node;
    node.data = element;
    return addALElement(pList, position, node);
}
int addALElementLast(ArrayList* pList, int element) {
    int ret = FALSE;
    int position = 0;
    if (pList != NULL) {
        position = getArrayListLength(pList);
        ArrayListNode node;
        node.data = element;
        ret = addALElement(pList, position, node);
    }
    return ret;
}
 cs


3.활용 예시 파일(Sample.c)

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
#include <stdio.h>
#include <stdlib.h>
#include "arraylist.h"
 
int main(int argc, char* argv[]) {
    int i = 0;
    int arrayCount = 0;
    ArrayList* pList = NULL;
    ArrayListNode* PValue = NULL;
 
    pList = createArrayList(6);
    if (pList != NULL) {
        ArrayListNode node;
        node.data = 1;
        addALElement(pList, 0, node);
 
        node.data = 2;
        addALElement(pList, 1, node);
 
        node.data = 3;
        addALElement(pList, 2, node);
        displayArrayList(pList);
 
        removeALElement(pList, 0);
        displayArrayList(pList);
 
        arrayCount = getArrayListLength(pList);
        for (i = 0; i < arrayCount; i++) {
            PValue = getALElement(pList, i);
            printf("위치 [%d]-%d\n", i, PValue->data);
        }
        clearArrayList(pList);
        displayArrayList(pList);
        deleteArrayList(pList);
    }
}
 cs

4.실행결과

 

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] C언어로 배열 스택 구현하기  (0) 2021.02.10
[자료구조] 연결리스트로 다항식 구현하기  (0) 2021.02.10
C언어로 원형 연결 리스트 만들기  (0) 2021.02.09
C언어로 링크드리스트(연결리스트) 만들기  (0) 2021.02.04
알고리즘 분석 기준  (0) 2021.01.29
'Computer Science/자료구조' Related Articles more