[問題] double linked 試做....居然compiler過了卻不能run....

[sansword (放下短暫追求永恆  Ｉ]

就像標題說的...

今天試做了一個double linked list...

結果compiler過  卻不能實際run(會出現windows XX程式發生問題的視窗...)

用的compiler 是 Dev-C++ 4

程式是寫出一個double linked list...

然後邊操作邊print 出來觀察list有沒有照我想要做的事情成立....

然後就....發生和標題說的一樣的事情了...orz



程式碼如下

#include <stdlib.h>
#include <stdio.h>
typedef int elementtype;
typedef struct node *ptrtonode;
typedef ptrtonode position;
typedef ptrtonode list;
typedef struct node{
   elementtype element;
   position previous;
   position next;  };

void makeempty(position P);
void DeleteList(list L);
position Find(elementtype X,list L);
void Insert(elementtype X,position P);
void Delete(elementtype X,list L);
void printlist(list L);
int main()
{     position l;
      makeempty(l);
      Insert(3,l);
      printlist(l);
      Insert(4,Find(3,l));
      printlist(l);
      Insert(5,Find(4,l));
      printlist(l);
      Insert(6,Find(5,l));
      printlist(l);
      Delete(5,l);
      printlist(l);
      DeleteList(l);
      system("PAUSE");
      return 0;
};

void DeleteList(list L)
{position temp;
  while(L->next!=NULL){
  temp=L->next->next;
  free(L->next);
  L=temp;              };
}

position Find(elementtype X,list L)
   {while(L->next!=NULL&&L->element!=X)L=L->next;
    return L;};

void makeempty(position P)
  {P=malloc(sizeof(struct node));
   P->previous=NULL;
   P->next=NULL;}


void Insert(elementtype X,position P)
  {position temp;
   temp=malloc(sizeof(struct node));
   temp->element=X;
   temp->previous=P;
   if(P->next!=NULL)
      {temp->next=P->next;
       temp->next->previous=temp;}
   else temp->next=NULL;
   P->next=temp;};

void Delete(elementtype X,list L)
  {position temp;
   temp=Find(X,L);
   if (temp->next!=NULL)
     {temp->previous->next=temp->next;
      temp->next->previous=temp->previous;}
   else temp->previous->next=NULL;
   free(temp);}

void printlist(list L)
  {position p;
   p=L->next;
   while(p!=NULL)
     {printf("%3d",p->element);
      p=p->next;};
   printf("\n");}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.191.249
→ sansword:由於compiler是過的...所以沒有錯誤訊息產生....
→ sansword:總之自認應該程式碼部分沒問題...可是硬生生不能run...
推 cptl:還沒細看程式碼,但compiler過只能說語法對,不能保證邏輯沒錯~
推 sansword:果然犯了大錯誤...感謝指教...
> -------------------------------------------------------------------------- <

作者: LPH66 (運命のルーレット廻して) 看板: C_and_CPP
標題: Re: [問題] double linked 試做....居然compiler過 …
時間: Fri Oct  7 07:55:21 2005

※ 引述《sansword (放下短暫追求永恆  Ｉ》之銘言：
: void DeleteList(list L)
: {position temp;
:   while(L->next!=NULL){
:   temp=L->next->next;
:   free(L->next);
:   L=temp;              };
: }
問題出在這一個函式

我把你的code寫成pseudocode

void DeleteList(L):=

    while L的下一個不接地
        temp ← L的下一個的下一個
        把L的下一個free掉
        L ← temp


好  現在假設剛傳進來的Linklist是這樣:

           Ｌ
           ↓
      ┌┬──┬┐    ┌┬──┬┐    ┌┬──┬┐
接    ││    │┼─→││    │┼─→││    │┼─→接
地←─┼│    ││←─┼│    ││←─┼│    ││    地
      └┴──┴┘    └┴──┴┘    └┴──┴┘

首先  檢查L的下一個接不接地  不接地

然後  temp ← L的下一個的下一個  所以

           Ｌ                             temp
           ↓                              ↓
      ┌┬──┬┐    ┌┬──┬┐    ┌┬──┬┐
接    ││    │┼─→││    │┼─→││    │┼─→接
地←─┼│    ││←─┼│    ││←─┼│    ││    地
      └┴──┴┘    └┴──┴┘    └┴──┴┘

再來  free掉L的下一個  所以

           Ｌ                             temp
           ↓                              ↓
      ┌┬──┬┐    ┌┬──┬┐    ┌┬──┬┐
接    ││    │┼─→││    │┼─→││    │┼─→接
地←─┼│    ││←─┼│    ││←─┼│    ││    地
      └┴──┴┘    └┴──┴┘    └┴──┴┘

黃色的那個node被free掉了

然後  L ← temp

所以

                                         L,temp
                                           ↓
      ┌┬──┬┐    ┌┬──┬┐    ┌┬──┬┐
接    ││    │┼─→││    │┼─→││    │┼─→接
地←─┼│    ││←─┼│    ││←─┼│    ││    地
      └┴──┴┘    └┴──┴┘    └┴──┴┘

灰色的是已經free掉了的

然後回到while  檢查L的下一個接不接地....?!?  所以就爆炸了

你可以用我畫的圖來思考一下該怎麼寫才對

注意到你有一個node沒有free到喔

--
"LPH" is for "Let Program Heal us"....

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.240.54
推 renderer:哇塞 還畫圖耶 真有心 推
推 qrtt1:對壓，呵，快偷偷收藏起來:P
推 khoguan:把你們寫的都收到精華區了 :-)
→ sansword:多謝!!!順利作出deleteList了
推 wefun:步推不行
> -------------------------------------------------------------------------- <

作者: qrtt1 (thinking in java) 看板: C_and_CPP
標題: Re: [問題] double linked 試做....居然compiler過 …
時間: Fri Oct  7 08:35:40 2005

亂改了一下XD
好久沒寫c了@"@
其實PO出來給大家劄伐一下才是

[slayer@rat testZone]$ cat dl.c
#include <stdlib.h>
#include <stdio.h>
#define  undef  -999
typedef int     elementtype;
typedef struct node *ptrtonode;
typedef ptrtonode position;
typedef ptrtonode list;
typedef struct node {
    elementtype     element;
    position        previous;
    position        next;
};

position        makeempty(position P);
void            DeleteList(list L);
position        Find(elementtype X, list L);
void            Insert(elementtype X, position P);
void            Delete(elementtype X, list L);
void            printlist(list L);

int
main()
{
    position        l;
    l = makeempty(l);
    Insert(3, l);
    printlist(l);
    Insert(4, Find(3, l));
    printlist(l);
    Insert(5, Find(4, l));
    printlist(l);
    Insert(6, Find(5, l));
    printlist(l);
    Delete(5, l);
    printlist(l);
    DeleteList(l);
    return 0;
};

void
DeleteList(list L)
{
    position        pnode = L->previous;
    position        cnode = L;
    position        tnode = L->next;

    free(L);
    while (pnode != NULL) {
        if (pnode)
            free(pnode);
        pnode = pnode->previous;
    }
    while (tnode != NULL) {
        if (tnode)
            free(tnode);
        tnode = tnode->next;
    }


}

position
Find(elementtype X, list L)
{
    while (L->next != NULL && L->element != X)
        L = L->next;
    return L;
};

position
makeempty(position P)
{
    P = malloc(sizeof(struct node));
    P->previous = NULL;
    P->next = NULL;
    P->element = undef;
    return P;
}


void
Insert(elementtype X, position P)
{
    position        temp;

    if (P->element == undef) {
        P->element = X;
        return;
    }
    temp = malloc(sizeof(struct node));
    temp->element = X;
    temp->previous = P;
    if (P->next != NULL) {
        temp->next = P->next;
        temp->next->previous = temp;
    } else {
        temp->next = NULL;
        P->next = temp;
    }
}

void
Delete(elementtype X, list L)
{
    position        temp;
    temp = Find(X, L);

    if (temp->next != NULL) {
        position        pnode = temp->previous;
        position        tnode = temp->next;
        pnode->next = tnode;
        tnode->previous = pnode;

    } else {
        temp->next = NULL;
    }

    free(temp);
}

void
printlist(list L)
{
    position        p;
    //p = L->next;
    p = L;
    while (p != NULL) {
        printf("%3d", p->element);
        p = p->next;
    };
    printf("\n");
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 210.59.94.119

> -------------------------------------------------------------------------- <

作者: qrtt1 (thinking in java) 看板: C_and_CPP
標題: Re: [問題] double linked 試做....居然compiler過 …
時間: Fri Oct  7 09:07:28 2005

※ 引述《LPH66 (運命のルーレット廻して)》之銘言：
: ※ 引述《sansword (放下短暫追求永恆  Ｉ》之銘言：
: : void DeleteList(list L)
: : {position temp;
: :   while(L->next!=NULL){
: :   temp=L->next->next;
: :   free(L->next);
: :   L=temp;              };
: : }
: 問題出在這一個函式
: 我把你的code寫成pseudocode
: void DeleteList(L):=
:     while L的下一個不接地
:         temp ← L的下一個的下一個

        問題不只這一個函式呦

以gdb debug：

# 找出發生錯誤的地點， p->element值不能存取合理懷疑此pointer沒正確配置
Program received signal SIGSEGV, Segmentation fault.
0x08048821 in printlist (L=0xbfbfebf8) at dl_old.c:101
101             printf("%3d", p->element);

將程式結束點提前：
main()
{
    position        l;
    makeempty(l);
    printlist(l);
    return 0;
//    Insert(3, l);
//    printlist(l);
    Insert(4, Find(3, l));
    printlist(l);
    Insert(5, Find(4, l));

# 一樣掛點，懷疑makeempty有問題
[slayer@rat testZone]$ gcc dl.c
dl.c:11: warning: useless keyword or type name in empty declaration
[slayer@rat testZone]$ ./a.out
Segmentation fault (core dumped)


再以gdb debug：

Breakpoint 1, main () at dl_old.c:23
23          makeempty(l);
(gdb) p *l

$1 = {element = 0, previous = 0x1, next = 0xbfbfecc8}
(gdb) s

# 進入makeempty函式
makeempty (P=0xbfbfebf8) at dl_old.c:61
61          P = malloc(sizeof(struct node));
(gdb) p *P
$2 = {element = 0, previous = 0x1, next = 0xbfbfecc8}
(gdb) s
62          P->previous = NULL;
(gdb) p *P
# 在函式中初始
$3 = {element = 0, previous = 0x0, next = 0x0}
(gdb) s
63          P->next = NULL;
(gdb) s
64      }
(gdb) s
main () at dl_old.c:24

# 進入Insert之前
24          Insert(3, l);
(gdb) p *l

# l沒有被初始
$4 = {element = 0, previous = 0x1, next = 0xbfbfecc8}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.59.94.119
※ 編輯: qrtt1           來自: 210.59.94.119        (10/07 09:10)
※ 編輯: qrtt1           來自: 210.59.94.119        (10/07 09:13)
※ 編輯: qrtt1           來自: 210.59.94.119        (10/07 09:14)
推 sansword:感恩您!!!!提醒我可以這樣檢查程式問題點
推 sansword:所以我只要malloc出來...就必須每個item都要有初始囉??
→ sansword:因為在這裡makeempty做出來的node我只想當header...
→ sansword:並不想真的放第一筆資料
> -------------------------------------------------------------------------- <

作者: sansword (放下短暫追求永恆  Ｉ 看板: C_and_CPP
標題: Re: [問題] double linked 試做....居然compiler過 …
時間: Sat Oct  8 01:27:28 2005

看了板上各位高手們的指教~~~

因為畢竟是本學期的自學作業....

所以並沒有完整的看Q大的程式碼...(這樣就不用自己寫啦~~~也學不到東西了說....)

被提點經過修改以後...今天終於run出來一點東西了...

有鑒於double linked list insert的時候會牽扯到那個位置的下一格是不是空的...

所以我多寫了一個function   addtoLast

如果現在要插入的位置下一個是空的...那就改為run這個function
(平常要在list最後加入一個node也可以用  感覺很方便....)

可是....問題來了....






這個function的code是這樣

void addtoLast(elementtype X,list L)
{position temp;

 while(L->next!=NULL){L=L->next;};

 temp=malloc(sizeof(struct node));
 temp->element=X;
 temp->next=NULL;
 temp->previous=L;
 L->next=temp;}


著色那行是為了讓L確定推到整個list的最後一個node....
偏偏就是這行的邏輯性出問題.....
  砍掉就很順....可是等於不能用...(會製造出斷頭List)
  不砍....錯誤視窗就無情的跑出來....

想破頭還是想不通為什麼......>"<  煩請各位指教....

--
回憶不會消失...只會被蓋在灰塵下...

              只要沒有風去吹動~~一切....就可以默默淡忘...

所以....不要成為那傷人的風吧.... ^.^                 

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.191.249
→ sansword:至於其他有bug的function..全部重寫了...都可以run的說~
→ sansword:再次大感謝!!!!
※ 編輯: sansword        來自: 140.119.191.249      (10/08 01:52)
※ 編輯: sansword        來自: 140.119.191.249      (10/08 06:13)
推 leeya:L有沒有可能一開始就NULL?