C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單鏈表與雙鏈表的增刪改查操作實(shí)現(xiàn)

更新時(shí)間：2022年07月07日 14:07:38 作者：葉落秋白

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中單鏈表與雙鏈表的增刪改查操作的實(shí)現(xiàn)，相信大家如果搞懂了本文內(nèi)容，應(yīng)對(duì)復(fù)雜的鏈表類(lèi)的題也就能慢慢鉆研了

前言

上篇博客分享了創(chuàng)建鏈表傳入二級(jí)指針的細(xì)節(jié)，那么今天就分享幾個(gè)c語(yǔ)言課程實(shí)踐設(shè)計(jì)吧。這些程序設(shè)計(jì)搞懂了的話相當(dāng)于鏈表的基礎(chǔ)知識(shí)牢牢掌握了，那么再應(yīng)對(duì)復(fù)雜的鏈表類(lèi)的題也就能慢慢鉆研了。學(xué)習(xí)是一個(gè)積累的過(guò)程，想要游刃有余就得勤學(xué)苦練！

單鏈表的增刪改查

(1)項(xiàng)目需求

構(gòu)造帶有頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)初始化、清空和銷(xiāo)毀操作，在兩端插入元素和刪除元素操作并在鏈表中查找操作，在指定位置插入和刪除元素操作，移除元素操作

(2)解決思路
① 定義節(jié)點(diǎn)類(lèi)型，定義單鏈表類(lèi)型，構(gòu)造創(chuàng)建新節(jié)點(diǎn)的函數(shù)。

② 初始化、清空和銷(xiāo)毀操作：初始化操作負(fù)責(zé)將參數(shù)指向的單鏈表類(lèi)型變量初始化為空鏈表。清空操作的作用是將一個(gè)鏈表清空。銷(xiāo)毀操作負(fù)責(zé)銷(xiāo)毀一個(gè)鏈表。

③ 在兩端插入元素和刪除元素操作：包括從鏈表頭部插入和刪除元素，從鏈表尾部插入和刪除元素。

④ 在鏈表中查找操作 : 查找操作用于在參數(shù)指向的鏈表中，查找首個(gè)值等于待插入參數(shù)的元素。并返回結(jié)點(diǎn)的首地址，返回的地址可供使用者修改結(jié)點(diǎn)信息。

⑤ 在指定位置插入和刪除元素操作：插入和刪除元素都涉及到前后位置指針的指向問(wèn)題，有多種解決方案。以插入元素為例，將元素插入指定位置、指定位置之 4前和指定位置之后等。

⑥ 移除元素：用于刪除鏈表中所有滿(mǎn)足某個(gè)條件的元素。刪除單向鏈表中的結(jié)點(diǎn) 需要修改前驅(qū)結(jié)點(diǎn)的指針域，鏈表的首元結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，需要考慮如何處理。

定義結(jié)構(gòu)體以及初始化

typedef struct LinkList //typedef是重命名的含義，此時(shí)LinkList * 和 List 含義一致，都是指向結(jié)點(diǎn)的指針
{
    int data;//數(shù)據(jù)域
    LinkList* next;//指針域
}*List; //指向結(jié)點(diǎn)的指針
//初始化鏈表
void init_List(List &L)
{
    //初始化后鏈表第一個(gè)結(jié)點(diǎn)就是頭結(jié)點(diǎn)
    L = (List)malloc(sizeof(LinkList));//為鏈表分配空間
    L->data = 0;//數(shù)據(jù)域?yàn)榱?
    L->next = NULL;//指針指向空
}
 
//清空鏈表
void clear_List(List &L)
{
    if (L->next != NULL)//如果頭結(jié)點(diǎn)連著的第一個(gè)結(jié)點(diǎn)不為NULL
    {
        L->next = NULL;//置為NULL，此時(shí)鏈表只有頭結(jié)點(diǎn)，相當(dāng)于清空鏈表
    }
    printf("清空鏈表成功");
}
//銷(xiāo)毀鏈表
void destory_List(List &L)
{
    if (L != NULL)//當(dāng)頭結(jié)點(diǎn)不為空時(shí)
    {
        free(L);//刪除頭結(jié)點(diǎn)地址
        L = NULL;//將指針指向NULL，徹底銷(xiāo)毀鏈表
    }
    printf("銷(xiāo)毀鏈表成功");
}

增加結(jié)點(diǎn)

1、頭插

