3장 - 연결 리스트 1

연결리스트에 앞서 추상 자료형을 설명한다.
추상 자료형이 뭐지?? -_-?
추상....... 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것
이라고 하는데 뭔소린지 모르겠다.
기능을 나열한 것을 뭐라 표현할 수 있을까??
예를 들면 TV에 대한 공통된 기능을 보자.

1. tv를 켠다.
2. 채널을 바꾼다.
3. 볼륨을 바꾼다.
4. tv를 끈다.

위 기능은 tv라면 다 있어야 하는 기능이다. 이것을 추상 자료형이라고 한다.

이제 이 추상자료형(ADT : Abstract Data Type)을 자료구조 학습에 포함 시킨다.

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

리스트란 무엇인가? 리스트라는 자료구조는 구현 방법에 따라 2가지로 나뉜다.

1. 순차 리스트 - 배열을 기반으로 구현된 리스트
2. 연결 리스트 - 메모리의 동적 할당을 기갑으로 구현된 리스트

이번 장에는 1번 배열을 기반으로 구현된 순차 리스트를 알아볼까 한다.
순차 리스트의 중요한 특성은 아래와 같다.

데이터를 나란히 저장함, 중복된 데이터의 저장을 막지 않음

그럼 리스트 자료구조의 ADT를 정의해 보자.

*void ListInit(List * plist)
-초기화할 리스트의 주소 값을 인자로 전달한다.
-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

*void LInsert(List * plist, LData data)
-리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

*int LFirst(List * plist, LData * pdata)
-첫 번째 데이터가 pdata가 가르키는 메모리에 저장된다.
-데이터의 참조를 위한 초기화가 진행된다.
-참조 성공시 true(1), 실패시 false(0) 반환

*int LNext(List * plist, LData * pdata)
-참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
-순차적인 참조를 위해서 반복 호출이 가능하다
-참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야한다.
-참조 성공시 true(1), 실패시 false(0) 반환

*LData LRemove(List * plist)
-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
-삭제된 데이터는 반환한다
-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

*int LCount(List * plist)
-리스트에 저장되어 있는 데이터의 수를 반환한다.

아래는 위의 정의를 구현한 소스 코드다.
---------------------------------------------------------------------------------

이건 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;
(plist->numOfData)++;
}
//첫번째 데이터를 pdata가 가르키는 메모리에 저장
int LFirst(List * plist, LData * pdata)
{
if(plist->numOfData == 0)
return FALSE;

(plist->curPosition) = 0;
*pdata = plist->arr[0];
return TRUE;
}
//참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장
int LNext(List * plist, LData * pdata)
{
if(plist->curPosition >= (plist->numOfData)-1)
return FALSE;

(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
//LFirst 또는 LNext 함수의 마지막 반환 데이터를 반환
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;
}

---------------------------------------------------------------------------------
헤더 부분

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE 1 //'참'을 표현하기 위한 매크로 정의
#define FALSE 0 //'거짓'을 표현하기 위한 매크로 정의

/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData; //LDdata에 대한 typedef 선언

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
---------------------------------------------------------------------------------
내가 공부하면서 잘 이해가 안갔던 것은 삭제 부분 이었다.
이 부분만 따로 한번 더 보자

1. 삭제할 데이터를 찾는다.
2. 삭제할 데이터를 임시로 저장한다.
3. 삭제 뒷부분의 데이터 전부를 -1칸 이동시킨다.
4. 데이터 수를 -1 줄인다.
5. 참조위치를 -1 한다.
6. 임시 저장한 데이터를 반환한다.(뭐를 지웠는지 보여주기 위함)


책에는 그림으로도 설명되어 있어서 더 이해가 빠르다.
왠만하면 책도 사서 보자.

책은 "윤성우의 열혈 자료구조" 이다.