C 中的链表——搜索方法
Linked list in C – search method
和上次一样,假设我们有节点的双向链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
struct Node* prev;
} Node;
typedef struct LinkedList {
Node *first;
Node *last;
} LinkedList;
void initList(LinkedList* l) {
l->first = NULL;
l->last = NULL;
}
我的任务是编写搜索方法代码,它应该找到具有给定值的节点
Node* search(LinkedList *list, int value) { ... }
好吧,我的尝试如下
Node* search(LinkedList *list, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL)
return NULL;
node->value = value;
node->prev = NULL;
node->next = list->first;
while((node->value != value) && (node->next != NULL)){
node->prev = node->next;
node->next = (node->next)->next;
}
return node;
}
根据实施测试(这不是我的工作:-)
void test_search_exist() {
printf("Test 3: ");
LinkedList l;
initList(&l);
Node n1, n2;
n1.value = 1;
n1.next = &n2;
n1.prev = NULL;
n2.value = 2;
n2.next = NULL;
n2.prev = &n1;
l.first = &n1;
l.last = &n2;
Node *i = search(&l, 2);
if (i == &n2) {
printf("OK\n");
}else{
printf("FAIL\n");
}
}
void test_search_not_exist(){
printf("Test 4: ");
LinkedList l;
initList(&l);
Node n1, n2;
n1.value = 1;
n1.next = &n2;
n1.prev = NULL;
n2.value = 2;
n2.next = NULL;
n2.prev = &n1;
l.first = &n1;
l.last = &n2;
Node *i = search(&l, 3);
if (i == NULL) {
printf("OK\n");
}else{
printf("FAIL\n");
}
}
我的代码因现有或不存在的节点而中断。那么是不是有什么逻辑错误之类的?
首先:不要在搜索中分配。数据成员已经存在,因为您提前创建了它们。
其次:遍历列表并检查每个节点的值。
Node* search(LinkedList *list, int value)
{
Node *node = list->first;
Node *found = NULL;
while(node != NULL)
{
if(node->value == value)
{
found = node;
break;
}
node = node->next;
}
return found;
}
更具体地说明您犯的错误:
您分配了一个节点,然后用第一个节点的指针填充它,但使用的是您要搜索的值。然后你开始循环列表,条件是当 node->value 等于你正在搜索的值时停止。由于 node->value 是用您正在搜索的值初始化的,因此此比较将 始终 为假(因为它相同),循环将终止并且您会得到不好的结果。
除此之外,您的原始代码会导致内存泄漏,因为您分配了一个新节点,但没有释放它。
和上次一样,假设我们有节点的双向链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
struct Node* prev;
} Node;
typedef struct LinkedList {
Node *first;
Node *last;
} LinkedList;
void initList(LinkedList* l) {
l->first = NULL;
l->last = NULL;
}
我的任务是编写搜索方法代码,它应该找到具有给定值的节点
Node* search(LinkedList *list, int value) { ... }
好吧,我的尝试如下
Node* search(LinkedList *list, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL)
return NULL;
node->value = value;
node->prev = NULL;
node->next = list->first;
while((node->value != value) && (node->next != NULL)){
node->prev = node->next;
node->next = (node->next)->next;
}
return node;
}
根据实施测试(这不是我的工作:-)
void test_search_exist() {
printf("Test 3: ");
LinkedList l;
initList(&l);
Node n1, n2;
n1.value = 1;
n1.next = &n2;
n1.prev = NULL;
n2.value = 2;
n2.next = NULL;
n2.prev = &n1;
l.first = &n1;
l.last = &n2;
Node *i = search(&l, 2);
if (i == &n2) {
printf("OK\n");
}else{
printf("FAIL\n");
}
}
void test_search_not_exist(){
printf("Test 4: ");
LinkedList l;
initList(&l);
Node n1, n2;
n1.value = 1;
n1.next = &n2;
n1.prev = NULL;
n2.value = 2;
n2.next = NULL;
n2.prev = &n1;
l.first = &n1;
l.last = &n2;
Node *i = search(&l, 3);
if (i == NULL) {
printf("OK\n");
}else{
printf("FAIL\n");
}
}
我的代码因现有或不存在的节点而中断。那么是不是有什么逻辑错误之类的?
首先:不要在搜索中分配。数据成员已经存在,因为您提前创建了它们。 其次:遍历列表并检查每个节点的值。
Node* search(LinkedList *list, int value)
{
Node *node = list->first;
Node *found = NULL;
while(node != NULL)
{
if(node->value == value)
{
found = node;
break;
}
node = node->next;
}
return found;
}
更具体地说明您犯的错误:
您分配了一个节点,然后用第一个节点的指针填充它,但使用的是您要搜索的值。然后你开始循环列表,条件是当 node->value 等于你正在搜索的值时停止。由于 node->value 是用您正在搜索的值初始化的,因此此比较将 始终 为假(因为它相同),循环将终止并且您会得到不好的结果。
除此之外,您的原始代码会导致内存泄漏,因为您分配了一个新节点,但没有释放它。