8-2장 포인터를 이용한 연결 리스트(1)

1. 포인터로 연결 리스트 만들기 

 

- 노드용 구조체 Node

 - data : 데이터 (Member형)

 - next : 다음 노드에 대한 포인터 (자기 자신과 같은 구조체형을 가리키는 포인터)

 

- 자기 참조형 (self-refernetial)

 - 자기 자신과 같은 자료형의 객체를 가리키는 데이터가 내부에 포함

//포인터로 만든 연결리스트 
#ifndef ___LinkedList
#define ___LinkedList

//노드 
typedef struct __node {
	Member data; //데이터
	struct __node *next; //뒤쪽 포인터(다음 노드에 대한 포인터)
}Node;

//연결 리스트 
typedef struct {
	Node *head; //머리 노드에 대한 포인터 
	Node *crnt; //선택한 노드에 대한 포인터  
}List;

 

2. 연결 리스트를 관리하는 구조체 List

 

리스트용 구조체 List

- 노드용 구조체 Node를 사용한 연결 리스트를 나타낸 것

 

head 

- 연결리스트의 머리 노드를 가리키는 머리 포인터 

- Node에 대한 포인터 자료형

 

crnt

- 현재 선택한 노드를 가리키는 선택 포인터 

- Node에 대한 포인터 자료형

 

 

3. 노드를 만드는 AllocNode 함수 

 

- Node형 객체를 만들고 만든 객체의 포인터를 반환

//노드를 동적으로 생성
static Node *AllocNode(void) 
{
	return calloc(1,sizeof(Node));
}

 

4. 노드의 멤버값을 설정하는 SetNode 함수 

 

- Node형 객체의 두 멤버 (data,next)의 값을 설정

//n이 가리키는 노드의 각 멤버에 값을 설정
static void SetNode(Node *n, const Member *x, const Node *next) 
{
	n->data = *x; //데이터 
	n->next = (Node*)next; //뒤쪽 포인터  
}

 

5. 연결 리스트를 초기화하는 Initialize 함수 

 

- 연결 리스트를 사용하기 전에 초기화 하는 함수 

//연결리스트를 초기화 
void Initialize(List *list) 
{
	list->head = NULL; //머리 노드 
	list->crnt = NULL; //선택 노드  
}

 

6. 연결리스트가 비어 있는지 판단하는 방법 

 

1) 노드가 하나도 없는 상태 

 

 - 현재 아무런 노드도 가리키고 있지 않음

//연결 리스트가 비어 있는지 (노드가 0개인지) 확인
List->head == NULL

 2) 노드가 1개 있는 상태

 

 - A는 list->head가 가리키는 머리 노드이면서 꼬리노드 

//노드가 1개인지 확인
list->head->next == NULL

 

 3) 노드가 2개 있는 상태 

 

 - 머리 노드 A

 - 두 번째 노드이자 꼬리노드는 B

 - 머리 포인터 list->head가 가리키는 노드 A의 next는 노드 B를 가리킴

//노드가 2개인지 확인
list->head->next->next == NULL

 

7. 포인터가 머리 노드를 가리키는지 판단하는 방법

 

- 자료형이 Node*형인 변수 p는 리스트의 노드 중 하나를 가리킴

//p가 가리키는 노드가 머리 노드인지 확인
p == list->head

 

8. 포인터가 꼬리 노드를 가리키는지 판단하는 방법

 

- 자료형이 Node*형인 변수 p는 리스트의 노드 중 하나를 가리킴

//p가 가리키는 노드가 꼬리 노드인지 확인
p->next == NULL

 

9. 검색을 수행하는 Search 함수 

 

- 어떤 조건을 만족하는 노드를 검색

//compare함수를 사용해 x를 검색 
Node *search(List *list, const Member *x, int compare(const Member *x, const Member *y)) 
{
	Node *ptr = list->head;
	while(ptr!=NULL) {
		if((compare(&ptr->data,x)==0) {
			//키 값이 같은 경우 
			list->crnt = ptr;
			return ptr; //검색 성공 
		}
		ptr=ptr->next; //다음 노드를 선택 
	}
	return NULL; //검색 실패  
}

-매개 변수 

• list : 검색 대상인 연결리스트를 가리키는 포인터
• x : 검색하는 키값을 저장한 회원 데이터를 가리키는 포인터 
• compare : x가 가리키는 객체와 연결 리스트의 노드 안의 데이터를 비교하는 함수를 가리키는 포인터 (성공시 0 반환)

 

-반환값 : 찾은 노드에 대한 포인터 , 실패시 NULL 반환

 

- 선형 검색 

 종료 조건 1: 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우

 or

 종료 조건 2: 검색 조건을 만족하는 노드를 찾은 경우 

 

 

1)

-ptr : 스캔하고 있는 노드를 가리키는 포인터 

-ptr을 list->head로 초기화

Node *ptr = list->head;

 

2)

-종료 조건 1 판단, ptr값이 널이면 스캔할 노드가 없음을 의미하므로 while문을 빠져 나옴

-종료 조건 2판단하기 위해 스캔하고 있는 노드의 데이터 ptr->data와 x가 가리키는 데이터를 compare함수로 비교

- 검색 성공

  -0 반환

  - list->crnt에 ptr을 대입하고 찾은 노드에 대한 포인터인 ptr을 반환 

while(ptr != NULL) {
	if((compare(&ptr->data,x) == 0) {
    	list->crnt = ptr;
        return ptr;
     }
     ptr = ptr->next;
}