共计 4927 个字符，预计需要花费 13 分钟才能阅读完成。
引言
在数据结构的学习过程中, 有时候会遇到一些一时无法理解的问题, 深究起来却是 语言的底层的语法机制所限制 .
就例如在链表的构建中, 链表的初始化和销毁为何需要使用一个二级指针, 而不是只需要传递一个指针就可以了, 其问题的 关键就在于 c 语言的参数传递的方式是值传递
那么, 这篇文章就来聊一聊在链表的初始化中一级指针的传递和二级指针的区别.
一级指针和二级指针的区别
1.前提知识:c 语言中参数传递的方式是值传递和地址传递
- 值传递:传递的是实参的副本, 即形参是一个新开辟的类型一样, 里面的内容一样, 地址不一样的一个变量, 主函数和被被调用函数用的是不一样的内存空间
- 地址传递:传递的是一个地址, 实际上主函数和被调用函数共用的是同一块内存空间, 被调用函数依然需要一个新的指针来保存起来这块地址
2.传递一级指针:无法对原指针指向第地址进行修改
一级指针实例:
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef int ElemType;
typedef struct SingleNode{
ElemType data;
struct SingleNode *next;
}SingleNodeList,*Linklist;
void LinkedListInit(SingleNodeList *head){// 用一个指针 head 接收传入的地址
Linklist p;
if((head=(SingleNodeList *)malloc(sizeof(SingleNodeList)))==NULL){exit(1);// 给 head 分配内存, 改变了 head 指针指向的地址(注意这里的 head 只是 LinkedListInit 的 head, 不是主函数那个)
}
head->next=NULL;
}// 这个函数结束后 head 被销毁了, 主函数的那个 head 不变;
int LinkedList_PushFront(SingleNodeList *head,ElemType x){// 2 单链表头插入
SingleNodeList *q;
if((q=(struct SingleNode *)malloc(sizeof (struct SingleNode)))==NULL){exit(1);
}
q->data=x; q->next=head->next;// 头节点的数据域与指针域赋值
head->next=q;// 头节点加入链表
return 1;
}
int LinkedList_PopFront(SingleNodeList *head,ElemType *x){// 3 单链表头删除
SingleNodeList *p=head,*q;
if(p->next==NULL){printf("There is no data in the Linkedlist to delete.\n");
*x = -12345;// 未成功删除则在 x 指向单元赋特定值
return 0;
}
p=head->next;
q=p;
head->next=p->next;
*x=q->data;
free(q);
return *x;// 请填写多行代码
}
int LinkedListGet_current(SingleNodeList *p,ElemType *x){// 4 取当前指针指数据
*x =p->data;
return 1;
}
int LinkedListUpdata_current(SingleNodeList *p,ElemType x){// 5 修改当前指针数据
p->data=x;
return 1;
}
int LinkedListShow(SingleNodeList *head){// 6 打印单链表
SingleNodeList *p=head;
if(p->next==NULL){printf("There is no data in the Linkedlist to print.\n");
return 0;
}
while(p->next!=NULL){printf("%d",p->next->data);
p=p->next;
}
printf("\n");
return 1;
}
void LinkedListDestroy(SingleNodeList **head){// 7 释放链表
SingleNodeList *p=*head,*q;
while(p!=NULL){
q=p;
p=p->next;
free(q);
}
*head=NULL;
}
int LinkedListLength(SingleNodeList *head){// 8 求单链表长度
SingleNodeList *p=head;
int size=0;
while(p->next!=NULL){
size++;
p=p->next;
}
return size;
}
int main(){
SingleNodeList *head,*p;
ElemType i,x;
int switch_num;
scanf("%d",&switch_num);
switch(switch_num){
case 1:
LinkedListInit(head); // 传入指针变量 head 的地址
LinkedList_PushFront(head,1);
LinkedList_PushFront(head,3);
LinkedList_PushFront(head,2);
LinkedListShow(head);
break;
}
LinkedListDestroy(&head);
return 0;
}传递流程如图所示
从图中可以看出,main 函数中我们定义了 一个指针 head, 假设它的地址是 0x10010, 但是还没给它初始化, 也就是说它存的地址是随机的, 我们也假设它存的是 0x12306
在 main 函数中, 我们把 head 这个指针 作为参数传递进去初始化函数 (值传递), 按照值传递的原则, 初始化函数首先开辟了一个*head 指针, 它的地址是 0x12345(与 main 函数的 0x10010 不一样), 但是它的内容是是和主函数的 head 是一样的, 都是指向 0x12306 这个地址
在初始化的过程中, 我们用 malloc 函数对初始化函数内的 head 指针分配内存空间, 也就是改变了 head 指针的值, 由未初始化的随机值 0x12306 改变成了 0x10086
也就是说, 由于这个 head 是作用在初始化函数内的,mallo 作用的不是主函数的 head, 初始化函数结束后, 这个 head 指针就被销毁掉了, 主函数中的 head 不受影响, 初始化失败, 而分配了内存不能使用, 造成了内存泄漏
3. 传递二级指针:对指针指向的内容进行操作,head 销毁后无影响
二级指针传递实例:
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef int ElemType;
typedef struct SingleNode{
ElemType data;
struct SingleNode *next;
}SingleNodeList,*Linklist;
void LinkedListInit(SingleNodeList **head){// 1 初始化有头节点的单链表
Linklist p;
if((*head=(SingleNodeList *)malloc(sizeof(SingleNodeList)))==NULL){exit(1);
}
(*head)->next=NULL;
}
int LinkedList_PushFront(SingleNodeList *head,ElemType x){// 2 单链表头插入
SingleNodeList *q;
if((q=(struct SingleNode *)malloc(sizeof (struct SingleNode)))==NULL){exit(1);
}
q->data=x; q->next=head->next;// 头节点的数据域与指针域赋值
head->next=q;// 头节点加入链表
return 1;
}
int LinkedList_PopFront(SingleNodeList *head,ElemType *x){// 3 单链表头删除
SingleNodeList *p=head,*q;
if(p->next==NULL){printf("There is no data in the Linkedlist to delete.\n");
*x = -12345;// 未成功删除则在 x 指向单元赋特定值
return 0;
}
p=head->next;
q=p;
head->next=p->next;
*x=q->data;
free(q);
return *x;// 请填写多行代码
}
int LinkedListGet_current(SingleNodeList *p,ElemType *x){// 4 取当前指针指数据
*x =p->data;
return 1;
}
int LinkedListUpdata_current(SingleNodeList *p,ElemType x){// 5 修改当前指针数据
p->data=x;
return 1;
}
int LinkedListShow(SingleNodeList *head){// 6 打印单链表
SingleNodeList *p=head;
if(p->next==NULL){printf("There is no data in the Linkedlist to print.\n");
return 0;
}
while(p->next!=NULL){printf("%d",p->next->data);
p=p->next;
}
printf("\n");
return 1;
}
void LinkedListDestroy(SingleNodeList **head){// 7 释放链表
SingleNodeList *p=*head,*q;
while(p!=NULL){
q=p;
p=p->next;
free(q);
}
*head=NULL;
}
int LinkedListLength(SingleNodeList *head){// 8 求单链表长度
SingleNodeList *p=head;
int size=0;
while(p->next!=NULL){
size++;
p=p->next;
}
return size;
}
int main(){
SingleNodeList *head,*p;
ElemType i,x;
int switch_num;
scanf("%d",&switch_num);
switch(switch_num){
case 1:
LinkedListInit(&head);
LinkedList_PushFront(head,1);
LinkedList_PushFront(head,3);
LinkedList_PushFront(head,2);
LinkedListShow(head);
break;
}
LinkedListDestroy(&head);
return 0;
}
如图所示, 如果传递的是二级指针就不一样了, 首先我们在 main 函数中的操作是和一级指针差不多, 只是传递的时候传递的不是一个指针变量, 而是这个指针变量的地址 ( 地址传递 ), 但是在初始化函数中我们接收这个地址的是用一个二级指针, 也就是 用一个 head 指针指向传递主函数那个 head 指针的地址, 从而来进行对初始化函数中 head 指针内容的改变去影响到主函数中的 head 的指向
如图所示, 我们在 mian 函数中传递了一个 head 的地址, 也就是 0x10010, 这个地址是指向 0x12306 指针的地址
在初始化函数中, 我们用一个另外的 head 指针接受这块地址, 也就是个二级指针, 第一级是 0x10010, 指向 0x12305), 第二级是 0x12345, 指向 0x10010
在初始化函数中,malloc 函数操作的对象是 head 指针内的内容, 也就是 0x10010 这块指针(主函数中的 head 指针), 这样成功改变了主函数中的 head 指向的地址, 而在销毁初始化函数的 head 指针的时候, 主函数的的 head 指针不受影响
4. 总结
- 参数传递时, 在需要改变指针指向的时候需要传递二级指针, 例如初始化和销毁链表
- 一二级指针的图片对比如下图
