快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解

更新時間：2022年07月27日 15:11:09 作者：代碼騎士

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語言中單鏈表的常用操作，感興趣的可以學(xué)習(xí)一下

1、插入操作

（1）創(chuàng)建一個新的要插入的結(jié)點

（2）將新結(jié)點的 next 指針指向插入位置后的結(jié)點

（3）將插入位置前的節(jié)點指針 next 指向新的結(jié)點

注意：步驟（2）（3）的順序不能顛倒，否則會導(dǎo)致插入位置后的部分鏈表丟失。

插入位置一共分三種，分別是頭部插入、中間插入和尾部插入。

如圖：

代碼：

link* insertElem(link* p,int elem,int pos){
    link* temp = p;//創(chuàng)建臨時結(jié)點temp
    //首先找到插入位置的上一個結(jié)點
    for(int i=1;i<pos;i++){
        temp=temp->next;
        if(temp==NULL){
            printf("插入位置無效\n");
            return p;
        }
    } 
    //創(chuàng)建插入結(jié)點c
    link *c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向鏈表中插入結(jié)點
    c->next = temp->next;
    temp->next=c;
    return p; 
}

2、刪除操作

（1）將結(jié)點從鏈表中摘下

temp->next=temp->next->next

（2）手動釋放掉結(jié)點，回收被結(jié)點占用的存儲空間

如圖：

代碼：

link*delElem(link*p,int pos){//p是原鏈表，pos是要刪除的元素值 
    link* temp=p;
    //遍歷到被刪除結(jié)點的上一個結(jié)點 
    for(int i =1;i<pos;i++){
        temp=temp->next;
        if(temp->next==NULL){
            printf("沒有該結(jié)點\n");
            return p;
        }
    } 
    link*del=temp->next;//單獨開辟一塊空間存放被刪結(jié)點
    temp->next=temp->next->next;//從鏈表中摘除被刪結(jié)點
    free(del);//手動釋放該結(jié)點防止內(nèi)存泄漏
    return p; 
}

3、查找操作

從頭遍歷鏈表。

int searchElem(link* p,int elem){
    //新建一個指針t，初始化為頭指針 p
    link*t=p;
    int i=1;
    //由于頭節(jié)點的存在，因此while中的判斷為t->next
    while(t->next){
        t=t->next;
        if(t->elem==elem){
            return i;
        }
        i++;
    }
    //程序執(zhí)行至此處，表示查找失敗
    return -1;
}

4、修改操作

先找到目標(biāo)位置再更改結(jié)點的數(shù)據(jù)域。

link* changeElem(link* p,int pos,int newElem){
    link* temp=p;
    temp=temp->next;//在遍歷之前，temp指向首元結(jié)點
    //遍歷到待更新結(jié)點
    for(int i=1;i<pos;i++){
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
}

5、完整代碼

#include<stdio.h>
#include<stdlib.h>
 
typedef struct Link{
    int elem;//數(shù)據(jù)域 
    struct Link *next;//指針域，用來連接后繼元素 
}link;//link為節(jié)點名，每個結(jié)點都是一個link結(jié)構(gòu)體 
 
link* initLink(){
    link *p=(link*)malloc(sizeof(link));//創(chuàng)建頭結(jié)點
    link*temp = p;//聲明一個指針temp指向頭結(jié)點，也就是頭結(jié)點的地址賦值給指針變量(注意這不是頭指針而是用來連接數(shù)組的臨時指針變量)
    //生成鏈表
    for(int i=1;i<5;i++)
    {
        link *a=(link*)malloc(sizeof(link));//生成一個結(jié)點 
        a->elem=i;//給結(jié)點的數(shù)據(jù)域賦值
        a->next=NULL;//指針域設(shè)置為空 
        temp->next=a;//上一個結(jié)點的指針指向新增結(jié)點 
        temp=temp->next;//臨時指針向后移動也可寫成temp=a 
    } 
    //返回頭結(jié)點，通過頭節(jié)點的指針即可找到整個鏈表
    return p;
} 
 
link* insertElem(link* p,int elem,int pos){
    link* temp = p;//創(chuàng)建臨時結(jié)點temp
    //首先找到插入位置的上一個結(jié)點
    for(int i=1;i<pos;i++){
        temp=temp->next;
        if(temp==NULL){
            printf("插入位置無效\n");
            return p;
        }
    } 
    //創(chuàng)建插入結(jié)點c
    link *c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向鏈表中插入結(jié)點
    c->next = temp->next;
    temp->next=c;
    return p; 
}
 
link* delElem(link*p,int pos){//p是原鏈表，pos是要刪除的元素值 
    link* temp=p;
    //遍歷到被刪除結(jié)點的上一個結(jié)點 
    for(int i =1;i<pos;i++){
        temp=temp->next;
        if(temp->next==NULL){
            printf("沒有該結(jié)點\n");
            return p;
        }
    } 
    link*del=temp->next;//單獨開辟一塊空間存放被刪結(jié)點
    temp->next=temp->next->next;//從鏈表中摘除被刪結(jié)點
    free(del);//手動釋放該結(jié)點防止內(nèi)存泄漏
    return p; 
}
 
link* changeElem(link* p,int pos,int newElem){
    link* temp=p;
    temp=temp->next;//在遍歷之前，temp指向首元結(jié)點
    //遍歷到待更新結(jié)點
    for(int i=1;i<pos;i++){
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
} 
 
int searchElem(link* p,int elem){
    //新建一個指針t，初始化為頭指針 p
    link*t=p;
    int i=1;
    //由于頭節(jié)點的存在，因此while中的判斷為t->next
    while(t->next){
        t=t->next;
        if(t->elem==elem){
            return i;
        }
        i++;
    }
    //程序執(zhí)行至此處，表示查找失敗
    return -1;
} 
 
void display(link *p){
    link*temp=p;//將temp指向頭結(jié)點
    printf("鏈表中的數(shù)據(jù)為 : "); 
    //只要temp指針指向的結(jié)點的next不是Null，就執(zhí)行輸出語句。
    while(temp->next){
        temp=temp->next;
        printf("%d ",temp->elem);
    } 
    printf("\n");
} 
 
int main()
{
    //初始化鏈表
    link *p = initLink();
    display(p); 
    printf("在第4的位置插入元素5：\n");
    p = insertElem(p, 5, 4);
    display(p);
    printf("刪除元素3:\n");
    p = delElem(p, 3);
    display(p);
    printf("查找元素2的位置為：\n");
    int address = searchElem(p, 2);
    if (address == -1) {
        printf("沒有該元素");
    }
    else {
        printf("元素2的位置為：%d\n", address);
    }
    printf("更改第3的位置上的數(shù)據(jù)為7:\n");
    p = changeElem(p, 3, 7);
    display(p);
    return 0;
}

輸出結(jié)果：