연결 리스트 2-3

정렬

 

 

 

 

연결 리스트에서의 정렬 

 

연결 리스트에서 정렬 기준의 설정과 관련된 부분은 다음과 같다. 

 

정렬 ADT 

void SetSortRule(List * plist, int (*comp) (LData d1, LData d2)); 

 

void SetSortRule(List * plist, int (*comp) (LData d1, LData d2))
{
	plist->comp=comp;
}

 

 

SetSortRule 함수는 리스트의 멤버 comp를 초기화하며, SInsert 함수에서 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.  

 

 

while(pred->next != NULL && plist->comp(data, pred->next->data) != 0) 
{
	pred = pred->next;
}

 

반복문을 사용해서 pred 다음의 노드가 NULL값이 아니고 두 노드의 우선순위를 비교하여 d2노드가 정렬 순서상 앞서거나 같다면 pred 는 다음 노드로 넘어가게 한다.  

 

 

 

정렬의 기준을 설정하기 위한 함수

 

SetSortRule 함수의 인자가 될 수 있는 함수를 정의하는 것이다. 

 

두 개의 인자가 필요하고, 첫번째 인자의 정렬 우선순위 (오름차순) 가 높다면 0을, 그렇지 않으면 1을 반환한다. 

 

int WhoIsPrecede(int d1, int d2)
{
	if(d1 < d2)
    	return 0;
    else
    	return 1;
}