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

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

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

前言

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

單鏈表的增刪改查

(1)項目需求

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

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

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

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

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

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

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

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

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

增加結(jié)點

1、頭插

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

2、尾插

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

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é)點
    s->data = data;//將形參列表的data數(shù)據(jù)賦值給s的data屬性
    s->next = NULL;
    if (n<1)
    {
        printf("插入位置錯誤!");
    }
    else if (n == 1)
    {
        printf("調(diào)用頭插法，請重寫輸入元素值：");
        headAdd_List(L);//如果插入第一個位置，調(diào)用頭插法
    }
    else 
    {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循環(huán)結(jié)束后，ptr指向待插入的位置,pre指向待插入位置的前一個位置
        s->next = ptr;//插入s結(jié)點
        pre->next = s;
    }
}

刪除結(jié)點

1、頭刪

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

2、尾刪

//尾刪
void tailDelete_List(List& L)
{
    printf("執(zhí)行尾刪：\n");
    List ptr = L;//ptr指針指向頭結(jié)點
    List pre = NULL;//創(chuàng)建結(jié)點pre
    while (ptr->next)//當(dāng)ptr的下一個結(jié)點不為NULL時
    {
        pre = ptr;//將pre指向ptr
        ptr = ptr->next;//ptr指向他的下一個結(jié)點
    }//循環(huán)結(jié)束時，pre指向鏈表最后一個結(jié)點的前一個結(jié)點,ptr指向鏈表最后一個結(jié)點
    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指向待插入位置的前一個位置
        pre->next = ptr->next;//刪除該位置的結(jié)點
        delete ptr;//刪除ptr地址
        ptr = NULL;//防止空指針異常
    }
   
}

查找修改結(jié)點

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

移除結(jié)點

//移除元素
void cancel_List(List &L,int n)
{
    List ptr = L->next;
    List pre = L;
    while (ptr)//ptr不空時
    {
        if (ptr->data == n)//如果和傳進來的n相等
        {
            pre->next = ptr->next;//刪除改結(jié)點
            delete ptr;//刪除地址
            ptr = pre;//重新指向前一個結(jié)點
        }
        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é)點指針
//雙鏈表的創(chuàng)建
void CreateDouList(LinkList &L, int n)
{
    LinkList  ptr;
    int i;
    L = (LinkList)malloc(sizeof(DousList));    //為頭結(jié)點申請空間
    L->next = NULL;
    L->head = NULL;
    L->data = n;//L->data記錄結(jié)點的個數(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é)點數(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é)點

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é)點

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é)點位置

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