20210408

回顾 | 数据结构-栈和队列(一)

Table of Contents

回顾

恋词复习

  • threshold n.门槛;入门;开端
  • preliminary adj.预备的;初步的

C语言函数传参方式:值传递和地址传递

函数是由返回值类型、函数名、函数参数列表组成的,其中函数调用时,将实参传递给参数列表的形参,函数根据传递的实参值计算出结果返回,这里涉及传递函数参数的方式。

形参 VS 实参

形参(形式参数):很简单,函数声明和定义中的参数名称就是形参,例如:定义一个计算两个整数和的函数,其中参数名称a和b就是形参。

int add(int a,int b)
{
return a+b;
}

实参(实际参数):当需要实际调用时,传递给函数的具体参数值或参数变量值就是实参。例如:

int x=1,y=2;
add(x,y); // x和y是实参
add(1,3); // 1和3也是实参
add(x,1); // x和1也是实参

很明显,当实参传递给函数形参以后,在函数内部通过形参名称访问实际的值,无法知道实参的名称。

函数参数传递方式:值传递和引用传递

值传递:又称为值调用,指的是将实参的值拷贝一份给形参,此时形参和实参是两个独立的变量或值,当函数修改内部的形参值时,不会影响外部的实参值。

引用传递:又称为引用调用,是指直接将实参传给函数形参,相当于函数内部直接可以访问到外部的实参,这种特性在C语言中是没有的,C++中支持,函数声明中参数使用 & 符号表示。例如:C++中:

int add(int &a, int &b);

本质上,C语言中没有引用传递,只有值传递,但是提供了几种方式,实现在函数内部修改实参值。

  1. 函数返回值
int modify(int x)
{
// 将x的值改为200
x = 200;
return x;
}
int main(void)
{
int a=0;
modify(a);
printf("%d\n", a); // 此时a仍然是0
a = modify(a); // 此时a通过返回值赋值为200
printf("%d\n", a); // 此时a是200
return 0;
}
  1. 全局变量

全局变量,很明显,所有函数内部均可以访问,可以修改其值。

备注:全局变量是最简单的方式,但是破坏了函数的模块化,容易造成变量冲突(局部变量中也有相同的名称)、任意修改全局变量可能会造成程序错误(多个函数修改该变量),不建议使用。

int a = 0;
void modify()
{
a = 200;
}
int main(void)
{
modify();
printf("%d\n", a); // 此时a肯定是200
return 0;
}

3. 指针传递

这个方式,是要大家掌握的,指针传递在C语言中可以实现引用传递的效果,因此,很多时候,一些书籍认为C语言也有引用传递,就是将指针传递当做引用传递。

本质上,指针传递仍然是值传递,会将指针的实参值赋值一份给形参,但是指针传递的是地址,因此函数内部可以通过地址间接修改实参的值。与上面引用传递做比较!请注意:引用传递是直接修改实参的值。

void modify(int *x)
{
// 将x的值改为200
*x = 200;
x = (int *)0;
}
int main(void)
{
int a=0;
int *p = &a;
modify(p);
printf("%d\n", a); // 此时a是200
printf("%p\n", p); // 此时p的值仍然是变量a的地址
return 0;
}

解析:形参是指针类型时,和普通变量一样,当实参传递地址给指针形参时,仍然是拷贝一份值给形参。例如p是实参,x是形参,p保存变量a的地址拷贝赋值给形参x,函数内部直接修改x的值,并不会影响实参p的值。

但是,由于p和x同时保存变量a的地址,函数内部通过间接访问变量a,可以修改变量a的值,因此从效果上看,的确是修改了函数外部实参所指向的变量的值。


补充:

#include <stdio.h>
/* 变量x、y为Swap函数的形式参数 */
void Swap(int x, int y)
{
int tmp;
tmp = x;
x = y;
y = tmp;
printf("x = %d, y = %d\n", x, y);
}
int main(void)
{
int a=10;
int b=20;
/*变量a、b为Swap函数的实际参数*/
Swap(a, b);
printf("a = %d, b = %d\n", a, b);
return 0;
}

