C++指针和栈的学习

傷城~ 2023-03-02 07:40 118阅读 0赞

## 理解栈的含义 ##

![在这里插入图片描述][20200728102104497.png]  
上图就是栈，只有一个出口（上端）  
那么假设我们有4个数字，要进入到这个栈，该怎么进入呢  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70]

### 先进的后出，后进的先出 ###

实践操作：  
1，2，3，4，那么按照从前向后的顺序依次进入这个栈中  
得知：1先进去，2，3两个数字次进，4后进去  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 1]  
进入之后，我们要拿出来，由于只有一个出口，所以进出的顺序不一样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 2]  
结论：先进的后出，后进的先出

### 递归中的栈 ###

#include<iostream>
    using namespace std;
    void op(int n)
    { 
    	if(n<1) cout<<"1\n";
    	else
    	{ 
    		cout<<n<<"\n";
    		return op(n-1);
    		cout<<n<<"\n";
    	}
    }
    int main()
    { 
    	int n;
    	cin>>n;
    	op(n);
    	return 0;
    }

代码执行后输入4，输出结果为：  
![在这里插入图片描述][20200728111542335.png]

### 理解递归中的出栈和入栈 ###

像中间递归，它就是一个栈  
上图中的一行代码`return op(n-1);`就是把n-1值放进了栈：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 3]  
所以递归语句的后面的执行语句就是从栈里取出，而取出的顺序正好是逆序  
栈的讲解到此结束，不要以为没用，在很多的题目中都会涉及到栈  
像跟栈有关的例题我没有讲解，在遇到这种题目时要列一个栈，把进出弄清，则迎刃而解

## 指针 ##

如果把计算机的内存看作是一个一个单元格，为每个单元格赋予一个编号，那么这个编号就可以称为内存地址，保存这些编号的变量我们就称之为**指针**

--------------------

指针是C/C++的共同特性之一，指针实现了对变量、常量、对象、函数的间接访问方式，并且指针本身就是一种数据类型，指针拥有其他数据相同的性质——无需在定义时赋初值，可以先后指向不同的对象  
它的标志性就是要有一个\*

--------------------

#include<iostream>
    using namespace std;
    int main()
    { 
    	int a=5;
    	int *p=&a;
    	cout<<*p;
    	return 0;
    }

这段代码执行后是5，因为指针p指向了a  
**注意事项：**

1.  想要获取该地址，需要使用取地址符号（&）
2.  如果想要输出该地址要加\*
3.  去掉\*就是0xXXXX
4.  如果指针值被修改，则被指向的值也被修改，因为指针是永远指向-那个-被指向的-数的
5.  原值修改也会导致指针被修改

### 使用指针交换两个数 ###

例题：现在要求使用指针为中间数，把a和b的值交换

--------------------

上述提到如果指针值被修改，则被指向的值也被修改  
如果只有一个指针的话，那么指针的值一但被修改则被指向的值也被修改  
所以要有**两个指针**  
再想，两个指针不能完成，需要两个中间数（我觉得这和不用指针差不多啊qwq）

#include<iostream>
    using namespace std;
    int main()
    { 
    	int a=5,b=2,num1=0,num=0;
    	int *n=&a,*m=&b;
    	num=a;
    	num1=b;
    	b=num;
    	a=num1;
    	cout<<a<<" "<<b;
    	return 0;
    }

好了，输出后就是2 5

### 用指针模拟栈的几种基本操作 ###

栈的操作有以下几种：（自己写的，有增加了几个）

1.  判断是否为空（empty）
2.  首位数字出栈（pop）
3.  加进一个数入栈（push）
4.  取首位数字（top）

事先准备两个指针，分别是top和end，首和尾，在给一个数组，用来给指针赋值  
**两个指针的值一样**  
**全局变量**

int stack[]={ 0};
    int *top=stack[sizeof(stack)/sizeof(int)];//不知道为什么这么长
    int *end=stack[sizeof(stack)/sizeof(int)];

--------------------

1，判断是否为空  
为什么要给指针赋值呢？这样好判断是否为空  
如果top==end，则知道这个栈没有任何东西  
**empty函数**

int sempty()//呵呵呵呵，我就不写empty
    { 
    	if(top==end) return 0;//如果首尾一样返回个0
    	return 1;
    }

2，首位数字出栈  
出栈默认把最上方的那个数字踢去，不要  
如果丢掉一个数字，那么top的值肯定要-1，因为少一个数字那么就剩下了top-1个数字  
所以：丢掉一个数字等价于top-1  
**pop函数**

int spop()//...
    { 
    	top--;
    }

3，加进一个数入栈  
有出必有进，所以push函数不可少  
上述提到：加\*则是地址，不加则是0xXXXX  
每加一个数字则有**top+1**个数字  
这时顶端数字便被改变

int spush(int num)
    { 
    	top++;
    	*top=num;
    }

4，取首位数字  
呵呵呵呵，不要太简单  
首先判断一下首位是不是为空，然后再输出

int stop()//stop!停止!
    { 
    	if(sempty()==0) return *top;
    	return -1;
    }

### 完整代码 ###

#include<iostream>
    using namespace std;
    int stack[]={ 0};
    int *top=&stack[sizeof(stack)/sizeof(int)];
    int *end=&stack[sizeof(stack)/sizeof(int)];
    int sempty()
    { 
    	if(top==end) return 1;
    	return 0;
    }
    int stop()
    { 
    	if(sempty()==0) return *top;
    	return -1;
    }
    int sszie()
    { 
    	return top-end;
    }
    int spop() 
    { 
    	top--;
    }
    int spush(int num)
    { 
    	top++;
    	*top=num;
    }
    int main()
    { 
    	int s;
    	cin>>s;
    	spush(10);
    	spush(s);
    	spop();
    	cout<<stop();
    	return 0;
    }

[20200728102104497.png]: /images/20230208/3cb29bc1984b4135a66c865184e5c062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70]: /images/20230208/b95eb628bd6740009550fe1904fca495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 1]: /images/20230208/290e85ce28a244a5a4f377d2085488b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 2]: /images/20230208/2030b7d6e284446c9ec918137ca5d366.png
[20200728111542335.png]: /images/20230208/678c6dcac55046129ed88f50663fc758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70 3]: /images/20230208/05f2a7f86c514bccb9db5b49c8998162.png