看csp j选择的时候看到链表题,那就来写一写吧
什么是链表
首先我们知道数组:
链表和数组有点像,他是这样的:
1----->2------->3------->4
链表中每个数据都有一个指针,指着自己的下一项数据是哪一个
比如上面:1的箭头指向2,2的箭头指向3
这样有一个好处,我们删除/添加一个数据是很快的,只要修改一些数据的指针就好了
比如我们往1和2之间加个100,我们需要写这样的代码就可以完成:
100的指针指向 1的下一项;
1的下一项=100
如果是数组要完成这个操作,我们就需要移动很多数字,很麻烦
这就是链表的好处,快速修改数据,他的缺点就是没有数组的下标,按下标找数据不方便
双向链表
刚刚我们讲到的就是单向链表,数据的指针只指着自己下一个,双向链表是这样的:
<-----1------> <------2--------> <------3--------> <------4-------->
双向链表是一个数据有两个指针,一个指向自己前面的数据,一个指向自己后面的数据
例题
整个csp j 选择题做,检查你们的学习成果:
(没看懂题目的看过来,p->next代表p下一项,p->prev代表p上一项,p->next->prev表示p的下一项的上一项(也就是下面给出的链表中e的上一项))
做这个题我们要注意,我画个图给你们看:
假设双向链表长这样:
a b c d p (s) e f g
我们要注意abcd选项中语句的顺序,我们需要修改e的prev,但想要得到e,我们需要用p->next
所以我们不应该先修改p->next,而是先修改p->next->prev,这样才不会出错
写完了
空洞骑士太好玩了