鏈表

對(duì)于確定長(zhǎng)度的同類型數(shù)據(jù)，之前學(xué)習(xí)了如何用數(shù)組存儲(chǔ)。對(duì)于長(zhǎng)度不確定的、經(jīng)常要改變的數(shù)據(jù)，我們則會(huì)選擇構(gòu)造一個(gè)被稱為鏈表（linked list）的結(jié)構(gòu)。

鏈表

鏈表由一系列存儲(chǔ)了數(shù)據(jù)的節(jié)點(diǎn)和他們之間的指向關(guān)系構(gòu)成。從第一個(gè)節(jié)點(diǎn)（鏈表頭）開始，每一個(gè)節(jié)點(diǎn)都會(huì)指向下一個(gè)節(jié)點(diǎn)，直到鏈表末端的一個(gè)節(jié)點(diǎn)為止。

C 語言通常會(huì)定義一個(gè)結(jié)構(gòu)體，來對(duì)鏈表節(jié)點(diǎn)進(jìn)行實(shí)現(xiàn)。在這結(jié)構(gòu)體中，有一系列數(shù)據(jù)，同時(shí)還有一個(gè)指向這一結(jié)構(gòu)體類型的指針。

在這種定義下，我們就可以通過將第二個(gè)節(jié)點(diǎn)的地址保存在第一個(gè)節(jié)點(diǎn)的指針變量中的方式實(shí)現(xiàn)節(jié)點(diǎn)之間的指向了。

相對(duì)于數(shù)組來說，鏈表有一定的優(yōu)勢(shì)和劣勢(shì)。

優(yōu)勢(shì)

存儲(chǔ)的元素?cái)?shù)不固定，數(shù)據(jù)結(jié)構(gòu)所需的內(nèi)存空間無需一開始就說明。
只要改變指針指向就可以動(dòng)態(tài)地在兩個(gè)節(jié)點(diǎn)之間插入數(shù)據(jù)。

劣勢(shì)

在內(nèi)存中不連續(xù)，查詢效率沒有數(shù)組高，需要從鏈表頭開始沿著指針方向依次訪問每一個(gè)節(jié)點(diǎn)才能到達(dá)目標(biāo)節(jié)點(diǎn)。

通過鏈表節(jié)點(diǎn)構(gòu)造一個(gè)鏈表

在這里，我們沒有太深入地對(duì)鏈表進(jìn)行操作，但是可以想一下如果我們要?jiǎng)h除一個(gè)節(jié)點(diǎn)、插入一個(gè)節(jié)點(diǎn)分別應(yīng)該怎么辦。

刪除一個(gè)節(jié)點(diǎn)，我們需要從head開始，沿著->next逐一地到達(dá)目標(biāo)節(jié)點(diǎn)。將目標(biāo)節(jié)點(diǎn)的前一節(jié)點(diǎn)的->next改為目標(biāo)節(jié)點(diǎn)當(dāng)前的->next內(nèi)保存的值。使用free將目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)的內(nèi)存空間釋放。

插入一個(gè)節(jié)點(diǎn)則需要?jiǎng)?chuàng)建一個(gè)新的節(jié)點(diǎn)，將鏈表目標(biāo)位置前的一個(gè)節(jié)點(diǎn)的->next修改為新的節(jié)點(diǎn)的地址，并將新的節(jié)點(diǎn)的->next插入目標(biāo)位置前的一個(gè)節(jié)點(diǎn)的原->next取值。

值得注意的是，在這一課的代碼中，我們?cè)诙褏^(qū)內(nèi)存上開了空間，但是沒有釋放。從內(nèi)存安全的角度出發(fā)，我們應(yīng)該還要在鏈表被使用完畢后釋放所有開辟給鏈表節(jié)點(diǎn)的堆區(qū)上內(nèi)存喔。

如果我們將鏈表的頭尾相連，我們還可以得到一個(gè)環(huán)形的鏈表，被稱為“循環(huán)鏈表”。

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} Node;

鏈表的性質(zhì)（判斷）：

image.png

問題：約瑟夫環(huán)

學(xué)習(xí)鏈表結(jié)構(gòu)后，需要用鏈表解決一個(gè)稍有改動(dòng)的“約瑟夫環(huán)（Josephus problem）”問題：
有N個(gè)同學(xué)圍成一圈，順序編號(hào)（分別為 1,2,3...n），從編號(hào)為 K的人開始報(bào) 1，他之后（順初始數(shù)字增長(zhǎng)方向計(jì)算序號(hào)）的人報(bào) 2，數(shù)到某個(gè)數(shù)字 M 的人出列。出列同學(xué)的下一人又從 1繼續(xù)報(bào)，數(shù)到某個(gè)數(shù) M 的人出列。重復(fù)直到所有人出列。

