关于数据结构问题？

Question

关于单链表第i个数据删除节点的算法怎么理解？ 我说一下我目前对该算法的理解。示意图如下，在该算法q=p->next；之前的内容是使指针变量p遍历链表，直到找到第i个结点元素。假设它找到了，*p指针也是指向的a(i)结点，为什么后面的删除操作要把p当作指向a(i-1)结点？

•  

• 

• 
  

• 
  

Answer 1

链表是有头结点的，而头结点在第一个节点之前，如你图中所画，假如a[i]为第一个元素，那么a[i-1]就是头指针，头指针里面不存放数据。假设你要找第1个节点，while(p->next && j < i)，这个循环退出的条件是p->next为NULL或j==i，刚开始j=1，p指向的是头节点，这个时候如果第一个节点不存在（即链表为空），则有p->next为空（头结点没有后继节点）；如果第一个节点存在则一定有j==i（i为1）成立，这个时候p指向的仍然是头结点，所以就有下面的q=p->next，这个q就是第i个节点，只不过推迟执行了一步。另外，书上那份代码有点小问题，中间的判断if(!(p->next) || j > i)当中的j>i完全是多余的，因为从第一个while循环结束时，j最多等于i，不会大于i。