C語言資料結構之單向連結串列詳解

2022-08-17 18:00:39

連結串列

連結串列實現了，記憶體零碎資料的有效組織。比如，當我們用 malloc 來進行記憶體申請的時候，當記憶體足夠，但是由於碎片太多，沒有連續記憶體時，只能以申請失敗而告終，而用連結串列這種資料結構來組織資料，就可以解決上類問題。

靜態連結串列

#include <stdio.h>
// 1.定義連結串列節點
typedef struct node{
    int data;
    struct node *next;
}Node;
int main(int argc, char *argv[]) {
    // 2.建立連結串列節點
    Node a;
    Node b;
    Node c;

    // 3.初始化節點資料
    a.data = 1;
    b.data = 3;
    c.data = 5;

    // 4.連結節點
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    // 5.建立連結串列頭
    Node *head = &a;

    // 6.使用連結串列
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %in", currentData);
        head = head->next;//指向下一個節點
    }

    return 0;
}

動態連結串列

靜態連結串列的意義不是很大，主要原因，資料儲存在棧上，棧的儲存空間有限，不能動態分配。所以連結串列要實現儲存的自由，要動態的申請堆裡的空間。

有頭連結串列

無頭連結串列

單向連結串列有有頭節點和無頭節點兩種列表, 有頭節點在列表的刪除,反轉,插入等操作會比無頭節點簡單,但是不好之處就是多佔用些空間,而且在多個連結串列結合處理的時候有頭連結串列每次都需要過濾頭節點,而無頭連結串列直接完美融合 ,而且很多高階語言都是無頭連結串列的便於日後的擴充套件 ,下面都是依據無頭節點進行演示

定義連結串列節點

// 1.定義連結串列節點
typedef struct node {
    void *data;
    struct node *next;
} Node;

建立連結串列

/**
 * 建立連結串列
 */
Node *createList() {

    // 1.建立頭節點
    Node *root = (Node *) malloc(sizeof(Node));
    root->data = NULL;
    root->next = NULL;
    //返回頭節點
    return root;
}

建立一個空節點

/**
 * 建立一個空節點
 */
Node *createNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = NULL;
    node->next = NULL;
    return  node;
}

尾插法

/**
 * @brief insertEndNode 尾插法插入節點
 * @param head 需要插入的頭指標
 * @param data 需要插入的資料
 */
void insertEndNode(Node *node, void *data) {
    Node *head = node;
    //找到資料為空的節點,沒有節點那麼就擴充套件
    while (head->data != NULL) {
        //擴容
        if(head->next == NULL) {
            Node *pNode = createNode();
            head->next = pNode;
            head = pNode;
            break;
        }
        head = head->next;
    }
    //插入資料
    head->data = data;
}

頭插法

/**
 * @brief insertHeadNode 頭插法插入節點
 * @param head 需要插入的頭指標
 * @param data 需要插入的資料
 */
void insertHeadNode(Node **node, void *data) {
    Node *pNode = createNode();
    pNode->data = data;
    pNode->next = *node;
    *node = pNode;
}

指定位置插入一個結點

簡單來說就是先找到需要插入的位置,然後將當前位置節點和他前一個節點連線到需要插入的節點就行了

/**
 * @brief insertNOde 將資料節點插入到指定資料位置節點,指定資料節點向後移動,  如果沒有找到插入的位置,那麼就插入到最後
 * @param insertionPoint 指定的資料節點
 * @param data 需要插入的資料
 */
void insertNode(Node *node ,void *insertionPoint,void *data){
    Node *pNode = node;
    Node *pre = pNode;//父節點
    while (pNode!=NULL){
        if(pNode->data == insertionPoint){
            break;
        }
        pre=pNode; //保留當前節點
        pNode=pNode->next;
    }
    //如果沒有找到那麼就插入到最後
    if(pNode==NULL){
        insertEndNode(node,data);
        return;
    }
    Node *dataNode = createNode();
    dataNode->data= data;
    pre->next = dataNode;
    dataNode->next = pNode;
}

遍歷連結串列

因為我們值儲存是使用無型別的指標,所以需要轉換為插入時候的型別才行

/**
 * @brief printNodeListDouble 遍歷連結串列
 * @param node 連結串列指標頭
 */
void printNodeListDouble(Node *node) {
    Node *head = node;
    while (head!=NULL&&head->data!=NULL){
        double *currentData = head->data;
        printf("currentData = %fn", *currentData);
        head = head->next;
    }
}

獲取連結串列長度

/**
 * @brief listLength 計算連結串列長度
 * @param head 連結串列頭指標
 * @return 連結串列長度
 */
int listLength(Node *head){
    int count = 0;
    head = head;
    while(head){
        count++;
        head = head->next;
    }
    return count;
}

連結串列搜尋

/**
 * @brief searchList 查詢指定節點
 * @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;
}

連結串列資料排序

因為我們儲存資料型別是使用無型別的指標,那麼在排序的時候需要轉換為指定型別才行

/**
 * @brief bubbleSort 對連結串列值進行排序  小到大
 * @param head 連結串列頭指標
 */
void sortDouble(Node *head){
    // 1.計算連結串列長度
    int len = listLength(head);
    // 2.定義變數記錄前後節點
    Node *cur = head;
    while (cur!=NULL){
        Node *cur1=cur->next;
        while (cur1!=NULL){
            //比較大小 ,然後交換資料
            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;
    }
}

反轉連結串列

斷開連結串列頭，然後以頭插法的方式將原連結串列的資料新增連結串列。

/**
 * @brief reverseList 反轉連結串列
 * @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;
}

刪除節點資料

先找到需要刪除的節點,之後將後一個結點賦值給前一個結點的next,然後將刪除位置的結點釋放即可

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

    Node *head1 = head->next;
    Node *pre = head;//根節點
    while (head1!=NULL){
        if(head1->data == key){
            pre->next = head1->next;
            free(head1->data);
            free(head1);
            break;
        }
        pre = head1;//當前節點
        head1 = head1->next; //下一個節點
    }
}

銷燬連結串列

/**
 * @brief destroyList 銷燬連結串列
 * @param head 連結串列頭指標
 */
void destroyList(Node *head){
    Node *cur = head;
    while(head != NULL){
        cur = head->next;
        free(head->data);//清除當前節點資料記憶體
        free(head);//清除當前節點記憶體
        head = cur;
    }
}

測試

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


    //建立連結串列
    Node *head = createList();

    //插入資料
    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 = %dn", i);

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

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

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

    //刪除節點
    printf("delNode ====================n");
    delNode(&head, f1);
    printNodeListDouble(head);

    //銷燬
    destroyList(head);


    return 0;
}