Question

关于链表冒泡排序的问题，以下是一个链表排序的函数，不明白q在这里面是怎样发挥“标记”作用的。

int squence(struct lnode *head)
{ //冒泡排序列表 if(head==NULL||head->next==NULL)return 1 ;
lnode *p;
int data,q;
// bool sorted = false;
q=0;
while(q=!q)
{ // 表达式返回true，继续下一轮冒泡
for(p=head;p->next!=NULL;p=p->next)
{ if(p->data > (p->next)->data)
{ //与紧邻的下一个node比较data的大小
data=(p->next)->data;
(p->next)->data=p->data;
p->data=data; //交换data
q=0; // 标记“发生了交换”，如果没有交换则跳出while循环
}
}
}
return 1;
}
这是一个冒泡排序的函数

Answer 1

（1） while(q=!q)//q = !q 若q==0 则q = !q = !0 =1 则while循环条件成立否则q = !q = !1 = 0此时循环条件不成立退出循环。
（2）每趟比较之前q = !q都使得q==1，此时若在内循环中没有将q赋值为0，则会在下一趟循环时使得q=!q==0,从而退出循环，起到了标记当前比较趟中没有数据交换的作用。
（3）在冒泡排序中若当前趟已无数据需要交换次序，则说明整个序列已经有序无需继续排序。