c - 将两个排序的链表合并为一个链表(递归)
问题描述
我必须编写一个接收两个排序列表的递归函数:
typedef struct listNode {
int* dataPtr;
struct listNode* next;
} ListNode;
typedef struct list
{
ListNode* head;
ListNode* tail;
} List;
并将它们合并到一个排序列表中。
我写了这些函数:
void mergeRec(ListNode* head1, ListNode* head2, ListNode* mergedList)
{
if (head1 == NULL && head2 == NULL)
return;
else if (head1 == NULL) {
mergedList->next = head2;
head2 = head2->next;
}
else if (head2 == NULL) {
mergedList->next = head1;
head1 = head1->next;
}
else if (*(head1->dataPtr) > *(head2->dataPtr)) {
mergedList->next = head1;
head1 = head1->next;
}
else
{
mergedList->next = head2;
head2 = head2->next;
}
mergeRec(head1, head2, mergedList->next);
}
List merge(List lst1, List lst2)
{
List mergedList;
makeEmptyList(&mergedList);
mergeRec(lst1.head, lst2.head, mergedList.head);
return mergedList;
}
现在,递归函数的问题是,在第一次调用时,合并列表指向 null,所以很明显,当我编写类似的东西时,mergeList->next
我会遇到一个正在运行的错误。
我试图通过在递归中添加以下条件来解决它:
if (mergedList == NULL)
{
if (*(head1->dataPtr) > *(head2->dataPtr))
{
mergedList = head1;
head1 = head1->next;
}
else
{
mergedList = head2;
head2 = head2->next;
}
}
但我收到了这个错误:
“在 q2d.exe 中的 0x00661EB9 处引发异常:0xC0000005:访问冲突写入位置 0x01000F48。”
我无法说出问题所在,或者我该如何解决。非常感谢您的帮助。
谢谢!
解决方案
对于初学者来说,完全不清楚为什么在这个结构中有一个类型的数据成员int *
typedef struct listNode {
int* dataPtr;
struct listNode* next;
}List;
而不仅仅是类型int
typedef struct listNode {
int data;
struct listNode* next;
}List;
然而,函数merge
和mergeRec
是无效的,因为它们处理列表值和指针 list1.head、list2.head 和 mergeList.head 的副本。
List merge(List lst1, List lst2)
mergeRec(lst1.head, lst2.head, mergedList.head);
此外,指针list1.tail、list2.tail 和mergedList.tail 被忽略。
我可以建议以下演示程序中显示的以下解决方案。
#include <stdio.h>
#include <stdlib.h>
typedef struct listNode
{
int *dataPtr;
struct listNode *next;
} ListNode;
typedef struct list
{
ListNode *head;
ListNode *tail;
} List;
void makeEmpty( List *list )
{
list->head = list->tail = NULL;
}
int push( List *list, int data )
{
ListNode *current = malloc( sizeof( ListNode ) );
int success = current != NULL;
if ( success )
{
current->dataPtr = malloc( sizeof( int ) );
success = current->dataPtr != NULL;
if ( success )
{
*current->dataPtr = data;
current->next = NULL;
if ( list->head == NULL )
{
list->head = list->tail = current;
}
else
{
list->tail = list->tail->next = current;
}
}
else
{
free( current );
current = NULL;
}
}
return success;
}
List merge( List *first, List *second )
{
List result;
makeEmpty( &result );
if ( ( second->head != NULL ) &&
( first->head == NULL || *second->head->dataPtr < *first->head->dataPtr ) )
{
result.head = result.tail = second->head;
second->head = second->head->next;
if ( second->head == NULL ) second->tail = NULL;
}
else if ( first->head != NULL )
{
result.head = result.tail = first->head;
first->head = first->head->next;
if ( first->head == NULL ) first->tail = NULL;
}
if ( !( first->head == NULL && second->head == NULL ) )
{
List tmp = merge( first, second );
result.head->next = tmp.head;
result.tail = tmp.tail;
}
return result;
}
void output( const List *list )
{
for ( const ListNode *current = list->head; current != NULL; current = current->next )
{
printf( "%d ", *current->dataPtr );
}
puts( "NULL" );
}
int main(void)
{
List even_numbers;
List odd_numbers;
makeEmpty( &even_numbers );
makeEmpty( &odd_numbers );
const int N = 10;
for ( int i = 0; i < N; i++ )
{
i % 2 == 0 ? push( &even_numbers, i )
: push( &odd_numbers, i );
}
printf( "even_numbers: " ); output( &even_numbers );
printf( "odd_numbers: " ); output( &odd_numbers );
List all_numbers = merge( &even_numbers, &odd_numbers );
printf( "all_numbers: " ); output( &all_numbers );
printf( "even_numbers: " ); output( &even_numbers );
printf( "odd_numbers: " ); output( &odd_numbers );
return 0;
}
程序输出为
even_numbers: 0 2 4 6 8 NULL
odd_numbers: 1 3 5 7 9 NULL
all_numbers: 0 1 2 3 4 5 6 7 8 9 NULL
even_numbers: NULL
odd_numbers: NULL
推荐阅读
- c# - Mongodb查询以获取特定于c#的嵌套文档的值
- google-apps-script - 谷歌脚本在编辑时将值从一列复制并粘贴到另一列
- javascript - TypeScript如何访问promise方法中的字段
- dictionary - 如何使用反射反转地图
- informatica - Informatica 服务自动停止
- php - 如何在 PHP docker 镜像上安装 yarn 和 npm(symfony 4 项目)
- excel - 将多个工作簿中的值合并到一个工作簿
- python - 在 Selenium 中处理动态页面
- python - 使用 *args 和 seaborn 绘图时如何显示所有图例
- kubernetes - kubectl 日志返回“您的意思是运行 dotnet SDK 命令吗?请安装 dotnet SDK”