关于<<数据结构>>严蔚敏 p38页,算法2.20的疑问: Status listinsert_L(linklist &L,int i,Elemtype e)...

Question

关于<<数据结构>>严蔚敏 p38页,算法2.20的疑问:
Status listinsert_L(linklist &L,int i,Elemtype e) //插值函数
{ if(!locatpos(L, i-1, h)) return fail; i值不合法
if(!Makenode(s, e)) reture fail; 储存分配失败
Insfirst(h, s);插入节点
Return turn;
}
疑问:在单链表中,每个节点只指示其直接后继.在第i个元素前插入元素(设其为s),则有s.next=i.但是,第i-1个元素的next域却未指向s.那么上述算法则存在问题.除非insfirst函数里有处理.请问高手的看法,谢谢.
上述算法的具体实现中,应该会有问题.所以,请给出您的改进意见.
如果您有什么好的看法,请发短信至15984837842或[email protected]
我期待与更多高手交流切磋.

Answer 1

严老师此书该算法有问题，InsertFirst(h,s)之前被定义为在将s插入在头结点之后（原文：已知h指向线性链表头结点，将s结点指向的结点插入在第一个结点之前）其中h已说明为头结点指针，可见不是元素结点指针，既然是头结点指针其实就是LinkList*。但是在ListInsert_L（&L，i，e）中是需要将e插入在第i个位序尚，所以应该将InsertFirst（h，s）替换为InsertAfter(&L,&h,s)（此函数被定义为将s结点插入在h结点之后）这里h是位序为i-1的结点，s是新的i结点

Answer 2

貌似没问题：
locatpos(L, i-1, h）; //找到i-1,指针为h
Makenode(s, e)) //表示创建值为e的节点，指针为s
Insfirst(h, s) //将s插入到h后面，即i的前面
你所担心的，其实可以通过locatpos函数来实现本回答被提问者采纳

Answer 3

Insfirst(h, s);已经包含了
1.找到第i-1个节点
2.s.next=(i-1).next
3.(i-1).next=s.next //从头结点开始找
如果已经知道指针指向i节点则不必再从头找第i-1个节点，在i节点后插入s，再把s和i中的数据交换即可