成人app

雙向鏈表一

點擊打開在線編譯器,邊學邊練

1.  雙向鏈表的簡介&概念

單鏈表在很多時候已經可以勝任很多優秀的操作了,但是,單鏈表任然存在不足,所謂‘單鏈表’,是指結點中只有一個指向其后繼的指針,具有單向性,有時需要搜索大量數據的時候,就必須要多次進行從頭開始的遍歷,這樣的搜索不是很便利。

圖:單鏈表示意圖

31.png


成人app對此在單鏈表的基礎上,產生了雙向鏈表的概念,即: 在單鏈表的基礎上,對于每一個結點設計一個前驅結點,前驅結點與前一個結點相互連接,構成一個鏈表。

成人app雙向鏈表可以簡稱為雙鏈表,是鏈表的一種,它的每個數據結點中都有兩個指針,分別指向直接后繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和后繼結點。

圖:雙向鏈表示意圖

32.png

成人app一個完整的雙向鏈表應該是頭結點的pre指針指為空,尾結點的next指針指向空,其余結點前后相鏈。


2. 雙向鏈表的結點設計

成人app對于每一個結點而言,有:

33.png

成人app其中,DATA表示數據,其可以是簡單的類型(如int,double等等),也可以是復雜的結構體(struct類型);

pre代表的是前驅指針,它永遠指向當前結點的前一個結點,注意,如果當前結點是頭結點,則pre指針為空;

成人appnext代表的是后繼指針,它永遠指向當前結點的下一個結點,注意,如果當前結點是尾結點,則next指針為空

其代碼設計可以為:

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分別表示該結點的前驅(pre),后繼(next),以及當前數據(data)


3. 雙鏈表的創建

對于創建雙向鏈表,我們需要先創建頭結點再逐步的進行添加,請注意,雙向鏈表的頭結點是有數據元素的,也就是頭結點的data域中是存有數據的,這與一般的單鏈表是不同的。

對于逐步添加數據,我們采取的做法是,開辟一段新的內存空間作為新的結點,為這個結點進行的data進行賦值,然后將已成鏈表的上一個結點的next指針指向自身,自身的pre指針指向上一個結點。

其代碼可以設計為:

//創建雙鏈表
line* initLine(line * head){
    int number,pos=1,input_data;
    //三個變量分別代表結點數量,當前位置,輸入的數據
    printf("請輸入創建結點的大小\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //輸入非法直接結束
    //////頭結點創建///////
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("輸入第%d個數據\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
 
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("輸入第%d個數據\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
       
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}

初步看起來雙向鏈表似乎比單鏈表的兩種創建方法要復雜,其實將過程逐步拆解為 創建頭結點----創建一個新的結點----將頭結點和新結點相互鏈接----再度創建新結點……這樣的過程去思考,再反過頭多看幾遍代碼會有助于理解。



本文固定URL:http://hnsaiyang.com/course/98

上一課:單鏈表二 下一課:雙向鏈表二
第一章 數據結構入門
第二章 鏈表
第三章 棧
第四章 隊列
第五章 從C語言到C++
第六章 串,數組,矩陣,廣義表
第七章 樹
第八章 圖
第九章 算法—查找
第十章 算法—排序
第十一章 算法&競賽,思維培養
第十二章 后記
Dotcpp在線編譯      (登錄可減少運行等待時間)