指针与链表
各位CTFer可以忽略这篇文章~
各位CTFer可以忽略这篇文章~
各位CTFer可以忽略这篇文章~
指针
指针的定义
指针对于变量来讲就像单人间的宿舍号一样。每个人(变量)都会有唯一的宿舍(地址),宿舍号(指针)可以迅速帮我们定位每个人(变量)。而指针变量是专门用来存放某变量的地址的变量。
定义语法
int *p1;
char *p2 = NULL; //将p2指向空,称为空指针
long long *p3 = # //将p3指向num的地址
...
要注意:
int *p1, p2;
这句话的意思是p1为一个指向int类型变量的指针变量,而p2是一个int类型的变量。如果希望p2也是指针,需要在p2前面也加上*。通常编辑器会将int和*连在一起,而*和p1分开,像:
int* p1, p2;
char* p3;
在写的时候注意一下就先行,反正我不喜欢这样。
使用语法
以下是对指针的赋值和调用的一些例子:
int array[100];
int a = 100;
int *p = NULL; //不进行初始化的指针称作“野指针”,调用野指针上的值会出大问题,注意和前文空指针的区别
p = &a; //将p指向a的地址
printf("%d\n", *p); //输出p中的地址上的变量的值,即a的值100
printf("%p\n", p); //输出p中的地址
printf("%p", array);//输出array[0]的地址
a = a + *p; //将a加上p中的地址上的变量的值,即a = a + a;
*代表取某地址上的值,&代表取某变量的地址。
通过上述代码我们可以发现指针没什么卵用甚至很麻烦,让我们看一看它在函数中的用途:
void func(int p)
{
p++;
return;
}
int main()
{
int a = 100;
printf("%d ", a); //输出100
func(a);
printf("%d ", a); //输出100
return 0;
}
void func(int *p) //将p指向传入的地址
{
(*p)++; //注意*和++的运算优先级
return;
}
int main()
{
int a = 100;
printf("%d ", a); //输出100
func(&a); //传入a的地址
printf("%d ", a); //输出101
return 0;
}
通常来讲,如果不定义全局变量,一个函数是无法修改其他函数中的变量的。但是上面两段代码告诉了我们,如果使用指针我们便可以实现跨函数修改变量。
总的来说,如果*p是一个指针变量,那么p代表地址,*p代表该地址上的值。
再进一步
int a = 0x1234; //0x代表16进制
int *p1 = &a;
char *p2 = (char *)&a; //将&a从int*转换成char*
printf("%x %x", *p1, *p2); //输出1234 34,其中%x代表16进制int数
对于上述代码我们发现同样是指针,仅仅是转换了指向对象的类型就会使得输出造成巨大的差别。这是为什么呢?
这是因为int类型的变量在内存中占据32位(称为32 bit或者4 byte)的空间,即转成二进制之后长度不能超过32,而char类型的变量只占据8位。因此,当我们将&a从int*转成char*后,只会保留后8位。再加上神奇的16进制数每一个数字占4位的特性,恰好就是后两位16进制数。
int a[10] = {5, 4, 3, 2, 1};
int *p;
for(p = a; p < a + 5; p++)
{
printf("%d ", *p); //输出5 4 3 2 1
}
通过上述代码,我们发现数组的名字就是数组首元素的地址;(数组名字+i)就是数组第i个元素的地址。
链表
链表的定义
链表顾名思义就是串成一条线的元素。这看起来跟数组很像,直接用数组不好吗?
事实上,链表的优势在对大量数据的增删改查。比如一个数组有1000万个元素,我要删掉中间那一个,那么就得把后500万个元素全都向前移一位。但链表仅需要单纯的删掉就可以了。
链表的结构
链表上的元素我们称之为“节点”,每个节点分为数据域和指针域
head | node | node | node | node | node | tail | |
---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
数据域 | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | NULL |
我们可以发现节点的指针域都指向下一个元素,尾元素指向NULL。在代码实现过程中节点编号是不存在的,此处仅为了方便展示。
如果我们想在上述链表尾部添加一个节点,可以分成3步:
第1步:构造当前节点
head | node | node | node | node | node | tail | new | |
---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
数据域 | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | NULL | NULL |
第2步:尾标识的指针指向当前节点
head | node | node | node | node | node | tail | new | |
---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
数据域 | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | NULL |
第3步:尾标识改为当前节点
head | node | node | node | node | node | node | tail | |
---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
数据域 | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | NULL |
如果我们想在上述链表中间添加一个节点,也可以分成3步:
第1步:构造当前节点
head | node | node | node | node | node | node | tail | new | |
---|---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
数据域 | num | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | NULL | NULL |
第2步:修改当前节点的指针
head | node | node | node | node | node | node | tail | new | |
---|---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
数据域 | num | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | NULL | 4 |
第3步:修改插入位置(3)的指针
head | node | node | node | node | node | node | tail | node | |
---|---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
数据域 | num | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 8 | 5 | 6 | 7 | NULL | 4 |
整理一下可以变成更好看的模样:
head | node | node | node | node | node | node | node | tail | |
---|---|---|---|---|---|---|---|---|---|
节点号 | 0 | 1 | 2 | 3 | 8 | 4 | 5 | 6 | 7 |
数据域 | num | num | num | num | num | num | num | num | num |
指针域 | 1 | 2 | 3 | 8 | 4 | 5 | 6 | 7 | NULL |
我们可以类似地进行增删改查等操作。
定义语法
struct NODE
{
int data;
struct NODE *next;
};
其中data为数据域,*next为指针域。下面为先输入n再输入n个数,并构建一条链表的代码。
int i, n, temp;
NODE *head = NULL, *tail = NULL;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
struct NODE *node;
node = (NODE *)malloc(sizeof(NODE)); //动态申请内存
scanf("%d", &temp);
node->data = temp; //构造当前节点,也就是尾节点
node->next = NULL; //构造当前节点,也就是尾节点
if(head == NULL) //如果链表里啥都没有
{
head = node; //将头、尾标识都改为当前节点
tail = node; //将头、尾标识都改为当前节点
}
else //如果链表里有东西
{
tail->next = node; //尾标识的指针指向当前节点
tail = node; //尾标识改为当前节点
}
}
对于上述代码,可以发现我们虽然创建了一条链表,但是它好像看不见摸不着,不像数组一样可以知道它的名字,访问具体元素等。的确,链表的访问只能通过从首节点开始遍历,但如果结合二叉树等数据结构,将会大大降低这个过程所花费的时间。
同时,构造链表的时候只能一个一个节点地申请内存,因为没人知道到底应当开多大。
链表的增删改查
基础样式如下:
以下代码中头节点算作第1个节点
void add(NODE *tail, NODE *node) //在链表尾部插入新节点
{
tail->next = node;
tail = node;
}
void del(NODE *head, int x) //删除第x个节点,不能是头节点
{
int i;
NODE *current = head;
for(i = 2; i < x; i++)
{
current = current->next;
}
current->next = current->next->next;
}
void change(NODE *head, int x, int y) //将第x个节点的data改为y
{
int i;
NODE *current = head;
for(i = 1; i < x; i++)
{
current = current->next;
}
current->data = y;
}
int search(NODE *head, int x) //查找data是x的节点,返回第一个这样的节点的编号
{
int i;
NODE *current = head;
for(i = 1; current->next != NULL; i++)
{
if(current->data == x)
{
return i;
}
current = current->next;
}
if(current->data == x)
{
return i;
}
return -1;
}
基于上述代码我们可以发现对于链表的遍历都是以节点进行的。
小作业?
1.读代码写结果(不要让计算机帮你读哦):
#include <stdio.h>
int main()
{
int a = 0x123456, b = 0xabcdef;
int t;
t = *((char *)&a + 1);
*((char *)&a + 1) = *((char *)&b + 2);
*((char *)&b + 2) = t;
printf("%x %x", a, b);
return 0;
}
2.读代码写结果(不要让计算机帮你读哦):
输入:
5
1 2
2 3
3 4
4 5
5 6
3
1 3
2 3
5 6
#include <stdio.h>
#include <cstdlib>
struct NODE
{
int month;
int date;
NODE *next;
};
int main()
{
NODE *head = NULL, *tail = NULL, *current;
int i, j, n, m, tm, td;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
NODE *node;
node = (NODE *)malloc(sizeof(NODE));
node->next = NULL;
scanf("%d%d", &(node->month), &(node->date));
if(head == NULL)
{
head = node;
tail = node;
}
else
{
tail->next = node;
tail = node;
}
}
scanf("%d", &m);
for(i = 0; i < m; i++)
{
scanf("%d%d", &tm, &td);
NODE *node = head;
int isFind = 0;
for(j = 1; node->next != NULL; j++)
{
if(node->month == tm && node->date == td)
{
printf("%d ", j);
isFind = 1;
}
node = node->next;
}
if(node->month == tm && node->date == td)
{
printf("%d ", j);
isFind = 1;
}
if(isFind == 0)
{
printf("-1 ");
}
}
return 0;
}
3.按要求写代码
构造一个函数,传入头节点head,目标编号x和新建节点node。使得新建节点插入在第x个节点后面。头节点视为第0个节点。