01.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
void ListInit(List *plist){
(pdata ->numOfData) = 0;
(pdata ->curPostion) = -1; //-1은 아무런 위치도 참조하지 않았음을 의미.
}
void LInsert(List *plist, LData data){
//#define LIST_LEN 이 있음.
if(LIST_LEN <= plist->numOfData){
return;
//puts("저장이 불가능합니다.");
}
plist->arr[plist->numOfData] = data;
(plist->numOfData]+=1;
}
|
cs |
02.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
void LFirst(List *plist, Ldata *pdata){
if(plist->numOfData == 0) return FALSE; //저장된 데이터가 하나도 없다면
(plist->curPoistion) = 0;//참조위치 초기화.
//curposition 이번에 참조할 위치의 인덱스값으로 갱신. 어디까지 참조가 이뤄졌는지 알수있다.
*pdatda = plist->arr[0]; //*1
return TRUE;
}
void LNext(List *plist, Ldata *pdata){
if(plist->curposition >= (plist->numOfdata)-1) return FALSE; //*01
(pdata->curPosition)+=1;
*pdata = plist->arr[plist->curposition];//*02
return TRUE;
} |
cs |
*01 : 다음데이터가 있을수도, 없을수도 있다. 그래서 curposition과 다음데이터-1의 갯수를 비교.
같거나 curpostion이 크면 데이터가 꽉찼다는것.
*02 : *pdata=plist->arr[plist->curPosition]; 도 가능.
차이점: 기존거는 arr[0]이 있기때문에 한줄만보고 LFirst 인걸 알수 있고
두번째꺼는 윗줄까지 봐야 알수있다.
03.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
int LCount(List *plist){
return plist->numOfData;
}
LData LRemove(List *plist){
int curPos = plist->curPosition; //삭제할 데이터의 인덱스값 참조
int num = plist->numOfData;
LData rdata = plist->arr[curPos]; // 삭제할 데이터 임시저장
//? 왜: 빈자리 채우기위해 데이터 나머지 앞으로 땡겨서 덮어씌울거라서.
for(int i = curpos; i<num-1; i++){
plist->arr[i] = plist->Arr[i+1];
}
(plist->numOfData)-=1;//데이터의 수 감소
(plist->curPosition)-=1; //참조위치를 하나 되돌린다.
return rdata; //삭제되는 데이터의 값은 반환해야하는게 원칙.
} |
cs |
배열특성상 비운자리를 채워주지않으면 관리가 어렵기 때문에,
나머지 데이터를 한칸씩 땡겨서 빈자리를 채운다.(LRemove함수도 이거에 기반.)
<---유효한 데이터자리--->|<---빈 데이터자리---> 이렇게.
삭제할데이터는 curposition과 관련있다.
자리가 비었을때, curpostion의 인덱스값을 기준으로 하나씩
땡겨주는데 이때 참조데이터가 바뀐다.
(curpostion은 최근에 참조가 이루어진 데이터를 가르켜야한다.
여기서는 B.)
그래서 참조위치를 하나 땡겨준다.
보통 데이터를 remove하면 확인을 안한다.
-> 데이터 삭제시 삭제되는 데이터의 값은 반환해야하는게 원칙이다.(동적할당때문에)
-> 주소값을 실질적 데이터로 평가하기 때문에 주소값과 관련된 메모리해제는
리스트의 책임이 아니다. 그래서 이거 삭제했어! 하고 삭제데이터 반환하는것.
04.(삭제데이터값반환: 보류)
|
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 |
int main(void){
List list;
Point compPos;
Point *ppos;
ListInit(&list);
//4개의 데이터저장
ppos = (Point*)malloc(sizeof(Point));
SetPointPos(ppos, 2, 1);
LInsert(&list, ppos);
ppos=(Point*)mallc(sizeof(Point));
SetPointPos(ppos,2,2);
LInsert(&list, ppos);
...
//저장된 데이터 출력
printf("현재 데이터의수:%dn", LCount(&list));
if(LFirst(&list, &ppos)){
ShowPointPos(ppos);
while(LNext(&list, &ppos)) { ShowPointPos(ppos); }
}
printf("\n");
...
//xpos가 2인 모든 데이터 삭제
compPos.xpos = 2;
compPos.ypos = 0;
if(LFirst(&list, &ppos)){
if(PointComp(ppos, &compPos) == 1){
ppos = LRemove(&list);
free(ppos);
}
while(LNext(&list, &ppos)){
if(PointComp(ppos, &compPos)==1){
ppos = LRemove(&list);
free(ppos);
}
}
...
}
|
cs |
05.
배열 리스트의 단점: 배열의 길이가 초기에 결정되어야 한다.
변경이 불가능하다, 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번하다.
배열 리스트의 장점: 데이터 참조가 쉽다, 인덱스 값 기준으로 어디든 한번에 참조 가능하다.
'프로그래밍 > 간단메모' 카테고리의 다른 글
| [자료구조]순환_오답 (0) | 2017.03.01 |
|---|---|
| [자료구조]04.연결리스트_2 (0) | 2017.02.12 |
| [자료구조]04.연결리스트(Linked List) (0) | 2017.02.09 |
| [자료구조]재귀함수 (0) | 2017.01.18 |
| [자료구조]탐색알고리즘, 시간복잡도 (0) | 2017.01.18 |