Question

写一算法，在带头结点的单链表llist中，p所指结点前面插入值为x的新结点，并返回插入成功与否的标志。

Answer 1

【答案】：(1)数据结构
采用单链表定义。
(2)思路
由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插入。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locate link类似的方式进行搜索。
(3)算法
int insertPre_link(LinkList llist,PNode p,DataType x){
/*在llist带头结点的单链表中，p所指结点前面插入值为x的新结点*/
PNode p1;
if(llist==NULL)return 0;
p1=llist;
while(p1!=NULL&&p1-＞link!=p)p1=p1-＞link;
/*寻找p所指结点的前驱结点*/
if(p1=NULL)return 0;
PNode q=(PNode)malloc(sizeof(struct Node)); /*申请新结点*/
if(q=NULL){printf("Out of space!!!\n");return0;}
q-＞info=x;
q-＞link=p1-＞link;
p1-＞link=q;
return 1;
}