链表操作3 双向链表的插入排序法

傷城~ 2022-08-07 15:50 135阅读 0赞

昨天做了某公司的数据结构笔试题：

其中一个小功能 是要求对 双向链表进行 快速排序。

思想：

借用了  nginx 链表排序思想

head   prev next

假设： 从小到大排序

从链表的 第二个 元素  head->next ， 开始，

1）首先删除该节点 在链表中的位置（但是不删除该节点）

2）逐次向前遍历链表 如果 比自己大 则不停向前遍历

3）找到合适位置，将该节点 插入即可。

贴上代码：

#include <iostream>
    #include <algorithm>
    #include <time.h>
    #include <stdio.h>
    #include <errno.h>
    #include <string.h>
    #include <stddef.h>
    #include<time.h>
    #include <fcntl.h>
    
    
    #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\n", 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();
    }