면접 문제 - 데이터 구조의 단일 체인 표 상술 (기본 편 3)

단일 체인 표 의 정방 향 정렬 은 데 이 터 를 삽입 할 때 작은 것 부터 큰 것 까지 정렬 하 는 것 이다.
코드 에 주석 이 있어 쉽게 이해 할 수 있 습 니 다.

//        
node *InsertSort(void)
{
	int data = 0;
	struct node *head = NULL;
	struct node *New, *Cur, *Pre;
	
	while(1)
	{
		printf("please input the data: ");
		scanf("%d", &data);
		if(0 == data)			//  0  
		{
			break;	
		}
		New = (struct node*)malloc(sizeof(struct node));
		New->data = data;		//     node  
		New->next = NULL;
		if(NULL == head)		//            
		{
			head = New;
			continue;
		}
		if(New->data <= head->data)	//head      
		{
			New->next = head;
			head = New;
			continue;
		}
		Cur = head;
		while(New->data > Cur->data && NULL != Cur->next)
		{							//         
			Pre = Cur;
			Cur = Cur->next;
		}
		if(Cur->data >= New->data)	//     
		{							// New     pre cur  
			Pre->next = New;
			New->next = Cur;
		}
		else						//    
		{							// new     cur  
			Cur->next = New;	
		}
	}
	return head;
}

단일 체인 시트 에 고리 형 링크 문제 가 존재 하 는 지 판단 하 는 데 비교적 간단 한 해법 이 있 습 니 다. 두 개의 지침 이 각각 p1 과 p2 라 고 가정 하고 한 번 순환 할 때마다 p1 은 한 걸음 앞으로 가 고 p2 는 두 걸음 앞으로 가 며 p2 가 NULL 지침 에 부 딪 히 거나 두 바늘 이 같 을 때 순환 이 끝 납 니 다.만약 두 바늘 이 같다 면 고리 가 존재 한 다 는 것 을 설명 한다.
프로그램 코드 는 다음 과 같 습 니 다:

//           
//    ，start         
bool IsLoop(node *head, node **start)
{
	node *p1 = head;
	node *p2 = head;
	if(NULL == head || NULL == head->next)
	{					//head NULL         false
		return false;
	}
	do
	{
		p1 = p1->next;				//p1   
		p2 = p2->next->next;		//p2   
	}while(p2 && p2->next && p1 != p2);
	if(p1 == p2)
	{
		*start = p1;				//p1       
		return true;
	}
	else
	{
		return false;
	}
}

다음은 인쇄 함수 와 주 함수 테스트 입 니 다.

void print(node *head)
{
	int pos = 0;
	node *p = head;
	while(NULL != p)
	{
		printf("the %dth node %d
", ++pos, p->data);
		p = p->next;
	}
}
int main()
{
	bool bLoop = false;
	node *head = InsertSort();	//         
	printf("Link Sort...
");
	print(head);
	
	printf("IsLoop test.........
");
	node *start = head->next->next->next;	//             
	start->next = head->next;				//          
	node *loopStart = NULL;
	bLoop = IsLoop(head, &loopStart);
	printf("bLoop = %d
", bLoop);
	printf("bLoop == loopStart ? %d
", (loopStart == start));

	return 0;
}

다음은 프로그램 실행 결과 입 니 다. 입력 은 1, 6, 4, 5, 3, 2 입 니 다.

please input the data: 1
please input the data: 6
please input the data: 4
please input the data: 5
please input the data: 3
please input the data: 2
please input the data: 0
Link Sort...
the 1th node 1
the 2th node 2
the 3th node 3
the 4th node 4
the 5th node 5
the 6th node 6
IsLoop test.........
bLoop = 1
bLoop == loopStart ? 1
Press any key to continue