单链表实现冒泡排序

思路：利用三个指针，一个指向尾结点（排序终止条件）的tail结点，一个prev指针，一个cur指针，进行比较，每次排完一遍后，将tail指针向前挪动一个单位，因为最大（或最小）的结点已经到最后了，已经不需要再进行排序了

当然也可以进行优化，加一个标志位...

#define _CRT_SECURE_NO_WARNINGS 1

//单链表冒泡排序
#include<iostream>
using namespace std;

typedef int DataType;
typedef struct SListNode
{
 DataType data;            //数据
 struct SListNode * next;   //指向下一个结点的指针
}SListNode;

SListNode* CreateNode(DataType x)  //创造结点
{
 //1.先开辟空间 2.数据赋给data 3.指针置空
 SListNode* NewNode = (SListNode *)malloc(sizeof (SListNode));
 NewNode->data = x;
 NewNode->next = NULL;

 return NewNode;
}

void PushBack(SListNode * &ppHead, DataType Data)
{
 //1.none 2.one and more
 if (ppHead == NULL)
 {
  ppHead = CreateNode(Data);
 }
 else
 {
  //1.先找到尾结点 2.把新节点链起来
  SListNode* cur = ppHead;
  while (cur->next)
  {
   cur = cur->next;
  }
  cur->next = CreateNode(Data);

 }
}
//打印
void PrintSNodeList(SListNode *&ppHead)
{
 while (ppHead)
 {
  printf("%d->", ppHead->data);
  ppHead = ppHead->next;
 }
 cout << "NULL" << endl;
}

//冒泡排序
void BubbleSortSlist(SListNode* pHead)
{
 if (pHead == NULL || pHead->next == NULL)  //边界条件
 {
  return;
 }
 SListNode* prev = pHead;          
 SListNode* cur = pHead->next;
 SListNode* Tail = NULL;

 while (Tail != pHead)   //tail=prev 每次调整完一次后都将tail向前挪动一次
 {
  cur = pHead->next;   //每次跳整完一次后，cur再次指向头结点的下一个结点
  prev = pHead;        //prev指向phead
  while (cur != Tail)
  {
   if (prev->data >cur->data)//比较节点信息，如果满足条件就交换它
   {
    DataType x;
    x = cur->data;
    cur->data = prev->data;
    prev->data = x;
   }
   prev = prev->next;
   cur = cur->next;//指向下一个节点，实现迭代
  }
  Tail = prev;//循环结束后prev指向尾节点，赋值给Tail
 }
}
void Test()
{
 SListNode* pHead = NULL;
 PushBack(pHead, 8);
 PushBack(pHead, 7);
 PushBack(pHead, 6);
 PushBack(pHead, 5);
 PushBack(pHead, 4);
 PushBack(pHead, 3);
 PushBack(pHead, 2);
 PushBack(pHead, 1);
 BubbleSortSlist(pHead);
 PrintSNodeList(pHead);
}
int main()
{
 Test();
 system("pause");
 return 0;
}

若有不正确的地方希望能够指出，大家一起学习进步，谢谢了