CH4연결리스트 정렬 삽입의 구현(1)

04-3. 연결 리스트의 정렬 삽입의 구현 ①

남은 부분은 연결리스트 부분 중 일부인 정렬삽입임.

단순 연결리스트 자료구조내 정렬관련된 요소 세가지

1. SetSortRule()
2. comp
3. SInsert()

우리는 위의 요소 세가지가 다음의 관계를 갖고 있다는걸 알 수 있다.

SetSortRule()이 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert() 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터 정렬해 저장한다.

즉 SetSortRule()은 리스트 자료구조내 comp변수에 함수포인터 할당시켜주는 친구이고… 실질적인 삽입은 SInsert()가 진행함.

SInsert()는 어떤 정렬 기준에 따라 노드를 삽입하는 기능을 가짐.

삽입을 어떻게 할까..? 그림을 그려보자.

어디든지 삽입을 위해서는 바로 전 노드 주소와 바로 앞 노드 주소가 필요하다는 결론. 그래야 새로 노드가 삽입된 이후에도 전체 노드가 끊기지 않는다.

즉 노드 주소 2개가 필요… 그렇다고 두 개를 다 새로 만들 필요는 없을 듯. 하나는 새로 할당한 노드가 DMY부터 탐색하면 되고, 하나는 새로 만들어서 바로 앞에서부터 따라가주면 된다. (혹은 반대도 가능하지 않을까?)

생각해보니 반대가 나을듯 하다. 새로 생긴 노드를 DMY부터 가리키게 하면, 최초에는 새로받은 데이터가 비교가 불가능함.(DMY와 비교할 순 없으니까) 그럼 낭비되는 시행이 하나 생긴다. 그래서 pred라는 새로만든 노드가 DMY부터 시작해서 따라오게 하고, 새로 생긴 노드를 첫 유효노드부터 comp통해 비교하게 만들어서, 만약 들어갈 자리를 찾았으면 그때 들어가면 될듯.

우선 만들어봤다.

int Asceding(LData* newdata, LData* curdata) //오름차순 정렬
{
	if (newdata <= curdata)
		return FALSE; //0
	else
		return TRUE; //1		
}