c - 单链表 - 删除/添加位置 x 处的项目

Question

这是关于单链表的。我有以下代码。我现在想扩展这些代码，以便可以在某个特定位置添加/删除元素。我不知道如何去实现它。

这是我迄今为止所拥有的:

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

struct list
{
    int amount;
    struct element *first;
};

struct element
{
    int number;
    struct element *next;
    int *temp;
};

int main()
{
    struct list lk;
    struct element *ptr, *temp;
    int amount;
    int i;

    printf("How much elements u want enter?");              
    scanf("%d", &amount);

    ptr = (struct element *) calloc(1, sizeof(struct element));   
    lk.first = ptr;                    
    lk.amount = 0;                      
    printf("Please enter 1. number :");
    scanf("%d", &(ptr->number));                
    temp = ptr;                 

    for (i = 2; i <= amount; i++)
    {
        printf("Please enter %d. number", i);
        ptr = (struct element *) calloc(1, sizeof(struct element));
        lk.amount++;                
        scanf("%d", &(ptr->number));
        ptr->next = NULL;           
        temp->next = ptr;           

        temp = ptr;
    }

    ptr = lk.first;

    while (ptr != NULL)
    {
        printf("%d \n", ptr->number);
        ptr = ptr->next;

    }

    getch();
    return 0;
}

我找到了以下方法，但我不知道如何针对我的程序调整它:

void insertInList (list* L, element* position, element* new)
{   
    if (position == 0)
    {
        new->next = L->first;
        L->first= new;
        L->amount++;
    }
    else
    { 
       new->next = position->next;
       position->next = new;
       L->amount++;
    }
}

我在用户输入后对此进行了测试:

struct list lk;
struct element *ptr, *temp, number1, number2;
int amount;
int i;

printf("Which element u want add:");
scanf("%d", number1.number);


printf("On which position u want add the element?:");
scanf("%d", number2.number);

initList(&lk);
insertInList(&lk, &zahl2, &zahl1);

在 > scanf("%d", number1.number); 行之后，我收到 AccessViolentException；

Answer 1

让我们从单链接非循环列表的 2 个特殊情况开始。第一种是添加数据的通用方法，就是继续将节点添加到列表的末尾。那里的函数可能看起来像:

/* insert node at end of list */
void insert_end (list *l, int n)
{
    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    if (l->cnt == 0) 
    {
        l->first = ptr;
        l->cnt++;
        return;
    }

    lnode *iter = l->first;  /* pointer to iterate list */

    while (iter->next) iter = iter->next;
    iter->next = ptr;
    l->cnt++;
}

上面您只需为下一个元素分配存储(我将它们保留为节点)。您只需检查金额(重命名为 cnt )是否为 0 。如果是，则添加为第一个节点。如果没有，则创建一个指向列表的指针以用作迭代器并迭代列表指针，直到 node->next是 NULL并在末尾添加新节点。

(注意:如果插入效率很重要，双链循环链表不需要迭代，只需在 list->prev 位置添加一个节点即可，即即使在具有数亿个节点的列表中也可以盲目地快速添加)

下一个变体是想要在列表的开头或开头添加一个新节点。在这里你只需做 ptr->next = l->first然后l->first = ptr :

/* insert node at beginning of list */
void insert_start (list *l, int n)
{
    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;

    if (l->cnt == 0) 
        ptr->next = NULL;
    else
        ptr->next = l->first;

    l->first = ptr;
    l->cnt++;
}

在列表中的给定位置插入一个节点怎么样？您需要验证位置 (0 <= pos <= lk->cnt) (或者您可以将任何大于 lk->cnt 的值设置为等于 lk->cnt )。您已经了解了如何使用列表指针迭代 iter = lter->next 来迭代节点以到达列表末尾。直到到达最后一个节点。前往nth节点没有什么不同。要在给定位置插入，您将获得该位置，因此只需迭代 pos 即可。到达插入点的次数:

