12.单链表排序

悠悠 2022-05-26 11:08 193阅读 0赞

###     ###

思路1：

将链表中的数据存入数组中，使用数组进行排序，排好后再存入链表中。

当然这并不是这题所要考察的。但是在实际应用中却相当有价值。因为链表中的排序算法都比较慢，进行转存再排序也是一种很好的方法。

思路2：

排序算法有

1，       插入排序：简单插入排序，希尔排序

2，       交换排序：冒泡排序， 快速排序

3，       选择排序：简单选择排序，堆排序

4，       归并排序

5，       基数排序

简单的排序算法有插入，冒泡，选择；

中等的有合并排序，快速排序；

复杂的有堆排序。

我实现了红色的三种排序方法。

使用链表进行排序比较繁琐，尤其是快排，需要拆分，

当然也可以多加一个指针指向要排序的队尾，这样就不用拆了。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //建立链表
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    //输出链表
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    //找到第index个元素
    struct node * find_node(struct node* phead, int index )
    {
    	if(!phead) return NULL;
    	struct node * pNode = phead;
    	while( index--)
    	{
    		pNode = pNode->next;
    		if( !pNode )
    			return NULL;
    	}
    	return pNode;
    }
    
    //检查链表有无环
    //有，则返回快慢指针共同指向的点
    //无，则返回空指针
    struct node * check_loop( struct node * phead )
    {
    	if(!phead)
    		 return NULL;
    	struct node * pFast = phead;
    	struct node * pSlow = phead;
    
    	int step = 1;
    	while( pFast )
    	{
    		pFast = pFast->next;
    		if( step++%2==0 )
    		{
    			pSlow = pSlow->next;
    			if( pSlow == pFast )
    				return pSlow;
    		}
    	}
    	return NULL;
    }
    
    
    //去掉重复元素
    void delete_repeat_element( struct node * phead )
    {
    	if( !phead || !phead->next ) return;
    	int * hashTable = new int[256]();		//加括号是为了将hashTable中所有元素初始化为0
    	struct node * pNode = phead->next;
    	struct node * pPreNode = phead;
    	while( pNode )
    	{
    		if( hashTable[pNode->val] !=0 )		//说明已经出现过，该结点要删除
    		{
    			pPreNode->next = pNode->next;
    			delete pNode;					//删除结点
    			pNode = pPreNode->next;
    		}
    		else								//没有出现过，则置出现标记
    		{
    			hashTable[pNode->val] = 1;
    			pPreNode = pNode;
    			pNode = pNode->next;
    		}
    	}
    	delete [] hashTable;                 //释放资源
    }
    
    //插入排序
    void insert_sort( struct node* phead)
    {
    	if( !phead || !phead->next) return;
    	struct node *pCur = phead->next->next; //当前处理的结点
    	struct node *pTail = phead->next;      //已排好序队列的尾部结点
    
    	while( pCur )
    	{
    		struct node *pNode = phead->next; //已排好序队列中与当前结点相比较的结点
    		struct node *pPre = phead;        //...............前一结点
    		while( pNode != pCur )
    		{
    			if(pNode->val > pCur->val)
    				break;
    			pNode = pNode->next;
    			pPre = pPre->next;
    		}
    		if( pNode == pCur )         //说明已排好序队列中没有比当前元素大的元素
    		{
    			pCur = pCur->next;
    			pTail = pTail->next;
    		}
    		else                        //将pCur结点插入到pNode之前，即pPre之后
    		{
    			pTail->next = pCur->next;
    			pPre->next = pCur;
    			pCur->next = pNode;
    			pCur = pTail->next;
    		}
    	}
    }
    
    
    //归并排序
    //pNode 为待排序链表的第一个元素
    //找中间结点
    struct node * find_mid_node( struct node * pNode )
    {
    	if( !pNode ) return NULL;
    	struct node * pFast = pNode;
    	struct node * pSlow = pNode;
    	int step=1;
    	while( pFast->next )
    	{
    		pFast = pFast->next;
    		if( step++%2==0 )
    			pSlow = pSlow->next;
    	}
    	return pSlow;
    }
    
    //合并之后，pNode1为表头
    void merge(struct node* &pNode1, struct node* pNode2)
    {
    	if( !pNode1 )  //特殊情况
    	{
    		pNode1 = pNode2;
    		return;
    	}
    	if( !pNode2 ) return;
    
    	struct node *pNode = NULL;
    	struct node *phead = NULL;
    	if( pNode1->val < pNode2->val )        //找到表头
    	{
    		phead = pNode1;
    		pNode1 = pNode1->next;
    	}
    	else
    	{
    		phead = pNode2;
    		pNode2 = pNode2->next;
    	}
    
    	pNode = phead;
    	while( pNode1 && pNode2 )
    	{
    		if( pNode1->val < pNode2->val)
    		{
    			pNode->next = pNode1;
    			pNode1 = pNode1->next;
    		}
    		else
    		{
    			pNode->next = pNode2;
    			pNode2= pNode2->next;
    		}
    		pNode = pNode->next;
    	}
    	if( !pNode1 )
    		pNode->next = pNode2;
    	else
    		pNode->next = pNode1;
    
    	pNode1 = phead;
    }
    
    //注意，这里的pNode是需要变的，所以用了引用，可能不太好理解
    //如果让返回值指向排行序的表头可能会好一些
    void merge_sort( struct node * &pNode )
    {
    	if( !pNode || !pNode->next ) return;    //递归终止条件，无结点或者只有一个结点
    
    	struct node* pMid = find_mid_node( pNode ); //分解成两半
    	struct node* pNode2 = pMid->next;
    	pMid->next = NULL;
    	merge_sort( pNode );
    	merge_sort( pNode2 );
    	merge( pNode, pNode2);
    }
    
    //快速排序
    //划分函数
    //输入：链表头， 输出：新的链表头，选中的结点
    struct node * patition( struct node * pNode, struct node * &pSelect )
    {
    	if( !pNode ) return NULL;
    	struct node* phead = NULL;
    	pSelect = pNode;				//选中的元素，划分的依据结点，选最后一个元素
    	while( pSelect->next )
    		pSelect = pSelect->next;
    
    	struct node *pScan = pNode;
    	struct node *pPre = NULL;            //指向pScan前一个结点
    	int flag = 0;
    	while( pScan != pSelect )
    	{
    		if( pScan->val >pSelect->val )      //比选中元素大的要掉到选中元素之后
    		{
    			if( !pPre )     //如果是第一个
    			{
    				struct node *temp =  pScan;
    				pScan = pScan->next;
    				temp->next = pSelect->next;
    				pSelect->next = temp;
    			}
    			else            //如果不是第一个
    			{
    				pPre->next = pScan->next;
    				pScan->next = pSelect->next;
    				pSelect->next = pScan;
    				pScan = pPre->next;
    			}
    		}
    		else
    		{
    			if( flag ==0 )
    			{
    				phead = pScan;      //第一个小于选中的元素为表头
    				flag = 1;
    			}
    			pPre = pScan;
    			pScan = pScan->next;
    		}
    	}
    	if( flag == 0 ) // 所有元素都比选中的大，即选中的为表头
    		return pSelect;
    	else
    		return phead;
    }
    
    struct node * QuickSort( struct node * pNode )
    {
    	if( !pNode || !pNode->next ) return pNode;
    	struct node * pSelect=NULL;
    	pNode = patition( pNode, pSelect );
    
    	if( pSelect == pNode )			//划分后的结点为第一个结点
    	{
    		pSelect->next = QuickSort(pSelect->next);
    		return pSelect;
    	}
    	else							//分两个部分，pSelect前面的和后面的
    	{
    		struct node * pFirstTail = pNode;
    		while( pFirstTail->next != pSelect )
    			pFirstTail = pFirstTail->next;
    		pFirstTail->next = NULL;                      //断开
    		struct node * phead1 = QuickSort( pNode );   //解决前一部分
    		pFirstTail = phead1;
    		while( pFirstTail->next )
    			pFirstTail = pFirstTail->next;
    		pFirstTail->next = pSelect;                   //连上
    		pSelect->next = QuickSort( pSelect->next );  //解决后一部分
    		return phead1;
    	}
    
    }
    void test()
    {
    	string str;
    	cout << "Input the link table :"<<endl;
    	cin >> str;
    	struct node *phead = create( str );
    	
    	//insert_sort( phead );					//选中即为插入排序
    	//merge_sort( phead->next );			//选中即为归并排序
    	phead->next = QuickSort( phead->next);  //选中即为快速排序
    
    	cout<< "The result of Sort is:" <<endl;
    	out_link( phead );
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	return 0;
    }