列表结构 - 检查子列表

Question

由于我是 C 编程的新手，我将发布完整的（不是长代码）。我得到的任务是在列表中插入一个元素，同时列表保持有序，打印它，然后检查一个列表是否是另一个列表的子列表。虽然我的 insert 和 print 方法有效，但我收到了一堆警告： 警告：从不兼容的指针类型传递 'Insert' 的参数 1 [默认启用]|。如何修复我的代码以删除这些警告？

另外，从逻辑上讲，我认为 Contains 方法是可以的，为什么它不起作用？它在比较两个单个元素列表时确实有效。

代码如下所示：

#include <stdio.h>
#include "stdlib.h"

typedef struct Book{
    int id;
    char name[50];
    float earnings;
} Book;

struct Node{
    struct Book data;
    struct Node* next;
};

void Insert(struct Node** list, struct Book k)
{
    struct Node* previous;
    struct Node* current;
    struct Node* newNode;

    newNode=(struct Node*)malloc(sizeof(struct Node));

    newNode->data = k;
    newNode->next = NULL;

    if(*list==NULL)
    {
        *list = newNode;
    }
    else
    {
        current = *list;
        previous = NULL;

        while((current!=NULL) && current->data.earnings<k.earnings){
            previous = current;
            current = current->next;
        }
        if(current == NULL)
            previous->next = newNode;
        else
        {
            if(previous == NULL)
            {
                newNode->next = (*list);
                *list = newNode;
            }
            else
            {
                previous->next = newNode;
                newNode->next = current;
            }
        }
    }
}

void Print(struct Node** list){
    if((*list)==NULL){
       printf("List is empty.");
       return;
    }
    printf("\nList looks like this:\n");
    while(*list!=NULL){
        printf("%d\n",(*list)->data.id);
        printf("%s\n",(*list)->data.name);
        printf("%f\n",(*list)->data.earnings);
        *list = (*list)->next;
    }
    printf("\n");
}


int Contains(struct Node** l1, struct Node** l2){
    while((*l2)!=NULL)
    {
        while((*l1)!=NULL)
        {
            if((*l1)->data.id==(*l2)->data.id && (*l1)->data.name==(*l2)->data.name)
                return 1;

            *l1 = (*l1)->next;
        }
        *l2 = (*l2)->next;
    }
    return 0;
}

int main()
{
    struct Book book = {5,"War and peace",100.50};
    struct Node** n = NULL;
    struct Book book1 = {6,"Anna Karenina",20.5};
    struct Book book2 = {7,"Master and Margarita", 150.60};
    struct Node** n1 = NULL;
    struct Book book3 = {6,"Anna Karenina",20.5};


    Insert(&n,book);
    Insert(&n,book1);
    Insert(&n,book2);
    Print(&n);
    Insert(&n1,book3);

    printf("\nDoes list2 contains list1? YES - 1, NO - 0 : %d",Contains(&n1,&n));

    return 0;
}

Answer 1

将 struct Node** n = NULL; 替换为 struct Node* n = NULL; 并对 n1

执行相同的操作

您目前正在做的事情实际上通过了 struct Node*** list，这就是您收到警告的原因

对于 Contains 的问题，首先比较字符串使用 strcmp 你所做的只是检查指针，在 l1 上的第一个循环之后的第二个你最终得到 l1==NULL 所以它不会在第一次

之后进入 while

int Contains(struct Node** l1, struct Node** l2)
{
    struct Node* tmp;

    while ((*l2) != NULL)
    {
        tmp = *l1;
        while (tmp != NULL)
        {
            if(tmp->data.id==(*l2)->data.id &&
                strcmp(tmp->data.name, (*l2)->data.name) == 0)
            {
                return 1;
            }

            tmp = tmp->next;
        }
        *l2 = (*l2)->next;
    }
    return 0;
}

Answer 2

您将 n 的地址传递给 Insert。 n 是指向节点指针的指针，struct Node **，所以 &n 是指向节点指针的指针，struct Node ***.

解决方案是使 n 和 n1 指向节点的指针：

struct Node* n = NULL;

Insert(&n, book);

插入代码的逻辑是n是一个链表的头部。当 n 为 NULL 时，列表为空。插入节点时，必须能够更新头指针，以便main中n的值发生变化。一种方法是将指针传递给头部并通过取消引用指针更新它。

您的 Contains 和 Print 函数不会更改列表，因此将指针传递给节点就足够了。这也将使您的代码看起来更简单，因为您不需要到处都使用 (*p) 语法。

contains 函数有两个错误：首先，不能将 C 字符串与 == 进行比较。 C 字符串是 char 数组；如果你想比较它们，你必须比较它们的内容。 <strings.h> 中的标准函数 strcmp 执行此操作。

其次，您有一个包含两个链表遍历的嵌套循环。外层循环可以使用原来的节点变量，但是内层循环必须使用额外的节点指针，并在遍历链表前重新设置。

也不清楚"contains"是什么意思。在当前（预期）实现中，这意味着：两个列表中是否有共同的书籍？一个更有用的函数会问这个问题：列表中有某本书吗？

这是 Contains

的修改变体

int Contains(struct Node *l1, struct Node *l2)
{
    while (l2 != NULL) {
        struct Node *p = l1;

        while (p != NULL) {
            if (p->data.id == l2->data.id 
            && strcmp(p->data.name, l2->data.name) == 0)
                return 1;

            p = p->next;
        }

        l2 = l2->next;
    }

    return 0;
}

