一篇文章学懂C++和指针与链表

指针

目录

指针

C++的指针学习

指针的基本概念

指针变量的定义和使用

指针的所占的内存空间

空指针和野指针

const修饰指针

指针和数组

指针和函数

指针、数组、函数

---

 接下来让我们开始进入学习吧！

C++的指针学习

指针的基本概念

指针的作用：可以通过指针间接访问内存

1. 内存编号是从0开始记录的，一般用十六进制数字表示

2. 可以利用指针变量保存地址

这个概念和C语言是一模一样的，只要记住指针就是地址。

指针变量的定义和使用

#include<iostream>
using namespace std;
int main()
{int a = 10;int *pa = &a;cout << a << endl;cout << pa << endl;cout << &a << endl;cout << *pa << endl;//可以通过解引用的方式来找到指针指向的内存*pa = 20;//通过指针来改变a的值cout << a << endl;cout << *pa << endl;return 0;
}

输出结果：
10
0x61fe14
0x61fe14
10
20
20

指针的所占的内存空间

指针也是一种数据类型，所以也会占内存空间。

#include<iostream>
using namespace std;
int main()
{int* pa;char* pb;short* pc;long* pd;float* pe;double* pf;cout << sizeof(pa) << endl;cout << sizeof(pb) << endl;cout << sizeof(pc) << endl;cout << sizeof(pd) << endl;cout << sizeof(pe) << endl;cout << sizeof(pf) << endl;return 0;
}

8
8
8
8
8
8

在32位的操作系统中，指针都是占4个字节的空间的。

在64位的操作系统中，指针则都是占8个字节的空间的。

所以看题目或者写代码的时候一定要清楚自己机器的大小和型号。

空指针和野指针

空指针：指针变量指向内存中编号为0的空间

用途：初始化针变量

注意：空指针指向的内存是不可以访间的

示例1：空指针

#include<iostream>
using namespace std;
int main()
{//空指针//空指针用于给指针变量进行初始化int* p = NULL;//2.空指针是不可以进行访问的，//0~255内存编号是系统占用的，使用会错误，因此不可访问cout << *p <<endl;return 0;
}

野指针：指针变量指向非法的内存空间

示例2：野指针

#include<iostream>
using namespace std;
int main()
{int* p = (int*)0x1100;cout << *p << endl;//这里还是无法输出，指向的是非法内存空间int arr[2] = { 1,2 };p = arr[2];//越界访问cout << *p <<endl;return 0;
}

总结：空指针和野指针都不是我们自己申请的空间，因此不要访问。

const修饰指针

const修饰指针的三种情况：

1. const修饰指针——常量指针

2. const修饰常量——指针常量

3. const既修饰指针，又修饰常量

示例：

#include<iostream>
using namespace std;
int main()
{int a = 10;int b = 20;//常量变量//特点：指针的指向可以修改，但是指针指向的值不可以改const int* p1 = &a;a = 0;//*p1也会相应改变p1 = &b;//可以实现*p1 = 0;//不允许//指针常量//特点：指针的指向不可以修改，但是指针指向的值可以改int* const p2 = &a;*p2 = 10;p1 = &b;//不允许*p1 = 0;//可以实现//既修饰指针，又修饰常量//特点：指针的指向不可以修改，但是指针指向的值也不可以改const int* const p3 = &a;p3 = &b;//不允许*p3 = 0;//不允许return 0;
}

指针和数组

作用：利用指针访问数组中元素

一维数组

#include<iostream>
using namespace std;
int main()
{int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };int * p = arr;for(int i = 0;i < 10; i++){cout << *p + i << endl;//用p[i]也可以做到}return 0;
}

二维数组

#include<iostream>
using namespace std;
int main()
{int arr[2][3] = { { 0,1,2 },{ 3,4,5} };int (* parr)[3] = arr;for(int i = 0;i < 2; i++){for(int j = 0;j < 3; j++){cout << (*parr[i]+j)<<endl;}}return 0;
}

指针和函数

作用：利用指针作函数参数，可以修改实参的值

