C语言数据结构_链表插入结点或删除结点

向链表插入结点

1、先创建一个新结点，并用指针p指向该结点

2、将q指向结点的next域的值(即q的后继结点的指针)赋值给p指向结点的next域

3、将p的值赋值给q的next域

void insertList(LinkList *list ,LinkList q, ElemType e){
    //向链表中由指针q指出的结点后面插入结点，结点数据为e
    LinkList p;
    p= ( LinkList)malloc(sizeof(LNode) );     //生成一个新结点，由p指向它
    p->data=e;                      //向该结点的数据域赋值e
    if(!*list){
        *list=p;
        p->next=NULL;
    }
    else{
        p->next=q->next;
        //将q指向的结点的next域的值赋值给p指向结点的next域
        q->next=p;
        //将p的值赋值给q的next域
    }
}

上面代码描述了如何在指针q指向的结点后面插入结点的过程。

1、首先生成一个新的结点，大小为sizeof(LNode)，用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。

2、接下来判断链表是否为空。如果链表为空，则将p赋值给list，p的next域的值置为空。否则，将q指向的结点的next域的值赋值给p指向结点的next域，这样p指向的结点就与q指向结点的下一个结点连接到了一起。

3、然后再将p的值赋值给q所指结点的next域，这样就将p指向的结点插入到了指针q指向结点的后面。

从链表中删除结点

从链表中删除结点的3种情形：

1、q所指向的是链表的第一个结点

2、q所指向的结点的前驱结点的指针已知

3、q所指向的结点的前驱结点的指针未知

第1，2种情形可以用下面代码描述：

void delLink(LinkList *list, LinkList r, LinkList q){
    if (q == *list)
        *list=q->next;          //适用于情形一
    else
        r->next=q->next;        //适用于情形二
    free(q);
}

第3种情形使用下面代码进行处理：

//当q所指向的结点的前驱结点的指针未知时，需要先通过链表头指针list遍历链表，找到q的前驱结点的指针，并将该指针赋值给指针变量r，再按照第二种情形去做
void delLink(LinkList *list, LinkList q) {
    LinkList r;
    if(q == list){
        *list=q->next;
        free(q);
    }
    else {
        for(r=*list; r->next != q; r= r->next); //遍历链表，找到q的前驱结点的指针
        if(r->next != NULL){
            r->next = q -> next;
            free(q);
        }
    }
}