单向链表 - deleting/adding 位置 x 处的项目
Singly linked list - deleting/adding item at position x
这是关于单链表的。我有以下代码。我现在想扩展这些代码，以便可以 add/delete 某个特定位置的元素。我不知道如何着手实施它。
这是我目前所拥有的：
#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
向列表中插入元素的功能还可以，但我有一些建议：
- 不要将变量命名为与关键字相同的名称（例如 new）。这会让其他人很困惑，我不确定是否所有编译器都允许这样做...
- 在纯 C 中，您需要编写例如
struct list* L 而不是 list* L （或者你添加一个类型定义，例如 typedef struct list LIST; 允许你写 LIST *L 而不是 struct list* L）。
- 在使用指针之前始终确保它们不为 NULL。
- 为您的函数添加 return 值，以便调用者可以区分成功与失败。
我写了以下函数：
void initList(struct list* L)
{
if (L)
{
L->amount = 0;
L->first = NULL;
}
}
int insertInList(struct list* L, struct element* position, struct element* newElem)
{
int result = 0;
struct element *iterator;
if (L)
{
/* Check if newElem is already within list and if so don't add it again! */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iterator == newElem)
{
break;
}
}
if (iterator != newElem) /* newElem not within list, yet? */
{
if (position != 0)
{
newElem->next = position->next;
position->next = newElem;
}
else
{
newElem->next = L->first;
L->first= newElem;
}
L->amount++;
result = 1;
}
}
return (result);
}
int deleteFromList(struct list* L, struct element* elem)
{
int result = 0;
struct element *iterator;
if ((L) && (L->amount > 0)) /* list with elements in it? */
{
if (L->first != elem) /* elem is not the first element? */
{
/* iterator all items to find entry preceeding elem */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iterator->next == elem)
{
iterator->next = elem->next; /* set next element to elemen after elem */
result = 1;
break;
}
}
}
else
{
L->first = elem->next; /* set new head of list */
result = 1;
}
if (result == 1) /* item deleted? */
{
L->amount--;
elem->next = NULL; /* ensure next pointer of elem does not point into list! */
}
}
return (result);
}
int deleteIndexFromList(struct list* L, int iElement) /* iElement is zero based: 0=first element, 1=second element, ... */
{
int result = 0;
struct element *iterator;
if ((L) && (L->amount >= iElement))
{
/* iterator all items to find entry preceeding elem */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iElement == 0)
{
result = deleteFromList(L, iterator);
break;
}
iElement--;
}
}
return (result);
}
您可以使用调试器和以下测试程序测试代码：
int main(void)
{
struct list L;
struct element A, B, C, D;
A.number = 5;
B.number = 10;
C.number = 15;
D.number = 20;
initList(&L);
insertInList(&L, NULL, &A);
insertInList(&L, &A, &B);
insertInList(&L, &B, &C);
insertInList(&L, &C, &D);
/* now your list is 5 -> 10 -> 15 -> 20 */
deleteFromList(&L, &A);
/* now your list is 10 -> 15 -> 20 */
deleteFromList(&L, &C);
/* now your list is 10 -> 20 */
return (0);
}
要在 "entry N" 之后添加条目，您只需搜索 "entry N"。然后你会做 new_entry->next = current_entry->next; current_entry->next = new_entry;.
在"entry N"之前添加一个条目，删除"entry N"，您需要在搜索时跟踪前一个条目的地址；这样当您找到 "entry N" 时，您仍然知道前一个条目的地址。
在这种情况下，删除 "entry N" 主要变成 previous_entry->next = current_entry->next;；并在 "entry N" 变为 new_entry->next = previous_entry->next; previous_entry->next = new_entry; 之前插入一个新条目。但是，对于这两种情况，对于 "N == 0"，先前的条目可能不存在。在这种情况下，您必须修改列表的头部而不是条目。
举个例子（删除，其中something是你的结构类型的名字）：
int deleteEntry(int n, something **headPtr) {
something *previous = NULL;
something *current = *headPtr;
while( (current != NULL) && (n > 0) ) {
previous = current;
current = current->next;
n--;
}
if(current == NULL) {
return ERROR; // End of list reached before N found
}
if(previous == NULL) {
*headPtr = current->next;
} else {
previous->next = current->next;
}
free(current);
return OK;
}
注意：完全有可能提前处理 n == 0 情况（在 while 循环之前）。我这样写是为了很容易修改搜索条件并将其转换为删除满足其他条件的第一个条目的内容。
让我们从单链非循环列表的 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++;
}
上面你只是为下一个元素分配了存储空间（我一直保留着它们nodes）。您只需检查金额（重命名为 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，那么在持有 5 和 7 的那些之间插入新的 ptr。 注意：下面的这个函数还处理放置第一个节点和小于列表中第一个节点的节点，以及将节点放置在列表的末尾。它基本上是在查找给定新节点的去向时完成所有工作。如果您的目标是按排序顺序插入节点，则可以将其用作唯一的输入例程，或者您可以仅使用它来填充特殊情况。
/* 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;
}
}
Use/Output
$ ./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)
这是关于单链表的。我有以下代码。我现在想扩展这些代码，以便可以 add/delete 某个特定位置的元素。我不知道如何着手实施它。
这是我目前所拥有的：
#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);
向列表中插入元素的功能还可以，但我有一些建议：
- 不要将变量命名为与关键字相同的名称（例如 new）。这会让其他人很困惑，我不确定是否所有编译器都允许这样做...
- 在纯 C 中，您需要编写例如
struct list* L而不是list* L（或者你添加一个类型定义，例如typedef struct list LIST;允许你写 LIST *L 而不是struct list* L）。 - 在使用指针之前始终确保它们不为 NULL。
- 为您的函数添加 return 值，以便调用者可以区分成功与失败。
我写了以下函数：
void initList(struct list* L)
{
if (L)
{
L->amount = 0;
L->first = NULL;
}
}
int insertInList(struct list* L, struct element* position, struct element* newElem)
{
int result = 0;
struct element *iterator;
if (L)
{
/* Check if newElem is already within list and if so don't add it again! */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iterator == newElem)
{
break;
}
}
if (iterator != newElem) /* newElem not within list, yet? */
{
if (position != 0)
{
newElem->next = position->next;
position->next = newElem;
}
else
{
newElem->next = L->first;
L->first= newElem;
}
L->amount++;
result = 1;
}
}
return (result);
}
int deleteFromList(struct list* L, struct element* elem)
{
int result = 0;
struct element *iterator;
if ((L) && (L->amount > 0)) /* list with elements in it? */
{
if (L->first != elem) /* elem is not the first element? */
{
/* iterator all items to find entry preceeding elem */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iterator->next == elem)
{
iterator->next = elem->next; /* set next element to elemen after elem */
result = 1;
break;
}
}
}
else
{
L->first = elem->next; /* set new head of list */
result = 1;
}
if (result == 1) /* item deleted? */
{
L->amount--;
elem->next = NULL; /* ensure next pointer of elem does not point into list! */
}
}
return (result);
}
int deleteIndexFromList(struct list* L, int iElement) /* iElement is zero based: 0=first element, 1=second element, ... */
{
int result = 0;
struct element *iterator;
if ((L) && (L->amount >= iElement))
{
/* iterator all items to find entry preceeding elem */
for (iterator = L->first; iterator != NULL; iterator = iterator->next)
{
if (iElement == 0)
{
result = deleteFromList(L, iterator);
break;
}
iElement--;
}
}
return (result);
}
您可以使用调试器和以下测试程序测试代码：
int main(void)
{
struct list L;
struct element A, B, C, D;
A.number = 5;
B.number = 10;
C.number = 15;
D.number = 20;
initList(&L);
insertInList(&L, NULL, &A);
insertInList(&L, &A, &B);
insertInList(&L, &B, &C);
insertInList(&L, &C, &D);
/* now your list is 5 -> 10 -> 15 -> 20 */
deleteFromList(&L, &A);
/* now your list is 10 -> 15 -> 20 */
deleteFromList(&L, &C);
/* now your list is 10 -> 20 */
return (0);
}
要在 "entry N" 之后添加条目，您只需搜索 "entry N"。然后你会做 new_entry->next = current_entry->next; current_entry->next = new_entry;.
在"entry N"之前添加一个条目，删除"entry N"，您需要在搜索时跟踪前一个条目的地址；这样当您找到 "entry N" 时，您仍然知道前一个条目的地址。
在这种情况下，删除 "entry N" 主要变成 previous_entry->next = current_entry->next;；并在 "entry N" 变为 new_entry->next = previous_entry->next; previous_entry->next = new_entry; 之前插入一个新条目。但是，对于这两种情况，对于 "N == 0"，先前的条目可能不存在。在这种情况下，您必须修改列表的头部而不是条目。
举个例子（删除，其中something是你的结构类型的名字）：
int deleteEntry(int n, something **headPtr) {
something *previous = NULL;
something *current = *headPtr;
while( (current != NULL) && (n > 0) ) {
previous = current;
current = current->next;
n--;
}
if(current == NULL) {
return ERROR; // End of list reached before N found
}
if(previous == NULL) {
*headPtr = current->next;
} else {
previous->next = current->next;
}
free(current);
return OK;
}
注意：完全有可能提前处理 n == 0 情况（在 while 循环之前）。我这样写是为了很容易修改搜索条件并将其转换为删除满足其他条件的第一个条目的内容。
让我们从单链非循环列表的 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++;
}
上面你只是为下一个元素分配了存储空间（我一直保留着它们nodes）。您只需检查金额（重命名为 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，那么在持有 5 和 7 的那些之间插入新的 ptr。 注意：下面的这个函数还处理放置第一个节点和小于列表中第一个节点的节点，以及将节点放置在列表的末尾。它基本上是在查找给定新节点的去向时完成所有工作。如果您的目标是按排序顺序插入节点，则可以将其用作唯一的输入例程，或者您可以仅使用它来填充特殊情况。
/* 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;
}
}
Use/Output
$ ./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)