9.指针与链表
一、指针
1.基本介绍
在程序中,我们的数据都有其存储的地址。在程序每次的实际运行过程中,变量在物理内存中的存储位置不尽相同。不过,我们仍能够在编程时,通过一定的语句,来取得数据在内存中的地址。地址也是数据。存放地址所用的变量类型有一个特殊的名字,叫做指针。
指针的大小在不同环境下有差异。在 32 32 32 位机上,地址用 32 32 32 位二进制整数表示,因此一个指针的大小为 4 4 4 字节。而 64 64 64 位机上,地址用 64 64 64 位二进制整数表示,因此一个指针的大小就变成了 8 8 8 字节。
针对不同类型的数据,指针也有不同的类型。比如,int
类型的指针,其中存储的地址对应一块大小为
32
32
32 位的空间的起始地址;有 char
类型的指针,其中存储的地址对应一块
8
8
8 位的空间的起始地址。
事实上,用户也可以声明指向指针的指针。多重指针会产生很多复杂的关系,所以在算法竞赛中使用得很少,这里仅作了解。
2.声明与使用
C/C++ 中,指针的类型为类型名后加上一个星号 *
。比如,int
类型的指针的类型名即为 int*
。
我们可以使用 &
符号取得一个变量的地址。
要想访问指针地址所对应的空间(又称指针所指向的空间),需要对指针变量进行解引用,使用 *
符号。
int a = 123;
int* p = &a;
*p = 321;
对结构体变量也是类似。如果要访问指针指向的结构中的成员,有两种写法,但实际应用中通常使用前一种写法。
- 使用箭头运算符
->
。 - 先对对指针进行解引用,再使用
.
成员关系运算符。
struct node
{
int a;
int b;
};
int main()
{
node x = {1, 2}, y = {3, 4};
node* p = &x;
*p = y;
p->a = 5;
(*p).b = 6;
return 0;
}
空指针通常用 NULL
来表示,或者是 nullptr
,二者是等价的。
3.指针的偏移
指针变量也可以进行加减操作(因为其实质是地址)。对于 int
型指针,每加
1
1
1,其指向的地址偏移
4
4
4 字节。同理,对于 char
型指针,每次递增,其指向的地址偏移
1
1
1 字节。
数组是存储在一块连续的空间中的,而数组名就是数组第一个元素的地址。当通过指针访问数组中的元素时,往往需要用到指针的偏移,换句话说,即通过一个基地址(数组起始的地址)加上偏移量来访问。
int main()
{
int a[3] = {1, 2, 3};
int* p = a; // p 指向 a[0]
*p = 4; // {4, 2, 3}
p = p + 1; // p 指向 a[1]
*p = 5; // a: [4, 5, 3]
}
我们常用 []
运算符来访问数组中某一指定偏移量处的元素。比如 a[3]
或者 p[4]
。这种写法和对指针进行运算后再引用是等价的,即 p[4]
和 *(p + 4)
是等价的。
4.指针在函数中的使用
默认情况下,函数仅能通过返回值,将结果返回到调用处。但是,如果某个函数希望修改外部数据,或某个结构体较大,则可以通过向其传入外部数据的地址,便得以在其中访问甚至修改外部数据。这就是函数调用的地址传递。
下面的 my_swap
方法,通过接收两个 int
型的指针,在函数中使用中间变量,完成对两个 int
型变量值的交换。
void my_swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int a = 6, b = 10;
my_swap(&a, &b);//a 变为 10,b 变为 6
return 0;
}
C++ 中引入了引用的概念,相对于指针来说,更易用,也更安全。
二、动态分配内存
1.基本使用
程序编写时往往会涉及到动态内存分配,即,程序会在运行时,向操作系统动态地申请或归还存放数据所需的内存。当程序通过调用操作系统接口申请内存时,操作系统将返回程序所申请空间的地址。要使用这块空间,我们需要将这块空间的地址存储在指针变量中。
在 C++ 中,我们使用 new
运算符来获取一块内存,使用 delete
运算符释放某指针所指向的空间。
int* p = new int(1234);
/*
...
*/
delete p;
上面的语句使用 new
运算符向操作系统申请了一块 int
大小的空间,将其中的值初始化为 1234,并声明了一个 int
型的指针 p
指向这块空间。
需要注意,当使用 new
申请的内存不再使用时,需要使用 delete
释放这块空间。不能对一块内存释放两次或以上。而对空指针 NULL
或 nullptr
使用 delete
操作是合法的。
2.动态创建数组
也可以使用 new[]
运算符创建数组,这时 new[]
运算符会返回数组的首地址,也就是数组第一个元素的地址,我们可以用对应类型的指针存储这个地址。释放时,则需要使用 delete[]
运算符。
size_t element_cnt = 5;
int *p = new int[element_cnt];
delete[] p;
数组中元素的存储是连续的,即 p + 1
指向的是 p
的后继元素。
3.二维数组
实际使用中,二维数组的大小可能不是固定的,需要动态内存分配。动态的二维数组有三种生成方式。
(1)一维数组模拟
常见的方式是声明一个长度为
N
×
M
N × M
N×M 的 一维数组,并通过下标 r * M + c
访问二维数组中下标为 (r, c)
的元素。
int* a = new int[N * M];
这种方法可以保证二维数组是连续的。
(2)数组的数组
此外,亦可以根据数组的数组这一概念来进行内存的获取与使用。对于一个存放的若干数组的数组,实际上为一个存放的若干数组的首地址的数组,也就是一个存放若干指针变量的数组。
我们需要一个变量来存放这个数组的数组的首地址。这个变量便是一个指向指针的指针,有时也称作二重指针,如:
int** a = new int* [5];
接着,我们需要为每一个数组申请空间:
for (int i = 0; i < 5; i++)
a[i] = new int[5];
至此,我们便完成了内存的获取。而对于这样获得的内存的释放,则需要进行一个逆向的操作:即先释放每一个数组,再释放存储这些数组首地址的数组,如:
for (int i = 0; i < 5; i++)
delete[] a[i];
delete[] a;
需要注意,这样获得的二维数组,不能保证其空间是连续的。
(3)指向数组的指针
还有一种方式,需要使用到指向数组的指针。
int main()
{
int(*a)[5] = new int[5][5];
int* p = a[2];
a[2][1] = 1;
delete[] a;
return 0;
}
这种方式获得到的也是连续的内存,但是可以直接使用 a[n]
的形式获得到数组的第
n
+
1
n+1
n+1 行的首地址,因此,使用 a[r][c]
的形式即可访问到下标为 (r, c)
的元素。
由于指向数组的指针也是一种确定的数据类型,因此除数组的第一维外,其他维度的长度均须为一个能在编译器确定的常量。不然,编译器将无法翻译如 a[n]
这样的表达式(a
为指向数组的指针)。
三、链表
1.基本介绍
链表是一种用于存储数据的数据结构,通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便,但寻找与读取数据的表现欠佳。
链表和数组都可用于存储数据。与链表不同,数组将所有元素按次序依次存储。不同的存储结构令它们有了不同的优势:
-
链表删除和插入数据的时间复杂度是 O ( 1 ) O(1) O(1)。寻找、读取数据的时间复杂度是 O ( n ) O(n) O(n)。
-
链表删除和插入数据的时间复杂度是 O ( n ) O(n) O(n)。寻找、读取数据的时间复杂度是 O ( 1 ) O(1) O(1)。
2.链表的结构
单向链表中,每一个结点包含数据域和指针域,其中数据域用于存放数据,指针域用来连接当前结点和下一节点。单向链表需要一个头结点作为起点。
双向链表比单向链表多一个指向上一个结点的指针域。双向链表需要一个头结点和一个尾结点进行标识。
3.链表的运用
下面以双向链表为例讲解链表的构造和操作方式。
(1)定义
//指针
struct node
{
ll value;
node *prev, *next;
};
node *head, *tail;
void init()
{
head = new node();
tail = new node();
head -> next = tail;
tail -> prev = head;
}
//数组模拟
struct node
{
ll val;
node *prev, *next;
}New[maxn];
ll head, tail, tot;
int init()
{
tot = 2;
head = 1;
tail = 2;
head.next = tail;
tail.prev = head;
}
(2)插入
//指针
void insert(node *p, ll val)
{
node q = new node();
q -> value = val;
p -> next -> prev = q;
q -> next = p -> next;
p -> next = q;
q -> prev = p;
}
//数组
void insert(ll p, ll val)
{
ll q = ++tot;
New[q].value = val;
New[New[p].next].prev = q;
New[q].next = New[p].next;
New[p].next = q;
New[q].prev = p;
}
(3)删除
//指针
void remove(node *p)
{
p->prev->next = p -> next;
p->next->prev = p -> prev;
delete p;
}
//数组
void remove(ll p)
{
New[New[p].prev].next = New[p].next;
New[New[p].next].prev = New[p].prev;
}
(4)回收
//指针
void recycle()
{
while(head != tail)
{
head = head -> next;
delete head -> prev;
}
delete tail;
}
//数组
void recycle()
{
memset(New,0,sizeof(New));
head = tail = tot = 0;
}
四、作业
原文地址:https://blog.csdn.net/qq_40760407/article/details/143063220
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!