指向链表中指针的指针
Pointer to pointer in linked list
谁能解释一下为什么这段代码给我的结果是空列表：
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
但是如果我用指向指针的指针更改 begin() 函数，它会给我正确的列表？
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
你也能解释一下为什么当我将节点头部传递给函数 begin 时，我必须将它作为“&head”传递吗？不再是“头”
因为 head 是（有效地）一个局部变量，所以改变它在函数之外没有影响，而改变 *head 会改变 head 指向的内容，因此.
如果您希望函数能够更改 int 变量中的值（例如，x），您可以向它传递一个指向 x 的指针，这将具有类型 int*，您将通过使用 &x 获得指向 x 的指针。无论 x 是什么类型，都一样。
在此代码段的第一个程序中
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
指针head按值传递给函数begin。这是在 main 中声明的指针 head 的值的副本被创建并分配给与函数 begin
同名的参数
void begin(node *head);
因此在函数内，最初保存原始指针 head 副本的参数 head 发生了变化。原始指针 head 其值分配给参数的值未更改。
要更改在 main 中声明的原始指针头，您必须通过指向指针头的指针通过引用间接将其传递给函数，就像在第二个程序中所做的那样。
所以函数应该这样声明
void begin(node **head);
而且你必须通过指向它的指针间接传递指针 head
begin( &head );
在这种情况下，取消引用传递的指针，函数将直接访问在 main 中声明的原始指针头并可以更改它（而不是其值的副本，因为它发生在第一个函数定义中）
new->next = *head;
*head = new;
为了更清楚地考虑这个简单的演示程序。
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
它的输出是
Before calling f t is equal to 0
After calling f t is equal to 0
由于函数 f 处理传递参数值的副本，因此在 main 中声明的变量 t 的值未更改。
所以需要像
这样通过指针通过引用传递原始变量t
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
现在程序输出为
Before calling f t is equal to 0
After calling f t is equal to 10
在这些演示程序中，名称 T 用作类型 int 的别名，主要是对象 t 具有此类型。
现在假设名称 T 是类型 int * 的别名。
typedef int * T;
在这种情况下，例如在 main 中声明
T t = NULL;
表示变量t的指针类型为int *。即相当于
int * t = NULL;
因此，要将其传递给必须更改原始变量 t 的函数，我们需要通过引用传递它，例如
f( &t );
这意味着相应的函数应该有声明的参数类型
void f( T *t );
但由于 T 是 int * 的别名，因此这意味着该函数具有 int **.
类型的参数
void f( int * *t );
声明可能会造成一些混乱
node *head;
而不是
node* head;
您正在声明 head。 head 是变量，它是一个指针。它不是一个节点。另请注意，节点不是链表：链表是节点的集合，可能还有其他一些东西，以便有一个有用的实现。稍后会详细介绍。
事实是您在 main() 中声明了 head，只是一个 node*。节点本身甚至还不存在。您将 begin() 声明为
void begin(node *head);
我想你会看得更清楚，因为
void begin(node* parameter);
parameter 是 node*.
在 begin() 中你得到一个指针的副本，改变指针不会改变 main() 中的原始指针。
在您的情况下，它将 main() 永远指向 NULL.
重要的是指针就像任何变量：指针有一个地址。和一个内容。当您按值传递时，就像您所做的那样，begin() 中的指针以 NULL 开始，即来自 main() 的 VALUE。但是他们之间的联系在调用中结束：初始值。
当您将 指针 传递给 begin() 时，使用运算符 'address of' 并写入 &head 事情发生了变化：您将使用运算符 '*' 意味着您将更改它指向的地址，因此它会在 main() 中更改。由于 head 是 node* 指向它的指针将被声明为 node**
但是考虑使用以下链接列表更改 begin() 的声明：
node* begin(node* node);
逻辑是插入一个节点可以改变列表的头部，所以你return新地址，如
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
是常用的写法。另一种是使用 node**.
按照我在这里描述的方式，任何可以改变列表头部的操作都必须
- return新团长
- 接收并更新指向头部指针的指针
再看这段插入列表开头的代码：
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
returning new 你得到 head 更新。你可以写成 main()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
注意行 another = _insert_begin(i, another);，您会看到 main() 中的指针是如何更新的。
这是输出
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
使用 display_list() 的实现，每行打印 5 个值：
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
另一个例子：在最后插入
注意在末尾插入也可以改变头部，在列表为空的情况下，所以我们还需要return头部地址
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
另一种用法：按升序插入
当然，按升序插入也可以换头，如
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
正在删除列表
删除列表还应该return一个node*以使头指针无效。这是平常的。当您习惯它的机制时，这可以确保无效指针不会保留。
请注意，此逻辑是合作的：您必须在每次可以更改头部的调用中重新分配头部指针
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
一个运行程序
示例程序的输出
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
示例 C 程序
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
一个可以说更有用的链表结构
考虑以下内容
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
这样链表被定义为节点的容器。
- 它甚至还有一个可选的
name。
size 始终可用并且是最新的- 大小限制可以实现为
capacity
- 在末尾插入和在开头不需要你跟随所有其他节点，因为列表封装了指向两者的指针头和尾
- 一个节点有指向下一个和前一个节点的指针，因此可以更轻松地迭代一些数据，例如 playlists 或类似的集合。
- 一个程序可以有任意数量的列表，因为每个列表都封装了所有这些元数据。
- 列表可以包含任何内容，因为数据是指向 void 的指针，
void*
- empty() 或 size() 等函数可以轻松实现
- 所有函数都使用指向列表的指针
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
关于：
void begin(node *head){
改变head只会改变调用堆栈'head'，需要改变的是调用者函数中'head'指向的位置。为此，调用者必须传递 'head' 的地址。 'head' 本身就是一个指针这一事实无助于明确需要做什么，
谁能解释一下为什么这段代码给我的结果是空列表：
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
但是如果我用指向指针的指针更改 begin() 函数，它会给我正确的列表？
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
你也能解释一下为什么当我将节点头部传递给函数 begin 时，我必须将它作为“&head”传递吗？不再是“头”
因为 head 是（有效地）一个局部变量，所以改变它在函数之外没有影响，而改变 *head 会改变 head 指向的内容，因此.
如果您希望函数能够更改 int 变量中的值（例如，x），您可以向它传递一个指向 x 的指针，这将具有类型 int*，您将通过使用 &x 获得指向 x 的指针。无论 x 是什么类型，都一样。
在此代码段的第一个程序中
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
指针head按值传递给函数begin。这是在 main 中声明的指针 head 的值的副本被创建并分配给与函数 begin
void begin(node *head);
因此在函数内，最初保存原始指针 head 副本的参数 head 发生了变化。原始指针 head 其值分配给参数的值未更改。
要更改在 main 中声明的原始指针头，您必须通过指向指针头的指针通过引用间接将其传递给函数，就像在第二个程序中所做的那样。
所以函数应该这样声明
void begin(node **head);
而且你必须通过指向它的指针间接传递指针 head
begin( &head );
在这种情况下，取消引用传递的指针，函数将直接访问在 main 中声明的原始指针头并可以更改它（而不是其值的副本，因为它发生在第一个函数定义中）
new->next = *head;
*head = new;
为了更清楚地考虑这个简单的演示程序。
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
它的输出是
Before calling f t is equal to 0
After calling f t is equal to 0
由于函数 f 处理传递参数值的副本，因此在 main 中声明的变量 t 的值未更改。
所以需要像
这样通过指针通过引用传递原始变量t
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
现在程序输出为
Before calling f t is equal to 0
After calling f t is equal to 10
在这些演示程序中，名称 T 用作类型 int 的别名，主要是对象 t 具有此类型。
现在假设名称 T 是类型 int * 的别名。
typedef int * T;
在这种情况下，例如在 main 中声明
T t = NULL;
表示变量t的指针类型为int *。即相当于
int * t = NULL;
因此，要将其传递给必须更改原始变量 t 的函数，我们需要通过引用传递它，例如
f( &t );
这意味着相应的函数应该有声明的参数类型
void f( T *t );
但由于 T 是 int * 的别名，因此这意味着该函数具有 int **.
void f( int * *t );
声明可能会造成一些混乱
node *head;
而不是
node* head;
您正在声明 head。 head 是变量，它是一个指针。它不是一个节点。另请注意，节点不是链表：链表是节点的集合，可能还有其他一些东西，以便有一个有用的实现。稍后会详细介绍。
事实是您在 main() 中声明了 head，只是一个 node*。节点本身甚至还不存在。您将 begin() 声明为
void begin(node *head);
我想你会看得更清楚，因为
void begin(node* parameter);
parameter 是 node*.
在 begin() 中你得到一个指针的副本，改变指针不会改变 main() 中的原始指针。
在您的情况下，它将 main() 永远指向 NULL.
重要的是指针就像任何变量：指针有一个地址。和一个内容。当您按值传递时，就像您所做的那样，begin() 中的指针以 NULL 开始，即来自 main() 的 VALUE。但是他们之间的联系在调用中结束：初始值。
当您将 指针 传递给 begin() 时，使用运算符 'address of' 并写入 &head 事情发生了变化：您将使用运算符 '*' 意味着您将更改它指向的地址，因此它会在 main() 中更改。由于 head 是 node* 指向它的指针将被声明为 node**
但是考虑使用以下链接列表更改 begin() 的声明：
node* begin(node* node);
逻辑是插入一个节点可以改变列表的头部，所以你return新地址，如
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
是常用的写法。另一种是使用 node**.
按照我在这里描述的方式，任何可以改变列表头部的操作都必须
- return新团长
- 接收并更新指向头部指针的指针
再看这段插入列表开头的代码：
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
returning new 你得到 head 更新。你可以写成 main()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
注意行 another = _insert_begin(i, another);，您会看到 main() 中的指针是如何更新的。
这是输出
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
使用 display_list() 的实现，每行打印 5 个值：
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
另一个例子：在最后插入
注意在末尾插入也可以改变头部，在列表为空的情况下，所以我们还需要return头部地址
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
另一种用法：按升序插入
当然，按升序插入也可以换头，如
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
正在删除列表
删除列表还应该return一个node*以使头指针无效。这是平常的。当您习惯它的机制时，这可以确保无效指针不会保留。
请注意，此逻辑是合作的：您必须在每次可以更改头部的调用中重新分配头部指针
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
一个运行程序
示例程序的输出
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
示例 C 程序
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
一个可以说更有用的链表结构
考虑以下内容
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
这样链表被定义为节点的容器。
- 它甚至还有一个可选的
name。 size始终可用并且是最新的- 大小限制可以实现为
capacity - 在末尾插入和在开头不需要你跟随所有其他节点，因为列表封装了指向两者的指针头和尾
- 一个节点有指向下一个和前一个节点的指针，因此可以更轻松地迭代一些数据，例如 playlists 或类似的集合。
- 一个程序可以有任意数量的列表，因为每个列表都封装了所有这些元数据。
- 列表可以包含任何内容，因为数据是指向 void 的指针，
void* - empty() 或 size() 等函数可以轻松实现
- 所有函数都使用指向列表的指针
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
关于：
void begin(node *head){
改变head只会改变调用堆栈'head'，需要改变的是调用者函数中'head'指向的位置。为此，调用者必须传递 'head' 的地址。 'head' 本身就是一个指针这一事实无助于明确需要做什么，