99 lines
1.6 KiB
C
99 lines
1.6 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
|
||
|
|
typedef struct Node {
|
||
|
|
int data;
|
||
|
|
struct Node *next;
|
||
|
|
} Node;
|
||
|
|
|
||
|
|
void swapNode(Node *a, Node *b);
|
||
|
|
void bubbleSort(Node *head);
|
||
|
|
|
||
|
|
Node *constructLinkedList();
|
||
|
|
Node *appendNode(Node *node, int data);
|
||
|
|
void deleteLinkedList(Node *head);
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
Node *head = constructLinkedList();
|
||
|
|
|
||
|
|
bubbleSort(head);
|
||
|
|
|
||
|
|
printf("The new list is:");
|
||
|
|
Node *ptr = head;
|
||
|
|
while (ptr->next != NULL) {
|
||
|
|
printf("%d ", ptr->data);
|
||
|
|
ptr = ptr->next;
|
||
|
|
}
|
||
|
|
printf("%d", ptr->data);
|
||
|
|
|
||
|
|
deleteLinkedList(head);
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Actually only swaps the data inside
|
||
|
|
void swapNode(Node *a, Node *b) {
|
||
|
|
int tmp = a->data;
|
||
|
|
a->data = b->data;
|
||
|
|
b->data = tmp;
|
||
|
|
}
|
||
|
|
|
||
|
|
void bubbleSort(Node *head) {
|
||
|
|
int swapped;
|
||
|
|
Node *ptr1;
|
||
|
|
Node *ptr2 = NULL;
|
||
|
|
|
||
|
|
if (head == NULL) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
do {
|
||
|
|
swapped = 0;
|
||
|
|
ptr1 = head;
|
||
|
|
|
||
|
|
while (ptr1->next != ptr2) {
|
||
|
|
if (ptr1->data > ptr1->next->data) {
|
||
|
|
swapNode(ptr1, ptr1->next);
|
||
|
|
swapped = 1;
|
||
|
|
}
|
||
|
|
ptr1 = ptr1->next;
|
||
|
|
}
|
||
|
|
ptr2 = ptr1;
|
||
|
|
} while (swapped);
|
||
|
|
}
|
||
|
|
|
||
|
|
Node *constructLinkedList() {
|
||
|
|
int data;
|
||
|
|
scanf("%d", &data);
|
||
|
|
|
||
|
|
Node *head = malloc(sizeof(Node));
|
||
|
|
head->data = data;
|
||
|
|
head->next = NULL;
|
||
|
|
Node *ptr = head;
|
||
|
|
|
||
|
|
scanf("%d", &data);
|
||
|
|
while (data != -1) {
|
||
|
|
ptr = appendNode(ptr, data);
|
||
|
|
scanf("%d", &data);
|
||
|
|
}
|
||
|
|
|
||
|
|
return head;
|
||
|
|
}
|
||
|
|
|
||
|
|
Node *appendNode(Node *node, int data) {
|
||
|
|
Node *new = malloc(sizeof(Node));
|
||
|
|
new->data = data;
|
||
|
|
new->next = NULL;
|
||
|
|
|
||
|
|
node->next = new;
|
||
|
|
|
||
|
|
return new;
|
||
|
|
}
|
||
|
|
|
||
|
|
void deleteLinkedList(Node *head) {
|
||
|
|
if (head != NULL) {
|
||
|
|
deleteLinkedList(head->next);
|
||
|
|
free(head);
|
||
|
|
}
|
||
|
|
}
|