欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2022年08月17日 15:36:54   作者：胡安民  
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問要通過順序讀取從頭部開始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用，需要的可以參考一下

鏈表

鏈表實(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)簡(jiǎ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)

簡(jiǎ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;
    }
}

測(cè)試

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

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解的文章就介紹到這了,更多相關(guān)C語言單向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • C++實(shí)現(xiàn)推箱子游戲

    C++實(shí)現(xiàn)推箱子游戲

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)推箱子游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2019-10-10
  • C++虛函數(shù)表與類的內(nèi)存分布深入分析理解

    C++虛函數(shù)表與類的內(nèi)存分布深入分析理解

    對(duì)C++ 了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）來實(shí)現(xiàn)的。簡(jiǎn)稱為V-Table。本文就將詳細(xì)講講虛函數(shù)表的原理與使用，需要的可以參考一下
    2022-08-08
  • C語言中進(jìn)程間通訊的方式詳解

    C語言中進(jìn)程間通訊的方式詳解

    這篇文章主要為大家詳細(xì)介紹了C語言中幾種進(jìn)程間通訊的方式，文中的示例代碼講解詳細(xì)，?對(duì)我們學(xué)習(xí)或工作有一定的借鑒價(jià)值，需要的可以參考一下
    2022-08-08
  • C++實(shí)現(xiàn)的打字母游戲示例

    C++實(shí)現(xiàn)的打字母游戲示例

    這篇文章主要介紹了C++實(shí)現(xiàn)的打字母游戲,涉及C++字體操作、時(shí)間及鍵盤響應(yīng)相關(guān)操作技巧,需要的朋友可以參考下
    2017-08-08
  • c語言多線程編程使用示例

    c語言多線程編程使用示例

    這篇文章主要介紹了c語言多線程編程使用示例,需要的朋友可以參考下
    2014-04-04
  • C++賦值運(yùn)算符

    C++賦值運(yùn)算符

    這篇文章主要介紹了C++賦值運(yùn)算符,C++當(dāng)中允許類對(duì)象賦值，這是通過默認(rèn)的重載賦值運(yùn)算符實(shí)現(xiàn)的,下面我們就來介紹介紹該內(nèi)容吧，,需要的朋友可以參考一下
    2022-01-01
  • C++單例模式的幾種實(shí)現(xiàn)方法詳解

    C++單例模式的幾種實(shí)現(xiàn)方法詳解

    這篇文章主要為大家詳細(xì)介紹了C++單例模式的幾種實(shí)現(xiàn)方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-03-03
  • c++中堆棧及創(chuàng)建對(duì)象示例代碼

    c++中堆棧及創(chuàng)建對(duì)象示例代碼

    這篇文章主要給大家詳細(xì)介紹了c++如何實(shí)現(xiàn)堆棧及創(chuàng)建對(duì)象，文中先進(jìn)行了簡(jiǎn)單的介紹，而后給出了詳細(xì)的示例代碼及注釋，相信對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面跟著小編一起來學(xué)習(xí)學(xué)習(xí)吧。
    2016-12-12
  • C++編寫高性能服務(wù)器實(shí)例教程

    C++編寫高性能服務(wù)器實(shí)例教程

    這篇文章主要介紹了如何用C++編寫高性能服務(wù)器，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)C++有一定的參考價(jià)值，需要的朋友們可以了解下
    2020-06-06
  • C++與Lua交互原理實(shí)例詳解

    C++與Lua交互原理實(shí)例詳解

    這篇文章主要介紹了C++與Lua交互原理實(shí)例詳解，有感興趣的同學(xué)可以研究下
    2021-02-02

最新評(píng)論