現(xiàn)需要根據(jù)同學(xué)人數(shù) N和給出的 K 和 M 計(jì)算出同學(xué)的正確出列順序。

輸入格式
輸入為一行，包括三個(gè)被空格分隔開的符合描述的正整數(shù) N、K和 M
（1≤K≤N≤1000，1≤M≤2000）。
輸出格式
輸出為一行，包含 N個(gè)整數(shù)，為依次順序出列的學(xué)生編號(hào)，由空格分隔開。

樣例輸入1

9 1 1

樣例輸出1

1 2 3 4 5 6 7 8 9

樣例輸入2

8 5 2

樣例輸出2

6 8 2 4 7 3 1 5

思路：在刪除循環(huán)鏈表節(jié)點(diǎn)的過程中，一般是先設(shè)置臨時(shí)指針，然后對(duì)臨時(shí)指針循環(huán)一圈，讓臨時(shí)指針在當(dāng)前的頭指針的前面，具體原理：鏈表修改的原理，臨時(shí)指針的next越過下節(jié)點(diǎn)，指向下下節(jié)點(diǎn)。同時(shí)將刪除的節(jié)點(diǎn)元素的內(nèi)存釋放出來。
遇到的坑主要有置空以后又引用，引起的段錯(cuò)誤。
代碼如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node *next;
} Node;                //構(gòu)造鏈表結(jié)構(gòu)體

Node *circle_create(int n);  //創(chuàng)建環(huán)的函數(shù)
void count_off(Node *head, int n, int k, int m);  //約瑟夫環(huán)出列函數(shù)

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    Node *head = circle_create(n);
    count_off(head, n, k, m);
    return 0;
}

Node *circle_create(int n) {
    Node *temp, *new_node, *head;
    int i;

    // 創(chuàng)建第一個(gè)鏈表節(jié)點(diǎn)并加數(shù)據(jù)
    temp = (Node *) malloc(sizeof(Node));  //臨時(shí)申請(qǐng)空間
    head = temp;                                          //申請(qǐng)到的空間賦給頭元素
    head->data = 1;

    // 創(chuàng)建第 2 到第 n 個(gè)鏈表節(jié)點(diǎn)并加數(shù)據(jù)
    for(i = 2; i <= n; i++) {              //”創(chuàng)指針“不斷開辟新空間，利用temp指針進(jìn)行跟隨
        new_node = (Node *) malloc(sizeof(Node));   //”創(chuàng)指針“申請(qǐng)臨時(shí)空間
        new_node->data = i;              
        temp->next = new_node;                      //臨時(shí)節(jié)點(diǎn)節(jié)點(diǎn)指向”創(chuàng)指針“
        temp = new_node;                                //”創(chuàng)指針“賦給臨時(shí)節(jié)點(diǎn)
    }

    // 最后一個(gè)節(jié)點(diǎn)指向頭部構(gòu)成循環(huán)鏈表
    temp->next = head;
    return head;
}

void count_off(Node *head, int n, int k, int m) {
Node *temp;
    temp = head;
    int i = 1;
    while(i<=n){
        temp = head;
        head = head->next;
        i++;         
    }                                            //置temp到head前一位
    i = 1;
    while(i<k){
        temp = head;
        head = head->next;
        i++;
    }                                        //head移到k號(hào)位置，temp移到k-1號(hào)位
    i = 1;
    while (1){
        while(i< m){
            temp = head;
            head = head->next;           //報(bào)m號(hào)，m號(hào)為head，temp則在head前一位
            i++;
        }
        i = 1;
        if (temp!= head){
            printf("%d ",head->data);                //輸出m號(hào)，即head節(jié)點(diǎn)內(nèi)容
            temp->next = head->next;              //這里把temp指向下下個(gè)節(jié)點(diǎn)
            free(head);                                      //輸出完了釋放head的內(nèi)存
            head = temp->next;                       //現(xiàn)在head就得是剛才head的下一位了
        }else {
            printf("%d",head->data);
            free(head);
            break;                               //實(shí)際上還應(yīng)該置野指針為NULL
        }
    }
    return;
}

共用體

