c - 链表元素在第 n 个位置插入

Question

我正在尝试在 C 中实现链表，并且我有两个不同的函数，它们应该在开头和第 n 个位置插入元素。当我的程序转到开始执行要在第 n 个位置插入的函数的部分时，它崩溃了。有人可以指出我的错误吗？此外，编译器往往会跳过最后一个 scanf 语句(在注释中标记)。

/****************************************************************
*Date: 12/30/2016
*This program adds an element to the beginning  and nth position
*of a linked list and then displays the elements in the list
*****************************************************************/


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



struct node
{
    int data;//Refers to the data part of the linked list
    struct node* next;//Refers to the pointer which points to the next element
};


/*************************************************************************************
Description   : This function is used to print the elements in the linked list
Input         : Pointer to the beginning of the linked list
Output        : N/A
*************************************************************************************/


void PrintElements(struct node *start)
{
    if(start==NULL)//If the list is empty
        printf("List is empty");
    else
    {
        while(start!=NULL)
        {
            printf("%d ",start->data);
            start=start->next;
        }
    }
}

/*************************************************************************************
Description   : This function is used to insert elements in the beginning of the
                linked list
Input         : Element to be inserted
Output        : N/A
*************************************************************************************/

struct node* InsertElementInTheBeginning(struct node *start, int x)
{
    struct node *new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node==NULL)
    {
        printf("Memory allocation failed");
        return start;
    }
    new_node->data=x;
    new_node->next=start;
    start=new_node;
    return new_node;

}

/*************************************************************************************
Description   : This function is used to insert elements in the nth position of the
                linked list
Input         : Element and position to be inserted, pointer to beginning of linked
                list
Output        : N/A
*************************************************************************************/

struct node* InsertElementAtN(struct node *start,int x, int n)//Here the starting position for the linked list is assumed to be 1
{
    int i;
    struct node* new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node==NULL)
    {
        printf("Memory allocation failed");
        return start;
    }
    new_node->data=x;
    new_node->next=NULL;
    if(n==1)
    {
        new_node->next=start;
        start=new_node;
        return start;
    }
    struct node *ptr;
    ptr=start;
    for(i=0;i<n-2;i++)
    {
        ptr=ptr->next;
    }

    new_node->next=ptr->next;
    ptr->next=new_node;
    return start;
}

int main()
{

    int x, n;
    struct node *HEAD;
    struct node *ptr;
    HEAD=NULL; //Assigning HEAD to null when there are no elements in the list
    ptr=NULL;
    printf("\n\rEnter numbers to be inserted into the list\n Press q to quit\n");
    while(scanf("%d",&x)==1)
    {
        HEAD=InsertElementInTheBeginning(HEAD,x);
        PrintElements(HEAD);
        printf("\n\rEnter numbers to be inserted into the list\n Press q to quit\n");
    }
        printf("\n\rEnter the number and position to be inserted");
        scanf("%d %d",&x,&n);//The compiler always skips this scanf no clue why
        HEAD=InsertElementAtN(HEAD, x, n);
        PrintElements(HEAD);

     //Freeing dynamic memory

    while(HEAD!=NULL)
    {
        ptr=HEAD;
        HEAD=ptr->next;
        free(ptr);

    }

    return 0;
}

Answer 1

我总是发现这样的东西对我来说更容易理解(我假设你的位置必须根据你的代码为 1 或更多，这与通常的 C 约定 0 或更多不同):

struct node *insertValueAt(struct node *head, int value, int position) {
    struct node *current;

    if (head == NULL || position == 1)
         return insertBefore(head, value);

    for (current = head; position > 1 && current->next != NULL; position--)
        current = current->next;

    current->next = insertBefore(current->next, value);

    return head;
}

请注意，我使用了名称 insertBefore，但您的 InsertElementAtTheBeginning 执行了相同的操作。在现有节点 A 和 B 之间插入节点 N 的关键是使 A->next 点到从 InsertElementAtTheBeginning(B, value) 返回的 N。

另一件事需要注意的是在 NULL 节点之前无条件插入(即在空列表的开头或列表的末尾)，无论 position< 的值如何 因为如果项目少于 4 个，则无法在位置 10 处插入项目。