內存管理

進程空間

• 程序，是經源碼編譯后的可執(zhí)行文件，可執(zhí)行文件可以多次被執(zhí)行，比如我們可以多次打開 office。
• 而進程，是程序加載到內存后開始執(zhí)行，至執(zhí)行結束，這樣一段時間概念，多次打開的wps,每打開一次都是一個進程，當我們每關閉一個 office，則表示該進程結束。
• 程序是靜態(tài)概念，而進程動態(tài)/時間概念。

進程空間圖示

有了進程和程序的概念以后，我們再來看一下，程序被加載到內存以后內存空間布局是什么樣的

棧內存(Stack)

• 棧中存放任意類型的變量，但必須是 auto 類型修飾的，即自動類型的局部變量， 隨用隨開，用完即消。
• 內存的分配和銷毀系統(tǒng)自動完成，不需要人工干預
• 棧的最大尺寸固定，超出則引起棧溢出
  • 局部變量過多，過大 或 遞歸層數(shù)太多等就會導致棧溢出

int ages[10240*10240]; // 程序會崩潰, 棧溢出

#include <stdio.h>

int main()
{
    // 存儲在棧中, 內存地址從大到小
    int a = 10;
    int b = 20;
    printf("&a = %p\n", &a); // &a = 0060FEAC
    printf("&b = %p\n", &b); // &b = 0060FEA8

    return 0;
}

堆內存(Heap)

• 堆內存可以存放任意類型的數(shù)據，但需要自己申請與釋放
• 堆大小，想像中的無窮大，但實際使用中，受限于實際內存的大小和內存是否連續(xù)性

int *p = (int *)malloc(10240 * 1024); // 不一定會崩潰

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // 存儲在棧中, 內存地址從小到大
    int *p1 = malloc(4);
    *p1 = 10;
    int *p2 = malloc(4);
    *p2 = 20;
   
    printf("p1 = %p\n", p1); //  p1 = 00762F48
    printf("p2 = %p\n", p2); // p2 = 00762F58

    return 0;
}

malloc函數(shù)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    /*
     * malloc
     * 第一個參數(shù): 需要申請多少個字節(jié)空間
     * 返回值類型: void *
     */ 
    int *p = (int *)malloc(sizeof(int));
    printf("p = %i\n", *p); // 保存垃圾數(shù)據
    /*
     * 第一個參數(shù): 需要初始化的內存地址
     * 第二個初始: 需要初始化的值
     * 第三個參數(shù): 需要初始化對少個字節(jié)
     */ 
    memset(p, 0, sizeof(int)); // 對申請的內存空間進行初始化
    printf("p = %i\n", *p); // 初始化為0
    return 0;
}

free函數(shù)

• 注意: 通過malloc申請的存儲空間一定要釋放, 所以malloc和free函數(shù)總是成對出現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    // 1.申請4個字節(jié)存儲空間
    int *p = (int *)malloc(sizeof(int));
    // 2.初始化4個字節(jié)存儲空間為0
    memset(p, 0, sizeof(int));
    // 3.釋放申請的存儲空間
    free(p);
    return 0;
}

calloc函數(shù)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    /*
    // 1.申請3塊4個字節(jié)存儲空間
    int *p = (int *)malloc(sizeof(int) * 3);
    // 2.使用申請好的3塊存儲空間
    p[0] = 1;
    p[1] = 3;
    p[2] = 5;
    printf("p[0] = %i\n", p[0]);
    printf("p[1] = %i\n", p[1]);
    printf("p[2] = %i\n", p[2]);
    // 3.釋放空間
    free(p);
    */

    // 1.申請3塊4個字節(jié)存儲空間
    int *p = calloc(3, sizeof(int));
    // 2.使用申請好的3塊存儲空間
    p[0] = 1;
    p[1] = 3;
    p[2] = 5;
    printf("p[0] = %i\n", p[0]);
    printf("p[1] = %i\n", p[1]);
    printf("p[2] = %i\n", p[2]);
    // 3.釋放空間
    free(p);

    return 0;
}

realloc函數(shù)

