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

更新時(shí)間：2022年08月17日 15:36:54 作者：胡安民

單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問要通過順序讀取從頭部開始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用，需要的可以參考一下

定義鏈表節(jié)點(diǎn)
創(chuàng)建鏈表
創(chuàng)建一個(gè)空節(jié)點(diǎn)
尾插法
頭插法
指定位置插入一個(gè)結(jié)點(diǎn)
遍歷鏈表
獲取鏈表長度
鏈表搜索
鏈表數(shù)據(jù)排序
反轉(zhuǎn)鏈表
刪除節(jié)點(diǎn)數(shù)據(jù)
銷毀鏈表
測試

鏈表

鏈表實(shí)現(xiàn)了，內(nèi)存零碎數(shù)據(jù)的有效組織。比如，當(dāng)我們用 malloc 來進(jìn)行內(nèi)存申請(qǐng)的時(shí)候，當(dāng)內(nèi)存足夠，但是由于碎片太多，沒有連續(xù)內(nèi)存時(shí)，只能以申請(qǐng)失敗而告終，而用鏈表這種數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)，就可以解決上類問題。

靜態(tài)鏈表

#include <stdio.h>
// 1.定義鏈表節(jié)點(diǎn)
typedef struct node{
    int data;
    struct node *next;
}Node;
int main(int argc, char *argv[]) {
    // 2.創(chuàng)建鏈表節(jié)點(diǎn)
    Node a;
    Node b;
    Node c;

    // 3.初始化節(jié)點(diǎn)數(shù)據(jù)
    a.data = 1;
    b.data = 3;
    c.data = 5;

    // 4.鏈接節(jié)點(diǎn)
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    // 5.創(chuàng)建鏈表頭
    Node *head = &a;

    // 6.使用鏈表
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;//指向下一個(gè)節(jié)點(diǎn)
    }

    return 0;
}

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

靜態(tài)鏈表的意義不是很大，主要原因，數(shù)據(jù)存儲(chǔ)在棧上，棧的存儲(chǔ)空間有限，不能動(dòng)態(tài)分配。所以鏈表要實(shí)現(xiàn)存儲(chǔ)的自由，要?jiǎng)討B(tài)的申請(qǐng)堆里的空間。

有頭鏈表

無頭鏈表

單向鏈表有有頭節(jié)點(diǎn)和無頭節(jié)點(diǎn)兩種列表, 有頭節(jié)點(diǎn)在列表的刪除,反轉(zhuǎn),插入等操作會(huì)比無頭節(jié)點(diǎn)簡單,但是不好之處就是多占用些空間,而且在多個(gè)鏈表結(jié)合處理的時(shí)候有頭鏈表每次都需要過濾頭節(jié)點(diǎn),而無頭鏈表直接完美融合 ,而且很多高級(jí)語言都是無頭鏈表的便于日后的擴(kuò)展 ,下面都是依據(jù)無頭節(jié)點(diǎn)進(jìn)行演示

定義鏈表節(jié)點(diǎn)

// 1.定義鏈表節(jié)點(diǎn)
typedef struct node {
    void *data;
    struct node *next;
} Node;

創(chuàng)建鏈表

/**
 * 創(chuàng)建鏈表
 */
Node *createList() {

    // 1.創(chuàng)建頭節(jié)點(diǎn)
    Node *root = (Node *) malloc(sizeof(Node));
    root->data = NULL;
    root->next = NULL;
    //返回頭節(jié)點(diǎn)
    return root;
}

創(chuàng)建一個(gè)空節(jié)點(diǎn)

/**
 * 創(chuàng)建一個(gè)空節(jié)點(diǎn)
 */
Node *createNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = NULL;
    node->next = NULL;
    return  node;
}

尾插法

/**
 * @brief insertEndNode 尾插法插入節(jié)點(diǎn)
 * @param head 需要插入的頭指針
 * @param data 需要插入的數(shù)據(jù)
 */
