关于拆分链表的问题
Question about about splitted Linked list
我遇到了这个问题，我应该在其中编写一个名为“createList”的函数，该函数获取整数的链表（没有虚拟元素）。该函数应删除大于前一个和下一个元素的每个元素。
另外，我必须制作一个新的链表（没有虚拟元素），我将所有从原始链表中删除的元素放在其中。 （元素应该保持它们在原始链表中出现的相同顺序）。
（createlist在我的代码中是createListEx4()）
比如原链表：3->6->1->9->8->4->5;
将更新为：3->1->8->4；
“删除的元素”链表为：6->9->5；
函数会return一个指向“已移除元素”链表的指针
我写了这段代码，但我似乎无法理解如何让它工作。
当我打印“已删除的元素”链表时出现内存泄漏，return 没有正确的元素。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int data_type;
typedef struct Node2
{
data_type data;
struct Node2 *next;
}Node2;
Node2 * createList2(data_type data);
Node2 * addToFirst2(Node2 *head, data_type data);
Node2 * addToLast2(Node2 *head, data_type data);
void printf_List2(Node2 *head);
void Free_List2(Node2 *head);
Node2* createListEx4(Node2 *);
void Insert_To_Big(Node2 **, int);
void delete_item(Node2 **, Node2 **);
Node2* insert_list();
void main()
{
Node2 *head = NULL;
Node2 *Odd_list = NULL;
head = insert_list(); // A Function which creates a Linked List
printf("You Entered This linked-list:\n");
printf_List2(head); // A Function which prints the Imported List
Odd_list = createListEx4(head); // a Function which Returns The address to The Odd linked list
printf("The Odd Linked-List is:\n");
printf_List2(Odd_list); // A Function Which Prints the Odd List
Free_List2(Odd_list); // Free The list After we have finished using it
}
Node2* insert_list() // A function Which imports numbers to the linked list till -1
{
int Num;
Node2 *Head = NULL;
printf("Please enter the Number you want to Sort untill -1:\n");
scanf("%d", &Num);
while (Num != -1)
{
Head = addToLast2(Head, Num); // The last entered Number will be the Head
scanf("%d", &Num);
}
return Head;
}
Node2* createListEx4(Node2 *head) // **head will be in the end the Even Linked List**
{
Node2 *Big = NULL;
Node2 *temp, *step, *prev = NULL;
if (head == NULL) // if the linked list is empty
return NULL;
if (head->data > head->next->data)
{
Insert_To_Big(&Big, head->data);
temp = head;
head = head->next;
free(temp);
}
prev = head;
// At this point we start runnig the list from an even Number //
step = head;
while (step ->next ->next != NULL)
{
if ((step->data < step->next->data) && (step->next->data > step->next->next->data))
{
Insert_To_Big(&Big, step->next->data);
delete_item(&step, &prev);
}
else
{
prev = step;
step = step->next;
}
}
if (step->data < step->next->data)
{
Insert_To_Big(&Big, step->next->data);
free(step->next);
}
step = NULL;
printf("The Even Linked-List is:\n");
printf_List2(head);
Free_List2(head);
return Big;
}
void delete_item(Node2 **step, Node2 **prev) //A Funtions Which Deletes a Node and Connects the prev Node to the Next one
{
Node2 *temp = *step;
*step = (*step)->next;
(*prev)->next = *step;
free(temp);
}
void Insert_To_Big(Node2 **head, int Num) // A Function Which Creates The Odd linked list
{
*head = addToLast2(*head, Num);
}
Node2 * createList2(data_type data)
{
Node2 *temp = (Node2*)malloc(sizeof(Node2));
temp->data = data;
temp->next = NULL;
return temp;
}
Node2 * addToFirst2(Node2 *head, data_type data)
{
Node2 *temp = createList2(data);
temp->next = head;
return temp;
}
Node2 * addToLast2(Node2 *head, data_type data)
{
Node2 *p = head;
Node2 *temp = createList2(data);
if (head == NULL)
return temp;
while (p->next != NULL)
p = p->next;
p->next = temp;
return head;
}
void printf_List2(Node2 *head)
{
Node2 *p = head;
while (p != NULL)
{
printf("%d, ", p->data);
p = p->next;
}
printf("\n\n");
}
void Free_List2(Node2 *head)
{
Node2 *temp = head;
while (temp != NULL)
{
head = head->next;
free(temp);
temp = head;
}
}
您的代码比需要的复杂得多，并且还包含一些逻辑错误。
例如，将节点从一个列表移动到另一个列表时，不应使用 malloc 和 free。只需更改指针。
这部分从createListEx4
开始
if (head->data > head->next->data)
{
Insert_To_Big(&Big, head->data);
temp = head;
head = head->next;
free(temp);
}
您只将 head 与 head->next 进行比较，但这不是您的要求。此外，您只是 free 元素，但它应该已被移动 - 而不是 freed.
下面是您可以查看的实现。有改进的余地，但我尽量保持代码简单，以便于理解。
typedef int data_type;
typedef struct node
{
data_type data;
struct node *next;
} node;
node* create_static_list(void)
{
// Bypassing check for NULL for readability - don't do it in real code
node* r = NULL;
int a[] = {5, 4, 8, 9, 1, 6, 3};
for (size_t i = 0; i < sizeof a / sizeof a[0]; ++i)
{
node* t = malloc(sizeof *t);
t->next = r;
t->data = a[i];
r = t;
}
return r;
}
void add_to_other_list(node** head, node* p)
{
static node* tail = NULL;
p->next = NULL;
if (tail == NULL)
{
*head = p;
}
else
{
tail->next = p;
}
tail = p;
}
node* remove_special(node* p)
{
node* res = NULL;
if (p == NULL) return res; // 0 elements
if (p->next == NULL) return res; // 1 element
if (p->next->next == NULL) // 2 elements
{
// Special handling of last element in list
if (p->next->data > p->data)
{
// Move p->next to other list
add_to_other_list(&res, p->next);
p->next = NULL;
return res;
}
}
// Repeat as long as the list has minimum 3 elements
while (p->next->next)
{
if ((p->next->data > p->data) &&
(p->next->data > p->next->next->data))
{
// Move p-next
node* t = p->next;
p->next = p->next->next;
add_to_other_list(&res, t);
}
p = p->next;
}
if (p->next == NULL) return res; // 1 element left, just return
if (p->next->next == NULL) // 2 elements left - check last element
{
// Special handling of last element in list
if (p->next->data > p->data)
{
// Move p->next to other list
add_to_other_list(&res, p->next);
p->next = NULL;
}
}
return res;
}
// This is OPs function (expect for variable names)
void print_list(node *p)
{
while (p != NULL)
{
printf("%d, ", p->data);
p = p->next;
}
printf("\n\n");
}
int main(void)
{
node* head = create_static_list();
print_list(head);
node* removed = remove_special(head);
print_list(head);
print_list(removed);
}
输出
3, 6, 1, 9, 8, 4, 5,
3, 1, 8, 4,
6, 9, 5,
不需要为返回的列表创建新元素。通过操作 links.
可以将从原始列表中删除的元素移动到返回的列表中
如果某个元素的数据大于其所有存在的相邻元素，则该元素将从原始列表移至返回列表。有两种特殊情况需要考虑： (1) 如果原始列表为空，则返回的列表为空； (2) 如果原始列表由单个元素组成，则将其移动到返回的列表中。 （情况（2）OP没有明确说明，但似乎是一致的。它只影响元素是否应该移动的测试，可以很容易地改变。）
由于可以从原始列表中删除第一个元素，因此函数的参数应该是一个双指针，指向 link 列表的第一个元素。
下面的函数实现了上面描述的列表处理：
Node2 *createListEx4(Node2 **list)
{
Node2 *bigHead = NULL; /* Head of 'big' list. */
Node2 **bigEnd = &bigHead; /* Pointer to terminating link of 'big' list. */
Node2 *prev = NULL; /* Previous element to compare data with. */
Node2 *next; /* Next element to compare data with. */
Node2 *cur; /* Current element. */
while ((cur = *list) != NULL)
{
next = cur->next;
if ((!prev || cur->data > prev->data) &&
(!next || cur->data > next->data))
{
/* Move current element to 'big' list. */
*bigEnd = cur;
bigEnd = &cur->next;
*list = next;
}
else
{
/* Skip over current element. */
list = &cur->next;
}
prev = cur;
}
/* Terminate the 'big' list. */
*bigEnd = NULL;
return bigHead;
}
示例：
原文：（空）
返回：（空）
剩余：（空）
原文：1
返回：1
剩余：（空）
原文：1 2
返回：2
剩余：1
原文：2 1
返回：2
剩余：1
原文：1 2 3
返回：3
剩余：1 2
原文：1 3 2
返回：3
剩余：1 2
原文：2 1 3
返回：2 3
剩余：1
原文：2 3 1
返回：3
剩余：2 1
原文：3 1 2
返回：3 2
剩余：1
原文：3 2 1
返回：3
剩余：2 1
我的五分钱。:)
这是一个演示程序。我将相应的函数命名为split。针对不同的极端情况调用该函数。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
} Node;
void clear( Node **head )
{
while ( *head )
{
Node *tmp = *head;
*head = ( *head )->next;
free( tmp );
}
}
size_t assign( Node **head, const int a[], size_t n )
{
clear( head );
size_t count;
for ( size_t i = 0; i < n && ( *head = malloc( sizeof( Node ) ) ) != NULL; i++ )
{
( *head )->data = a[i];
( *head )->next = NULL;
head = &( *head )->next;
++count;
}
return count;
}
FILE * display( const Node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->data );
}
fputs( "null", fp );
return fp;
}
Node * split( Node **head )
{
Node *out_head = NULL;
Node **out_current = &out_head;
for ( Node *prev = NULL; *head != NULL; )
{
if ( prev != NULL || ( *head )->next != NULL )
{
if ( ( prev == NULL || prev->data < ( *head )->data ) &&
( ( *head )->next == NULL || ( *head )->next->data < ( *head )->data ) )
{
Node *tmp = *head;
*head = ( *head )->next;
tmp->next = NULL;
*out_current = tmp;
out_current = &tmp->next;
}
else
{
prev = *head;
}
}
else
{
prev = *head;
}
if ( *head != NULL ) head = &( *head )->next;
}
return out_head;
}
int main(void)
{
Node *head = NULL;
int a1[] = { 3 };
assign( &head, a1, sizeof( a1 ) / sizeof( *a1 ) );
fputc( '\n', display( head, stdout ) );
Node *head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a2[] = { 3, 6 };
assign( &head, a2, sizeof( a2 ) / sizeof( *a2 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a3[] = { 6, 3 };
assign( &head, a3, sizeof( a3 ) / sizeof( *a3 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a4[] = { 3, 6, 1, 9, 8, 4, 5 };
assign( &head, a4, sizeof( a4 ) / sizeof( *a4 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
return 0;
}
程序输出为
3 -> null
3 -> null
null
3 -> 6 -> null
3 -> null
6 -> null
6 -> 3 -> null
3 -> null
6 -> null
3 -> 6 -> 1 -> 9 -> 8 -> 4 -> 5 -> null
3 -> 1 -> 8 -> 4 -> null
6 -> 9 -> 5 -> null
我遇到了这个问题，我应该在其中编写一个名为“createList”的函数，该函数获取整数的链表（没有虚拟元素）。该函数应删除大于前一个和下一个元素的每个元素。 另外，我必须制作一个新的链表（没有虚拟元素），我将所有从原始链表中删除的元素放在其中。 （元素应该保持它们在原始链表中出现的相同顺序）。 （createlist在我的代码中是createListEx4()）
比如原链表：3->6->1->9->8->4->5;
将更新为：3->1->8->4；
“删除的元素”链表为：6->9->5；
函数会return一个指向“已移除元素”链表的指针
我写了这段代码，但我似乎无法理解如何让它工作。 当我打印“已删除的元素”链表时出现内存泄漏，return 没有正确的元素。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int data_type;
typedef struct Node2
{
data_type data;
struct Node2 *next;
}Node2;
Node2 * createList2(data_type data);
Node2 * addToFirst2(Node2 *head, data_type data);
Node2 * addToLast2(Node2 *head, data_type data);
void printf_List2(Node2 *head);
void Free_List2(Node2 *head);
Node2* createListEx4(Node2 *);
void Insert_To_Big(Node2 **, int);
void delete_item(Node2 **, Node2 **);
Node2* insert_list();
void main()
{
Node2 *head = NULL;
Node2 *Odd_list = NULL;
head = insert_list(); // A Function which creates a Linked List
printf("You Entered This linked-list:\n");
printf_List2(head); // A Function which prints the Imported List
Odd_list = createListEx4(head); // a Function which Returns The address to The Odd linked list
printf("The Odd Linked-List is:\n");
printf_List2(Odd_list); // A Function Which Prints the Odd List
Free_List2(Odd_list); // Free The list After we have finished using it
}
Node2* insert_list() // A function Which imports numbers to the linked list till -1
{
int Num;
Node2 *Head = NULL;
printf("Please enter the Number you want to Sort untill -1:\n");
scanf("%d", &Num);
while (Num != -1)
{
Head = addToLast2(Head, Num); // The last entered Number will be the Head
scanf("%d", &Num);
}
return Head;
}
Node2* createListEx4(Node2 *head) // **head will be in the end the Even Linked List**
{
Node2 *Big = NULL;
Node2 *temp, *step, *prev = NULL;
if (head == NULL) // if the linked list is empty
return NULL;
if (head->data > head->next->data)
{
Insert_To_Big(&Big, head->data);
temp = head;
head = head->next;
free(temp);
}
prev = head;
// At this point we start runnig the list from an even Number //
step = head;
while (step ->next ->next != NULL)
{
if ((step->data < step->next->data) && (step->next->data > step->next->next->data))
{
Insert_To_Big(&Big, step->next->data);
delete_item(&step, &prev);
}
else
{
prev = step;
step = step->next;
}
}
if (step->data < step->next->data)
{
Insert_To_Big(&Big, step->next->data);
free(step->next);
}
step = NULL;
printf("The Even Linked-List is:\n");
printf_List2(head);
Free_List2(head);
return Big;
}
void delete_item(Node2 **step, Node2 **prev) //A Funtions Which Deletes a Node and Connects the prev Node to the Next one
{
Node2 *temp = *step;
*step = (*step)->next;
(*prev)->next = *step;
free(temp);
}
void Insert_To_Big(Node2 **head, int Num) // A Function Which Creates The Odd linked list
{
*head = addToLast2(*head, Num);
}
Node2 * createList2(data_type data)
{
Node2 *temp = (Node2*)malloc(sizeof(Node2));
temp->data = data;
temp->next = NULL;
return temp;
}
Node2 * addToFirst2(Node2 *head, data_type data)
{
Node2 *temp = createList2(data);
temp->next = head;
return temp;
}
Node2 * addToLast2(Node2 *head, data_type data)
{
Node2 *p = head;
Node2 *temp = createList2(data);
if (head == NULL)
return temp;
while (p->next != NULL)
p = p->next;
p->next = temp;
return head;
}
void printf_List2(Node2 *head)
{
Node2 *p = head;
while (p != NULL)
{
printf("%d, ", p->data);
p = p->next;
}
printf("\n\n");
}
void Free_List2(Node2 *head)
{
Node2 *temp = head;
while (temp != NULL)
{
head = head->next;
free(temp);
temp = head;
}
}
您的代码比需要的复杂得多，并且还包含一些逻辑错误。
例如，将节点从一个列表移动到另一个列表时，不应使用 malloc 和 free。只需更改指针。
这部分从createListEx4
if (head->data > head->next->data)
{
Insert_To_Big(&Big, head->data);
temp = head;
head = head->next;
free(temp);
}
您只将 head 与 head->next 进行比较，但这不是您的要求。此外，您只是 free 元素，但它应该已被移动 - 而不是 freed.
下面是您可以查看的实现。有改进的余地，但我尽量保持代码简单，以便于理解。
typedef int data_type;
typedef struct node
{
data_type data;
struct node *next;
} node;
node* create_static_list(void)
{
// Bypassing check for NULL for readability - don't do it in real code
node* r = NULL;
int a[] = {5, 4, 8, 9, 1, 6, 3};
for (size_t i = 0; i < sizeof a / sizeof a[0]; ++i)
{
node* t = malloc(sizeof *t);
t->next = r;
t->data = a[i];
r = t;
}
return r;
}
void add_to_other_list(node** head, node* p)
{
static node* tail = NULL;
p->next = NULL;
if (tail == NULL)
{
*head = p;
}
else
{
tail->next = p;
}
tail = p;
}
node* remove_special(node* p)
{
node* res = NULL;
if (p == NULL) return res; // 0 elements
if (p->next == NULL) return res; // 1 element
if (p->next->next == NULL) // 2 elements
{
// Special handling of last element in list
if (p->next->data > p->data)
{
// Move p->next to other list
add_to_other_list(&res, p->next);
p->next = NULL;
return res;
}
}
// Repeat as long as the list has minimum 3 elements
while (p->next->next)
{
if ((p->next->data > p->data) &&
(p->next->data > p->next->next->data))
{
// Move p-next
node* t = p->next;
p->next = p->next->next;
add_to_other_list(&res, t);
}
p = p->next;
}
if (p->next == NULL) return res; // 1 element left, just return
if (p->next->next == NULL) // 2 elements left - check last element
{
// Special handling of last element in list
if (p->next->data > p->data)
{
// Move p->next to other list
add_to_other_list(&res, p->next);
p->next = NULL;
}
}
return res;
}
// This is OPs function (expect for variable names)
void print_list(node *p)
{
while (p != NULL)
{
printf("%d, ", p->data);
p = p->next;
}
printf("\n\n");
}
int main(void)
{
node* head = create_static_list();
print_list(head);
node* removed = remove_special(head);
print_list(head);
print_list(removed);
}
输出
3, 6, 1, 9, 8, 4, 5,
3, 1, 8, 4,
6, 9, 5,
不需要为返回的列表创建新元素。通过操作 links.
可以将从原始列表中删除的元素移动到返回的列表中如果某个元素的数据大于其所有存在的相邻元素，则该元素将从原始列表移至返回列表。有两种特殊情况需要考虑： (1) 如果原始列表为空，则返回的列表为空； (2) 如果原始列表由单个元素组成，则将其移动到返回的列表中。 （情况（2）OP没有明确说明，但似乎是一致的。它只影响元素是否应该移动的测试，可以很容易地改变。）
由于可以从原始列表中删除第一个元素，因此函数的参数应该是一个双指针，指向 link 列表的第一个元素。
下面的函数实现了上面描述的列表处理：
Node2 *createListEx4(Node2 **list)
{
Node2 *bigHead = NULL; /* Head of 'big' list. */
Node2 **bigEnd = &bigHead; /* Pointer to terminating link of 'big' list. */
Node2 *prev = NULL; /* Previous element to compare data with. */
Node2 *next; /* Next element to compare data with. */
Node2 *cur; /* Current element. */
while ((cur = *list) != NULL)
{
next = cur->next;
if ((!prev || cur->data > prev->data) &&
(!next || cur->data > next->data))
{
/* Move current element to 'big' list. */
*bigEnd = cur;
bigEnd = &cur->next;
*list = next;
}
else
{
/* Skip over current element. */
list = &cur->next;
}
prev = cur;
}
/* Terminate the 'big' list. */
*bigEnd = NULL;
return bigHead;
}
示例：
原文：（空）
返回：（空）
剩余：（空）
原文：1
返回：1
剩余：（空）
原文：1 2
返回：2
剩余：1
原文：2 1
返回：2
剩余：1
原文：1 2 3
返回：3
剩余：1 2
原文：1 3 2
返回：3
剩余：1 2
原文：2 1 3
返回：2 3
剩余：1
原文：2 3 1
返回：3
剩余：2 1
原文：3 1 2
返回：3 2
剩余：1
原文：3 2 1
返回：3
剩余：2 1
我的五分钱。:)
这是一个演示程序。我将相应的函数命名为split。针对不同的极端情况调用该函数。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
} Node;
void clear( Node **head )
{
while ( *head )
{
Node *tmp = *head;
*head = ( *head )->next;
free( tmp );
}
}
size_t assign( Node **head, const int a[], size_t n )
{
clear( head );
size_t count;
for ( size_t i = 0; i < n && ( *head = malloc( sizeof( Node ) ) ) != NULL; i++ )
{
( *head )->data = a[i];
( *head )->next = NULL;
head = &( *head )->next;
++count;
}
return count;
}
FILE * display( const Node *head, FILE *fp )
{
for ( ; head != NULL; head = head->next )
{
fprintf( fp, "%d -> ", head->data );
}
fputs( "null", fp );
return fp;
}
Node * split( Node **head )
{
Node *out_head = NULL;
Node **out_current = &out_head;
for ( Node *prev = NULL; *head != NULL; )
{
if ( prev != NULL || ( *head )->next != NULL )
{
if ( ( prev == NULL || prev->data < ( *head )->data ) &&
( ( *head )->next == NULL || ( *head )->next->data < ( *head )->data ) )
{
Node *tmp = *head;
*head = ( *head )->next;
tmp->next = NULL;
*out_current = tmp;
out_current = &tmp->next;
}
else
{
prev = *head;
}
}
else
{
prev = *head;
}
if ( *head != NULL ) head = &( *head )->next;
}
return out_head;
}
int main(void)
{
Node *head = NULL;
int a1[] = { 3 };
assign( &head, a1, sizeof( a1 ) / sizeof( *a1 ) );
fputc( '\n', display( head, stdout ) );
Node *head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a2[] = { 3, 6 };
assign( &head, a2, sizeof( a2 ) / sizeof( *a2 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a3[] = { 6, 3 };
assign( &head, a3, sizeof( a3 ) / sizeof( *a3 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
putchar( '\n' );
int a4[] = { 3, 6, 1, 9, 8, 4, 5 };
assign( &head, a4, sizeof( a4 ) / sizeof( *a4 ) );
fputc( '\n', display( head, stdout ) );
head2 = split( &head );
fputc( '\n', display( head, stdout ) );
fputc( '\n', display( head2, stdout ) );
clear( &head2 );
clear( &head );
return 0;
}
程序输出为
3 -> null
3 -> null
null
3 -> 6 -> null
3 -> null
6 -> null
6 -> 3 -> null
3 -> null
6 -> null
3 -> 6 -> 1 -> 9 -> 8 -> 4 -> 5 -> null
3 -> 1 -> 8 -> 4 -> null
6 -> 9 -> 5 -> null