C语言写单链表按照商品剩余数量排序的函数方法
时间: 2024-10-18 20:21:42 浏览: 3
在C语言中,要编写一个函数对单链表中的商品按照剩余数量进行排序,通常我们会选择使用“插入排序”的思想,因为链表不适合直接使用快速排序或归并排序等复杂算法。这里假设我们有一个结构体`Product`表示商品,其中包含一个整数字段`quantity`代表剩余数量,以及指向下一个商品的指针`next`。
下面是一个简单的示例函数,使用插入排序实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义产品结构体
typedef struct Product {
int quantity;
struct Product* next;
} Product;
void sort_by_quantity(Product** head) {
if (*head == NULL || (*head)->next == NULL) { // 如果链表为空或只有一个元素,无需排序
return;
}
Product* current = *head;
Product* prev = NULL;
while (current != NULL) {
Product* next暂存当前元素的下一个节点;
if (prev == NULL || prev->quantity > current->quantity) {
// 将较小的元素插入到已排序部分的适当位置
prev = current;
while (prev->next != NULL && prev->next->quantity < current->quantity) {
prev = prev->next;
}
if (prev->next != NULL) {
prev->next = current->next; // 更新prev的next指针
} else {
prev->next = current; // 插入到链表尾部
}
current = next; // 指向下一个未处理的元素
} else {
current = current->next; // 直接移动到下一个元素,因为它已经排好序了
}
}
}
// 添加商品到链表的示例
void add_product(Product** head, int quantity) {
Product* newNode = (Product*)malloc(sizeof(Product));
newNode->quantity = quantity;
newNode->next = *head;
*head = newNode;
}
// 打印链表示例
void print_list(Product* head) {
while (head != NULL) {
printf("Quantity: %d -> ", head->quantity);
head = head->next;
}
printf("NULL\n");
}
int main() {
Product* head = NULL;
// 假设你已经有了一个商品链表,并且填充了数据
// 添加商品并保持链表排序
add_product(&head, 5); // 假设第一个商品量为5
add_product(&head, 2); // 假设第二个商品量为2
add_product(&head, 8); // 假设第三个商品量为8
sort_by_quantity(&head);
print_list(head);
return 0;
}
```
这个函数首先检查链表是否为空,然后遍历链表,对于每个节点,将其插入到已排序部分的合适位置。记住,这个实现假设了剩余数量总是非负的。
阅读全文