chapter 03. 연결 리스트(Linked list 1)

03-1

Abstrant Data Type

순수하게 기능..

자료형은 기능이다. 구체적인 기능을 언급하지 않고 그냥 순수하게 기능이다.  기능을 나열한다.

연산자이다.

int data ??  

> int num=10;  초기화를 할 때는 대입 연산자를 사용한다. 핵심..

num1+num2

자료형은 연산에 더 효용이 있다.

구조체의 정의. 자료형의 정의이다. 기능

03-2

C언어란?

1?

C라는 언어로 만들어진 프로그램은 함수로 시작해서 함수로 끝난다.

작은 함수를 만들어 호출 관계를 묶어 주어서 구성된다.

2? GOOD

프로그램이라는 것은 함수는 기능을 표현된다. 

DATA(구조체)를 정의하고 함수를 정의한다.

3 VERY GOOD. 

구조체로 정의한다. 더불어 함수도 같이 정의한다. = 자료형 정의이다.

구조체를 정의하고 연산을 담당하는 함수를 정의한다.(이렇게 말 해야 한다.)

자료형의 정의에서 연산이 정말 중요하다. 

03-1 abstract data type 3

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

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

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

03-2 배열을 이용한 리스트의 구현 1

#ifndef __ARRAY_LIST_H__  //매크로

#define __ARRAY_LIST_H__ //매크로 : 해더파일의 중복파일을 막기 위한 설정이다.

#define TRUE 1

#define FALSE 0

/*** ArrayList의 정의 ****/

#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

ArrayList.h 는 제공받는 것이 맞다.

ArrayList.c 는 보지 말 것.

ListMain.c 리스트 관련 main 함수가 담긴 소스파일..

리스트 자료구조는 데이터가 나란히 저장된다. 중복 저장을 허용한다. 

리스트 자료구조는 데이터를 저장하는 것.

리스트 자료구조는 데이터의 저장과 삭제 그리고 참조가 가능한 것이다.

int main(void)

{

LInset(&list, 11);

LInset(&list, 22);

LInset(&list, 33);

}

int main(void)

{

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

연결 리스트 : 메모리의 동적 할당

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

리스튼 저장이 나란히 된다. 기준만 만족하면 앞에서 뒤에서 저장 할 수도 있다.

LFirst

LNext

시작을 알리는 형태 존재, 두 번쨰를 알리는 형태가 존재한다.

03-2 배열을 이용한 리스트의 구현 3

int LFirst(List * plist, LDate * pdata)

{

if(plist

03-2 배열을 이용한 리스트의 구현4

리스트! 배열을 기반으로 구현하기3: 삭제

삭제되는 데이터는 반환된 과정을 통해서 되돌려주는 것이 옳다!!

LData LRmove(List * plist)

{

int rpos=plist -> plist->curPosition // 삭제할 데이터의 인덱스 값 참조

int num=plist->numOfData

int i;

LData rdata=plist->arr[rpos]; // 삭제할 데이터를 임시로 저장

// 삭제를 위한 데이터의 이동을 진행하는 반복문

for(i=rpos; i<num-1; i++)

plist->arr[i]

03-2 배열을 이용한 리스트의 구현 5

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

배열의 장점과 단점! 그리고 연결 기반 리스트

배열 기반 리스트의 단점

배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

배열 기반 리스트의 장점

데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

"배열도 각종 자료구조의 구현에 중요한 도구이고, 그 자체로도 훌륭한 자료구조입니다."