배열 기반의 리스트(List)2

전의 예제를 토대로 리스트를 구현하자 .

LCount는 별도의 설명이 필요없다.

 

//ArrayList.c
#include <stdio.h>
#include "ArrayList.h"

//리스트의 초기화
void ListInit(List *plist)
{
 	(plist -> numOfData) = 0; //저장된  데이터의 수 
    (plist -> curPosition) = -1;  //참조되는 위치(배열인덱스값)
}

//데이터의 삽입
void LInsert(List * plist, LData data)
{
	if(plist ->numOfData >= LIST_LEN) //저장된 데이터 수가 배열의 길이를 넘으면
    {
		puts("저장이 불가능합니다.");
        return;
   	}
    
    plist->arr[plist ->numOfData] =data;  //현재 데이터 수의 위치에 data값 삽입
    (plist->numOfData)++;  				//저장 데이터 수 증가
}

//데이터 참조
int LFirst(LIst *plist , LData *pdata)
{
	if(plist->numOfData ==0)  //저장 데이터가 없으면
      	return FALSE;
        
   	(plist ->curPosition) = 0;  //참조 위치의 인덱스 값을 0으로 초기화
    *pdata = plist->arr[0];   //*pdata가 가리키는 공간에 arr[0]에 있는 데이터 저장
    retrun TRUE;
}

int LNext(List *plist ,LData *pdata)
{
	if(plist ->curPosition >= (plist -> numOfData)-1)  //더이상 참조할 데이터가 없으면
      	reutnr FALSE;
        
   	(plist -> curPosition)++;  	//참조값 증가 순서대로 데이터 참조할수 있게 해줌
    *pdata = plist -> arr[plist ->curPosition];
    return TRUE;
}

//최근에 참조된 데이터 삭제
LData LRemove(List *plist)
{
	int rpos = plist ->curPosition;  //삭제할 위치 인덱스 임시 저장
    int num = plist -> numOfData;    //총 갯수 임시 저장
    int i;
    LData rdata = plist ->arr[rpos];  //삭제할 데이터를 임시저장
    
    for(i=rpos; i<num-1; i++)	//삭제됬으므로 배열 한칸씩 땡기기
    	plist->arr[i] = plist ->arr[i+1];  
        
    (plist->numOfData)--;  	//총 데이터 갯수 감소
    (plist->curPosition)--; 	//참조 위치를 하나 감소시켜 삭제된 위치의 전으로 되돌림
    return rdata;  	//삭제값 반환
}

int LCount(List *plist)
{
	return plist->numOfData;
}

이로써 배열 기반 리스트를 구현하였다.  

우리가 만든 리스트를 사용하기 위해서는 헤더파일 ArrayList.h를 포함하고, 이 헤더 파일에 선언된 함수의 기능을 숙지하면 된다.

 

---

리스트에 구조체 변수 저장하기 1 : 구조체 Point 와 관련 함수들의 정의

앞에서는 설명의 편의를 위해서 단순히 정수를 젖아하였는데, 실제로는 구조체 변수를 비롯해서 각종 데이터들이 저장된다. 따라서 우리가 정의한 리스트에 '구조체 변수의 주소 값'을 저장해보자.

이를 위해서 다음 구조체를 정의한다.

 

typedef struct _point

{

       int xpos;

     int ypos;

}Point;

 

다음은 구조체와 관련있는 함수들도 함께 정의  한다.

void SetPointPos(Point *ppos, int xpos, int ypos);  //값을 저장

void ShowPointPos(Point *ppos);   //정보 출력

int PointComp(Point *pos1, Point * pos2);  //비교

 

SetPointPos 함수는 구조체 변수에 값을 저장하는 함수이고, ShowPointPos는 이렇게 저장된 값의 정보를 출력하는 함수이다. 그리고 마지막으로 PointComp함수는 두 구조체 변수에 저장된 값을 비교하여 그 결과를 반환하는 함수이다.  이 함수가 반환하는 값은 다음과 같이 정의한다.

두 Point 변수의 멤버 xpos만 같으면 1반환

두 Point 변수의 멤버 ypos만 같으면 2반환

두 Point 변수의 멤버가 모두 같으면 0반환

두 Point 변수의 멤버가 모두 다르면 -1반환

 

//Point.h
#ifndef __POINT_H__
#define __POINT_H__

typedef struct _point
{
 	int xpos;
    int ypos;
}Point;

//Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point * ppos, int xpos, int ypos);

//Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point *ppos);

