추상 자료형과 리스트사용

2019.01.05.

 

추상자료형(Abstract Data Type)이란 어떠한 기능이 무엇인가를 나타내는것이다

 

내가 이해한 바로는 어떤 기능을 수행하는데 필요한 함수들을 나타내는것 같다.

 

 

자료구조 리스트는 두가지로 나뉜다.

- 순차 리스트: 배열을 기반으로 구현된 리스트

- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트

 

먼저 현재 공부하는 책에서 배열 리스트를 만드려하고 리스트 자료구조 ADT는 다음을 정의했다.

-ListInit: 리스트의 주소값을 인자로 전달

-LInsert: 리스트에 데이터를 저장 

-LFirst: 첫번째 데이터를 저장

-LNext: 참조된 데이터 다음 데이터를 메모리에 저장

-LRemove: 마지막 반환 데이터를 삭제

-LCount: 리스트에 저장되있는 데이터 수 반환

 

위의 정의를 헤더파일과 소스파일로 구분하여 구현하였다.

 

http://www.orentec.co.kr/teachlist/DA_ST_1/teach_sub1.php

위 주소에서 만들어져 있는 소스파일을 받아 올 수 있었다.

 

리스트를 활용하는 방법을 익히고 리스트의 정의를 세부적으로 살펴보았다.

ArrayList.h, ArrayList.c를 받아와서

 

1. 리스트 생성 및 초기화 후 정수 1-9까지 리스트에 저장

2. 리스트에 저장된 값의 합을 계산하여 출력

3. 리스트에 저장된 값중 2,3 배수 삭제

4. 리스트에 저장된 데이터 출력

 

#include <stdio.h>
#include "ArrayList.h"
 
int main(void)
{
 
    List list;
    int data;
    ListInit(&list);
    int total = 0;
 
    for (int i = 1;i < 10;i++)
    {
        LInsert(&list, i);
    }
 
    if (LFirst(&list, &data))
    {
        total += data;
        while (LNext(&list, &data))
            total += data;
    }
 
    printf("%d\n", total);
 
    if (LFirst(&list, &data))
    {
        if (data % 2 ==0 || data %3 ==0)
            LRemove(&list);
 
        while (LNext(&list, &data))
        {
            if (data % 2 == 0 || data % 3 == 0)
                LRemove(&list);
        }
    }
    
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        while(LNext(&list, &data))
            printf("%d ", data);
    }
    printf("\n\n");
 
    return 0;
}

 

 

실행 결과는 다음과 같았다.

 

이후로 현재 구현되 있는 ADT를 분석해 보았다.

 

ArrayList.h:

 

#define LIST_LEN    100
typedef int LData;
 
typedef struct __ArrayList
{
    LData arr[LIST_LEN];
    int numOfData;
    int curPosition;
} ArrayList;
 
 
/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;
 
void ListInit(List * plist);
void LInsert(List * plist, LData data);
 
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
 
LData LRemove(List * plist);
int LCount(List * plist);
 
#endif

 

ListInit

plist를 초기화하고 curPosition(현재위치)를 초기화한다.

 

LInsert

plist에 data를 저장한다. numOfData(현재데이터양)이 배열크기 이상이면 멈춘다.

 

LFirst

현재위치를 초기화하고 pdata공간에 plist[curPosition] 처음 저장된 내용을 저장한다.

 

LNext

참조할 데이터가 없으면 반환하고

현재위치+1하고 데이터에 다음 내용을 저장한다.

 

LRemove

현재위치를 확인하고 데이터 위치를 확인한후 데이터를 삭제한다.

데이터를 삭제하고 그 이후 index값들을 한칸 씩 당겨준다.

현재위치를 한칸 당겨준다.

 

 

참고: 윤성우의 열혈 자료구조

 

고찰: 

나중에 리스트를 스스로 구현해 봐야겠다.