Question

数据结构链表问题

已知L是无表头的单链表，其P结点既不是首元结点，也不是尾元结点，在p结点后插入s结点的语句序列是

Q. 已知L是无表头的单链表，其P结点既不是首元结点，也不是尾元结点，
c.在表首插入s结点的语句序列是----------------
d.在表尾插入s结点的语句序列是----------------

1. P-> next :=s;
2.p-> next :=p-> next-> next;
3.p-> next :=s-> next;
4.s-> next := p-> next;
5.s-> next := L;
6.s-> next := NIL;
7.q := p ;
8.while (p-> next != q ) do p := p-> next;
9.while (p-> next !=NIL) do p := p-> next;
10.p := q;
11.p := L;
12.L := s;
13.L:= P;

c和d答案分别是什么？d我写的是9、1、6，为什么答案给的是11、9、1、6？

Answer 1

c.在表首插入s结点的语句序列是----------------
5.s-> next := L; //s接原来的表头
12.L := s; //将s设为新的表头

d.在表尾插入s结点的语句序列是----------------
11.p := L; //从头开始搜素
9.while (p-> next !=NIL) do p := p-> next; //找到最后一个节点
1. P-> next :=s; //把s接到最后一个节点上
6. s-> next := NIL; //将s设置为表尾。

追问

11.p := L; //从头开始搜素这一步为什么不能省略呢？不是说P是在中间吗？往后查找总会到尾部的

追答

如果省略11的话，第一步p := p-> next;就会将p节点的信息丢失，11其实起的是临时指针的作用。

追问

第一步不是p=L吗？也没有存储p的信息呀，如果少了这一步，为什么会丢失p的信息呢？

追答

这么说的话p是指针，存了P节点的物理内存地址，p指向L后，p的值改为表的第一个元素的地址，然后遍历，也会寻找到原先p节点的地址，然后读p指向节点的内容；如果不指向L，P直接等于P->next，那P中的值改为p节点指向的下一个节点的内存位置，但原先P指向节点的信息还存在，P->before->next也没修改，那原先P指向的节点的信息通过遍历仍能得到。好吧，11这一步不需要也可以的，答案错了。我开始的时候也没细想，只是顺着你给的答案解释了一下，不好意思。