不带头单链表的冒泡排序，及其常见算法题

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef  int   DataType;
typedef struct  LinkNode
{
	DataType _data;
	struct   LinkNode *_next;
}LinkNode, *pLinkNode;
pLinkNode BuyNode(DataType x);//开辟节点
void  InitNode(pLinkNode& pHead);//初始化
void  DestoryNode(pLinkNode& pHead);//销毁节点
void  PushBack(pLinkNode&  pHead, DataType x);//尾插节点
void  PrintNode(pLinkNode pHead);//打印
//合并两个有序链表,标准程序和递归
pLinkNode  CombineTwoLink(pLinkNode firstpHead, pLinkNode  secondpHead);
//查找两个已排序链表中相同元素，只能遍历一次
//三种情况1.升序还是降序2.一个升一个降（参数问题）
void  SearchCommonData(pLinkNode  firstpHead, pLinkNode  secondpHead);
//查找倒数第k个节点，只需遍历一次
pLinkNode  SearchKFromTail(pLinkNode  pHead, int k);
//冒泡排序
void  BubbleSort(pLinkNode& pHead);
pLinkNode BuyNode(DataType x)
{
	pLinkNode tmp;
	tmp = (pLinkNode)malloc(sizeof(LinkNode));
	tmp->_data = x;
	tmp->_next = NULL;
	return  tmp;
}
void  InitNode(pLinkNode& pHead)
{
	pHead = NULL;
}
void  DestoryNode(pLinkNode& pHead)
{
	if (pHead == NULL)
	{
		return;
	}
	pLinkNode del = pHead;
	while (pHead != NULL)//如果phead指向结构体还有数据
	{
		del = pHead;
		pHead = pHead->_next;
		free(del);
	}
}
void  PushBack(pLinkNode&  pHead, DataType x)
{
	if (pHead == NULL)
	{
		pHead = BuyNode(x);
	}
	else
	{
		pLinkNode newNode = BuyNode(x), cur = pHead;
		while (cur->_next != NULL)
		{
			cur = cur->_next;
		}
		cur->_next = newNode;
	}
}
void  PrintNode(pLinkNode pHead)
{
	assert(pHead);
	while (pHead != NULL)
	{
		printf("%d->", pHead->_data);
		pHead = pHead->_next;
	}
	printf("NULL\n");
}
pLinkNode  CombineTwoLink(pLinkNode firstpHead, pLinkNode  secondpHead)
{
	//假定升序排列

	//法一：连接法
	/*pLinkNode  ret = firstpHead;
	if (firstpHead==NULL||secondpHead==NULL)
	{
		return  firstpHead == NULL ? secondpHead: firstpHead;
	}*/
	//先给target赋值两个链表中较小元素的，并使其后移
	/*if (firstpHead->_data > secondpHead->_data)
	{
		ret = secondpHead;
		secondpHead = secondpHead->_next;
	}
	else
	{
		firstpHead = firstpHead->_next;
	}

	pLinkNode  target = ret;
	while (firstpHead&&secondpHead)
	{
		if (firstpHead->_data > secondpHead->_data)
		{
			target->_next = secondpHead;
			secondpHead = secondpHead->_next;
		}
		else
		{
			target->_next = firstpHead;
			firstpHead = firstpHead->_next;
		}
		target = target->_next;
	}

	if (firstpHead != NULL)
	{
		target->_next = firstpHead;
	}
	else if(secondpHead)
	{
		target->_next = secondpHead;
	}
	return  ret;*/

	//递归法
	if (firstpHead == NULL)
		return  secondpHead;
	if (secondpHead == NULL)
		return  firstpHead;
	if (firstpHead->_data < secondpHead->_data)
	{
	    firstpHead->_next=CombineTwoLink(firstpHead->_next, secondpHead);
		return  firstpHead;
	}
	else
	{
		secondpHead->_next=CombineTwoLink(secondpHead->_next, firstpHead);
		return  secondpHead;
	}
}
void  SearchCommonData(pLinkNode  firstpHead, pLinkNode  secondpHead)
{
	assert(firstpHead&&secondpHead);//判断链表非空
	while (firstpHead&&secondpHead)
	{
		if (firstpHead->_data < secondpHead->_data)
		{
			firstpHead = firstpHead->_next;
		}
		else if (firstpHead->_data>secondpHead->_data)
		{
			secondpHead = secondpHead->_next;
		}
		else
		{
			printf("%d  ", firstpHead->_data);//两个链表此时数一样
			firstpHead = firstpHead->_next;
			secondpHead = secondpHead->_next;
		}
	}
}
pLinkNode  SearchKFromTail(pLinkNode  pHead, int k)
{
	assert(pHead);
	//考虑k大于链表总长度
	pLinkNode  fast = pHead,slow=pHead;
	int  tag = 0;
	while (fast)
	{
		if (tag >= k)
		{
			slow = slow->_next;
		}
		fast = fast->_next;
		tag++;
	}
	return  slow;
}

void  BubbleSort(pLinkNode& pHead)
{
	//假定升序排列
	pLinkNode  cur = pHead, inCur = pHead, checkNode = NULL;
	DataType  tmp = 0;//若是存储double类型数，直接改重定义
	int   count = 0;//优化，若不改变，则已完成排序
	assert(pHead);
	while (cur->_next)//n个数需要n-1次
	{
		while (inCur->_next != checkNode)//考虑边界问题
		{
			if (inCur->_data > inCur->_next->_data)
			{
				tmp = inCur->_data;
				inCur->_data = inCur->_next->_data;
				inCur->_next->_data = tmp;
				count++;
			}
			inCur = inCur->_next;
		}
		//不能用count=1,判断
		//例如：2  4  5  3  6，直交换5和3，没排对
		if (count == 0)
		{
			return;//优化
		}
		checkNode = inCur;//j<size-1-i;
		inCur = pHead;
		cur = cur->_next;
	}
}
void Test1()
{
	pLinkNode  Link1, Link2,ret;
	InitNode(Link1);
	InitNode(Link2);
	InitNode(ret);
	PushBack(Link1, 1);
	PushBack(Link1, 3);
	PushBack(Link1, 5);
	PushBack(Link1, 7);
	PushBack(Link1, 8);
	PushBack(Link1, 9);
	PushBack(Link1, 12);
	PrintNode(Link1);
	
	PushBack(Link2, 1);
	PushBack(Link2, 2);
	PushBack(Link2, 4);
	PushBack(Link2, 6);
	PushBack(Link2, 7);
	PushBack(Link2, 9);
	PushBack(Link2, 10);
	PushBack(Link2, 12);
	PushBack(Link2, 13);
	PushBack(Link2, 15);
	PrintNode(Link2);

	ret = SearchKFromTail(Link1, 2);
	//SearchCommonData(Link1, Link2);
	//ret = CombineTwoLink(Link1, Link2);
    printf("%d\n",ret->_data);

	DestoryNode(Link1);
	DestoryNode(Link2);
	
}
void  Test2()
{
	pLinkNode  Link;
	InitNode(Link);
	PushBack(Link, 1);
	PushBack(Link, 2);
	PushBack(Link, 4);
	PushBack(Link, 5);
	PushBack(Link, 3);
	PushBack(Link, 9);
	PushBack(Link, 7);
	PushBack(Link, 12);


	BubbleSort(Link);
	PrintNode(Link);
	DestoryNode(Link);
}
int main()
{
	//Test1();
	Test2();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1706058

不带头单链表的冒泡排序，及其常见算法题

原文：http://10541556.blog.51cto.com/10531556/1706058