박하의 나날

[자료구조] 배열을 이용한 리스트구현

프로그래밍/간단메모

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 == 0return FALSE; //저장된 데이터가 하나도 없다면
    
    (plist->curPoistion) = 0;//참조위치 초기화. 
    //curposition 이번에 참조할 위치의 인덱스값으로 갱신. 어디까지 참조가 이뤄졌는지 알수있다.
    *pdatda = plist->arr[0]; //*1
    return TRUE;
}
void LNext(List *plist, Ldata *pdata){
    if(plist->curposition >= (plist->numOfdata)-1return 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, 21);
    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.

배열 리스트의 단점: 배열의 길이가 초기에 결정되어야 한다.

변경이 불가능하다, 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번하다.

 

배열 리스트의 장점: 데이터 참조가 쉽다, 인덱스 값 기준으로 어디든 한번에 참조 가능하다.