Java教程

数据结构刷题day11

本文主要是介绍数据结构刷题day11，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

C和C++的链表函数传递

关于链表，已经写了三篇博客研究了，虽然考研的数据结构并没有细致入微，但是关于书上的不同写法，我心里总是有个疙瘩。

所以今天进行一次系统的总结，彻底写清链表在C/C++中作为函数被传递的问题。

先创建结构体。

1
2
3
4
5
typedef struct Link
{
    int elem;
    struct link* next;
}link, *linkpointer;

定义了一个名为link的数据形式，以及一个名为linkpointer的指向link形式数据的指针。

C++

在初始化链表时，有时需要这样写：

1
2
3
4
5
linkpointer p;//创建一个头指针
initlink(linkpointer &q);//将头指针传入
{
    q=(linkpointer)malloc(siezof(link));
}

学数据结构只写过c的我，当时就蒙了，这&是个什么东西？取地址吗？为什么要在这里取地址啊？

我们将这一句单独摘出来看。

1
linkpointer &q = p;

将一个结构体指针p的值，赋予给另一个结构体指针q的地址？什么玩意儿

实际上这里的&并非取地址的意思，而是C++中的特殊用法：引用。

C++中的引用是什么意思，可以自己看教程，作者看的是：

c++中引用&的使用 http://c.biancheng.net/view/2251.html

在函数传参中使用&，相当于q与函数外的p完全等价，数据形式相同，指向同一块内存。

我们写一段C++的程序来验证这一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
typedef struct Link
{
    int elem;
    struct Link* next;
}link, *linkpointer;
 
void init(linkpointer &p)
{
    printf("%d", p);
}
 
int main()
{
    linkpointer p;
    p = (linkpointer)malloc(sizeof(link));
    p->elem = 1;
    p->next = NULL;
    init(p);
}

经过断点调试，我们确实验证了，p和q，两者完全等价。

1
2
3
4
5
传入前：
    +       p   0xcccccccccccccccc {elem=??? next=??? } Link *
传入后：
    +       q   0xcccccccccccccccc {elem=??? next=??? } Link *
//一模一样

所以也有了我们在书上看到的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<stdlib.h>
typedef struct Link
{
    int elem;
    struct Link* next;
}link, *linkpointer;
 
void init(linkpointer &p)
{
    p = (linkpointer)malloc(sizeof(link));
    p->elem = 1;
    p->next = NULL;
    printf("%d", p);
}
 
int main()
{
    linkpointer p;
    init(p);
}

我说实话，这种写法挺离谱的，main函数中的linkpointer p完全是个没有意义的声明，p既没有被分配内存，结构体内也没有数据，还非要通过&这种困难的方式传递给函数。

如果没有这个&

1
2
void init(linkpointer q)
init(p);

q为形参，而p又没有任何数据，在这里就会直接报错。

1
The variable 'p' is being used without being initialized.

我们来看另一种情况，在对链表进行操作时的情况。

1
2
void nodeinsert(linkpointer p,int target,int element)
nodeinsert(L,target,element)

这里的L一般已经初始化过了，摘出来是这样的

1
linkpointer p = L;

将结构体指针L的值，即链表的地址直接赋给形参p，p也就能在函数中正确操作内存中的链表了。

C语言

接下来还有一个问题，那在C语言中，没有引用这个用法，那怎么办呢？

想信弄懂了前面的知识，这个问题也难不住你了。

我们只需要用C语言的常规方法，将变量取址，传入时多加一个*即可。

1
2
void init(linkpointer *q)
init(&p)

而在普通对链表进行操作时，和C++完全一样，直接传就完事了

1
2
void nodeinsert(linkpointer p,int target,int element)
nodeinsert(L,target,element)

总结及鸣谢

一句话总结：需要更改链表指针本身的值时，必须加&，否则不需要加。

前者是调用了完全相同的变量，后者则是新定义了一个形参指针，指向相同的内存。

严蔚敏老师版的数据结构，说是C语言，又用了C++的”引用“传参，真的搞心态。

被传参戏耍了三天，和几个同学讨论了很久，也请教了老师。今天终于是彻彻底底弄明白了，讨论了每一种情况，在此总结，也希望可以帮到你。

鸣谢
吉吉同学和鱼同学
数据结构贾老师
这篇关于数据结构刷题day11的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
原文链接：https://www.cnblogs.com/huigugu/p/16056878.html
您可能喜欢
栏目导航