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语言中没有引用传递，只有值传递，但是提供了几种方式，实现在函数内部修改实参值。
- 函数返回值
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;
}
- 全局变量
全局变量，很明显，所有函数内部均可以访问，可以修改其值。
备注：全局变量是最简单的方式，但是破坏了函数的模块化，容易造成变量冲突（局部变量中也有相同的名称）、任意修改全局变量可能会造成程序错误（多个函数修改该变量），不建议使用。
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;
数据结构-栈和队列（一）
栈的基本概念(逻辑结构）
- 栈是一种只能在一端进行插入或者删除操作的线性表
- 线性表：栈的逻辑结构属于线性表，只不过在操作上加了一些约束。
- 一端：可以插入或删除的一端叫栈顶，另一端叫栈底。
栈的存储结构
顺序栈
- 顺序栈的定义：
int stack[maxSize];
int top = -1;
}
- 元素入栈
stack[top++] = 1;//先让top自增，然后对top自增后的top取值
- 元素出栈
x = stack[top--];//先取现在top所指元素值，然后top前移一位。
4.特殊状态
链栈
- 链栈定义
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.特殊状态