연결 리스트 1

추상 자료형 | 리스트 자료구조

 

 

추상 자료형 ADT 

 

추상 자료형이란? 

Abstract Data Type 약자 ADT 라고 부르며,

어떠한 행위나 사물에서 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능만을 나열한 것이다. 

 

리스트 

 

다른 언어를 공부할 때 배웠던 리스트의 자료구조에 관해 알아보자

 

리스트는 구현 방법에 따라 두 가지 형태로 나뉜다. 

 

1. 순차 리스트 : 배열을 기반으로 구현, 배열의 길이 초기에 구현  

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

 

헤더파일 

#include "ArrayList.h"

 

 

리스트 자료구조의 ADT 

 

• void ListInit(List * plist); 

// 초기화할 리스트의 주소 값을 인자로 전달 

// 리스트 생성 후 제일 먼저 호출되어야 하는 함수 

• void LInsert(List * plist, LData * pdata); 

// 리스트에 데이터를 저장

// 매개변수에 전달된 값 저장 

• int LFirst(List * plist, LData * pdata);

// 첫 데이터가 pdata가 가리키는 메모리에 저장 

// 데이터의 참조를 위한 초기화 진행

// 참조 성공 시 True 실패 시 False 

• int LNext(List *  plist, LData * pdata);

// 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장

// 반복 호출 가능

// 새로운 참조를 시작하려면 다시 LFirst 함수 사용해야 함

// 참조 성공 시 True 실패 시 False 

• LData LRemove( LData* plist);

// 마지막 반환 데이터를 삭제 

// 삭제된 데이터는 반환 

// 반복호출이 허용되지 않음

// 삭제할 데이터 위치 참조와 데이터 이동 과정 필요 

• int LCount(List * plist);

// 저장된 데이터의 수를 반환

 

 

 

구조체 변수 저장

 

정수가 아닌 다른 데이터를 리스트에 저장하는 것이다. 

 

• void SetPointPos(Point * ppos, int xpos, int ypos);

// 값을 저장

• void ShowPointPos(Point * ppos);

// 정보 출력

• int PointComp(Point * pos1, Point * pos2);

// 비교 

 

헤더파일 #include "Point.h" 

 

 

 관련 함수  

 

strcpy 문자열 복사 함수 

헤더 파일 #include <string.h> 

 

 

문제코드 

 

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

int main() {
    List list;
    int data;
    int i;
    int sum;
    ListInit(&list); //리스트 초기화하기 

    for(i=1; i<10; i++)
        LInsert(&list, i); 

    if(LFirst(&list, &data)){ //리스트 합 계산
        sum+=data;

        while(LNext(&list, &data)) 
            sum+=data;
    }

    printf("sum: %d \n", sum);

    if(LFirst(&list, &data)){
        if(data%2)
            LRemove(&list);
        while(LNext(&list, &data)){
            if(data%2==0)
                LRemove(&list);
        }
    }
    if(LFirst(&list, &data)){
        printf("%d ", data);
        while(LNext(&list, &data))
            printf("%d ", data);
    }
    printf("\n\n");
    return 0;
}