//頭插法
void headAdd_List(List &L)
{
    List ptr = L->next;//ptr指針初始化指向首元結(jié)點(diǎn)，也就是除了頭結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)
    int value = 0;//用來(lái)賦值為插入結(jié)點(diǎn)的data屬性
    printf("輸入頭插的結(jié)點(diǎn)值："); 
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 為待插入結(jié)點(diǎn)
    s->data = value;//將value賦值給s data屬性
    s->next = ptr;//s 指向 ptr，即指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    L->next = s;//L頭結(jié)點(diǎn)指向s,那么現(xiàn)在s結(jié)點(diǎn)就插入
}

2、尾插

//尾插法
void tailAdd_List(List &L)
{
    int value = 0;//用來(lái)賦值為插入結(jié)點(diǎn)的data屬性
    printf("輸入尾插的結(jié)點(diǎn)值：");
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 為待插入結(jié)點(diǎn)
    s->data = value;//將value賦值給s data屬性
    List ptr = L->next;//ptr指針初始化指向首元結(jié)點(diǎn)，也就是除了頭結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)
    if (ptr == NULL)//此時(shí)鏈表為空
    {
        s->next = L->next;
        L->next = s;
    }
    else {
        List pre = NULL;//創(chuàng)建pre指針
        while (ptr)//當(dāng)ptr不為NULL時(shí)
        {
            pre = ptr;//將pre指向ptr
            ptr = ptr->next;//ptr指向他的下一個(gè)結(jié)點(diǎn)
        }//循環(huán)結(jié)束時(shí)，pre指向鏈表最后一個(gè)結(jié)點(diǎn),ptr指向最后一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        s->next = ptr;//待插入s結(jié)點(diǎn)指向ptr
        pre->next = s;//將s結(jié)點(diǎn)插入到鏈表最后，尾插完成
    }
}

3、指定位置插入

//插入操作
void insert_List(List &L,int n,int data)
{
    List ptr = L->next;
    List pre = NULL;
    List s = (List)malloc(sizeof(LinkList));//s 為待插入結(jié)點(diǎn)
    s->data = data;//將形參列表的data數(shù)據(jù)賦值給s的data屬性
    s->next = NULL;
    if (n<1)
    {
        printf("插入位置錯(cuò)誤!");
    }
    else if (n == 1)
    {
        printf("調(diào)用頭插法，請(qǐng)重寫(xiě)輸入元素值：");
        headAdd_List(L);//如果插入第一個(gè)位置，調(diào)用頭插法
    }
    else 
    {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循環(huán)結(jié)束后，ptr指向待插入的位置,pre指向待插入位置的前一個(gè)位置
        s->next = ptr;//插入s結(jié)點(diǎn)
        pre->next = s;
    }
}

刪除結(jié)點(diǎn)

1、頭刪

void headDelete_List(List &L)
{
    printf("執(zhí)行頭刪：\n");
    List ptr = L->next;//ptr指針初始化指向首元結(jié)點(diǎn)，也就是除了頭結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)
    L->next = ptr->next;//直接讓頭結(jié)點(diǎn)指向首元結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，跳過(guò)首元結(jié)點(diǎn)就是刪除
    delete ptr;//將首元結(jié)點(diǎn)地址刪除
    ptr = NULL;//指針指向空，防止空指針異常
}

2、尾刪

//尾刪
void tailDelete_List(List& L)
{
    printf("執(zhí)行尾刪：\n");
    List ptr = L;//ptr指針指向頭結(jié)點(diǎn)
    List pre = NULL;//創(chuàng)建結(jié)點(diǎn)pre
    while (ptr->next)//當(dāng)ptr的下一個(gè)結(jié)點(diǎn)不為NULL時(shí)
    {
        pre = ptr;//將pre指向ptr
        ptr = ptr->next;//ptr指向他的下一個(gè)結(jié)點(diǎn)
    }//循環(huán)結(jié)束時(shí)，pre指向鏈表最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn),ptr指向鏈表最后一個(gè)結(jié)點(diǎn)
    pre->next = NULL;//將pre的next指針置為空，刪除掉
    free(ptr);//釋放刪除掉的ptr指針
}

3、指定位置刪除

