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;
}

　　效果圖如下：

　　這篇順便把查也談了一下，下一篇談談最后一個改，比較簡單，就是查到然后改掉就可以了，

　　總結：①中間插入元素的方法和頭插法有些類似，可以做類比對比，但是要注意是否越界問題，

　　　　 ②這些順序都不是死的，只是程式上要多些步驟保存一下地址而已，好比洗掉，也可以先釋放記憶體，前提是先保存好地址，避免找不到next，

　　以上只是本人的理解和所見，如有不同見解和看法，歡迎在評論區批評指正，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/557095.html

標籤：其他

上一篇：一文了解 io.LimitedReader型別

下一篇：返回列表