C语言：数据结构之单链表（三）寻技术

　　上篇谈了谈尾插法和头插法，这篇谈谈中间插入元素和删除。

　　1、中间插入元素

　　既然谈到了要从中间插入那就得确定插入的位置是否合法了，我总不能链表总长为5，但是插入的位置是60，这就不对了。所以得先确定这个链表的长度为多少。这个比较简单，就是在寻找尾部的过程中计数，直到走到最后一个节点。

　　代码如下：

int Get_Length(LinkList header)
{
    LinkList p = header->next;
    int i = 0;
    while(p != NULL)
    {
        p = p->next;
        i++;
    }
    return i;
}

　　头结点记为0，首元结点开始计数为1，再往后就是2,3,4等等。

　　在确定了链表长度以后，就得开始想办法往里插入元素了，方法如图。

　　从这儿就已经可以看出和头结点有异曲同工之妙了。

　　思路又来了：

　　①新建一个结点。（老规矩）

　　②找到一个结点，然后准备将新结点放在这个结点后面。

　　③开始插入新结点：改变找到的结点的next的指针，将其指向新结点，然后将新结点的next指向找到的结点的原next。（有些拗口，结合图片应该是好理解些）

　　下面开始写代码，咱们现在①和③都明白，主要是这个找该怎么整，简单想一想就是想找的位置和遍历的当前位置是否相等，这也算是增删改查的查了。

　　代码如下：（对越界行为做特殊处理）

LinkList Search_Site(LinkList header, int site_)
{    
    int i = 1;
    LinkList p = header->next;
    if(site_ == 0)
    {
        return header;
    }

    if(site_ > Get_Length(header))
    {
        printf("more than now.\n");
        return NULL;
    }

    if(site_ >= 1 && site_ <= Get_Length(header))
    {    
        while(site_ != i)
        {
            p = p->next;
            i++;
        }
    }

    return p;
}

　　先对上述函数进行验证main函数如下：

int main()

{
    printf("This is Struct_Data:\n\n");

    LinkList head = Init_linklist();

    AddLetter_Tail(head,'H');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,',');
    AddLetter_Tail(head,'L');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,'n');
    AddLetter_Tail(head,'u');
    AddLetter_Tail(head,'x');
    AddLetter_Tail(head,'.');
    PrintList(head);
    printf("len: %d\n",Get_Length(head));    

    printf("Search2:%c  \n",Search_Site(head,2)->letter);
    printf("search9:%c  \n",Search_Site(head,9)->letter);
    printf("search1:%c  \n",Search_Site(head,1)->letter);
    printf("search3:%c  \n",Search_Site(head,3)->letter);
    printf("\n");
    printf("len: %d\n",Get_Length(head));    

    return 0;
}

　　效果如下：

　　发现没有毛病٩(๑❛ᴗ❛๑)۶

　　在链表中间加入新元素：

void Add_Inster(LinkList header, int site_, char letter_)
{
    LinkList p = Search_Site(header,site_);
    LinkList q = (LinkList)malloc(sizeof(LNode));
    q->letter = letter_;
    q->next = p->next;
    p->next = q;
}

　　main函数如下：（在4,4,9的位置插入元素）

int main()

{
    printf("This is Struct_Data:\n\n");

    LinkList head = Init_linklist();

    AddLetter_Tail(head,'H');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,',');
    AddLetter_Tail(head,'L');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,'n');
    AddLetter_Tail(head,'u');
    AddLetter_Tail(head,'x');
    AddLetter_Tail(head,'.');
    PrintList(head);
    printf("len: %d\n",Get_Length(head));

    printf("Add_Inster 4,4,9\n ");
    Add_Inster(head,4,'-');
    Add_Inster(head,4,'?');
    Add_Inster(head,9,'<');
    PrintList(head);
    printf("len: %d\n",Get_Length(head));    

    return 0;
}

　　效果如下：

　　2、下面就是删除操作了，这个有一丢丢麻烦，因为要抹掉链表中的一个结点，那就涉及指针重新指向和释放内存（因为新建结点是申请出来的，不要它的话自然就得free掉了）了。

　　先看图，主观上就是找到这个结点扔掉，然后再续上。仔细一想会出现问题，比如我想删掉C，也就是第三个，找到之后应该利用第二个指向第四个，但是我们不知道第二个的地址，所以要想删除第三个得寻找到第二个然后再改变指针指向。

　　代码如下：

void Delete(LinkList header,int site_)
{
    if(site_ < 1 || site_ > Get_Length(header))
    {
        printf("delete error.\n");
        return;
    }    

    else
    {
        LinkList p = Search_Site(header,site_ - 1);
        LinkList q = p->next;
        p->next = q->next;

        free(q);
    }
}

　　main函数代码如下：（删除第6,3,2,1位）

int main()

{
    printf("This is Struct_Data:\n\n");

    LinkList head = Init_linklist();

    AddLetter_Tail(head,'H');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,',');
    AddLetter_Tail(head,'L');
    AddLetter_Tail(head,'i');
    AddLetter_Tail(head,'n');
    AddLetter_Tail(head,'u');
    AddLetter_Tail(head,'x');
    AddLetter_Tail(head,'.');
    PrintList(head);
    printf("len: %d\n",Get_Length(head));    

    printf("Delete 6,2,3,1\n");
    Delete(head,6);
    Delete(head,2);
    Delete(head,3);
    Delete(head,1);
    PrintList(head);
    printf("len: %d\n",Get_Length(head));    

    return 0;
}