링크 작업 3 양 방향 링크 의 삽입 정렬 법

어제 모 회사 의 데이터 구조 필기시험 문 제 를 풀 었 다.
그 중 하 나 는 양 방향 링크 에 대해 빠 른 정렬 을 요구 하 는 것 이다. 
생각:
빌리다 nginx 링크 정렬 사상 
head   prev next 
가설: 작은 것 부터 큰 것 까지 정렬
링크 의 두 번 째 요소 에서 head - > next, 시작,
         1) 우선 이 노드 가 링크 에 있 는 위 치 를 삭제 합 니 다 (단, 이 노드 는 삭제 하지 않 습 니 다)
         2) 링크 를 한 번 씩 앞으로 옮 겨 다 니 며 자신 보다 크 면 끊임없이 앞으로 옮 겨 다 닌 다.
3) 적당 한 위 치 를 찾 아 이 노드 를 삽입 하면 된다.
코드 붙 이기:
 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 


#define MAX_PATH   256
typedef char WCHAR;
typedef unsigned long DWORD;


#if 1
	typedef struct _FILE_NODE {

	struct _FILE_NODE  *Prev;
	struct _FILE_NODE  *Next;

	int          size;
	WCHAR        wzFileName[MAX_PATH];
	DWORD        dwLowDateTimeLastWrite;

} FILE_NODE, *LPFILENODE;

typedef struct Node
{
	FILE_NODE *head;
	FILE_NODE *tail;
	int list_size;
}Node;
#endif

	int compare(const FILE_NODE *a, const FILE_NODE *b)
	{
		if(NULL == a)
			return 1;
		if(NULL == b)
			return 0;
		return a->size > b->size;
	}

	
	void LIST_INIT(Node** node)
	{
		if(NULL != *node)
			return ;
		
		Node *tmp_node = (Node*)malloc(sizeof(Node)); 
		tmp_node->head = (FILE_NODE*)malloc(sizeof(FILE_NODE));
		memcpy(tmp_node->head->wzFileName, "NULL ", strlen("NULL "));
		tmp_node->head->wzFileName[strlen("NULL ")]='\0';
		tmp_node->head->dwLowDateTimeLastWrite = 0;
		tmp_node->head->size = -1;
		tmp_node->head->Next = NULL;
		tmp_node->head->Prev = NULL;
		tmp_node->tail = tmp_node->head;
		tmp_node->list_size= 1 ;
		*node = tmp_node;
		return ;
	}
	
	void ADD_LIST(Node* plist, FILE_NODE* pnode)
	{
		if(NULL == plist || NULL == pnode)
			return ;
		
		if(NULL != pnode)
		{
			if(plist->head == plist->tail)
			{	
				plist->tail = pnode;
				pnode->Prev = plist->head;
				plist->head->Next= pnode;
				pnode->Next = NULL;
			}	
			else
			{
				FILE_NODE* tmp = plist->tail;
				pnode->Next = tmp->Next;
				pnode->Prev = tmp;
				tmp->Next = pnode;
				plist->tail = pnode;
			}
			plist->list_size ++;
		}
		
	}
	
	
	
	//           
	FILE_NODE*  SEARCH_NAME(Node* node, char* name)
	{
		if(NULL == node)
			return NULL;
		FILE_NODE* tmp = node->head;
		while(tmp)
		{
			if(!memcpy(tmp->wzFileName, name, strlen(name)))
			{
				return tmp;
			}
			tmp = tmp->Next;
		}
		return NULL;
	}
	
	
	//           
	void  DELETE_NAME(Node* node, char* name)
	{
		if(NULL == node)
			return ;
		FILE_NODE* tmp = node->head;
		while(tmp)
		{
			if(!memcpy(tmp->wzFileName, name, strlen(name)));
			{
				//                       
				tmp->Prev->Next = tmp->Next;
				tmp->Next->Prev = tmp->Prev;
				node->list_size--;
			}
			tmp = tmp->Next;
		}
			
	}
	
	
	void FREE_LIST(Node* node)
	{
		if( node->list_size == 0 )
		{
			return ;
		}
		
		FILE_NODE* tmp_node = NULL;
		FILE_NODE* swap = NULL;
		tmp_node = node->head;
	
		while(tmp_node != NULL)
		{
			swap = tmp_node->Next;
			{
				free(tmp_node);
				tmp_node = NULL ;
				node->list_size--;
			}
			tmp_node = swap;
		}
		return ;
	}
	
	
	void travel(Node* node)
	{
		if(NULL == node)
			return;
		FILE_NODE* tmp = node->head->next;
		while(tmp)
		{
			printf("size:%d, name:%s, time=%u
", tmp->size, tmp->wzFileName, tmp->dwLowDateTimeLastWrite); 
			tmp = tmp->Next;
		}
		return ;
	}
	
	
#if 1	
#define list_insert_head(h, x)                                           \
		(x)->Next = (h)->Next;													  \
		(x)->Next->Prev = x;													  \
		(x)->Prev = h;															  \
		(h)->Next = x
	
#define list_remove(x)                                           \
		(x)->Next->Prev = (x)->Prev;													  \
		(x)->Prev->Next = (x)->Next;													  \
		(x)->Prev = NULL;															  \
		(x)->Next = NULL;


	void
	list_sort(Node *node,
			int (*cmp)(const FILE_NODE *, const FILE_NODE *))
		{
				
			FILE_NODE  *q, *prev, *next;
		
			q = node->head;
		
			if (q == node->tail) {
				return;
			}
		
			for (q = node->head->Next; q != NULL; q = next) {
		
				prev = q->Prev;
				next = q->Next;
		
				if(NULL == q->Next)
				{
					q->Prev->Next = NULL;	
				}
				else
				{
					list_remove(q);
				}	
				do {
					//   prev   q
					if (cmp(prev, q) <= 0) {
						break;
					}
	
					prev = prev->Prev;
		
				} while (prev != node->head);
		// q    prev   ，
				list_insert_head(prev, q);
				//travel(node);
			}
		}
	
#endif



int  main()
{
	Node *node = NULL;
	LIST_INIT(&node);

	int i = 0;
	for(i; i< 10; i++)
	{
		FILE_NODE* sp = (FILE_NODE*)malloc(sizeof(FILE_NODE));
		memset(sp, 0, sizeof(FILE_NODE));

		sp->size  = rand()%10;
		sp->dwLowDateTimeLastWrite = 100000000;
		memcpy(sp->wzFileName, "luchenfei", 32);

		ADD_LIST(node,sp);

	}

	travel(node);
	list_sort(node, compare);
	travel(node);
	getchar();
}