void delete_List(List & L, int n)
{
    List ptr = L->next;
    List pre = NULL;
    if (n<1)
    {
        printf("刪除位置有誤!");
    }
    else if (n == 1)
    {
        headDelete_List(L);//調(diào)用頭刪
    }
    else
    {
        for (int i = 1; i < n ;i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循環(huán)結(jié)束后，ptr指向待插入的位置,pre指向待插入位置的前一個(gè)位置
        pre->next = ptr->next;//刪除該位置的結(jié)點(diǎn)
        delete ptr;//刪除ptr地址
        ptr = NULL;//防止空指針異常
    }
   
}

查找修改結(jié)點(diǎn)

List find_List(int data,List &L)
{
    int i = 1;
    List ptr = L->next;
    while (ptr)//當(dāng)結(jié)點(diǎn)不為空時(shí)
    {
        if (ptr->data == data)
        {
            printf("該元素在鏈表的位置為第 %d個(gè)\n",i);
            return ptr;//找到就返回地址
        }
        i++;
        ptr = ptr->next;//繼續(xù)遍歷
    }
    printf("鏈表中沒(méi)有該元素\n");
    return NULL;
}

移除結(jié)點(diǎn)

//移除元素
void cancel_List(List &L,int n)
{
    List ptr = L->next;
    List pre = L;
    while (ptr)//ptr不空時(shí)
    {
        if (ptr->data == n)//如果和傳進(jìn)來(lái)的n相等
        {
            pre->next = ptr->next;//刪除改結(jié)點(diǎn)
            delete ptr;//刪除地址
            ptr = pre;//重新指向前一個(gè)結(jié)點(diǎn)
        }
        else {
            pre = ptr;//如果ptr不和n相等，讓pre往后走
            ptr = ptr->next;//ptr向后遍歷
        }
    }
}

最終效果

雙鏈表的基本操作

初始化建表

typedef int ElemType;//將整型數(shù)據(jù)重命名為int
typedef int Status;//整型重命名為Status
 
//雙鏈表的數(shù)據(jù)結(jié)構(gòu)定義
typedef struct DouNode {
    ElemType data;               //數(shù)據(jù)域
    struct DouNode* head;        //前驅(qū)指針
    struct DouNode* next;        //后繼指針
}DousList, * LinkList;// 結(jié)點(diǎn)指針
//雙鏈表的創(chuàng)建
void CreateDouList(LinkList &L, int n)
{
    LinkList  ptr;
    int i;
    L = (LinkList)malloc(sizeof(DousList));    //為頭結(jié)點(diǎn)申請(qǐng)空間
    L->next = NULL;
    L->head = NULL;
    L->data = n;//L->data記錄結(jié)點(diǎn)的個(gè)數(shù)
    ptr = L;
    for (i = 0; i < n; i++)
    {
        int value = 0;
        scanf("%d",&value);
        LinkList me = (LinkList)malloc(sizeof(DouNode));
        me->data = value;    //節(jié)點(diǎn)數(shù)據(jù)域
        me->next = NULL;
        me->head = NULL;
        ptr->next = me;     
        me->head = ptr;
        ptr = ptr->next;     //尾插法建表
    }
}

遍歷雙鏈表

//雙鏈表的遍歷
void DisPlayList(LinkList L)
{
    printf("當(dāng)前鏈表數(shù)據(jù)為：\n");
    LinkList ptr= L->next;
    while (ptr)
    {
        printf("%d ",ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

指定位置插入結(jié)點(diǎn)

void InsertNode(LinkList &L, int n, ElemType data)
{
    LinkList pre=NULL;
    LinkList ptr = L->next;
    LinkList me = (LinkList)malloc(sizeof(DouNode));
    me->head = NULL;
    me->next = NULL;
    me->data = data;
    if (n<1 || n>L->data)
    {
        printf("插入位置有誤!");
        return ;
    }
    else if (n == 1)
    {
        ptr->head = me;
        me->next = ptr;
        L->next = me;
        me->head = L;
        L->data++;
    }
    else
    {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }
        ptr->head = me;
        me->next = ptr;
        pre->next = me;
        me->head = pre;
        L->data++;
    }
    
}

指定位置刪除結(jié)點(diǎn)

Status DeleteNode(LinkList& L, int n, ElemType* v)
{
    LinkList ptr = L->next;
    if (n<1 || n>L->data)
    {
        printf("刪除位置有誤!");
        return -1;
    }
    else 
    {
        for (int i = 1; i < n; i++)
        {
            ptr = ptr->next;
        }
        v= &ptr->data;
        ptr->head->next = ptr->next;
        ptr->next->head = ptr->head;
       
 
    }
    L->data--;
    return *v;
}

查找結(jié)點(diǎn)位置

void FindNode(LinkList L, ElemType data)
{
    int i = 0;
    LinkList ptr = L;
    while (ptr) {
        i++;
        ptr=ptr->next;
        if (ptr->data == data) {
            printf("該元素在鏈表中的位置為：%d\n",i);
        }
    }
}