在上面这个示例代码中,实参将值传递给形参,形参值发生互换后的值不能回传给主调函数。因此,主调函数中的数值不变,代码的运行结果为: x = 20, y = 10 a = 10, b = 20

对于上面这个示例,或许有人会有如下疑问:上面的示例中明确地把 a、b 分别代入了 x、y 中,并在函数 Swap() 里完成了两个变量值的交换,为什么 a、b 变量值还是没有交换。其结果仍然是“a=10,b=20”,而不是“a=20,b=10”呢?

其实,原因很简单。函数在调用时,隐含地把实参 a 的值赋值给了参数 x,而将实参 b 的值赋值给了参数 y,如下面的代码所示:

/*将a的值赋值给x(隐含动作)*/
int x = a;
/*将a的值赋值给y(隐含动作)*/
int y = b;

因此,之后在 Swap() 函数体内再也没有对 a、b 进行任何操作。而在 Swap() 函数体内交换的只是 x、y,并不是 a、b,当然,a、b 的值没有改变。整个 Swap() 函数调用是按照如下顺序执行的:

/*将a的值赋值给x(隐含动作)*/
int x = a;
/*将a的值赋值给y(隐含动作)*/
int y = b;
int tmp;
tmp = x;
x = y;
y = tmp;
printf("x = %d, y = %d\n", x, y);

由此可见,函数只是把 a、b 的值通过赋值传递给 x、y,在函数 Swap() 中操作的只是 x、y 的值,并不是 a、b 的值,这也就是所谓的参数的值传递。

地址传递
这种方式使用数组名或者指针作为函数参数,传递的是该数组的首地址或指针的值,而形参接收到的是地址,即指向实参的存储单元,形参和实参占用相同的存储单元,这种传递方式称为“参数的地址传递”。

地址传递的特点是形参并不存在存储空间,编译系统不为形参数组分配内存。数组名或指针就是一组连续空间的首地址。因此在数组名或指针作函数参数时所进行的传送只是地址传送,形参在取得该首地址之后,与实参共同拥有一段内存空间,形参的变化也就是实参的变化。

void Swap(int *px, int *py)
{
int tmp;
tmp = *px;
*px = *py;
*py = tmp;
printf("*px = %d, *py = %d\n", *px, *py);
}
int main(void)
{
int a=10;
int b=20;
Swap(&a, &b);
printf("a = %d, b = %d\n", a, b);
return 0;
}

在上面的示例代码中,函数 void Swap(intpx,intpy) 中的参数 px、py 都是指针类型,在 main 函数中使用语句“Swap(&a,&b)”进行调用,该调用语句将 a 的地址(&a)代入 px,b 的地址(&b)代入 py。很显然,这里的函数调用有两个隐含操作:将 &a 的值赋值给参数 px,将 &b 的值赋值给参数 py,如下面的代码所示:

px = &a;
py = &b;

数据结构-栈和队列(一)

栈的基本概念(逻辑结构)

  • 栈是一种只能在一端进行插入或者删除操作的线性表
    • 线性表:栈的逻辑结构属于线性表,只不过在操作上加了一些约束。
    • 一端:可以插入或删除的一端叫栈顶,另一端叫栈底。

栈的存储结构

顺序栈

  1. 顺序栈的定义:
int stack[maxSize];
int top = -1;
}
  1. 元素入栈
stack[top++] = 1;//先让top自增,然后对top自增后的top取值
  1. 元素出栈
x = stack[top--];//先取现在top所指元素值,然后top前移一位。

4.特殊状态

链栈

  1. 链栈定义
LNode* head = (LNode*)malloc(sizeof(LNode)); //申请头结点存储空间
head->next = NULL;
LNode *top = NULL; //定义栈顶指针

2.元素入栈

top = (LNode*)malloc(sizeof(LNode));
top->next = NULL;
top->data = 'A';//'B'、'C'
top->next = head->next;
head->next = top;
}

3.元素出栈

x = top->data;
head->next = top->next;
free(top);
top = head->next;

4.特殊状态