它看起來和結(jié)構(gòu)體很像的東西，稱為共用體（union）。
結(jié)構(gòu)體特性解決了一系列不同類型的變量可以怎么被放在一起組織的問題；
而共用體，則使多種不會(huì)同時(shí)出現(xiàn)的變量共用同一塊內(nèi)存，十分方便。

共用體初始化：

定義共用體的關(guān)鍵字是union，一個(gè)共用體可以包括多個(gè)合法的類型描述成員，例如：

union register {
    struct {
        unsigned char byte1;
        unsigned char byte2;
        unsigned char byte3;
        unsigned char byte4;
    } bytes;
    unsigned int number;
};

這共用體所占用的內(nèi)存空間是被公用的，可通過struct類型的bytes和unsigned int類型的number兩種不同的類型描述成員進(jìn)行訪問。

無論我們通過哪一種描述成員訪問這一共用體，我們?cè)L問的都會(huì)是同一塊內(nèi)存空間。

image.png

如果用這個(gè)union register類型聲明一個(gè)變量reg。我們將可以通過reg.bytes按字節(jié)訪問或者通過reg.number整體訪問兩種不同的方式獲得或修改同一片內(nèi)存。

共用體在涉及到直接操作內(nèi)存的嵌入式編程、需要極度節(jié)省空間的通信協(xié)議設(shè)計(jì)中都會(huì)有它的優(yōu)勢(shì)。

在之前的內(nèi)容中，我們看到了一種通過共用體實(shí)現(xiàn)的可以整體修改，也可以按字節(jié)修改的類型。類似的，我們也可以定義一個(gè)既可以按位訪問，也可以按字節(jié)訪問的類型：

union {
    struct {
        unsigned char b1:1;
        unsigned char b2:1;
        unsigned char b3:1;
        unsigned char b4:1;
        unsigned char reserved:4;
    } bits;
    unsigned char byte;
}

這里有一個(gè)冒號(hào)是用來定義變量使用內(nèi)存的“位長(zhǎng)”的。這里:1、:4表示冒號(hào)前的變量只需要占 1 個(gè)和 4 個(gè)二進(jìn)制位，而不按照char類型默認(rèn)的字節(jié)數(shù)占用內(nèi)存。這樣，用這個(gè)類型生成的變量就可以被我們就按字節(jié)或者按位進(jìn)行訪問和使用了（這個(gè)概念被稱為位域（bit field），在其它場(chǎng)景下也可以被使用）。

再舉一個(gè)被設(shè)計(jì)出來專門儲(chǔ)存IP地址的共用體結(jié)構(gòu)。使用了它的變量，既可以存儲(chǔ) IPv4 的 IP 地址，也可以存儲(chǔ) IPv6 的 IP 地址，這些地址既可以作為一個(gè)整體被操作，也可以分幾個(gè)部分分別操作。

union {
    // IPv4 地址
    union {
        struct {
            unsigned char _reserved[12];
            unsigned char _ip_bytes[4];
        } _raw;
        struct {
            unsigned char _reserved[12];
            unsigned char _o1;
            unsigned char _o2;
            unsigned char _o3;
            unsigned char _o4;    
        } _octet;    
    } _IPv4;

    // IPv6 地址
    union {
        struct {
            unsigned char _IpBytes[16];
        } _raw;
        struct {
            unsigned short _w1;
            unsigned short _w2;
            unsigned short _w3;
            unsigned short _w4;
            unsigned short _w5;
            unsigned short _w6;
            unsigned short _w7;
            unsigned short _w8;   
        } _word;
    } _IPv6;
} _IP;

共用體其實(shí)也可以被視為一種特殊的結(jié)構(gòu)體，但是一般的結(jié)構(gòu)體中的成員會(huì)在內(nèi)存中對(duì)齊排列（如果你對(duì)這塊有興趣可以在互聯(lián)網(wǎng)上通過搜索多了解一些，我們?cè)谶@里不做過多介紹），而共用體則都選擇以同一位置作為起點(diǎn)，共用同一開始地址的內(nèi)存。

共用體類型的變量占用內(nèi)存的大小將會(huì)和他所有成員中占用內(nèi)存的最大的一致。
類型別名在共用體類型上的使用方式與在其他類型上相同,沒有區(qū)別。
和其他類型一樣,共用體類型也可以被用于結(jié)構(gòu)體類型定義。
和其他類型一樣,共用體類型也可以被用于結(jié)構(gòu)體類型定義。

