1.리스트란?
- 리스트(list), 선형리스트(linear list) : 순서를 가진 항목들의 모임.
2. 리스트의 연산
- 새로운 항목을 리스트의 처음, 중간 , 끝에 추가한다.
- 기존의 항목을 리스트의 임의의 위치에서 삭제한다.
- 모든 항목을 삭제한다.
- 리스트가 특정한 항목을 가지고 있는지 확인.
- 리스트의 특정위치 항목을 반환.
- 리스트의 항목개수를 세고, 안에 비었는지 꽉 찼는지 채크한다.
- 리스트 안의 모든 항목을 표시.
3.리스트 구현 방법
- 배열을 이용하는 방법
→ 구현방법이 간단함.
→ 삽입 및 삭제 할 경우 오버헤드 발생.
→ 항목의 개수가 제한됨.
- 연결리스트를 이용하는 방법
→ 구현방법이 복잡함.
→ 삽입,삭제가 효율적임.
→ 크기가 별도로 제한되지 않음.
4. 배열로 구현된 리스트
|
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 |
#include<stdio.h>
#include<stdlib.h>
#define MAX_LIST_SIZE 100 // 배열의 최대 사이즈 선언
typedef int element; //리스트의 요소 선언
typedef struct
{
int list[MAX_LIST_SIZE]; //배열 정의
int length; //현재 배열에 저장된 자료들의 길이
}ArrayListType;
void error(char *message) // 오류 처리 함수
{
fprintf(stderr, "%s \n", message);
exit(1);
}
void init(ArrayListType *L) //리스트 초기화 함수.
{
L->length = 0;
}
// list가 비어있으면 1을 반환.
//그렇치 않으면 0을 반환.
int is_empty(ArrayListType *L)
{
return L->length == MAX_LIST_SIZE;
}
//list가 가득 차있으면 1을 반환
//그렇치 않으면 0을 반환
int is_full(ArrayListType *L) {
return L->length == MAX_LIST_SIZE;
}
//list출력 함수.
void display(ArrayListType *L)
{
int i;
for (i = 0; i<L->length; i++)
printf("%d \n", L->list[i]);
}
//position : 삽입하고자 하는 위치
//item : 삽입하고자 하는 자료
void add(ArrayListType *L, int position, element item)
{
if (!is_full(L) && (position >= 0) && (position <= L->length))
{
int i;
for (i = (L->length - 1); i >= position; i--)
L->list[i + 1] = L->list[i];
L->list[position] = item;
L->length++;
}
}
//position : 삭제하고자 하는 위치
//반환값 : 삭제되는 자료
element _delete_(ArrayListType *L, int position)
{
int i;
element item;
if (position<0 || position >= L->length)
error("위치오류");
item = L->list[position];
for (i = position; i<(L->length - 1); i++)
L->list[i] = L->list[i + 1];
L->length--;
return item;
}
//position의 위치의 요소를 item으로 대채
void replace(ArrayListType *L, int position, element item)
{
if (is_empty(L) == 1)
printf("비어있습니다.");
else if (position<0 || position >= L->length)
printf("위치오류");
L->list[position] = item;
}
//현재 리스트의 길이를 구해서 출력.
void get_length(ArrayListType *L)
{
int len;
len = L->length;
printf("리스트의 길이는 %d 입니다. \n", len);
}
//init와 같은 리스트 초기화 함수.
void clear(ArrayListType *L)
{
L->length = 0;
}
int main()
{
ArrayListType list1;
ArrayListType *plist;
//ArrayListType의 구조체를 정적으로 생성하고 이 구조체를 가리키는
// 포인터를 함수의 매개변수로 전달.
init(&list1);
add(&list1, 0, 10);
add(&list1, 0, 20);
add(&list1, 0, 30);
display(&list1);
get_length(&list1);
//ArrayListType의 구조체를 동적으로 생성하고 이 구조체를 가리키는
// 포인터를 함수의 매개변수로 전달.
plist = (ArrayListType *)malloc(sizeof(ArrayListType));
init(plist);
add(plist, 0, 10);
add(plist, 0, 20);
add(plist, 0, 30);
is_empty(plist);
get_length(plist);
add(plist, 0, 40);
add(plist, 0, 50);
add(plist, 0, 60);
get_length(plist);
clear(plist);
free(plist);
return 0;
} |
cs |
이렇듯 순차적으로 만들어져서 각 list에 저장된것을 알 수 가 있다.
'programing > C,자료구조' 카테고리의 다른 글
| 리스트(3) - 이중 연결 리스트 (0) | 2017.04.07 |
|---|---|
| 리스트 - (2) 선형 리스트, 원형 리스트 (0) | 2017.04.03 |
| C언어 pragma (0) | 2017.03.28 |
| 순환 (0) | 2017.03.13 |
| 자료구조와 알고리즘 (0) | 2017.03.08 |
