列表与另一个列表的交集时出现问题

Question

这个函数将第一个列表与第二个列表相交，它必须返回一个新列表， 我用过 elemtype.h 和 list.h，（当然还有 elemtype.c 和 list.c）

这是 elemtype.c:

#define _CRT_SECURE_NO_WARNINGS
#include "elemtype.h"

#include <string.h>
#include <stdlib.h>

#define _unused(x) ((void)(x))

int ElemCompare(const ElemType *e1, const ElemType *e2) {
    return (*e1 > *e2) - (*e1 < *e2);
}

ElemType ElemCopy(const ElemType *e) {
    return *e;
}

void ElemSwap(ElemType *e1, ElemType *e2) {
    ElemType tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

void ElemDelete(ElemType *e) {

    _unused(e);
}

int ElemRead(FILE *f, ElemType *e) {
    return fscanf(f, "%d", e);
}

int ElemReadStdin(ElemType *e) {
    return ElemRead(stdin, e);
}

void ElemWrite(const ElemType *e, FILE *f) {
    fprintf(f, "%d", *e);
}

void ElemWriteStdout(const ElemType *e) {
    ElemWrite(e, stdout);
}

这是 elemtype.h:

#ifndef ELEMTYPE_INT_H_
#define ELEMTYPE_INT_H_

#include <stdbool.h>
#include <stdio.h>

typedef int ElemType;


int ElemCompare(const ElemType *e1, const ElemType *e2);


ElemType ElemCopy(const ElemType *e);


void ElemSwap(ElemType *e1, ElemType *e2);


void ElemDelete(ElemType *e);


int ElemRead(FILE *f, ElemType *e);


int ElemReadStdin(ElemType *e);


void ElemWrite(const ElemType *e, FILE *f);


void ElemWriteStdout(const ElemType *e);

#endif // ELEMTYPE_INT_H_

这是 list.c:

#define _CRT_SECURE_NO_WARNINGS
#include "list.h"

#include <string.h>
#include <stdlib.h>

/*****************************************************************************/
/*                           Item & Primitives                               */
/*****************************************************************************/

Item *ListCreateEmpty(void) {
    return NULL;
}

Item *ListInsertHead(const ElemType *e, Item *i) {
    Item *n = malloc(sizeof(Item));
    n->value = ElemCopy(e);
    n->next = i;
    return n;
}

bool ListIsEmpty(const Item *i) {
    return i == NULL;
}

const ElemType *ListGetHeadValue(const Item *i) {
    if (ListIsEmpty(i)) {
        printf("ERROR: null list\n");
        exit(1);
    }
    else {
        return &i->value;
    }
}

Item *ListGetTail(const Item *i) {
    if (ListIsEmpty(i)) {
        printf("ERROR: null list \n");
        exit(2);
    }
    else {
        return i->next;
    }
}

Item *ListInsertBack(Item *i, const ElemType *e) {

    Item *n = ListInsertHead(e, ListCreateEmpty());

    if (ListIsEmpty(i)) {
        return n;
    }

    Item *tmp = i;
    while (!ListIsEmpty(ListGetTail(tmp))) {
        tmp = ListGetTail(tmp);
    }

    tmp->next = n;
    return i;
}

void ListDelete(Item *i) {
    while (!ListIsEmpty(i)) {
        Item *tmp = i;
        i = i->next;
        ElemDelete(&tmp->value);
        free(tmp);
    }
}

/*****************************************************************************/
/*                            Non Primitives                                 */
/*****************************************************************************/

void ListWrite(const Item *i, FILE *f) {
    fprintf(f, "[");
    while (!ListIsEmpty(i)) {
        ElemWrite(&i->value, f);
        i = ListGetTail(i);
        if (!ListIsEmpty(i)) {
            fprintf(f, ", ");
        }
    }
    fprintf(f, "]\n");
}

void ListWriteStdout(const Item *i) {
    ListWrite(i, stdout);
}

这是 list.h:

#ifndef LIST_H_
#define LIST_H_

#include "elemtype.h"

#include <stdbool.h>
#include <stdio.h>

/*****************************************************************************/
/*                           Item & Primitives                               */
/*****************************************************************************/


struct Item {
    ElemType value; 
    struct Item *next; 
};

typedef struct Item Item;


Item *ListCreateEmpty(void);
Item *ListInsertHead(const ElemType *e, Item *i);


bool ListIsEmpty(const Item *i);


const ElemType *ListGetHeadValue(const Item *i);


Item *ListGetTail(const Item *i);



Item *ListInsertBack(Item *i, const ElemType *e);


void ListDelete(Item *i);

/*****************************************************************************/
/*                             Non Primitives                                */
/*****************************************************************************/

void ListWrite(const Item *i, FILE *f);


void ListWriteStdout(const Item *i);

#endif // LIST_H_

这是我对 intersect.c 的实现：

#include "elemtype.h"
#include "list.h"

Item* Intersect(const Item* i1, const Item* i2) {
    Item* ris = ListCreateEmpty(); 
    for (; !ListIsEmpty(i1); i1 = ListGetTail(i1)) {
        for (const Item* tmp2 = i2; !ListIsEmpty(tmp2); tmp2 = ListGetTail(i2)) {
            if (ElemCompare(ListGetHeadValue(i1), ListGetHeadValue(tmp2))) {
                ris = ListInsertBack(ris, ListGetHeadValue(i1)); 
                break; 
            }
        }
    }
    return ris; 
}



   int main(void) {
    ElemType v1[] = { 0, 1, 2};
    Item* i1 = ListCreateEmpty();
    for (size_t i = 0; i < 3; i++) {
        i1 = ListInsertHead(v1 + i, i1);
    }
    ElemType v2[] = { 4, 0, 2 }; 
    Item* i2 = ListCreateEmpty(); 
    for (size_t i = 0; i < 3; i++) {
        i2 = ListInsertHead(v2 + i, i2); 
    }
    Item* i3 = Intersect(i1, i2); 
    ListDelete(i3); ListDelete(i1); 
    ListDelete(i2); 
    return 0; 
} 

这个解决方案工作正常，但它只返回第一个列表（即 i1），而不仅仅是公共值，即使它执行 elemcompare 并且它正确插入每个值。

（旁注：其他文件中有 2 个警告，但您可以忽略它们）

Answer 1

看来问题出在这个if语句

if (ElemCompare(ListGetHeadValue(i1), ListGetHeadValue(tmp2))) {

当两个元素彼此不相等时，if 语句的条件评估为逻辑真。

其实你需要写

if (ElemCompare(ListGetHeadValue(i1), ListGetHeadValue(tmp2)) == 0 ) {

注意该函数在任何情况下都是错误的，因为例如对于列表 { 0, 0 } 和 { 0, 1 }，值

0

将在新列表中插入两次，而它应该只插入一次.