//두 Point 변수의 비교
int PointComp(Point *pos1, Point * pos2);

#endif

//Point.c
#include <stdio.h>
#include "Point.h"

void SetPointPos(Point *ppos, int xpos, int ypos)
{
	ppos->xpos = xpos;
    ppos->ypos = ypos;
}

void ShowPointPos(Point * ppos)
{
	printf("[%d, %d] \n", ppos->xpos, ppos->ypos);
}

int PointComp(Point *pos1, Point *pos2)
{
	if(pos1->xpos == pos2->xpos && pos1->ypos == pos2 ->ypos)
    	return 0;
    else if(pos1->xpos == pos2 -> xpos)
    	return 1;
    else if(pos1->ypos == pos2 ->ypos)
    	return 2;
    else
    	return -1;
}       

 

---

리스트에 구조체 변수 저장하기2 : 구조체 Point 와 관련 함수들의 정의

이제 다음 두파일이 담겨있는 코드를 Point 구조체 변수의 주소 값을 저장할 수  잇도록 변경하자

ArrayList.h  배열 기반 리스트의 헤더파일

ArrayList.c  배열 기반 리스트의 소스파일

이 중에서 헤더파일은 일부 변경해야 한다. 

typedef int LData; (typedef 선언 변경) ->  typedef Point *LData;

 

물론 Point 라는 구조체의 이름이 등장 했으니, 다음의 헤더파일의 선언이 추가되어야 한다.

#include "Point.h"  //ArrayList.h에 추가할 헤더파일 선언문

 

//PointListMain.c
#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"

int main()
{
	List list;  	//리스트의 선언
    Point compPos;	//비교값을 담을 구조체변수 선언
    Point *ppos;	//데이터를 저장할 변수 선언
    
    ListInit(&list); //리스트의 초기화
    
    //4개의 데이터 저장
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos,2,1);
    LInsert(&list, ppos);
    
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos,2,2);
    LInsert(&list, ppos);
    
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos,3,1);
    LInsert(&list, ppos);
    
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos,3,2);
    LInsert(&list, ppos);
    
    //저장된 데이터의 출력
    printf("현재 데이터의 수 : %d \n", LCount(&list));
    
    if(LFirst(&list, &ppos))
    {
		ShowPointPos(ppos);
        
        while(LNext(&list, &ppos))
        	ShowPointPos(ppos);
  	}
	printf("\n");
    
    //xpos가 2인 모든 데이터 삭제
    comPos.xpos == 2;
    comPos.ypos == 0;
    
    if(LFirst(&list, &data))
    {
    	if(PointComp(ppos, &compPos) == 1)
        {
        	ppos = LRemove(&list);
            free(ppos);
       	}
        
        while(LNext(&list, &ppos))
        {
        	if(PointComp(ppos, &compPos)==1)
            {
            	ppos= LRemove(&list(;
                free(ppos);
          	}
       	}
   	}
    
    //삭제 후 남은 데이터전체 출력
    printf("현재 데이터의 수 : %d \n", LCount(&list));
    
    if(LFirst(&list, &ppos))
    {
		ShowPointPos(ppos);
        
        while(LNext(&list, &ppos))
        	ShowPointPos(ppos);
  	}
	printf("\n");
    
    return 0;
}
================================실행 결과======================================
현재 데이터 수 : 4
[2,1]
[2,2]
[3,1]
[3,2]

현재 데이터 수 : 2
[3, 1]
[3, 2]

 

위의 main함수를 보면 LRemove함수가 삭제된 데이터를 반환하도록 디자인 한 이유를 알 수 있다.

위의 예제에서 리스트에 저장한 데이터는 'Point 구조체 변수의 주소 값'이다 . 물론 이 주소값은 Point 구조체를 동적을 할당한 결과이기 때문에, 반드시 free함수를 통한 메모리의 해제과정을 거쳐야 한다.

 

일반적인 리스트는 메모리의 해제까지의 책임을 지지 않는다. 리스트에 저장된 값이 주소값인 경우 , 그리고 그 주소값이 동적 할당의 결과인 경우를 구분하여 메모리 해제를 진행하도록 구현하는 것은 무리이다.

때문에 LRemove 함수처럼 데이터를 소멸하는 함수는 , 소멸된 데이터를 반환하도록 정의 해야한다. 

그래서 메모리 소멸의 기회를 줄 수 있어야 한다.

조금 달리말하면, 할당된 메모리 소멸의 책임을 전가해야 한다.