/* insert node at position */
void insert_pos (list *l, int n, int pos)
{
    /* validate position */
    if (pos < 0 || pos > l->cnt) {
        fprintf (stderr, "%s() error: invalid position.\n", __func__);
        return;
    }

    /* if empty or pos 0, insert_start */
    if (l->cnt == 0 || pos == 0) {
        insert_start (l, n);
        return;
    }

    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    lnode *iter = l->first;  /* pointer to iterate list */

    while (--pos)
        iter = iter->next;

    if (iter->next)
        ptr->next = iter->next;

    iter->next = ptr;
    l->cnt++;
}

下一个变体是按数字排序顺序在列表中的任意位置添加节点。若新ptr->number = 6;你已经有了5和7 ，然后插入新的 ptr持有 5 的人之间和7 。 注意:下面的这个函数还处理放置第一个节点、小于列表中第一个节点的节点，以及将节点放置在列表末尾。它基本上就是找到给定的新节点将去往的位置。如果您的目标是按排序顺序插入节点，则可以使用它作为唯一的输入例程，或者您可以使用它来填充特殊情况。

/* insert node at end of list */
void insert_ordered (list *l, int n)
{
    /* if first node of n < first->number */
    if (l->cnt == 0 || n < l->first->number) {
        insert_start (l, n);
        return;
    }

    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    lnode *iter = l->first;  /* pointer to iterate list */

    while (iter->next && n > iter->next->number) {
        iter = iter->next;
    }

    if (iter->next)
        ptr->next = iter->next;

    iter->next = ptr;
    l->cnt++;
}

只要我们扩展您的列表，您就应该保留 main功能干净，功能为 print为您和 free 提供的列表完成后分配给列表的所有内存。可以完成此任务的几个辅助函数可能是:

void prn_list (list l)
{
    lnode *ptr = l.first;
    int i = 0;
    while (ptr)
    {
        printf("   node[%2d] : %d\n", i++, ptr->number);
        ptr = ptr->next;
    }
}

void free_list (list l)
{
    lnode *ptr = l.first;

    while (ptr)
    {
        lnode *del = ptr;
        ptr = ptr->next;
        free (del);
        del = NULL;
    }
}

以类似的方式删除作品。将它们放在一起，您将得到一个具有输入特征的半鲁棒列表。请注意struct也有过typedefs创建减少打字并提高可读性。

#include <stdio.h>
#include <stdlib.h>
// #include <conio.h>

typedef struct lnode
{
    int number;
    struct lnode *next;
} lnode;

typedef struct
{
    int cnt;
    lnode *first;
} list;

void insert_end (list *l, int n);
void insert_start (list *l, int n);
void insert_ordered (list *l, int n);
void insert_pos (list *l, int n, int pos);
void prn_list (list l);
void free_list (list l);

int main (void)
{
    list lk = { 0, NULL };

    int num = 0;
    int i = 0;

    printf ("\n number of nodes to enter: ");              
    scanf ("%d", &num);

    for (i = 0; i < num; i++)
    {
        int n = 0;
        printf (" enter node[%d]->number: ", i);
        scanf("%d", &n);
        insert_end (&lk, n);
    }

    printf ("\n The list contains '%d' nodes.\n", lk.cnt);
    printf ("\n The list nodes are:\n\n");
    prn_list (lk);

    printf ("\n enter number to add at start: ");              
    scanf("%d", &num);
    insert_start (&lk, num);

    printf ("\n The list contains '%d' nodes.\n", lk.cnt);
    printf ("\n The list nodes are:\n\n");
    prn_list (lk);

    printf ("\n enter number to add in order: ");              
    scanf("%d", &num);
    insert_ordered (&lk, num);

    printf ("\n The list contains '%d' nodes.\n", lk.cnt);
    printf ("\n The list nodes are:\n\n");
    prn_list (lk);

    printf ("\n enter number to add at position: ");              
    scanf("%d", &num);
    printf ("\n position must be (0 <= pos <= %d)\n", lk.cnt);
    printf ("\n enter position in list for '%d': ", num);
    scanf("%d", &i);
    insert_pos (&lk, num, i);

    printf ("\n The list contains '%d' nodes.\n", lk.cnt);
    printf ("\n The list nodes are:\n\n");
    prn_list (lk);

    printf ("\n Freeing list memory:\n\n");
    free_list (lk);

    //getch();
    return 0;
}