驗(yàn)證共用體類型的變量取出的內(nèi)存地址是不是完全一致

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

typedef union type_x {
    char a;
    int b;
    float c;
} Type_x;

typedef struct type_y {
    char a;
    int b;
    float c;
} Type_y;

int main() {
    Type_x x;
    Type_y y;
    printf("%p %p %p\n", &(x.a),&(x.b),&(x.c));
    printf("%p %p %p\n", &(y.a),&(y.b),&(y.c));
    return 0;
}

可能的運(yùn)行結(jié)果：

0x7ffd44294e40 0x7ffd44294e40 0x7ffd44294e40                                  
0x7ffd44294e50 0x7ffd44294e54 0x7ffd44294e58

枚舉

C 語言提供了一種數(shù)據(jù)類型叫枚舉（enumeration）。由一系列整數(shù)成員組成，表示這一數(shù)據(jù)類型的變量可以取的所有可能值；但這些值都不直接以字面量形式存在，每一個(gè)值都被單獨(dú)給予了一個(gè)名字。例如：

enum week {
SUNDAY,
MONDAY,
TUESDAY,
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY
};
這種方式定義了一個(gè)與周相關(guān)的枚舉類型，其中每一個(gè)成員都會(huì)對(duì)應(yīng)一個(gè)編號(hào)。

當(dāng)像上面例子這樣沒有對(duì)它們進(jìn)行顯性的編號(hào)時(shí)，系統(tǒng)默認(rèn)編號(hào)會(huì)從 0開始。也就是如果直接使用SUNDAY，將和使用0一樣，而使用MONDAY則會(huì)相當(dāng)于使用了1，依此類推。
也可以給枚舉類型成員進(jìn)行顯性的編號(hào)。如果我們給SUNDAY編號(hào)為1

enum week {
    SUNDAY = 1,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
};

我們使用MONDAY則會(huì)相當(dāng)于使用了2，每一個(gè)成員都比之前編號(hào)多1

也可以給多個(gè)枚舉類型成員進(jìn)行顯性的編號(hào)。

enum week {
    SUNDAY = 1,
    MONDAY,
    TUESDAY,
    WEDNESDAY = 1,
    THURSDAY,
    FRIDAY,
    SATURDAY
};

當(dāng)將SUNDAY和WEDNESDAY都編號(hào)為1的時(shí)候，使用MONDAY或者使用THURSDAY則都會(huì)相當(dāng)于使用了2。

不難發(fā)現(xiàn)，其實(shí)可以對(duì)任何一個(gè)枚舉成員進(jìn)行顯性的編號(hào)，那么：
沒有顯性編號(hào)的其他成員的編號(hào)將從它之前一個(gè)顯性編號(hào)的成員開始計(jì)算，按順序依次加一獲得。

當(dāng)一個(gè)枚舉類型被定義以后，我們可以直接用這一類型聲明變量。如：

enum week {
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
};
enum week exam_date;

聲明了一個(gè)enum week類型的變量exam_date，它只能取定義過的枚舉類型中的成員名作為值，如exam_date = TUESDAY;。

與struct、union以及其它類型一樣，我們也可以給枚舉類型通過typedef設(shè)置類型別名。

輸出枚舉類型舉例：

#include <stdio.h>
typedef enum week {
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
} Week;
int main() {
    Week meeting_date;
    meeting_date = FRIDAY;
    printf("%d\n", meeting_date);
    return 0;
}

枚舉類型中成員的編號(hào)只能是整數(shù)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

12 重憶C之鏈表、共用體、枚舉

12 重憶C之鏈表、共用體、枚舉

鏈表

通過鏈表節(jié)點(diǎn)構(gòu)造一個(gè)鏈表

問題：約瑟夫環(huán)

共用體

共用體初始化：

驗(yàn)證共用體類型的變量取出的內(nèi)存地址是不是完全一致

枚舉

輸出枚舉類型舉例：

相關(guān)閱讀更多精彩內(nèi)容

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

12 重憶C之 鏈表、共用體、枚舉

鏈表

通過鏈表節(jié)點(diǎn)構(gòu)造一個(gè)鏈表

問題：約瑟夫環(huán)

共用體

共用體初始化：

驗(yàn)證共用體類型的變量取出的內(nèi)存地址是不是完全一致

枚舉

輸出枚舉類型舉例：

相關(guān)閱讀更多精彩內(nèi)容

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

12 重憶C之鏈表、共用體、枚舉