C語(yǔ)言鏈表

鏈表

  • 鏈表用于解決合理利用存儲(chǔ)空間的問(wèn)題

  • malloc在沒(méi)有連續(xù)內(nèi)存空間的時(shí)候分配會(huì)失敗

  • 解決方案:

    • 不要一次性開(kāi)辟一塊連續(xù)的存儲(chǔ)空間, 每次少開(kāi)辟一點(diǎn)
      最后利用指針將所有開(kāi)辟的小的存儲(chǔ)空間鏈接在一起, 組成一個(gè)整體

靜態(tài)鏈表

typedef struct node{
    int data; // 專(zhuān)門(mén)用于存儲(chǔ)數(shù)據(jù)的
    struct node *next; // 專(zhuān)門(mén)用于實(shí)現(xiàn)鏈接的
} Node;
int main()
{
 // 1.定義三個(gè)結(jié)構(gòu)體
    Node a;
    Node b;
    Node c;
    // 2.讓三個(gè)結(jié)構(gòu)體保存數(shù)據(jù)
    a.data = 1;
    b.data = 3;
    c.data = 5;
    // 3.將三個(gè)結(jié)構(gòu)體鏈接在一起
    a.next = &b;
    b.next = &c;
    // 如果指針沒(méi)有值, 那么就可以賦值為NULL, 明確告訴系統(tǒng)該指針沒(méi)有值
    // 如果一個(gè)指針沒(méi)有值,也沒(méi)有賦值為NULL, 那么這個(gè)指針就是一個(gè)野指針
    // 注意: 一定不要操作沒(méi)有值的指針和野指針
    c.next = NULL;
    // 4.定義鏈表的頭指針
    Node *head = &a;
    return 0;
}

空鏈表

  • 只有一個(gè)頭指針和頭結(jié)點(diǎn),并且頭結(jié)點(diǎn)沒(méi)有下一個(gè)結(jié)點(diǎn)且沒(méi)有數(shù)據(jù)
#include <studio.h>
Node * createNode();
typedef struct node{
int data;
struct node *next;
} Node;
int main()
{
    Node *head = createNode();
    return 0;
}
Node *createNode()
{
    //1.創(chuàng)建一個(gè)頭結(jié)點(diǎn)
    Node *head= (Node *)malloc(sizeof(Node));
    //1.1可能分配失敗
    if(head == NULL)
{
    exit(-1);
}
    //2.下一個(gè)節(jié)點(diǎn)賦值為空
    head -> next = NULL;
    return head;
}

  • 內(nèi)存分配圖解:


動(dòng)態(tài)鏈表尾差法

  • 規(guī)則:
    1.把新結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    2.把頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)

代碼如下:

#include <stdio.h>
typedef struct node
{
    int data;
    struct node *next;
} Node;
void printList(Node * head);
Node *createList();
int main()
{
    //0.創(chuàng)建頭結(jié)點(diǎn)和頭指針
    Node *head = createList();
    //1.打印數(shù)據(jù)
    printList(head);
    return 0;
}

