연결 리스트(Linked list) 1-2

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

리스트의 이해

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

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

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

 

리스트 자료구조의 기본적이고 중요한 특성

- 리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다.

 

리스트 자료구조의 ADT

void ListInit(List * plist);

-초기화 할 리스트의 주소 값을 인자로 전달한다.

-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

 

void LInsert(List * plist, LData data);

-리스트에 데이터를 저장한다. 매개 변수 data에 전달된 값을 저장한다.

 

int LFirst(List * plist, LData * data);

-첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.

-데이터의 참조를 위한 초기화가 진행된다.

-참조 성공시 TRUE(1), 실패시 FALSE(0) 반환

 

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

-참조된 데이터의

 

LData LRemove(List * plist);

-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.

-삭제된 데이터는 반환된다.

-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다. 

 

list관련 함수들

함수들에 대한 소스코드이다. list를 사용하기 위해서는 변수 들의 초기화에 해당하는 ListInit 함수를 호출해야한다. 이후 LInsert 함수를 통해 list에 데이터를 삽입 시킬 수가 있다.

 

데이터 참조에 사용되는 함수는 LFirst와 LNext이다. LNext가 호출되기 위해서는 반드시  LFirst가 호출되어야 한다. 이후 LNext를 호출하여 list를 순차적으로 참조할 수있다. LNext함수는 호출 할 때마다 다음에 저장된 데이터를 얻을 수 있다.

 

데이터 삭제에는 LRemove함수가 사용된다. LFrist나 LNext함수를 통해 참조된 데이터를 삭제하는데 사용된다.

LCount함수는 리스트에 저장되어있는 데이터의 수를 반환한다.

 

List를 이용한 문제 03-1

문제 03-1

 

List를 이용한 문제 03-2

 

NameCard.h

NameCard.h

문제 03-2(1)

문제03-2(2)