void insertEndNode(Node *node, void *data) {
    Node *head = node;
    //找到數(shù)據(jù)為空的節(jié)點(diǎn),沒有節(jié)點(diǎn)那么就擴(kuò)展
    while (head->data != NULL) {
        //擴(kuò)容
        if(head->next == NULL) {
            Node *pNode = createNode();
            head->next = pNode;
            head = pNode;
            break;
        }
        head = head->next;
    }
    //插入數(shù)據(jù)
    head->data = data;
}

頭插法

/**
 * @brief insertHeadNode 頭插法插入節(jié)點(diǎn)
 * @param head 需要插入的頭指針
 * @param data 需要插入的數(shù)據(jù)
 */
void insertHeadNode(Node **node, void *data) {
    Node *pNode = createNode();
    pNode->data = data;
    pNode->next = *node;
    *node = pNode;
}

指定位置插入一個(gè)結(jié)點(diǎn)

簡單來說就是先找到需要插入的位置,然后將當(dāng)前位置節(jié)點(diǎn)和他前一個(gè)節(jié)點(diǎn)連接到需要插入的節(jié)點(diǎn)就行了

/**
 * @brief insertNOde 將數(shù)據(jù)節(jié)點(diǎn)插入到指定數(shù)據(jù)位置節(jié)點(diǎn),指定數(shù)據(jù)節(jié)點(diǎn)向后移動(dòng),  如果沒有找到插入的位置,那么就插入到最后
 * @param insertionPoint 指定的數(shù)據(jù)節(jié)點(diǎn)
 * @param data 需要插入的數(shù)據(jù)
 */
void insertNode(Node *node ,void *insertionPoint,void *data){
    Node *pNode = node;
    Node *pre = pNode;//父節(jié)點(diǎn)
    while (pNode!=NULL){
        if(pNode->data == insertionPoint){
            break;
        }
        pre=pNode; //保留當(dāng)前節(jié)點(diǎn)
        pNode=pNode->next;
    }
    //如果沒有找到那么就插入到最后
    if(pNode==NULL){
        insertEndNode(node,data);
        return;
    }
    Node *dataNode = createNode();
    dataNode->data= data;
    pre->next = dataNode;
    dataNode->next = pNode;
}

遍歷鏈表

因?yàn)槲覀冎荡鎯?chǔ)是使用無類型的指針,所以需要轉(zhuǎn)換為插入時(shí)候的類型才行

/**
 * @brief printNodeListDouble 遍歷鏈表
 * @param node 鏈表指針頭
 */
void printNodeListDouble(Node *node) {
    Node *head = node;
    while (head!=NULL&&head->data!=NULL){
        double *currentData = head->data;
        printf("currentData = %f\n", *currentData);
        head = head->next;
    }
}

獲取鏈表長度

/**
 * @brief listLength 計(jì)算鏈表長度
 * @param head 鏈表頭指針
 * @return 鏈表長度
 */
int listLength(Node *head){
    int count = 0;
    head = head;
    while(head){
        count++;
        head = head->next;
    }
    return count;
}

鏈表搜索

/**
 * @brief searchList 查找指定節(jié)點(diǎn)
 * @param head 鏈表頭指針
 * @param key 需要查找的值
 * @return
 */
Node *searchList(Node *head, void *key){
    head = head;
    while(head){
        if(head->data == key){
            break;
        }else{
            head = head->next;
        }
    }
    return head;
}

鏈表數(shù)據(jù)排序

因?yàn)槲覀兇鎯?chǔ)數(shù)據(jù)類型是使用無類型的指針,那么在排序的時(shí)候需要轉(zhuǎn)換為指定類型才行

/**
 * @brief bubbleSort 對(duì)鏈表值進(jìn)行排序  小到大
 * @param head 鏈表頭指針
 */
