Re: [問題] 鍊結串列在記憶體配置時，如何分散配置？

[maerdimer (void)]

※ 引述《frankhsu421 (問號)》之銘言：
: 我想將鍊結串列在一開始配置進記憶體時，不是佔用連續空間，
: 而是分散開的（沒有實際目的，純粹想實驗看看），
: 所以我先寫了下面這些程式碼：
: struct linked
: {
:     int value;
:     linked* next;
: };
:        .
:        .
:        .
:        .
: int main(){
:     int size;
:     cout<<"Linked List的欄位數：";
:     cin>>size;
:     linked* pl=new linked;
:     for(int i=0; i<size; i++){
:           linked* ptmp=pl;
:           ptmp->value=2*i;
:           if(i==size-1) ptmp->next=NULL;
:           else {ptmp->next=new linked; ptmp=ptmp->next;}
:     }
:        .
:        .
:        .
: }
: 但是執行後會發生錯誤，我猜原因是因為寫在迴圈內的
: linked* ptmp=pl;  及  ptmp->next=new linked;
: 只會執行一次，所以不會一直重複配置。
: 想請問：程式碼要怎麼寫才能達到我的目的？









version 1:

    size = 10;

    linked *p1 = new linked;

    for (int i = 0; i < size; i++) {
        linked *ptmp = p1;
        ptmp->value = 2 * i;

        if (i == size - 1) {
            ptmp->next = NULL;
        } else {
            ptmp->next = new linked;
            ptmp = ptmp->next;
        }
    }




linked *p1 = new linked;

┌───┐
│v: ???│
│next ?│
└───┘
  p1


i == 0:

linked *ptmp = p1;
ptmp->value = 2 * i;

┌───┐
│v: 0  │
│next ?│
└───┘
  p1
  ptmp


ptmp->next = new linked;

┌───┐ ┌───┐
│v: 0  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1
  ptmp

ptmp = ptmp->next;

┌───┐ ┌───┐
│v: 0  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1         ptmp






i == 1:

linked *ptmp = p1;
ptmp->value = 2 * i;
┌───┐ ┌───┐
│v: 2  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
 p1、ptmp

ptmp->next = new linked;
           ┌───┐ˊ???
           │v: ???│
           │next ?│
           └───┘
┌───┐ ┌───┐
│v: 2  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1、ptmp


ptmp = ptmp->next;

           ┌───┐ˊ???
           │v: ???│
           │next ?│
           └───┘
┌───┐ ┌───┐
│v: 2  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1         ptmp


        .
        .
        .






i == 9:
        .
        .
        .

           ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
           │v: ???│ │v: ???│ │v: ???│ │v: ???│ │v: ???│
           │next ?│ │next ?│ │next ?│ │next ?│ │next ?│
           └───┘ └───┘ └───┘ └───┘ └───┘
           ┌───┐ ┌───┐ ┌───┐
           │v: ???│ │v: ???│ │v: ???│
           │next ?│ │next ?│ │next ?│
           └───┘ └───┘ └───┘
┌───┐ ┌───┐
│v: 18 │ │v: ???│
│next ─→│next ─→ NULL
└───┘ └───┘
  p1         ptmp







version 2:

    size = 10;

    linked *p1 = new linked;
    linked *ptmp = p1;

    for (int i = 0; i < size; i++) {
        ptmp->value = 2 * i;

        if (i == size - 1) {
            ptmp->next = NULL;
        } else {
            ptmp->next = new linked;
            ptmp = ptmp->next;
        }
    }





linked *p1 = new linked;

┌───┐
│v: ???│
│next ?│
└───┘
  p1

linked *ptmp = p1;

┌───┐
│v: ???│
│next ?│
└───┘
  p1
  ptmp



i == 0:

ptmp->value = 2 * i;

┌───┐
│v: 0  │
│next ?│
└───┘
  p1
  ptmp

ptmp->next = new linked;

┌───┐ ┌───┐
│v: 0  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1
  ptmp



ptmp = ptmp->next;

┌───┐ ┌───┐
│v: 0  │ │v: ???│
│next ─→│next ?│
└───┘ └───┘
  p1         ptmp















i == 1:

ptmp->value = 2 * i;

┌───┐ ┌───┐
│v: 0  │ │v: 2  │
│next ─→│next ?│
└───┘ └───┘
  p1         ptmp

ptmp->next = new linked;

┌───┐ ┌───┐ ┌───┐
│v: 0  │ │v: 2  │ │v: ???│
│next ─→│next ─→│next ?│
└───┘ └───┘ └───┘
  p1         ptmp





ptmp = ptmp->next;

┌───┐ ┌───┐ ┌───┐
│v: 0  │ │v: 2  │ │v: ???│
│next ─→│next ─→│next ?│
└───┘ └───┘ └───┘
  p1                    ptmp
        .
        .
        .

i == 5:
        .
        .
        .

┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐  ┌───┐
│v: 0  │ │v: 2  │ │v: 4  │ │v: 6  │ │v: 8  │ │v: 10 │  │v: ???│
│next ─→│next ─→│next ─→│next ─→│next ─→│next ─→ │next ?│
└───┘ └───┘ └───┘ └───┘ └───┘ └───┘  └───┘
  p1                                                                 ptmp







結論：

1.畫圖就懂了

2.請做好縮排

3.每次 new 完，最後程式結束前請記得 delete


----

第一次在 BBS 畫圖... 不知道會不會很難懂... @rz

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.90.198
推 TaiwanXDman:不推不行
※ 編輯: maerdimer       來自: 111.252.90.198       (08/04 18:10)
推 kevin68x:精美
推 damody:精美貼圖風~
推 frankhsu421:感謝精美製圖
※ 編輯: maerdimer       來自: 111.252.90.198       (08/04 21:44)
推 coal511464:推 雖然目前沒遇過....但學了一課
推 k387259:哈哈 真淺顯易懂
※ 編輯: maerdimer       來自: 111.252.90.198       (08/05 00:25)
推 VictorTom:推精美的圖XD
推 dibery:這圖一定畫了很久
推 lairrol:偶爾來一下這樣精美的圖還不錯^^"
推 walker2009:意圖使人m文