網站首頁編程語言正文

C語言數據結構之單鏈表與雙鏈表的增刪改查操作實現_C 語言

作者：葉落秋白 ? 更新時間： 2022-08-31 編程語言

前言

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

單鏈表的增刪改查

(1)項目需求

構造帶有頭結點的單鏈表數據結構，實現初始化、清空和銷毀操作，在兩端插入元素和刪除元素操作并在鏈表中查找操作，在指定位置插入和刪除元素操作，移除元素操作

(2)解決思路
① ?定義節點類型，定義單鏈表類型，構造創建新節點的函數。

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

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

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

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

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

定義結構體以及初始化

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

增加結點

1、頭插

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

2、尾插

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

3、指定位置插入

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

刪除結點

1、頭刪

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

2、尾刪

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

查找修改結點

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

移除結點

//移除元素
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;//刪除改結點
            delete ptr;//刪除地址
            ptr = pre;//重新指向前一個結點
        }
        else {
            pre = ptr;//如果ptr不和n相等，讓pre往后走
            ptr = ptr->next;//ptr向后遍歷
        }
    }
}

最終效果

雙鏈表的基本操作

初始化建表

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

遍歷雙鏈表

//雙鏈表的遍歷
void DisPlayList(LinkList L)
{
    printf("當前鏈表數據為：\n");
    LinkList ptr= L->next;
    while (ptr)
    {
        printf("%d ",ptr->data);
        ptr = ptr->next;
    }
    printf("\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++;
    }
    
}

指定位置刪除結點

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

查找結點位置

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

最終效果

結語

鏈表的操作看著復雜其實也不復雜，和數組的區別就是需要動態分配內存空間，然后遍歷有點小復雜罷了，多加練習就好了。

原文鏈接：https://blog.csdn.net/m0_58618795/article/details/125652787

上一篇：Flask接收上傳圖片方法實現_python
下一篇：C#泛型語法詳解_C#教程

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁編程語言正文

C語言數據結構之單鏈表與雙鏈表的增刪改查操作實現_C 語言

目錄

前言

單鏈表的增刪改查

定義結構體以及初始化

增加結點

刪除結點

查找修改結點

移除結點

最終效果

雙鏈表的基本操作

初始化建表

遍歷雙鏈表

指定位置插入結點

指定位置刪除結點

查找結點位置

最終效果

結語

相關推薦

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁 編程語言 正文

C語言數據結構之單鏈表與雙鏈表的增刪改查操作實現_C 語言

目錄

前言

單鏈表的增刪改查

定義結構體以及初始化

增加結點

刪除結點

查找修改結點

移除結點

最終效果

雙鏈表的基本操作

初始化建表

遍歷雙鏈表

指定位置插入結點

指定位置刪除結點

查找結點位置

最終效果

結語

相關推薦

網站首頁編程語言正文