struct Node;

typedef struct Node * PNode;

struct Node{

    DataType info;

    PNode link;

};

typedef struct Node * LinkList;
//很明显我们定义的结点指针类型和单链表的类型实际上是一样的东西
//后续的代码暂时与书上的内容保持一致，均使用有头结点的链表
//总结过后再将不带头结点的单链表实现补上

LinkList creatNullList_link(void){

    LinkList llist = (LinkList)malloc(sizeof(struct Node));　　//创建一个指向Node类型的指针llist

    if(llist != NULL)      llist->link = NULL;　　//将其指向为空，也就是链表末尾

    else    printf("OUTOFSPACE!");

    return llist;    //看上面的代码后可知，llist可能为空，所以后面其他的函数经常会先判断了llist的情况

}

int isNullList_link(LinkList llist){

    return (llist->link == NULL);

}
//判断链表是否为空的代码比较简单

PNode locate_link(LinkList llist,DataType x){

    PNode p;

    if (llist == NULL)    return NULL;　　

    p = llist->link;

    while(p != NULL && p->info != x)    p = p->link;

    return p;

}
//为什么要判断llist是否为空而不是判断llist->link是否为空？
//如果llist为空，那使用llist->link不就是对一个空指针操作了吗，记得学指针的时候书上的一句话嘛，千万不要用没有初始化的指针，这里如果其指向为空，那llist->link也就不知道指向哪里

int insertPost_link(LinkList llist,PNode p,DataType x){
　　PNode q = (PNode)malloc(sizeof(struct Node));
　　if (q == NULL){
　　　　printf("OUTOFSPACE");
　　　　return 0;
　　}　
　　q->info = x;
　　q->link = p->link;
　　p->link = q;
　　return 1;

}//下图为操作顺序，操作顺序不能反
//这一个方法是不需要用到llist

int insertPre_link(LinkList llist,PNode p,DataType x){
　　PNode r;
　　PNode q = (PNode)malloc(sizeof(struct Node));
　　if(q == NUll){
　　　　printf("OUTOFSPACE");
　　　　return 0;
　　}
　　r = locatePre_link(llist,p);
　　q->info = x;
　　q->link = r->link;
　　r->link = q;
　　reutrn 1;
}
//找p结点的前驱结点
PNode locatePre_link(LinkList llist,PNode p){
　　PNode p1;
　　if (llist == NULL)　　return NULL;
　　p1 = llist;
　　while(p1->link!=NULL && p1->link==p){
　　　　p1 = p1->link;
　　}
　　reutn p1;
}
//感觉这个难一点的就是前驱结点的查找，p1->link!=NULL && p1->link == p是这个找前驱结点的灵魂

int deleteV_link(LinkList llist,DataType x){
　　//不展示的方法：前面有一个定位方法，找到元素x的结点p，然后前面还有一个找前驱结点的方法，然后就可以执行删除操作了
　　//下面是书上的方法
　　PNode q,p;
　　p = llist;
　　if (p == NULL)　　return 0;
　　while(p->link!=NULL && p->link->info==x) p = p->link;
　　//p是要删除结点的前驱结点
　　if (p->link == NULL){
　　　　printf("NOT EXIST!");
　　　　return 0;
　　}
　　else{
　　　　q = p->link;
　　　　p->link = q->link;
　　　　//也可以是p->link = p->link->link
　　　　free(q);
　　　　return 1;
　　}
}