• 注意點:
  • 若參數(shù)ptr==NULL，則該函數(shù)等同于 malloc
  • 返回的指針，可能與 ptr 的值相同，也有可能不同。若相同，則說明在原空間后面申請，否則，則可能后續(xù)空間不足，重新申請的新的連續(xù)空間，原數(shù)據拷貝到新空間， 原有空間自動釋放

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    // 1.申請4個字節(jié)存儲空間
    int *p = NULL;
    p = realloc(p, sizeof(int)); // 此時等同于malloc
    // 2.使用申請好的空間
    *p = 666;
    printf("*p = %i\n",  *p);
    // 3.釋放空間
    free(p);

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    // 1.申請4個字節(jié)存儲空間
    int *p = malloc(sizeof(int));
    printf("p = %p\n", p);
    // 如果能在傳入存儲空間地址后面擴容, 返回傳入存儲空間地址
    // 如果不能在傳入存儲空間地址后面擴容, 返回一個新的存儲空間地址
    p = realloc(p, sizeof(int) * 2);
    printf("p = %p\n", p);
    // 2.使用申請好的空間
    *p = 666;
    printf("*p = %i\n",  *p);
    // 3.釋放空間
    free(p);

    return 0;
}

鏈表

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

  
  

靜態(tài)鏈表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 1.定義鏈表節(jié)點
typedef struct node{
    int data;
    struct node *next;
}Node;
int main()
{

    // 2.創(chuàng)建鏈表節(jié)點
    Node a;
    Node b;
    Node c;

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

    // 4.鏈接節(jié)點
    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;
    }
    return 0;
}

動態(tài)鏈表

• 靜態(tài)鏈表的意義不是很大，主要原因，數(shù)據存儲在棧上，棧的存儲空間有限，不能動態(tài)分配。所以鏈表要實現(xiàn)存儲的自由，要動態(tài)的申請堆里的空間。

• 有一個點要說清楚，我們的實現(xiàn)的鏈表是帶頭節(jié)點。至于，為什么帶頭節(jié)點，需等大家對鏈表有個整體的的認知以后，再來體會，會更有意義。

• 空鏈表

  • 頭指針帶了一個空鏈表節(jié)點, 空鏈表節(jié)點中的next指向NULL

    
    

#include <stdio.h>
#include <stdlib.h>

// 1.定義鏈表節(jié)點
typedef struct node{
    int data;
    struct node *next;
}Node;
int main()
{
    Node *head = createList();
    return 0;
}
// 創(chuàng)建空鏈表
Node *createList(){
    // 1.創(chuàng)建一個節(jié)點
    Node *node = (Node *)malloc(sizeof(Node));
    if(node == NULL){
        exit(-1);
    }
    // 2.設置下一個節(jié)點為NULL
    node->next = NULL;
    // 3.返回創(chuàng)建好的節(jié)點
    return node;
}

• 非空鏈表

  • 頭指針帶了一個非空節(jié)點, 最后一個節(jié)點中的next指向NULL

    
    

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

• 1.讓新節(jié)點的下一個節(jié)點等于頭結點的下一個節(jié)點
• 2.讓頭節(jié)點的下一個節(jié)點等于新節(jié)點

#include <stdio.h>
#include <stdlib.h>

// 1.定義鏈表節(jié)點
typedef struct node{
    int data;
    struct node *next;
}Node;
Node *createList();
void printNodeList(Node *node);
int main()
{
    Node *head = createList();
    printNodeList(head);
    return 0;
}
/**
 * @brief createList 創(chuàng)建鏈表
 * @return  創(chuàng)建好的鏈表
 */