#include<iostream>
using namespace std;
void Swap(int* x,int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
int main()
{//实现a，b交换int a,b;cin >> a >> b;Swap(&a,&b);cout << "a = " << a << endl;cout << "b = " << b << endl;return 0;
}

指针、数组、函数

案例描述：封装一个函数，利用冒泡排序，实现对整型数组的升序排序 如数组：int arr[10]={4,3,6,9,1,2,10,8,7,5}

#include<iostream>
using namespace std;
​
void bubbleSort(int *p,int sz)
{for(int i = 0;i < sz - 1; i++){for(int j = 0; j < sz - i - 1; j++){//如果j>j+1的数据就要交换if(*(p + j) > *(p + j + 1)){int tmp = *(p + j);*(p + j) = *(p + j + 1);*(p + j + 1) = tmp;}}}
}
​
//打印数组
void printArray(int * p,int sz)
{for(int i = 0;i < sz; i++){cout << *p + i << " ";}
}
int main()
{//1.创建数组int arr[10];for(int i = 0;i < 10; i++){cin >> arr[i];}//数组长度int sz = sizeof(arr) / sizeof(arr[0]);//2.创建函数bubbleSort(arr,sz);
​//3.打印排序后的数组printArray(arr,sz);return 0;
}

链表

学习C++链表

链表的基本概念avi_

数据域1+next地址 ——> 数据域2+next地址 ——> 数据域3+next地址 ——> 数据域4+next地址 ——> 数据域5+next地址 ——> NULL（空）

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

链表在指定位置插入和删除不需要移动元素，只需要修改指针即可。

查找效率低于数组

链表相对于数组而言，多了指针域空间开销

链表种类：

静态链表 动态链表 单向链表 双向链表 循环链表 单向循环链表 双向循环链表

拿到链表的第一个节点，就相当于拿到整个链表

头节点不保存任何数据

静态链表

 

静态链表：分配一整片连续的内存空间，各个结点集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构，静态链表实际上就是一个结构体数组

实现一个链表

#define _CRT_SECURE_NO_WARNING
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
​
//链表节点类型定义
struct LinkNode
{int data;struct LinkNode *next;
};
​
void test()
{struct LinkNode node1 = { 10, NULL };struct LinkNode node2 = { 20, NULL };struct LinkNode node3 = { 30, NULL };struct LinkNode node4 = { 40, NULL };struct LinkNode node5 = { 50, NULL };struct LinkNode node6 = { 60, NULL };node1.next = &node2;node2.next = &node3;node3.next = &node4;node4.next = &node5;node5.next = &node6;//连成链表//如何遍历这个链表struct LinkNode *pCurrent = &node1;while(pCurrent != NULL){printf("%d ",pCurrent->data);//指针移动到下一个元素的首地址pCurrent = pCurrent->next;}
}
​
int main()
{test();return 0;
}

如何遍历这个链表 需要一个pCurrent指针能够指向下一个链表的地址

pCurrent = pCurrent->next

动态链表

这种链表在初始时不一定分配足够的空间, 但是在后续插入的时候需要动态申请存储空间，并且存储空间不一定连续, 在进行插入和删除时则不需要移动元素, 修改指针域即可,所以仍然具有链表的主要优点，链表结构可以是动态地分配存储的，即在需要时才开辟结点的存储空间，实现动态链接。

链表的实现

LinkList.h

#define _CRT_SECURE_NO_WARNINGS
​
#pragma once
​
#include<stdio.h>
#include<stdnool.h>
#include<stdlib.h>
​
#iddef __cplusplus
#endif//定义节点数据类型struct LinkNode{int data;struct LinkNode *next;}
​//初始化链表struct LinkNode * Init_LinkList();//在值为oldval的后面插入一个新的数据newvalvoid InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval);//删除值为val的节点void RemoveByValue_LinkList(struct LinkNode *header,int delValue);//遍历void Foreach_LinkList(struct LinkNode *header);//销毁void Destroy_LinkList(struct LinkNode *header);//清空void Clear_LinkList(struct LinkNode *header);#ifdef __cplusplus
#endif

LinkList.c

#include "LinkList.h"
//初始化链表
struct LinkNode * Init_LinkList()
{//创建头节点struct LinkNode *header = malloc(sizeof(struct LinkNode));header->data = -1;header->next = NULL;//尾部指针struct LinkNode *pRear = header;int val = -1;while(true){printf("输入插入的数据：\n");scanf("%d",&val);if(val == -1){break;}//先创建新节点struct LinkNode *newnode = malloc(sizeof(struct LinkNode));newnode->data = val;newnode->next = NULL;//新节点插入到链表中pRear->next = newnode;//更新尾部指针指向pRear = newnode;}return header;
}
​//在值为oldval的位置插入一个新的数据newvalvoid InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval){if(NULL == header){return;}//两个辅助指针变量struct LinkNode *pPrev = header;struct LinkNode *pCurrent = pPrev->next;while(*pCurrent != NULL){if(pCurrent->data == oldval){break;}pPrev = pCurrent;pCurrent = pCurrent->next;}//pCurrent为空那就说明链表中不存在职位oldval的节点if(pCurrent == NULL){return;}//先创建新节点struct LinkNode *newnode = malloc(sizeof(struct LinkNode));newnode->data = newval;newnode->next = NULL;//新节点插入到链表中pPrev->next = newnode;newnode->next = pCurrent;//删除值为val的节点void RemoveByValue_LinkList(struct LinkNode *header,int delValue){if(NULL == header){return;}//两个辅助指针变量struct LinkNode *pRrev = header;struct LinkNode *pCurrent = pRrev->next;//while(pCurrent != NULL){if(pCurrent->data == delValue){break;}//移动两个辅助指针pPrev = pCurrent;pCurrent = pCurrent->next;}if(pCurrent == NULL){return;}//重新建立待删除节点的前驱和后继节点关系pPrev->next = pCurrent->next;free(pCurrent);pCurrent == NULL;}
​//遍历void Foreach_LinkList(struct LinkNode *header){if(NULL == header){return;}//辅助指针变量struct LinkNode *pCurrent = header->next;while(pCurrent != Null){printf("%d ",pCurrent->data);pCurrent = pCurrent->next;}}
​//销毁void Destroy_LinkList(struct LinkNode *header){if(NULL == header){return;}//辅助指针变量struct LinkNode *pCurrent = header;while(pCurrent != NULL){//先保存当前节点的下一个节点地址struct LinkNode *pNext = pCurrent->next;//释放当前节点内存free(pCurrent);//指针向后移动pCurrent = pNext;}}//清空void Clear_LinkList(struct LinkNode *header){if(NULL == header){return;}//辅助指针变量struct LinkNode *pCurrent = header->next;while(pCurrent != NULL){//先保存当前节点的下一个节点位置struct LinkNode *pNext = pCurrent->next;//释放当前节点内存free(pCurrent);//pCurrent指向下一个节点pCurrent = pNext;}header->next = NULL;}

TestLinkList.c