关于指针
一个比较简单的记忆方法,比如:结点a指向结点b,即a出现在"指向"的前面,那么就把a写在等号"="的左边,
以下示例并未考虑边界情况或特殊情况(如:删除的是最后一个结点)
例如:双向链表的插入操作,在结点p后面插入结点s
双向链表结点定义:
typedef struct DNode{
int data;
struct DNode *pre; //前驱
struct DNode *next; //后继
} DNode;
插入操作前,假设p后面的结点为q,即q=p->next
插入结点后,s位于p和q之间
首先我们先从s结点考虑,让结点s分别指向p和q结点
结点s指向结点q,即s出现在“指向”前面,我们应该写为: s->next = q
结点s指向结点p,即s出现在“指向”前面,我们应该写为: s->pre = p
现在从结点s出发的两个搞定了(虽然不太恰当,但可以将s简单理解为有向图中有向边的弧头),我们再考虑指向结点s的问题:
结点p指向结点s,p出现在“指向”前面,写作:p->next = s
结点q指向结点s,q出现在“指向”前面,写作:q->pre = s
所以在结点p后面插入结点s的重要操作为:
q=p->next
s->next = q
s->pre = p
p->next = s
q->pre = s
删除结点p的操作:
首先先记录下结点p的前驱q: q = p->pre
结点p的后继r:r=p->next
q指向r: q->next = r
r指向q: r->pre = q
释放掉结点p: free(p)