/*
有一个带头结点的单链表L，设计一个算法使其递增有序
分析：
我们可以采用冒泡排序对其操作，使其递增有序,时间复杂度为O(n^2)。
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int value;
struct LNode *next;
}LNode,*Linklist;
Linklist list_TailInsert(Linklist &L)
{ int value;
L = (Linklist)malloc(sizeof(LNode));
LNode *head = L,*rear = L;
head->next = NULL;
head->value = NULL;
printf("请输入链表一个结点的值，输入9999代表结束：");
scanf("%d",&value);
while(value != 9999)
{
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next=NULL;
rear->next = s;
rear = s;
scanf("%d",&value);
}
rear->next = NULL;
}
void Display(Linklist L)
{
LNode *p = L->next ;
while(p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
void bubbleSort(Linklist &L)//冒泡排序
{
LNode *pre = L,*p = L->next,*q = p->next;
int flag = 0;//排序标志，如果产生过变动flag = 1
int count = 0;//记录链表长度
while(p != NULL)
{
count++;
p = p->next;
}
printf("count = %d\n",count);
p = L->next;//切记，在计算链表长度后一定要重新设定p的指针
for(int i = 0;i < count;i++)
{ flag = 0;
pre = p;
p = q;
q = q->next;
while(p != NULL)
{
if(p->value < pre->value)
{ printf("%d->%d ",p->value,pre->value);
p->next = pre;
L->next = p;
pre->next = q;
p=q;
q=q->next;
flag = 1;
printf("flag=%d\n",flag);
}
else
{
pre = p;
p = q;
q = q->next;
}
}
if(flag = 0)break;//我的代码到这就不运行了，怎么回事？？？
pre = L;
p = L->next;
q = p->next;
}
}
int main()
{
Linklist L1;
list_TailInsert(L1);
Display(L1);
bubbleSort(L1);
Display(L1);
return 0;
}
