3.연결리스트 - 배열

 

 

추상 자료형(ADT)의 이해

 

추상자료형이란?

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것

 

 

지갑을 의미하는 구조체 Wallet의 정의

 

int TakeoutMoney(Wallet* pw, int coinNum, int billNum);

-첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.

-두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달한다.

-꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

 

void PutMoney(Wallet* pw, int CoinNum, int billNum);

-첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다.

-두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다.

-넣은 만큼 동전과 지폐의 수가 증가한다.

 

main함수에서 사용하는 모습
int main()
{
    Wallet myWallet; //지갑장만
    PutMoney(&myWallet, 5, 10);//돈을 넣는다.
    ret = TakeoutMoney(&myWallet,2,3);//돈을 꺼낸다.

    return 1;
}

이처럼 ADT는 내부의 구현을 상세하게 몰라도 사용할 수 있다. 예로 FILE 구조체를 모르고 사용을 하는 것도 마찬가지다. 구조체 또는 클래스를 정의 할때 ADT를 미리 정의 해놓으면 구현하는데 어려움이 덜하다.

 

자료구조 학습의 옳은 순서

1. 리스트 자료구조의 ADT를 정의한다.

2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다.

3. ADT를 근거로 리스트를 구현한다.

 

*자료구조의 내부 구현을 모르고도 해당 자료구조의 활용이 가능하도록 ADT를 정의하는 것이 옳다.

*main 함수를 먼저 접하게 되면, 구현할 자료구조를 구성하는 함수들을 잘 이해 할 수 있다.

 

배열을 이용한 리스트의 구현

리스트라는 자료구조는 구현방법에 따라 두가지로 나뉜다.

 

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

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

​

리스트의 가장 기본적이고 중요한 특성

-리스트는 선형 자료구조이며 데이터의 중복저장을 막지 않는다.

 

ArrayList.h 예제

ArrayList.c 예제

main.m 예제

 

메모리 해제는?

리스트 자체에서 포인터 변수에 들어있는 주소값이 동적할당되어서, 힙영역에 있는 메모리의 주소값인지, 스택영역에 있는 메모리의 주소값인지 동적으로 구분하기가 어렵다. 따라서 Remove함수의 리턴값을 삭제할 데이터의 주소값으로 전달하여서 메모리 해제의 책임을 외부로 전가하는게 바람직하다.

 

리스트에 구조체를 넣을때 포인터를 많이 쓰는 이유?

리스트에 있는 자료를 복사, 참조할때  포인터로 되어있지 않은 자료를 대상으로 연산을 하면 그 내용을 복사해서 새로운 변수로 만들어야 하기 때문에 효율이 좋지 않을 수 있다. 그리고 복사의 과정에서 얕은복사 깊은복사에 관한 이슈도 발생하기 때문에 번거롭다.

 

 

0901.zip

0.02MB

 

 

 

 

응용예제

 

 

 

 

List.zip

0.04MB

 

 

 

 

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