用另一个值重命名列表
Rename a list with value of another one
我尝试实现一个用 C 语言编写的程序，其中有两个链表，我需要创建第三个链表，其中包含第一个列表的所有值，最终用第二个链表的值重命名一个基于他们的订单。更新的第三个列表中的任何值都不应重复，它应该 return 错误。
查看下面给出的示例以了解此程序的工作原理：
示例 1
A = [a, b, c, d]
B = [e, f]
第三个将是：
C = [e, f, c, d]
例 2
A = [a, b, c, d]
B = [a, e]
第三个将是：
C = [a, e, c, d]
例 3
A = [a, b, c, d]
B = [c, d]
这应该 return 一个错误，因为 C 将是
C = [c, d c, d]
但不能有重复值。
例 4
A = [a, b, c, d]
B = [b, a]
这不应该 return 任何错误，因为 C 将是
C = [b, a, c, d]
（没有重复值，列表A的前两个元素将被重命名为列表B的前两个元素）。
您可以在下面找到我的想法，但我对这个问题的不同解决方案很感兴趣
T //Temp
C //Result
for (int i = 0; i < |A|; i++)
{
if(i > length of B && T is not empty)
{
//One or more elements were not been renamed
return ERROR
}
if(A[i] == B[i])
{
C[i] = B[i];
}
else
{
C[i] = B[i];
if(T contains A[i])
{
pop A[i] from T
}
else
{
push A[i] in T
}
}
}
编辑
背景：此算法支持从具体的 table (A) 给定文件名列表 (B) 创建别名 table (C)。
- 每个 list/table 不能包含重复值。
- B 的长度小于或等于 A 的长度（我无法重命名已有的更多值）
这可以在 Python 中轻松完成。像这样：
def merge_lists(list1, list2):
if len(list2) > len(list1):
raise ValueError("list2 cannot be of greater length than list1")
list3 = list(list1) # make copy of list1
list_after_overlap = list1[len(list2):] # get slice of list1 starting from end of list2
index = 0
for item in list2:
if item not in list_after_overlap:
list3[index] = item
else:
raise ValueError("merged list would have repeated values")
index += 1
return list3
这不仅仅是 Python 炫耀，尽管它可以说是完成这项工作的更好工具。这也像伪代码一样读起来很好，并且已经原型化并测试了我们的算法，我们可以在 C 中实现相同的逻辑，我们只需要一些辅助函数。
如前所述，一个简单的数组就可以了，并且由于您没有在问题中指定数据类型，我们将使用普通的旧 int：
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
result.merged_list.list_length = 0;
result.merged_list.values = NULL;
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
result.merged_list.values = (int*)malloc(sizeof(int)*(list1.list_length));
result.error = (result.merged_list.values == NULL) ? ERROR_MEMORY : ERROR_NONE;
}
if (result.error == ERROR_NONE)
{
replicate_list(&result.merged_list, list1, list2.list_length);
list_t list_after_overlap = get_list_slice(list1, list2.list_length);
for (size_t index = 0; index < list2.list_length && result.error == ERROR_NONE; index++)
{
if (!item_in_list(list2.values[index], list_after_overlap))
{
result.merged_list.values[index] = list2.values[index];
}
else
{
result.error = ERROR_REPEATED_VALUES;
free(result.merged_list.values); /* we won't be needing this anymore */
result.merged_list.values = NULL;
result.merged_list.list_length = 0;
}
}
}
return result;
}
如您所见，算法本质上是相同的，但有所改进。在 python 代码中，我们复制了整个 list1，只是为了覆盖重叠的值，这是一种浪费，但对于大型列表来说可能是有意义的。现在我们只得到重叠之后的部分，它在 list2 之后开始，并用它来测试重复项。下面是完整的代码，在 main 上进行了一些基本测试：
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef enum {
ERROR_NONE, /* success */
ERROR_REPEATED_VALUES, /* merged list would have repeated values */
ERROR_LENGTH_EXCEEDED, /* second list length exceeds that of first list */
ERROR_MEMORY /* could not allocate memory for the merged list */
} error_t;
typedef struct {
int *values; /* pointer to int array that contains the list values */
size_t list_length; /* the number of elements in the list (array) */
}list_t;
typedef struct {
list_t merged_list; /* has pointer (values) to merged list (array), which MUST be freed */
error_t error; /* indicates success or the error code of the merge operation */
}merged_list_t;
typedef enum {FALSE=0, TRUE=1} bool_t; /* use stdbool.h preferably, if available */
/* === Test Utility functions */
static void print_list(const list_t list)
{
putchar('[');
for (size_t index = 0; index < list.list_length; index++)
{
printf("%d", list.values[index]);
if (index < list.list_length - 1)
{
printf(", ");
}
}
printf("]\n");
}
static void print_merged_list(const merged_list_t list)
{
if (list.merged_list.values != NULL && list.error == ERROR_NONE)
{
print_list(list.merged_list);
}
else
{
switch (list.error)
{
case ERROR_NONE: printf("Merged list is null (empty)\n"); break;
case ERROR_LENGTH_EXCEEDED: printf("Error: Length of list2 is greater than length of list1\n"); break;
case ERROR_MEMORY: printf("Error: Unable to allocate memory for result\n"); break;
case ERROR_REPEATED_VALUES: printf("Error: Merged list would have duplicate entries\n"); break;
default: printf("Unexpected or unhandled error\n"); break;
}
}
}
/* utility functions */
static void replicate_list(list_t *new_list, const list_t list, size_t start)
{
for (size_t index = start; index < list.list_length; index++)
{
new_list->values[index] = list.values[index];
}
new_list->list_length = list.list_length;
}
static list_t get_list_slice(const list_t list, size_t start_index)
{
list_t sliced_list;
if (list.values != NULL && start_index < list.list_length)
{
sliced_list.values = list.values + start_index;
sliced_list.list_length = list.list_length - start_index;
}
return sliced_list;
}
static bool_t item_in_list(int item, const list_t list)
{
bool_t in_list = FALSE;
for (size_t i=0; i < list.list_length && !in_list; i++)
{
in_list = (item == list.values[i]) ? TRUE : FALSE;
}
return in_list;
}
/*
Produces a merged list which consists of list1 replaced by the overlapping elements of list2,
as long as the resulting list does not cause elements of the merged list to be repeated.
Input:
list1[]: int array of arbitrary length consisting of unique elements
list2[]: int array of length smaller than of list1 consisting of unique elements
Returns:
A merged_list_t structure containing the merged list structure (which MUST be freed) and its length
or an error code if the lists are of invalid length or the merge operation produces duplicate values
*/
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
result.merged_list.list_length = 0;
result.merged_list.values = NULL;
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
result.merged_list.values = (int*)malloc(sizeof(int)*(list1.list_length));
result.error = (result.merged_list.values == NULL) ? ERROR_MEMORY : ERROR_NONE;
}
if (result.error == ERROR_NONE)
{
replicate_list(&result.merged_list, list1, list2.list_length);
list_t list_after_overlap = get_list_slice(list1, list2.list_length);
for (size_t index = 0; index < list2.list_length && result.error == ERROR_NONE; index++)
{
if (!item_in_list(list2.values[index], list_after_overlap))
{
result.merged_list.values[index] = list2.values[index];
}
else
{
result.error = ERROR_REPEATED_VALUES;
free(result.merged_list.values); /* we won't be needing this anymore */
result.merged_list.values = NULL;
result.merged_list.list_length = 0;
}
}
}
return result;
}
void main(void)
{
printf("Testing basic scenario\n");
int a1[] = { 1, 2, 3, 4, 5 };
int a2[] = { 6, 7 };
list_t l1;
l1.list_length = sizeof(a1) / sizeof(a1[0]); /* get number of elements */
l1.values = a1;
list_t l2;
l2.list_length = sizeof(a2) / sizeof(a2[0]);
l2.values = a2;
merged_list_t ml = merge_lists(l1, l2);
print_list(l1);
print_list(l2);
print_merged_list(ml);
free(ml.merged_list.values);
printf("Testing merge with duplicate values\n");
int a3[] = { 1, 2, 3, 4, 5 };
int a4[] = { 4, 6, 8 };
list_t l3;
l3.list_length = sizeof(a3) / sizeof(a3[0]); /* get number of elements */
l3.values = a3;
list_t l4;
l4.list_length = sizeof(a4) / sizeof(a4[0]);
l4.values = a4;
merged_list_t ml2 = merge_lists(l3, l4);
print_list(l3);
print_list(l4);
print_merged_list(ml2);
free(ml2.merged_list.values);
printf("Testing list2 with value from list1\n");
int a5[] = { 1, 2, 3, 4, 5 };
int a6[] = { 3, 6, 9 };
list_t l5;
l5.list_length = sizeof(a5) / sizeof(a5[0]); /* get number of elements */
l5.values = a5;
list_t l6;
l6.list_length = sizeof(a6) / sizeof(a6[0]);
l6.values = a6;
merged_list_t ml3 = merge_lists(l5, l6);
print_list(l5);
print_list(l6);
print_merged_list(ml3);
free(ml3.merged_list.values);
_getch();
}
但是你特别要求链表，所以要最终回答你的问题，这里有一种方法可以做到：
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
list_t list_after_overlap;
initialize_list(&result.merged_list);
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
bool_t success = replicate_list(&list_after_overlap, list1, list2.list_length);
result.error = (success) ? ERROR_NONE: ERROR_MEMORY;
}
if (result.error == ERROR_NONE)
{
for (list_item_t *item = list2.head; item != NULL && result.error == ERROR_NONE; item = item->next)
{
if (!item_in_list(*item->value, list_after_overlap))
{
/* duplicate each item and append to merged_list */
bool_t success = append_list_item(&result.merged_list, new_list_item(*item->value));
result.error = success ? ERROR_NONE : ERROR_MEMORY;
}
else
{
result.error = ERROR_REPEATED_VALUES;
destroy_list(&list_after_overlap);
destroy_list(&result.merged_list);
}
}
}
if (result.error == ERROR_NONE)
{
/* join overlap with difference */
result.merged_list.tail->next = list_after_overlap.head;
list_after_overlap.head = result.merged_list.head;
result.merged_list.tail = list_after_overlap.tail;
}
return result;
}
同样，同样的逻辑，合并函数和朋友只是被重构来处理链表。这是完整的代码：
/* Enable debug heap functions (Visual Studio) */
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#include <stdio.h>
#include <conio.h>
typedef enum {
ERROR_NONE, /* success */
ERROR_REPEATED_VALUES, /* merged list would have repeated values */
ERROR_LENGTH_EXCEEDED, /* second list length exceeds that of first list */
ERROR_MEMORY /* could not allocate memory for the merged list */
} error_t;
typedef struct list_item_ {
int *value; /* pointer to single value */
list_item_ *next;
list_item_ *previous;
}list_item_t;
typedef struct {
list_item_t *head;
list_item_t *tail;
size_t list_length;
}list_t;
typedef struct {
list_t merged_list; /* linked list with result, MUST be freed */
error_t error; /* indicates success or the error code of the merge operation */
}merged_list_t;
typedef enum {FALSE=0, TRUE=1} bool_t;
/* === Test Utility functions === */
static void print_list(const list_t list)
{
putchar('[');
for (list_item_t *item = list.head; item != NULL; item = item->next)
{
printf("%d", *item->value);
if (item->next != NULL)
{
printf(", "); /* add comma if it's not the last item (tail) */
}
}
printf("]\n");
}
static void print_merged_list(const merged_list_t list)
{
if (list.merged_list.head != NULL && list.error == ERROR_NONE)
{
print_list(list.merged_list);
}
else
{
switch (list.error)
{
case ERROR_NONE: printf("Merged list head is null (empty list)\n"); break;
case ERROR_LENGTH_EXCEEDED: printf("Error: Length of list2 is greater than length of list1\n"); break;
case ERROR_MEMORY: printf("Error: Unable to allocate memory for result\n"); break;
case ERROR_REPEATED_VALUES: printf("Error: Merged list would have duplicate entries\n"); break;
default: printf("Unexpected or unhandled error\n"); break;
}
}
}
/* helper functions */
static void initialize_list(list_t *list)
{
list->head = NULL;
list->tail = NULL;
list->list_length = 0;
}
static list_item_t* new_list_item(int value)
{
list_item_t *item = (list_item_t*)malloc(sizeof(list_item_t));
if (item != NULL)
{
item->value = (int*)malloc(sizeof(int));
if (item->value != NULL)
{
*item->value = value;
item->next = NULL;
item->previous = NULL;
}
else
{
free(item);
item = NULL;
}
}
return item;
}
static bool_t append_list_item(list_t *list, list_item_t *item)
{
bool_t success = TRUE;
if (item == NULL)
{
success = FALSE;
}
else
{
if (list->head == NULL)
{
/* first item, set as head and tail */
list->head = item;
list->head->next = NULL;
list->head->previous = NULL;
list->tail = item;
}
else
{
/* item (new tail) will be preceded by the current tail */
item->previous = list->tail;
/* link current tail to new item */
list->tail->next = item;
/* make item the new tail */
list->tail = item;
list->tail->next = NULL;
}
list->list_length++;
}
return success;
}
static bool_t set_list_values(list_t *list, const int *values, size_t values_length)
{
bool_t success = TRUE;
initialize_list(list);
for (size_t index = 0; index < values_length && success; index++)
{
list_item_t *item = new_list_item(values[index]);
success = append_list_item(list, item);
}
if (success)
{
list->list_length = values_length;
}
return success;
}
static void destroy_list(list_t *list)
{
list_item_t *next_item = NULL;
for (list_item_t *item = list->head; item != NULL; item = next_item)
{
next_item = item->next;
free(item->value);
item->value = NULL;
free(item);
item = NULL;
}
list->list_length = 0;
list->head = NULL;
list->tail = NULL;
}
static bool_t replicate_list(list_t *new_list, const list_t list, const size_t start)
{
size_t count = 0;
list_item_t *item;
bool_t success = TRUE;
initialize_list(new_list);
for (item = list.head; item != NULL && success; item = item->next, count++)
{
/* skip items before start */
if (count >= start)
{
/* create new list with remaining items */
success = append_list_item(new_list, new_list_item(*item->value));
}
}
if (!success)
{
destroy_list(new_list);
}
return success;
}
static bool_t item_in_list(int item, const list_t list)
{
bool_t in_list = FALSE;
for (list_item_t *l_item = list.head; (l_item != NULL) && !in_list; l_item = l_item->next)
{
in_list = (item == *l_item->value) ? TRUE : FALSE;
}
return in_list;
}
/*
Produces a merged list which consists of list1 replaced by the overlapping elements of list2,
as long as the resulting list does not cause elements of the merged list to be repeated.
Input:
list1[]: a linked list of arbitrary length consisting of unique elements
list2[]: a linked list of length less than or equal to the length of list 1, also with unique elements
Returns:
A merged_list_t structure containing the merged linked list (which MUST be freed) and its length
or an error code if the lists are of invalid length or the merge operation produces duplicate values
*/
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
list_t list_after_overlap;
initialize_list(&result.merged_list);
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
bool_t success = replicate_list(&list_after_overlap, list1, list2.list_length);
result.error = (success) ? ERROR_NONE: ERROR_MEMORY;
}
if (result.error == ERROR_NONE)
{
for (list_item_t *item = list2.head; item != NULL && result.error == ERROR_NONE; item = item->next)
{
if (!item_in_list(*item->value, list_after_overlap))
{
/* duplicate each item and append to merged_list */
bool_t success = append_list_item(&result.merged_list, new_list_item(*item->value));
result.error = success ? ERROR_NONE : ERROR_MEMORY;
}
else
{
result.error = ERROR_REPEATED_VALUES;
destroy_list(&list_after_overlap);
destroy_list(&result.merged_list);
}
}
}
if (result.error == ERROR_NONE)
{
/* join overlap with difference */
result.merged_list.tail->next = list_after_overlap.head;
list_after_overlap.head = result.merged_list.head;
result.merged_list.tail = list_after_overlap.tail;
}
return result;
}
void main(void)
{
printf("Testing basic scenario\n");
int a1[] = { 1, 2, 3, 4, 5 };
int a2[] = { 6, 7 };
list_t l1;
set_list_values(&l1, a1, sizeof(a1) / sizeof(a1[0]));
list_t l2;
set_list_values(&l2, a2, sizeof(a2) / sizeof(a2[0]));
print_list(l1);
print_list(l2);
merged_list_t ml = merge_lists(l1, l2);
print_merged_list(ml);
destroy_list(&l1);
destroy_list(&l2);
destroy_list(&ml.merged_list);
printf("Testing merge with duplicate values\n");
int a3[] = { 1, 2, 3, 4, 5 };
int a4[] = { 4, 6, 8 };
list_t l3;
set_list_values(&l3, a3, sizeof(a3) / sizeof(a3[0]));
list_t l4;
set_list_values(&l4, a4, sizeof(a4) / sizeof(a4[0]));
print_list(l3);
print_list(l4);
ml = merge_lists(l3, l4);
print_merged_list(ml);
destroy_list(&l3);
destroy_list(&l4);
destroy_list(&ml.merged_list);
printf("Testing list2 with value from list1\n");
int a5[] = { 1, 2, 3, 4, 5 };
int a6[] = { 3, 6, 9 };
list_t l5;
set_list_values(&l5, a5, sizeof(a5) / sizeof(a5[0]));
list_t l6;
set_list_values(&l6, a6, sizeof(a6) / sizeof(a6[0]));
print_list(l5);
print_list(l6);
ml = merge_lists(l5, l6);
print_merged_list(ml);
destroy_list(&l5);
destroy_list(&l6);
destroy_list(&ml.merged_list);
printf("Try printing empty list...\n");
print_merged_list(ml);
/* print memory leak report (Visual Studio)*/
_CrtDumpMemoryLeaks();
_getch();
}
如果您正在使用 Visual Studio，请注意 _CrtDumpMemoryLeaks() 宏，这对于检测内存泄漏非常方便。当然，如果你很幸运成为 运行 Linux 就摆脱它并改用 Valgrind。在我的系统上，它很干净。
这是 main 生成的输出示例：
Testing basic scenario
[1, 2, 3, 4, 5]
[6, 7]
[6, 7, 3, 4, 5]
Testing merge with duplicate values
[1, 2, 3, 4, 5]
[4, 6, 8]
Error: Merged list would have duplicate entries
Testing list2 with value from list1
[1, 2, 3, 4, 5]
[3, 6, 9]
[3, 6, 9, 4, 5]
Try printing empty list...
Merged list head is null (empty list)
我尝试实现一个用 C 语言编写的程序，其中有两个链表，我需要创建第三个链表，其中包含第一个列表的所有值，最终用第二个链表的值重命名一个基于他们的订单。更新的第三个列表中的任何值都不应重复，它应该 return 错误。
查看下面给出的示例以了解此程序的工作原理：
示例 1
A = [a, b, c, d]
B = [e, f]
第三个将是：
C = [e, f, c, d]
例 2
A = [a, b, c, d]
B = [a, e]
第三个将是：
C = [a, e, c, d]
例 3
A = [a, b, c, d]
B = [c, d]
这应该 return 一个错误，因为 C 将是
C = [c, d c, d]
但不能有重复值。
例 4
A = [a, b, c, d]
B = [b, a]
这不应该 return 任何错误，因为 C 将是
C = [b, a, c, d]
（没有重复值，列表A的前两个元素将被重命名为列表B的前两个元素）。
您可以在下面找到我的想法，但我对这个问题的不同解决方案很感兴趣
T //Temp
C //Result
for (int i = 0; i < |A|; i++)
{
if(i > length of B && T is not empty)
{
//One or more elements were not been renamed
return ERROR
}
if(A[i] == B[i])
{
C[i] = B[i];
}
else
{
C[i] = B[i];
if(T contains A[i])
{
pop A[i] from T
}
else
{
push A[i] in T
}
}
}
编辑
背景：此算法支持从具体的 table (A) 给定文件名列表 (B) 创建别名 table (C)。
- 每个 list/table 不能包含重复值。
- B 的长度小于或等于 A 的长度（我无法重命名已有的更多值）
这可以在 Python 中轻松完成。像这样：
def merge_lists(list1, list2):
if len(list2) > len(list1):
raise ValueError("list2 cannot be of greater length than list1")
list3 = list(list1) # make copy of list1
list_after_overlap = list1[len(list2):] # get slice of list1 starting from end of list2
index = 0
for item in list2:
if item not in list_after_overlap:
list3[index] = item
else:
raise ValueError("merged list would have repeated values")
index += 1
return list3
这不仅仅是 Python 炫耀，尽管它可以说是完成这项工作的更好工具。这也像伪代码一样读起来很好，并且已经原型化并测试了我们的算法，我们可以在 C 中实现相同的逻辑，我们只需要一些辅助函数。
如前所述，一个简单的数组就可以了，并且由于您没有在问题中指定数据类型，我们将使用普通的旧 int：
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
result.merged_list.list_length = 0;
result.merged_list.values = NULL;
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
result.merged_list.values = (int*)malloc(sizeof(int)*(list1.list_length));
result.error = (result.merged_list.values == NULL) ? ERROR_MEMORY : ERROR_NONE;
}
if (result.error == ERROR_NONE)
{
replicate_list(&result.merged_list, list1, list2.list_length);
list_t list_after_overlap = get_list_slice(list1, list2.list_length);
for (size_t index = 0; index < list2.list_length && result.error == ERROR_NONE; index++)
{
if (!item_in_list(list2.values[index], list_after_overlap))
{
result.merged_list.values[index] = list2.values[index];
}
else
{
result.error = ERROR_REPEATED_VALUES;
free(result.merged_list.values); /* we won't be needing this anymore */
result.merged_list.values = NULL;
result.merged_list.list_length = 0;
}
}
}
return result;
}
如您所见，算法本质上是相同的，但有所改进。在 python 代码中，我们复制了整个 list1，只是为了覆盖重叠的值，这是一种浪费，但对于大型列表来说可能是有意义的。现在我们只得到重叠之后的部分，它在 list2 之后开始，并用它来测试重复项。下面是完整的代码，在 main 上进行了一些基本测试：
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef enum {
ERROR_NONE, /* success */
ERROR_REPEATED_VALUES, /* merged list would have repeated values */
ERROR_LENGTH_EXCEEDED, /* second list length exceeds that of first list */
ERROR_MEMORY /* could not allocate memory for the merged list */
} error_t;
typedef struct {
int *values; /* pointer to int array that contains the list values */
size_t list_length; /* the number of elements in the list (array) */
}list_t;
typedef struct {
list_t merged_list; /* has pointer (values) to merged list (array), which MUST be freed */
error_t error; /* indicates success or the error code of the merge operation */
}merged_list_t;
typedef enum {FALSE=0, TRUE=1} bool_t; /* use stdbool.h preferably, if available */
/* === Test Utility functions */
static void print_list(const list_t list)
{
putchar('[');
for (size_t index = 0; index < list.list_length; index++)
{
printf("%d", list.values[index]);
if (index < list.list_length - 1)
{
printf(", ");
}
}
printf("]\n");
}
static void print_merged_list(const merged_list_t list)
{
if (list.merged_list.values != NULL && list.error == ERROR_NONE)
{
print_list(list.merged_list);
}
else
{
switch (list.error)
{
case ERROR_NONE: printf("Merged list is null (empty)\n"); break;
case ERROR_LENGTH_EXCEEDED: printf("Error: Length of list2 is greater than length of list1\n"); break;
case ERROR_MEMORY: printf("Error: Unable to allocate memory for result\n"); break;
case ERROR_REPEATED_VALUES: printf("Error: Merged list would have duplicate entries\n"); break;
default: printf("Unexpected or unhandled error\n"); break;
}
}
}
/* utility functions */
static void replicate_list(list_t *new_list, const list_t list, size_t start)
{
for (size_t index = start; index < list.list_length; index++)
{
new_list->values[index] = list.values[index];
}
new_list->list_length = list.list_length;
}
static list_t get_list_slice(const list_t list, size_t start_index)
{
list_t sliced_list;
if (list.values != NULL && start_index < list.list_length)
{
sliced_list.values = list.values + start_index;
sliced_list.list_length = list.list_length - start_index;
}
return sliced_list;
}
static bool_t item_in_list(int item, const list_t list)
{
bool_t in_list = FALSE;
for (size_t i=0; i < list.list_length && !in_list; i++)
{
in_list = (item == list.values[i]) ? TRUE : FALSE;
}
return in_list;
}
/*
Produces a merged list which consists of list1 replaced by the overlapping elements of list2,
as long as the resulting list does not cause elements of the merged list to be repeated.
Input:
list1[]: int array of arbitrary length consisting of unique elements
list2[]: int array of length smaller than of list1 consisting of unique elements
Returns:
A merged_list_t structure containing the merged list structure (which MUST be freed) and its length
or an error code if the lists are of invalid length or the merge operation produces duplicate values
*/
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
result.merged_list.list_length = 0;
result.merged_list.values = NULL;
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
result.merged_list.values = (int*)malloc(sizeof(int)*(list1.list_length));
result.error = (result.merged_list.values == NULL) ? ERROR_MEMORY : ERROR_NONE;
}
if (result.error == ERROR_NONE)
{
replicate_list(&result.merged_list, list1, list2.list_length);
list_t list_after_overlap = get_list_slice(list1, list2.list_length);
for (size_t index = 0; index < list2.list_length && result.error == ERROR_NONE; index++)
{
if (!item_in_list(list2.values[index], list_after_overlap))
{
result.merged_list.values[index] = list2.values[index];
}
else
{
result.error = ERROR_REPEATED_VALUES;
free(result.merged_list.values); /* we won't be needing this anymore */
result.merged_list.values = NULL;
result.merged_list.list_length = 0;
}
}
}
return result;
}
void main(void)
{
printf("Testing basic scenario\n");
int a1[] = { 1, 2, 3, 4, 5 };
int a2[] = { 6, 7 };
list_t l1;
l1.list_length = sizeof(a1) / sizeof(a1[0]); /* get number of elements */
l1.values = a1;
list_t l2;
l2.list_length = sizeof(a2) / sizeof(a2[0]);
l2.values = a2;
merged_list_t ml = merge_lists(l1, l2);
print_list(l1);
print_list(l2);
print_merged_list(ml);
free(ml.merged_list.values);
printf("Testing merge with duplicate values\n");
int a3[] = { 1, 2, 3, 4, 5 };
int a4[] = { 4, 6, 8 };
list_t l3;
l3.list_length = sizeof(a3) / sizeof(a3[0]); /* get number of elements */
l3.values = a3;
list_t l4;
l4.list_length = sizeof(a4) / sizeof(a4[0]);
l4.values = a4;
merged_list_t ml2 = merge_lists(l3, l4);
print_list(l3);
print_list(l4);
print_merged_list(ml2);
free(ml2.merged_list.values);
printf("Testing list2 with value from list1\n");
int a5[] = { 1, 2, 3, 4, 5 };
int a6[] = { 3, 6, 9 };
list_t l5;
l5.list_length = sizeof(a5) / sizeof(a5[0]); /* get number of elements */
l5.values = a5;
list_t l6;
l6.list_length = sizeof(a6) / sizeof(a6[0]);
l6.values = a6;
merged_list_t ml3 = merge_lists(l5, l6);
print_list(l5);
print_list(l6);
print_merged_list(ml3);
free(ml3.merged_list.values);
_getch();
}
但是你特别要求链表，所以要最终回答你的问题，这里有一种方法可以做到：
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
list_t list_after_overlap;
initialize_list(&result.merged_list);
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
bool_t success = replicate_list(&list_after_overlap, list1, list2.list_length);
result.error = (success) ? ERROR_NONE: ERROR_MEMORY;
}
if (result.error == ERROR_NONE)
{
for (list_item_t *item = list2.head; item != NULL && result.error == ERROR_NONE; item = item->next)
{
if (!item_in_list(*item->value, list_after_overlap))
{
/* duplicate each item and append to merged_list */
bool_t success = append_list_item(&result.merged_list, new_list_item(*item->value));
result.error = success ? ERROR_NONE : ERROR_MEMORY;
}
else
{
result.error = ERROR_REPEATED_VALUES;
destroy_list(&list_after_overlap);
destroy_list(&result.merged_list);
}
}
}
if (result.error == ERROR_NONE)
{
/* join overlap with difference */
result.merged_list.tail->next = list_after_overlap.head;
list_after_overlap.head = result.merged_list.head;
result.merged_list.tail = list_after_overlap.tail;
}
return result;
}
同样，同样的逻辑，合并函数和朋友只是被重构来处理链表。这是完整的代码：
/* Enable debug heap functions (Visual Studio) */
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#include <stdio.h>
#include <conio.h>
typedef enum {
ERROR_NONE, /* success */
ERROR_REPEATED_VALUES, /* merged list would have repeated values */
ERROR_LENGTH_EXCEEDED, /* second list length exceeds that of first list */
ERROR_MEMORY /* could not allocate memory for the merged list */
} error_t;
typedef struct list_item_ {
int *value; /* pointer to single value */
list_item_ *next;
list_item_ *previous;
}list_item_t;
typedef struct {
list_item_t *head;
list_item_t *tail;
size_t list_length;
}list_t;
typedef struct {
list_t merged_list; /* linked list with result, MUST be freed */
error_t error; /* indicates success or the error code of the merge operation */
}merged_list_t;
typedef enum {FALSE=0, TRUE=1} bool_t;
/* === Test Utility functions === */
static void print_list(const list_t list)
{
putchar('[');
for (list_item_t *item = list.head; item != NULL; item = item->next)
{
printf("%d", *item->value);
if (item->next != NULL)
{
printf(", "); /* add comma if it's not the last item (tail) */
}
}
printf("]\n");
}
static void print_merged_list(const merged_list_t list)
{
if (list.merged_list.head != NULL && list.error == ERROR_NONE)
{
print_list(list.merged_list);
}
else
{
switch (list.error)
{
case ERROR_NONE: printf("Merged list head is null (empty list)\n"); break;
case ERROR_LENGTH_EXCEEDED: printf("Error: Length of list2 is greater than length of list1\n"); break;
case ERROR_MEMORY: printf("Error: Unable to allocate memory for result\n"); break;
case ERROR_REPEATED_VALUES: printf("Error: Merged list would have duplicate entries\n"); break;
default: printf("Unexpected or unhandled error\n"); break;
}
}
}
/* helper functions */
static void initialize_list(list_t *list)
{
list->head = NULL;
list->tail = NULL;
list->list_length = 0;
}
static list_item_t* new_list_item(int value)
{
list_item_t *item = (list_item_t*)malloc(sizeof(list_item_t));
if (item != NULL)
{
item->value = (int*)malloc(sizeof(int));
if (item->value != NULL)
{
*item->value = value;
item->next = NULL;
item->previous = NULL;
}
else
{
free(item);
item = NULL;
}
}
return item;
}
static bool_t append_list_item(list_t *list, list_item_t *item)
{
bool_t success = TRUE;
if (item == NULL)
{
success = FALSE;
}
else
{
if (list->head == NULL)
{
/* first item, set as head and tail */
list->head = item;
list->head->next = NULL;
list->head->previous = NULL;
list->tail = item;
}
else
{
/* item (new tail) will be preceded by the current tail */
item->previous = list->tail;
/* link current tail to new item */
list->tail->next = item;
/* make item the new tail */
list->tail = item;
list->tail->next = NULL;
}
list->list_length++;
}
return success;
}
static bool_t set_list_values(list_t *list, const int *values, size_t values_length)
{
bool_t success = TRUE;
initialize_list(list);
for (size_t index = 0; index < values_length && success; index++)
{
list_item_t *item = new_list_item(values[index]);
success = append_list_item(list, item);
}
if (success)
{
list->list_length = values_length;
}
return success;
}
static void destroy_list(list_t *list)
{
list_item_t *next_item = NULL;
for (list_item_t *item = list->head; item != NULL; item = next_item)
{
next_item = item->next;
free(item->value);
item->value = NULL;
free(item);
item = NULL;
}
list->list_length = 0;
list->head = NULL;
list->tail = NULL;
}
static bool_t replicate_list(list_t *new_list, const list_t list, const size_t start)
{
size_t count = 0;
list_item_t *item;
bool_t success = TRUE;
initialize_list(new_list);
for (item = list.head; item != NULL && success; item = item->next, count++)
{
/* skip items before start */
if (count >= start)
{
/* create new list with remaining items */
success = append_list_item(new_list, new_list_item(*item->value));
}
}
if (!success)
{
destroy_list(new_list);
}
return success;
}
static bool_t item_in_list(int item, const list_t list)
{
bool_t in_list = FALSE;
for (list_item_t *l_item = list.head; (l_item != NULL) && !in_list; l_item = l_item->next)
{
in_list = (item == *l_item->value) ? TRUE : FALSE;
}
return in_list;
}
/*
Produces a merged list which consists of list1 replaced by the overlapping elements of list2,
as long as the resulting list does not cause elements of the merged list to be repeated.
Input:
list1[]: a linked list of arbitrary length consisting of unique elements
list2[]: a linked list of length less than or equal to the length of list 1, also with unique elements
Returns:
A merged_list_t structure containing the merged linked list (which MUST be freed) and its length
or an error code if the lists are of invalid length or the merge operation produces duplicate values
*/
merged_list_t merge_lists(const list_t list1, const list_t list2)
{
merged_list_t result;
list_t list_after_overlap;
initialize_list(&result.merged_list);
if (list2.list_length > list1.list_length)
{
result.error = ERROR_LENGTH_EXCEEDED;
}
else
{
bool_t success = replicate_list(&list_after_overlap, list1, list2.list_length);
result.error = (success) ? ERROR_NONE: ERROR_MEMORY;
}
if (result.error == ERROR_NONE)
{
for (list_item_t *item = list2.head; item != NULL && result.error == ERROR_NONE; item = item->next)
{
if (!item_in_list(*item->value, list_after_overlap))
{
/* duplicate each item and append to merged_list */
bool_t success = append_list_item(&result.merged_list, new_list_item(*item->value));
result.error = success ? ERROR_NONE : ERROR_MEMORY;
}
else
{
result.error = ERROR_REPEATED_VALUES;
destroy_list(&list_after_overlap);
destroy_list(&result.merged_list);
}
}
}
if (result.error == ERROR_NONE)
{
/* join overlap with difference */
result.merged_list.tail->next = list_after_overlap.head;
list_after_overlap.head = result.merged_list.head;
result.merged_list.tail = list_after_overlap.tail;
}
return result;
}
void main(void)
{
printf("Testing basic scenario\n");
int a1[] = { 1, 2, 3, 4, 5 };
int a2[] = { 6, 7 };
list_t l1;
set_list_values(&l1, a1, sizeof(a1) / sizeof(a1[0]));
list_t l2;
set_list_values(&l2, a2, sizeof(a2) / sizeof(a2[0]));
print_list(l1);
print_list(l2);
merged_list_t ml = merge_lists(l1, l2);
print_merged_list(ml);
destroy_list(&l1);
destroy_list(&l2);
destroy_list(&ml.merged_list);
printf("Testing merge with duplicate values\n");
int a3[] = { 1, 2, 3, 4, 5 };
int a4[] = { 4, 6, 8 };
list_t l3;
set_list_values(&l3, a3, sizeof(a3) / sizeof(a3[0]));
list_t l4;
set_list_values(&l4, a4, sizeof(a4) / sizeof(a4[0]));
print_list(l3);
print_list(l4);
ml = merge_lists(l3, l4);
print_merged_list(ml);
destroy_list(&l3);
destroy_list(&l4);
destroy_list(&ml.merged_list);
printf("Testing list2 with value from list1\n");
int a5[] = { 1, 2, 3, 4, 5 };
int a6[] = { 3, 6, 9 };
list_t l5;
set_list_values(&l5, a5, sizeof(a5) / sizeof(a5[0]));
list_t l6;
set_list_values(&l6, a6, sizeof(a6) / sizeof(a6[0]));
print_list(l5);
print_list(l6);
ml = merge_lists(l5, l6);
print_merged_list(ml);
destroy_list(&l5);
destroy_list(&l6);
destroy_list(&ml.merged_list);
printf("Try printing empty list...\n");
print_merged_list(ml);
/* print memory leak report (Visual Studio)*/
_CrtDumpMemoryLeaks();
_getch();
}
如果您正在使用 Visual Studio，请注意 _CrtDumpMemoryLeaks() 宏，这对于检测内存泄漏非常方便。当然，如果你很幸运成为 运行 Linux 就摆脱它并改用 Valgrind。在我的系统上，它很干净。
这是 main 生成的输出示例：
Testing basic scenario
[1, 2, 3, 4, 5]
[6, 7]
[6, 7, 3, 4, 5]
Testing merge with duplicate values
[1, 2, 3, 4, 5]
[4, 6, 8]
Error: Merged list would have duplicate entries
Testing list2 with value from list1
[1, 2, 3, 4, 5]
[3, 6, 9]
[3, 6, 9, 4, 5]
Try printing empty list...
Merged list head is null (empty list)