void printList(Node * head){
    //1.接收頭指針,頭指針指向頭結(jié)點(diǎn)
    //2.頭結(jié)點(diǎn)是沒(méi)有數(shù)據(jù)的,我們可以將頭指針直接指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    //輸出數(shù)據(jù)
    Node *cur = head;
    while(cur->next != NULL){
        cur = cur -> next;
        printf("%d\n",cur -> data);
    }
/**
 * @brief createList 尾差法創(chuàng)建動(dòng)態(tài)鏈表
 * @return 返回頭指針
 */
Node *createList(){
    //1.創(chuàng)建頭指針和頭結(jié)點(diǎn)
    Node *head = (Node *)malloc(sizeof(Node));
    if(head == NULL){
        exit(-1);
    }
    head -> next = NULL;

    //1.用一個(gè)變量表示循環(huán)條件
    //2.提示用戶輸入要保存的數(shù)據(jù)
    int num = 0;
    printf("請(qǐng)輸入想要保存的數(shù)據(jù),輸入-1結(jié)束\n");
    scanf("%d",&num);
    while(-1 != num)
    {
        Node *node = (Node*)malloc(sizeof(Node));
        //保存數(shù)據(jù)
        node -> data = num;
        //1.把新結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        node -> next = head -> next;
        //2.把頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
        head -> next = node;

        printf("請(qǐng)輸入想要保存的數(shù)據(jù),輸入-1結(jié)束\n");
        scanf("%d",&num);
    }
    return head;
}

  • 圖解


動(dòng)態(tài)鏈表頭插法

  • 規(guī)則:
    1.定義變量記錄最后一個(gè)結(jié)點(diǎn)
    2.讓新結(jié)點(diǎn)成為上一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    3.把新結(jié)點(diǎn)作為下一個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
#include <stdio.h>
typedef struct node
{
    int data;
    struct node *next;
} Node;
Node *createList();
void printList(Node *head);
int main()
{
    //動(dòng)態(tài)鏈表頭插法
    Node *head = createList();
    printList(head);
    return 0;
}

void printList(Node *head){
    Node *cur = head;
    while(cur->next != NULL)//首先判斷不是空鏈表
    {
        cur = cur -> next;
        printf("%d\n",cur -> data);
    }
}
Node *createList(){
    //1.創(chuàng)建頭結(jié)點(diǎn)和頭指針
    Node *head = (Node*)malloc(sizeof(Node));
    //分配失敗
    if(head == NULL){
        exit(-1);
    }
    head->next = NULL;

    //定義變量控制循環(huán)
    int num = -1;
    printf("請(qǐng)輸入你想要保存的數(shù)據(jù):\n");
    scanf("%d",&num);
    //1.定義變量記錄最后一個(gè)結(jié)點(diǎn)
    Node *cur = head;//一定要放在最外面,否則會(huì)引起值覆蓋
    while(-1 != num)
    {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = num;
        node->next = NULL;
        //2.讓新結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
        cur->next = node;
        //3.把新結(jié)點(diǎn)作為下一個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
        cur = node;
        printf("請(qǐng)輸入你想要保存的數(shù)據(jù):\n");
        scanf("%d",&num);
    }
    return head;
}

  • 圖解


封裝

  • 我們可以封裝一個(gè)創(chuàng)建空鏈表的函數(shù)
/**
 * @brief createEmpty 創(chuàng)建空鏈表
 * @return 鏈表的頭指針
 */
Node *createEmpty(){
    // 1.定義頭指針
    Node *head = NULL;
    // 2.創(chuàng)建一個(gè)空節(jié)點(diǎn), 并且賦值給頭指針
    head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    // 3.返回頭指針
    return head;
}
  • 我們可以將插入數(shù)據(jù)封裝成一個(gè)函數(shù)
void  insertNode(Node *head, int num){
    // 1.創(chuàng)建一個(gè)新的節(jié)點(diǎn)
    Node *node = (Node *)malloc(sizeof(Node));
    // 2.將數(shù)據(jù)保存到新節(jié)點(diǎn)中
    node->data = num;

    // 3.進(jìn)行插入
    // 3.1讓新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 等于 頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    node->next = head->next;
    // 3.2讓頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 等于 新節(jié)點(diǎn)
    head->next = node;
}
  • 我們可以封裝一個(gè)銷(xiāo)毀鏈表的函數(shù)
// 封裝一個(gè)專(zhuān)門(mén)用于銷(xiāo)毀鏈表的函數(shù)
/**
 * @brief destroyList 銷(xiāo)毀鏈表
 * @param head 鏈表的頭指針
 */
void destroyList(Node *head){
    Node *cur = NULL;
    while(head != NULL){
        cur = head->next;
        free(head);
        head = cur;
    }
}
  • 我們可以封裝一個(gè)計(jì)算鏈表長(zhǎng)度的函數(shù)
// 封裝一個(gè)專(zhuān)門(mén)用于計(jì)算鏈表長(zhǎng)度的函數(shù)
int listLength(Node *head){
    // 1.定義變量記錄節(jié)點(diǎn)的個(gè)數(shù)
    int count = 0;
    // 注意點(diǎn): 頭結(jié)點(diǎn)不要
    Node *cur = head->next;
    // 2.遍歷統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)
    while(cur != NULL){
        count++;
        cur = cur->next;
    }
    return count;
}
  • 我們可以封裝一個(gè)查找指定結(jié)點(diǎn)的函數(shù)
// 封裝一個(gè)專(zhuān)門(mén)用于查找指定節(jié)點(diǎn)的函數(shù)
/**
 * @brief findNode 查找指定節(jié)點(diǎn)
 * @param head 鏈表的頭指針
 * @param key 需要查找的key
 * @return 符合要求的節(jié)點(diǎn), 如果找不到返回NULL
 */
Node *findNode(Node* head, int key){
    // 注意點(diǎn): 頭結(jié)點(diǎn)不需要查找
    head = head->next;
    while(head != NULL){
        // 判斷當(dāng)前節(jié)點(diǎn)保存的值是否是要查找的值
        if(head->data == key){
            return head;
        }else{
            head = head->next;
        }
    }
    return NULL;
}
  • 我們可以封裝一個(gè)刪除指定結(jié)點(diǎn)的函數(shù)
//封裝一個(gè)專(zhuān)門(mén)用于刪除指定節(jié)點(diǎn)的函數(shù)
/**
 * @brief deleteNode 刪除指定節(jié)點(diǎn)
 * @param head 鏈表的頭指針
 * @param node 需要?jiǎng)h除的節(jié)點(diǎn)
 */
void deleteNode(Node *head, Node *node){
    // 1.找到需要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
    while(head->next != node){
        head = head->next;
    }
    // 2.將刪除節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)的next改為 , 刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    head->next = node->next;
    // 3.刪除對(duì)應(yīng)節(jié)點(diǎn)
    free(node);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容