Node *createList(){
    // 1.創(chuàng)建頭節(jié)點
    Node *head = (Node *)malloc(sizeof(Node));
    if(head == NULL){
        return NULL;
    }
    head->next = NULL;

    // 2.接收用戶輸入數(shù)據
    int num = -1;
    printf("請輸入節(jié)點數(shù)據\n");
    scanf("%i", &num);

    // 3.通過循環(huán)創(chuàng)建其它節(jié)點
    while(num != -1){
        // 3.1創(chuàng)建一個新的節(jié)點
        Node *cur = (Node *)malloc(sizeof(Node));
        cur->data = num;

        // 3.2讓新節(jié)點的下一個節(jié)點指向頭節(jié)點的下一個節(jié)點
        cur->next = head->next;
        // 3.3讓頭節(jié)點的下一個節(jié)點指向新節(jié)點
        head->next = cur;

        // 3.4再次接收用戶輸入數(shù)據
        scanf("%i", &num);
    }

    // 3.返回創(chuàng)建好的節(jié)點
    return head;
}
/**
 * @brief printNodeList 遍歷鏈表
 * @param node 鏈表指針頭
 */
void printNodeList(Node *node){
    Node *head = node->next;
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;
    }
}

動態(tài)鏈表尾插法

• 1.定義變量記錄新節(jié)點的上一個節(jié)點
• 2.將新節(jié)點添加到上一個節(jié)點后面
• 3.讓新節(jié)點成為下一個節(jié)點的上一個節(jié)點

#include <stdio.h>
#include <stdlib.h>

// 1.定義鏈表節(jié)點
typedef struct node{
    int data;
    struct node *next;
}Node;
Node *createList();
void printNodeList(Node *node);
int main()
{
    Node *head = createList();
    printNodeList(head);
    return 0;
}
/**
 * @brief createList 創(chuàng)建鏈表
 * @return  創(chuàng)建好的鏈表
 */
Node *createList(){
    // 1.創(chuàng)建頭節(jié)點
    Node *head = (Node *)malloc(sizeof(Node));
    if(head == NULL){
        return NULL;
    }
    head->next = NULL;

    // 2.接收用戶輸入數(shù)據
    int num = -1;
    printf("請輸入節(jié)點數(shù)據\n");
    scanf("%i", &num);

    // 3.通過循環(huán)創(chuàng)建其它節(jié)點
    // 定義變量記錄上一個節(jié)點
    Node *pre = head;
    while(num != -1){
        // 3.1創(chuàng)建一個新的節(jié)點
        Node *cur = (Node *)malloc(sizeof(Node));
        cur->data = num;

        // 3.2讓新節(jié)點鏈接到上一個節(jié)點后面
        pre->next = cur;
        // 3.3當前節(jié)點下一個節(jié)點等于NULL
        cur->next = NULL;
        // 3.4讓當前節(jié)點編程下一個節(jié)點的上一個節(jié)點
        pre = cur;

        // 3.5再次接收用戶輸入數(shù)據
        scanf("%i", &num);
    }

    // 3.返回創(chuàng)建好的節(jié)點
    return head;
}
/**
 * @brief printNodeList 遍歷鏈表
 * @param node 鏈表指針頭
 */
void printNodeList(Node *node){
    Node *head = node->next;
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;
    }
}

動態(tài)鏈優(yōu)化

#include <stdio.h>
#include <stdlib.h>

// 1.定義鏈表節(jié)點
typedef struct node{
    int data;
    struct node *next;
}Node;
Node *createList();
void printNodeList(Node *node);
void insertNode1(Node *head, int data);
void insertNode2(Node *head, int data);
int main()
{
    // 1.創(chuàng)建一個空鏈表
    Node *head = createList();
    // 2.往空鏈表中插入數(shù)據
    insertNode1(head, 1);
    insertNode1(head, 3);
    insertNode1(head, 5);
    printNodeList(head);
    return 0;
}
/**
 * @brief createList 創(chuàng)建空鏈表
 * @return  創(chuàng)建好的空鏈表
 */
Node *createList(){
    // 1.創(chuàng)建頭節(jié)點
    Node *head = (Node *)malloc(sizeof(Node));
    if(head == NULL){
        return NULL;
    }
    head->next = NULL;
    // 3.返回創(chuàng)建好的節(jié)點
    return head;
}
/**
 * @brief insertNode1 尾插法插入節(jié)點
 * @param head 需要插入的頭指針
 * @param data 需要插入的數(shù)據
 * @return  插入之后的鏈表
 */
