作者airwaves (airwaves)
看板C_and_CPP
标题[问题] C语言 Bubble Sort with linked-list
时间Tue Oct 8 11:19:15 2019
各位大神好，
最近在学习C语言。
想要用linked-list写bubble sort
这是我参考网路上的做法，最後有成功排序的程式码
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
void printLinkedList(struct node *start);
void swap(struct node *node1, struct node *node2);
void bubbleSort(struct node *start);
// ================================================
int main()
{
int arry[10];
struct node *prev, *first = NULL, *current;
printf("Please type in the 01st number:");
scanf("%d", &arry[0]);
printf("Please type in the 02nd number:");
scanf("%d", &arry[1]);
printf("Please type in the 03rd number:");
scanf("%d", &arry[2]);
printf("Please type in the 04th number:");
scanf("%d", &arry[3]);
printf("Please type in the 05th number:");
scanf("%d", &arry[4]);
printf("Please type in the 06th number:");
scanf("%d", &arry[5]);
printf("Please type in the 07th number:");
scanf("%d", &arry[6]);
printf("Please type in the 08th number:");
scanf("%d", &arry[7]);
printf("Please type in the 09th number:");
scanf("%d", &arry[8]);
printf("Please type in the 10th number:");
scanf("%d", &arry[9]);
int i;
for (i = 0; i < 10; i++)
{
current = (struct node*)malloc(sizeof(struct node));
current -> data = arry[i];
if (i == 0)
{
first = current;
}
else
{
prev -> next = current;
}
current -> next = NULL;
prev = current;
}
printf("\n");
printf("List before sorting:");
printLinkedList(first);
printf("\n");
bubbleSort(first);
printf("List after sorting:");
printLinkedList(first);
printf("\n\n");
return 0;
}
// ================================================
void printLinkedList(struct node *start)
{
struct node *tmp = start;
while(tmp != NULL)
{
printf("%d,", tmp -> data);
tmp = tmp -> next;
}
}
// ------------------------------------------------
void swap(struct node *node1, struct node *node2)
{
int tmp = node2 -> data;
node2 -> data = node1 -> data;
node1 -> data = tmp;
}
// ------------------------------------------------
void bubbleSort(struct node *start)
{
struct node *startSort;
struct node *endSort = NULL;
int swapped;
if (start == NULL)
{
return;
}
do
{
swapped = 0;
startSort = start;
while (startSort -> next != endSort)
{
if (startSort -> data >= startSort -> next -> data)
{
swap(startSort, startSort -> next);
swapped = 1;
}
startSort = startSort -> next;
}
endSort = startSort;
}
while (swapped);
}
以下是我的问题，
我原本的做法在bubbleSort子程式没有加入swapped这个参数(如下)，
但是网路上找到的做法都有这种旗标。
想请问两种是否只差在我会多执行几次多余的while (startSort -> next != endSort)？
还是说我的做法会有什麽bug呢？？
谢谢大家~
void bubbleSort(struct node *start)
{
struct node *startSort;
struct node *endSort = NULL;
int swapped;
if (start == NULL)
{
return;
}
while(1)
{
startSort = start;
while (startSort -> next != endSort)
{
if (startSort -> data >= startSort -> next -> data)
{
swap(startSort, startSort -> next);
}
startSort = startSort -> next;
}
endSort = startSort;
if (endSort == start -> next)
{
break;
}
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.44.82.152 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1570504758.A.3A4.html
※ 编辑: airwaves (114.44.82.152 台湾), 10/08/2019 11:22:21
※ 编辑: airwaves (114.44.82.152 台湾), 10/08/2019 11:27:33
1F：推 Gway: 你写的的终止条件有可能不会满足而造成无穷回圈欧 10/08 17:04
2F：→ jepk007: 不觉得第一段输入的部分重复性很高吗 10/08 17:42
3F：→ Gway: 我眼残 把startSort = startSort -> next;看成在括号内 请 10/08 18:43
4F：→ Gway: 忽略我讲的 囧 但你的终止条件确实定的比较不好 用flag主要 10/08 18:43
5F：→ Gway: 是看还有没有bubble（I.eswap的动作）你的写法是无条件都做 10/08 18:43
6F：推 alan23273850: 我没仔细检查，但印象中起标只是侦测已排序後提早 10/09 12:00
7F：→ alan23273850: 终止，是加速的手段，跟正确性无关 10/09 12:00
8F：推 fragmentwing: 你如果担心有多做 首先改成随机输入1~10（反正就是1 10/15 15:23
9F：→ fragmentwing: ~10随机交换几百次後丢进去排序） 10/15 15:23
10F：→ fragmentwing: 立参数a1 a2纪录该次排序次数 b1 b2纪录总排序次数 10/15 15:23
11F：→ fragmentwing: 每次大概做10次後看你高兴要不要继续就按个键啥的 10/15 15:23
12F：→ fragmentwing: 相信很快就能看出来了 10/15 15:23