void sortDouble(Node *head){
    // 1.計(jì)算鏈表長度
    int len = listLength(head);
    // 2.定義變量記錄前后節(jié)點(diǎn)
    Node *cur = head;
    while (cur!=NULL){
        Node *cur1=cur->next;
        while (cur1!=NULL){
            //比較大小 ,然后交換數(shù)據(jù)
            if(*((double *)cur->data) > *((double *)cur1->data)){
                double *temp = (double *)cur->data;
                cur->data = cur1->data;
                cur1->data = temp;
            }
            cur1 = cur1->next;
        }
        cur= cur->next;
    }
}

反轉(zhuǎn)鏈表

斷開鏈表頭，然后以頭插法的方式將原鏈表的數(shù)據(jù)添加鏈表。

/**
 * @brief reverseList 反轉(zhuǎn)鏈表
 * @param head 鏈表頭指針
 */
void reverseList(Node **root){
    Node *head = *root;
    Node *pre=head, *cur=head->next;
    pre->next = NULL;
    while (cur!=NULL){
        Node *node = cur->next;
        cur->next = pre;
        pre = cur;
        cur=node;
    }
    *root=pre;
}

刪除節(jié)點(diǎn)數(shù)據(jù)

先找到需要?jiǎng)h除的節(jié)點(diǎn),之后將后一個(gè)結(jié)點(diǎn)賦值給前一個(gè)結(jié)點(diǎn)的next,然后將刪除位置的結(jié)點(diǎn)釋放即可

/**
 * @brief delNode 刪除指定節(jié)點(diǎn)
 */
void delNode(Node **root, void *key){
    Node *head = *root;
    //根節(jié)點(diǎn)單獨(dú)處理
    if(head->data == key&&head->next != NULL){
        *root = head->next;
        free(head->data);
        free(head);
        return;
    }

    Node *head1 = head->next;
    Node *pre = head;//根節(jié)點(diǎn)
    while (head1!=NULL){
        if(head1->data == key){
            pre->next = head1->next;
            free(head1->data);
            free(head1);
            break;
        }
        pre = head1;//當(dāng)前節(jié)點(diǎn)
        head1 = head1->next; //下一個(gè)節(jié)點(diǎn)
    }
}

銷毀鏈表

/**
 * @brief destroyList 銷毀鏈表
 * @param head 鏈表頭指針
 */
void destroyList(Node *head){
    Node *cur = head;
    while(head != NULL){
        cur = head->next;
        free(head->data);//清除當(dāng)前節(jié)點(diǎn)數(shù)據(jù)內(nèi)存
        free(head);//清除當(dāng)前節(jié)點(diǎn)內(nèi)存
        head = cur;
    }
}

測試

int main(int argc, char *argv[]) {


    //創(chuàng)建鏈表
    Node *head = createList();

    //插入數(shù)據(jù)
    printf("insert ====================\n");
    double *f = (double *)malloc(sizeof(double));
    *f=2.1;
    insertEndNode(head, f);
    double *f1 = (double *)malloc(sizeof(double));
    *f1=1.1;
    insertEndNode(head, f1);
    double *f2= (double *)malloc(sizeof(double));
    *f2=0.1;
    insertEndNode(head, f2);

    double *f3= (double *)malloc(sizeof(double));
    *f3=3.1;
    insertHeadNode(&head, f3);


    double *se = (double *)malloc(sizeof(double));
    *se=111.1;
    double *f4= (double *)malloc(sizeof(double));
    *f4=7.1;
    insertNode(head,se, f4);
    free(se);
    printNodeListDouble(head);

    //獲取長度
    printf("listLength ====================\n");
    int i = listLength(head);
    printf("listLength = %d\n", i);

    //搜索
    printf("searchList ====================\n");
    Node *pNode = searchList(head, f1);
    printf("currentData = %f\n", *((double *)pNode->data));

    //排序
    printf("sortDouble ====================\n");
    sortDouble(head);
    printNodeListDouble(head);

    //反轉(zhuǎn)
    printf("reverseList ====================\n");
    reverseList(&head);
    printNodeListDouble(head);

    //刪除節(jié)點(diǎn)
    printf("delNode ====================\n");
    delNode(&head, f1);
    printNodeListDouble(head);

    //銷毀
    destroyList(head);


    return 0;
}