为什么我不能在 C 中使用连续实现将元素插入到列表中？

Question

我确实在 C 中实现了一个列表，如下所示。问题是当我尝试使用 InsertList() 函数插入元素时它 returns “ 尝试插入到不在列表 中的位置”消息。但相反，我希望列表将元素插入到上述位置。要实现它，我应该如何修改我的代码？

#include <stdlib.h>
#define MAX 20
#define EMPTY 0
#define FULL MAX-1

typedef enum {FALSE, TRUE} Boolean;
typedef char ListEntry;
typedef int Position;
typedef struct list
{
    int count;
    ListEntry entry[MAX];
}List;

void CreateList(List *l)
{
    l->count=EMPTY;
}

Boolean IsListEmpty(List *l)
{
    return (l->count==EMPTY);
}

Boolean IsListFull(List *l)
{
    return (l->count==FULL);
}

int ListSize(List *l)
{
    return (l->count);
}

void InsertLast(ListEntry x,List *l)
{
    if(IsListFull(l))
        printf("Try to insert to full list\n");
    else
    {
        l->entry[l->count]=x;
        l->count++;
        printf("The entered element at last is %d\n", x);
    }
}

void InsertList(Position p,ListEntry x,List *l)
{
    if(IsListFull(l))
        printf("Try to insert to full list\n");
    else if(p<0 || p>ListSize(l))
        printf("Try to insert to a position not in list\n");
    else
    {
        int i;
        for(i=ListSize(l)-1;i>=p;i--)
            l->entry[i+1]=l->entry[i];
        l->entry[p-1]=x;
        printf("The entered element is: %d\n",x);
        l->count++;
    }
}

void ReplaceList(Position p,ListEntry x,List *l)
{
    if(IsListFull(l))
        printf("Try to replace to full list\n");
    else if(p<0 || p>ListSize(l))
        printf("Try to replace a position not in list\n");
    else
        l->entry[p-1]=x;
}

void DeleteList(Position p,List *l)
{
    int i;
    if(IsListEmpty(l))
        printf("Try to delete from a empty list\n");
    else if(p<0 || p>ListSize(l))
        printf("Try to delete a position not in list\n");
    else
    {
        ListEntry x=l->entry[p-1];
        for(i=p-1;i<ListSize(l);i++)
            l->entry[i]=l->entry[i+1];
        l->count--;
        printf("Deleted element is %d\n", x);
    }
}

void RetrieveList(Position p,List *l)
{
    if(IsListEmpty(l))
        printf("Try to retrieve from a empty list\n");
    else if(p<0 || p>ListSize(l))
        printf("Try to retrieve a position not in list\n");
    else{
        ListEntry x=l->entry[p-1];
    printf("Retrieved element is: %d\n", x);
    }
}
void Traverse(List *l)
{
    if(IsListEmpty(l))
        printf("Try to traverse a empty list\n");
    else
        printf("The elements of this list are: ");
    {
        for(int i=0;i<ListSize(l);i++)
        {
            printf("%d ", l->entry[i]);
        }
    }
}

我的main()函数如下：

{
    List l;
    CreateList(&l);
    Traverse(&l);
    DeleteList(2,&l);
    //InsertLast(5,&l);
    //InsertLast(6,&l);
    InsertList(1,3,&l);
    InsertList(2,2,&l);
    InsertList(3,1,&l);
    RetrieveList(1,&l);
    DeleteList(2,&l);
    int results = ListSize(&l);
    printf("The size of the list%d\n",results);
    Traverse(&l);

    return 0;
}

Answer 1

一开始。您的列表是空的。因此，ListSize returns 0。您尝试插入绝对位于列表边界之外的位置 1。尝试在位置 0 插入。这是有道理的，因为列表是空的，位置 0 没有设置。为什么要在位置1插入？

您的代码中还有一些错误。例如，当你插入时，你希望先移动内容，然后再设置新元素。您将其设置在索引 (p-1) 处。通过在位置 1 插入来遵循您的逻辑，它可能会起作用，但会造成混淆。如果你在某个位置插入东西，它应该正好插入那里。

您的代码可能如下所示

 void InsertList(Position p,ListEntry x,List *l)                                                                                                                                                                                                                                             
 {                                                                                                                                                                                                                                                                                               
     if(IsListFull(l))                                                                                                                                                                                                                                                                               
         printf("Try to insert to full list\n");                                                                                                                                                                                                                                                 
     else if(p<0 || p>ListSize(l))                                                                                                                                                                                                                                                                   
         printf("Try to insert to a position not in list\n");                                                                                                                                                                                                                                    
     else                                                                                                                                                                                                                                                                                        
     {                                                                                                                                                                                                                                                                                               
         int i;                                                                                                                                                                                                                                                                                      
         for(i=ListSize(l)-1;i>=p;i--)                                                                                                                                                                                                                                                                   
             l->entry[i+1]=l->entry[i];                                                                                                                                                                                                                                                              
         l->entry[p]=x;                                                                                                                                                                                                                                                                              
         printf("The entered element is: %d\n",x);                                                                                                                                                                                                                                                   
         l->count++;                                                                                                                                                                                                                                                                             
     }                                                                                                                                                                                                                                                                                       
}

我看到你有一个额外的功能 InsertLast 但是 InsertList 也可以成功附加一个元素。保留原样或禁止在插入函数中追加由您决定。

那么，调试愉快！

Answer 2

第一次插入时，列表中的元素计数为 0，因此 ListSize() 将 return 0。因此，条件 'if(p<0 || p>ListSize(l))' 无法满足。

void InsertList(Position p,ListEntry x,List *l)
    {
        if(IsListFull(l))
            printf("Try to insert to full list\n");
        else if(p<0 || p>ListSize(l)) // the condition is never satisfied
     ...

相反，尝试条件 if(p<0 || p>= MAX)。此外，您的 InsertList 函数中还有其他错误。尝试编写类似于以下代码的内容：

else if(p<0 || p>= MAX)
    printf("Try to insert to a position not in list\n");
else
{
    int i;
    for(i=MAX-2;i>=p;i--)  // important point
        l->entry[i+1]=l->entry[i];
    l->entry[p-1]=x;
    printf("The entered element is: %d\n",x);
    l->count++;
}

为什么我不能在 C 中使用连续实现将元素插入到列表中？

Why I couldn't insert elements into the list with contiguous implementation in C?

c

list

data-structures

contiguous