你可以这样调用：

int c = Contains(n1, n);

Answer 3

请学习以下内容。主要思想是我们更好地利用函数，而不是将指针到指针的引用传递给列表；我们的 Insert 函数 returns 新列表。我们还利用了递归。

#include <stdio.h>
#include "stdlib.h"

typedef struct Book {
    int id;
    char name[50];
    float earnings;
} Book;

typedef struct Node{
    Book data;
    struct Node* next;
} Node, *List;

#define Empty ((List) NULL)

List NewNode(struct Book data, List next)
{
    List newNode = (Node *) malloc(sizeof *newNode);
    newNode->data = data;
    newNode->next = next;
    return newNode;
}

List Insert(List list, struct Book book)
{
    if (list == Empty) {
        return NewNode(book, Empty);
    } else if (list->data.earnings < book.earnings) {
        return NewNode(book, list);
    } else {
        /* Rewrite the rest of the list by inserting into it,
           then patch the front node to point to the rewritten list. */
        List subList = Insert(list->next, book);
        list->next = subList;
        return list;
    }
}

void PrintOne(List list)
{
    printf("%d\n", list->data.id);
    printf("%s\n", list->data.name);
    printf("%f\n" ,list->data.earnings);
}

void Print(List list)
{
    if (list == Empty) {
       puts("List is empty.");
    } else {
        puts("List looks like this:");
        for (; list != Empty; list = list->next)
            PrintOne(list);
    }
}

int IsTailOf(List leftList, List rightList)
{
    if (leftList == rightList)
        return 1; /* Every list is its own tail */
    else if (rightList == Empty)
        return 1; /* The empty list is the tail of all lists, incl. itself */
    else if (leftList == Empty)
        return 0; /* Nonempty right cannot be tail of empty left */
    else
        return IsTailOf(leftList->next, rightList); /* Tail of my rest is my tail */
}


int main()
{
    Book book0 = {5,"War and peace",100.50};
    Book book1 = {6,"Anna Karenina",20.5};
    Book book2 = {7,"Master and Margarita", 150.60};
    Book book3 = {6,"Anna Karenina",20.5};

    List n0, n1, n2;

    List list = Empty;

    n0 = list = Insert(list, book0);
    list = Insert(list, book1);
    n1 = list = Insert(list, book2);
    Print(n0);
    n1 = list = Insert(list, book3);

    printf("List pointers: list == %p, n0 == %p, n1 == %p, n2 == %p\n",
           (void *) list, (void *) n0, (void *) n1, (void *) n2);

    printf("Does list contain n0? YES - 1, NO - 0 : %d\n",
           IsTailOf(list, n0));

    printf("Does n1 contain list? YES - 1, NO - 0 : %d\n",
           IsTailOf(n1, list));

    printf("Does n0 contain list? YES - 1, NO - 0 : %d\n",
           IsTailOf(n0, list));

    return 0;
}

子列表函数 IsTailOf 严格使用节点指针，基于对 "sublist" 含义的可能解释。它检测右列表在物理上是否是左列表的一部分（或整个列表）。

如果你想计算一个给定的列表是否有一个尾部与另一个列表相同，那是不同的。一种导致易于编写（和阅读）代码的简单方法是首先实现一个比较两个列表的等价性测试函数。那么这个测试可以反复尝试：

#include <string.h> /* for strcmp */

int EqualBooks(Book left, Book right)
{
    return left.id == right.id && strcmp(left.name, right.name) == 0;
}

int EqualLists(List left, List right)
{
    /* Different style here from IsTailOf, just for variety:
       no "if else", just "if and return" */

    if (left == right)
        return 1; /* They are the same object! */

    if (left == Empty || right == Empty)
        return 0; /* Empty is not equal to nonempty */

    if (!EqualBooks(left->data, right->data))
        return 0; /* Equal lists must be equal in the first item */

    /* Equal lists must have equal remainders, not only first items */
    return EqualLists(left->next, right->next);
}

一个简单实现的子列表测试（我们称之为 "suffix" 测试）看起来像：

int IsSuffixOf(List left, List right)
{
    if (EqualLists(left, right))
        return 1; /* a full match implies suffix relationship */

    if (left == Empty)
        return 0; /* Nonempty cannot be a suffix of empty */

    return IsSuffixOf(left->next, right);
}

平凡的尾递归很容易变成迭代。让我们以 IsSuffixOf 为例。首先，通过对 left 和 right 变量的赋值重新替换尾部调用，并向后添加 goto:

int IsSuffixOf(List left, List right)
{
tail:
    if (EqualLists(left, right))
        return 1; /* a full match implies suffix relationship */

    if (left == Empty)
        return 0; /* Nonempty cannot be a suffix of empty */

    left = left->next;
    goto tail;
}

现在是迭代；我们只是通过重写 for 循环来消除 goto：

int IsSuffixOf(List left, List right)
{
    for (;; left = left->next) {
        if (EqualLists(left, right))
            return 1; /* a full match implies suffix relationship */

        if (left == Empty)
            return 0; /* Nonempty cannot be a suffix of empty */
     }
}

列表结构 - 检查子列表

List structure - checking for sublist

c

pointers

sublist