C程序来划分一个简单的链表

Question

所以我一直在研究一个小函数(一个更大程序的一部分(，它基本上完成以下任务：定义一个列表和元素的数量N，然后输入N个元素。然后输入一个值X；我必须对列表进行"拆分"/重新排序，使其值<X按其相对顺序在开头，值高于X的在后面；例如：

Input:
list 6
2 5 6 4 3 1
X 3
Output:
2 3 1 5 6 4

我的代码和列表结构如下：(分区函数在底部，就在主函数的上方(

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STRING_SIZE 64
typedef struct ll_node_t
{
void* data;
struct ll_node_t* next;
} ll_node_t;
typedef struct linked_list_t
{
ll_node_t* head;
unsigned int data_size;
unsigned int size;
} linked_list_t;
linked_list_t*
ll_create(unsigned int data_size)
{
linked_list_t* list = malloc(sizeof(list));
// err handle

list->head = NULL;
list->data_size = data_size;
list->size = 0;
return list;
}
void
ll_add_nth_node(linked_list_t* list, unsigned int n, const void* new_data)
{
if(n < 0) exit(0);
ll_node_t* new_node = malloc(sizeof(ll_node_t*));
new_node->data = malloc(list->data_size);
// err handle
memcpy(new_node->data, new_data, list->data_size);

if(n == 0  || list->size == 0) { 
new_node->next = list->head;
list->head = new_node;
list->size++;
return;
}   
if(n < list->size)
{
ll_node_t* current = list->head;
for(int i = 0; i < n - 1; i++)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
list->size++;
return;
}
if(n >= list->size)
{
ll_node_t* current = list->head;
for(unsigned int i = 0; i < list->size - 1; i++)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
list->size++;
return;
}
}

ll_node_t*
ll_remove_nth_node(linked_list_t* list, unsigned int n)
{
if(n < 0) exit(0);
ll_node_t* removedNode = NULL;
if(n == 0)
{
removedNode = list->head;
list->head = list->head->next;
list->size--;
return removedNode;
}
if(n < list->size)
{
ll_node_t* current = list->head;
// err handle
for(int i = 0; i < n - 1; i++)
{
current = current->next;
}
removedNode = current->next;
current->next = current->next->next;
list->size--;
return removedNode;
}
if(n >= list->size)
{
ll_node_t* current = list->head;
// err handle
for(int i = 0; i < n - 1; i++)
{
current = current->next;
}
removedNode = current->next;
current->next = NULL;
list->size--;
return removedNode;
}
}
unsigned int
ll_get_size(linked_list_t* list)
{
return list->size;
}
void
ll_free(linked_list_t** pp_list)
{
ll_node_t* current = (*pp_list)->head;
for(int i = 0; i < (*pp_list)->size; i++)
{
(*pp_list)->head = current->next;
free(current->data);
free(current);
current = (*pp_list)->head;
}
free(*pp_list);
}
void
ll_print_int(linked_list_t* list)
{
if(!list->size) exit(0);
ll_node_t* current = list->head;
for(int i = 0; i < list->size; i++)
{
printf("%d ", *(int*)current->data);
current = current->next;
}
printf("n");
}
void
ll_print_string(linked_list_t* list)
{
if(!list->size) exit(0);
ll_node_t* current = list->head;
for(int i = 0; i < list->size; i++)
{
printf("%s ", (char*)current->data);
current = current->next;
}
printf("n");
}
void partition(linked_list_t* list, int x)
{
ll_node_t* current = list->head;
ll_node_t* tail = list->head;
for(int i = 0; i < list->size; i++)
{
tail = tail->next;
}
//special case for the first element of the list
if(*(int*)current->data > x)
{
tail->next = current;
list->head = current->next;
tail = current;
}

// loop that finds elements > X
for(int i = 0; i < list->size - 1; i++)
{   
if(*(int*)current->data > x)
{
// assigning the element to the end
tail->next = current->next;
// linking the previous element to the one after the element
current->next = current->next->next;
tail = tail->next;
tail->next = NULL;
// moving on to next element
current = current->next;
}
else current = current->next;
// moving on to next element 
}
}
int main()
{
linked_list_t* linkedList;
while (1) {
char command[16];
long size, num;
scanf("%s", command);
if (strcmp(command, "list") == 0) {
linkedList = ll_create(sizeof(int));
scanf("%ld", &size);
long int curr_nr;
for (int i = 0; i < size; ++i) {
scanf("%ld", &curr_nr);
ll_add_nth_node(linkedList, size, &curr_nr);
}
}
if (strcmp(command, "X") == 0) {
scanf("%ld", &num);
partition(linkedList, num);
ll_print_int(linkedList);
break;
}
}
ll_free(&linkedList);
return 0;
}

因此，由于我也有列表大小，即列表中元素的数量，我认为如下：

在循环列表之前，检查头(第一个元素(是否需要在末尾移动(如果>X(，然后有一个循环list->size-1次，当内部条件满足时，执行以下操作：

它基本上会遍历元素并查看它们的下一个，所以当一个元素的下一步是>X、 它将被转移：将尾部的下一个元素指定为元素>X(当前->下一个(，然后将当前元素链接到元素后面的元素。之后，新的尾部将是在末尾添加的元素。

目前，我在for循环中条件内的第一行出现分段故障，在这一行：tail->next = current->next;

免责声明：正如我测试过的，主程序可以很好地添加元素，等等

Answer 1

我将提供一个答案，它并不完全是对现有代码的解决方案，而是在处理数据时提供一种不同的思考方式。

如果在迭代时不尝试对列表进行重新排序(管理head、current和tail(，而是解构列表并构造两个新列表，该怎么办？我们的结果变成了这两个列表的串联。

在伪代码中可视化，其工作方式如下：

Q is [2 5 6 4 3 1]
part Q <= 3
L is []     
R is []

Q eql [2 5 6 4 3 1]
^ -> L eql [2]
Q eql [5 6 4 3 1]
^ -> R eql [5]
Q eql [6 4 3 1]
^ -> R eql [5 6]
Q eql [4 3 1]  
^ -> R eql [5 6 4]
Q eql [3 1]    
^ -> L eql [2 3]
Q eql [1]
^ -> L eql [2 3 1]
Q eql []
Q is L concat R
Q eql [2 3 1 5 6 4]

通过这样做，我们的分区函数可以利用与最初构建列表时相同的逻辑。

下面是一个C中的例子，使用一个非常简单的链表：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
struct node *next;
int value;
} node;
typedef struct {
node *head;
} list;
void list_append_node(list *l, node *n) {
node *root = l->head;
if (root) {
while (root->next)
root = root->next;
root->next = n;
} else
l->head = n;
}
void list_append_value(list *l, int v) {
node *n = calloc(1, sizeof *n);
n->value = v;
list_append_node(l, n);
}
void list_part(list *l, int v) {
list lower = { 0 };
list upper = { 0 };
for (node *curr = l->head, *temp; curr; curr = temp) {
temp = curr->next;
curr->next = NULL;
list_append_node(curr->value <= v ? &lower : &upper, curr);
}
list_append_node(&lower, upper.head);
l->head = lower.head;
}
int main(void) {
int inputs[] = { 2, 5, 6, 4, 3, 1 };
size_t len = sizeof inputs / sizeof *inputs;
list l = { 0 };
for (size_t i = 0; i < len; i++)
list_append_value(&l, inputs[i]);
list_part(&l, 3);
for (node *n = l.head, *t; n; n = t) {
t = n->next;
printf("%d ", n->value);
free(n);
}
putchar('n');
}

stdout:

2 3 1 5 6 4 

---

注意，对于每个列表使用node *tail成员可以实现将list_append_node的性能从O(N(提高到O(1(。