/* insert node at end of list */
void insert_end (list *l, int n)
{
    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    if (l->cnt == 0) 
    {
        l->first = ptr;
        l->cnt++;
        return;
    }

    lnode *iter = l->first;  /* pointer to iterate list */

    while (iter->next) iter = iter->next;
    iter->next = ptr;
    l->cnt++;
}

/* insert node at beginning of list */
void insert_start (list *l, int n)
{
    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;

    if (l->cnt == 0) 
        ptr->next = NULL;
    else
        ptr->next = l->first;

    l->first = ptr;
    l->cnt++;
}

/* insert node at end of list */
void insert_ordered (list *l, int n)
{
    /* if first node of n < first->number */
    if (l->cnt == 0 || n < l->first->number) {
        insert_start (l, n);
        return;
    }

    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    lnode *iter = l->first;  /* pointer to iterate list */

    while (iter->next && n > iter->next->number)
        iter = iter->next;

    if (iter->next)
        ptr->next = iter->next;

    iter->next = ptr;
    l->cnt++;
}

/* insert node at position */
void insert_pos (list *l, int n, int pos)
{
    /* validate position */
    if (pos < 0 || pos > l->cnt) {
        fprintf (stderr, "%s() error: invalid position.\n", __func__);
        return;
    }

    /* if pos 0, insert_start */
    if (l->cnt == 0 || pos == 0) {
        insert_start (l, n);
        return;
    }

    struct lnode *ptr = NULL;
    if (!(ptr = calloc (1, sizeof *ptr))) {
        fprintf (stderr, "%s() error: memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    ptr->number = n;
    ptr->next = NULL;

    lnode *iter = l->first;  /* pointer to iterate list */

    while (--pos)
        iter = iter->next;

    if (iter->next)
        ptr->next = iter->next;

    iter->next = ptr;
    l->cnt++;
}

/* print all nodes in list */
void prn_list (list l)
{
    lnode *ptr = l.first;
    int i = 0;
    while (ptr)
    {
        printf("   node[%2d] : %d\n", i++, ptr->number);
        ptr = ptr->next;
    }
}

/* free memory for all nodes */
void free_list (list l)
{
    lnode *ptr = l.first;

    while (ptr)
    {
        lnode *del = ptr;
        ptr = ptr->next;
        free (del);
        del = NULL;
    }
}

使用/输出

$ ./bin/ll_single_ins

 number of nodes to enter: 3
 enter node[0]->number: 5
 enter node[1]->number: 7
 enter node[2]->number: 9

 The list contains '3' nodes.

 The list nodes are:

   node[ 0] : 5
   node[ 1] : 7
   node[ 2] : 9

 enter number to add at start: 2

 The list contains '4' nodes.

 The list nodes are:

   node[ 0] : 2
   node[ 1] : 5
   node[ 2] : 7
   node[ 3] : 9

 enter number to add in order: 6

 The list contains '5' nodes.

 The list nodes are:

   node[ 0] : 2
   node[ 1] : 5
   node[ 2] : 6
   node[ 3] : 7
   node[ 4] : 9

 enter number to add at position: 4

 position must be (0 <= pos <= 5)

 enter position in list for '4': 4

 The list contains '6' nodes.

 The list nodes are:

   node[ 0] : 2
   node[ 1] : 5
   node[ 2] : 6
   node[ 3] : 7
   node[ 4] : 4
   node[ 5] : 9

 Freeing list memory:

valgrind 内存错误检查

$ valgrind ./bin/ll_single_ins
==22898== Memcheck, a memory error detector
==22898== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==22898== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==22898== Command: ./bin/ll_single_ins
==22898==

number of nodes to enter: 3
enter node[0]->number: 5
enter node[1]->number: 7
enter node[2]->number: 9

The list contains '3' nodes.
<snip>

==22519== HEAP SUMMARY:
==22519==     in use at exit: 0 bytes in 0 blocks
==22519==   total heap usage: 5 allocs, 5 frees, 80 bytes allocated
==22519==
==22519== All heap blocks were freed -- no leaks are possible
==22519==
==22519== For counts of detected and suppressed errors, rerun with: -v
==22519== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)