void insertNode1(Node *head, int data){
    // 1.定義變量記錄最后一個節(jié)點
    Node *pre = head;
    while(pre != NULL && pre->next != NULL){
        pre = pre->next;
    }
    // 2.創(chuàng)建一個新的節(jié)點
    Node *cur = (Node *)malloc(sizeof(Node));
    cur->data = data;

    // 3.讓新節(jié)點鏈接到上一個節(jié)點后面
    pre->next = cur;
    // 4.當前節(jié)點下一個節(jié)點等于NULL
    cur->next = NULL;
    // 5.讓當前節(jié)點編程下一個節(jié)點的上一個節(jié)點
    pre = cur;
}
/**
 * @brief insertNode1 頭插法插入節(jié)點
 * @param head 需要插入的頭指針
 * @param data 需要插入的數(shù)據
 * @return  插入之后的鏈表
 */
void insertNode2(Node *head, int data){
    // 1.創(chuàng)建一個新的節(jié)點
    Node *cur = (Node *)malloc(sizeof(Node));
    cur->data = data;

    // 2.讓新節(jié)點的下一個節(jié)點指向頭節(jié)點的下一個節(jié)點
    cur->next = head->next;
    // 3.讓頭節(jié)點的下一個節(jié)點指向新節(jié)點
    head->next = cur;
}
/**
 * @brief printNodeList 遍歷鏈表
 * @param node 鏈表指針頭
 */
void printNodeList(Node *node){
    Node *head = node->next;
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;
    }
}

鏈表銷毀

/**
 * @brief destroyList 銷毀鏈表
 * @param head 鏈表頭指針
 */
void destroyList(Node *head){
    Node *cur = NULL;
    while(head != NULL){
        cur = head->next;
        free(head);
        head = cur;
    }
}

鏈表長度計算

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

鏈表查找

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

鏈表刪除

void deleteNodeList(Node *head, Node *find){
    while(head->next != find){
        head = head->next;
    }
    head->next = find->next;
    free(find);
}

作業(yè)

• 給鏈表排序

/**
 * @brief bubbleSort 對鏈表進行排序
 * @param head 鏈表頭指針
 */
void bubbleSort(Node *head){
    // 1.計算鏈表長度
    int len = listLength(head);
    // 2.定義變量記錄前后節(jié)點
    Node *cur = NULL;
   // 3.相鄰元素進行比較, 進行冒泡排序
    for(int i = 0; i < len - 1; i++){
        cur = head->next;
        for(int j = 0; j < len - 1 - i; j++){
            printf("%i, %i\n", cur->data, cur->next->data);
            if((cur->data) > (cur->next->data)){
                int temp = cur->data;
                cur->data = cur->next->data;
                cur->next->data = temp;
            }
            cur = cur->next;
        }
    }
}

/**
 * @brief sortList 對鏈表進行排序
 * @param head 鏈表頭指針
 */
void sortList(Node *head){
    // 0.計算鏈表長度
    int len = listLength(head);
    // 1.定義變量保存前后兩個節(jié)點
    Node *sh, *pre, *cur;
    for(int i = 0; i < len - 1; i ++){
        sh = head; // 頭節(jié)點
        pre = sh->next; // 第一個節(jié)點
        cur = pre->next; // 第二個節(jié)點
        for(int j = 0; j < len - 1 - i; j++){
            if(pre->data > cur->data){
                // 交換節(jié)點位置
                sh->next = cur;
                pre->next = cur->next;
                cur->next = pre;
                // 恢復節(jié)點名稱
                Node *temp = pre;
                pre = cur;
                cur = temp;
            }
            // 讓所有節(jié)點往后移動
            sh = sh->next;
            pre = pre->next;
            cur = cur->next;
        }
    }
}

• 鏈表反轉

/**
 * @brief reverseList 反轉鏈表
 * @param head 鏈表頭指針
 */
void reverseList(Node *head){
    // 1.將鏈表一分為二
    Node *pre, *cur;
    pre = head->next;
    head->next = NULL;
    // 2.重新插入節(jié)點
    while(pre){
        cur = pre->next;
        pre->next = head->next;
        head->next = pre;

        pre = cur;
    }
}