看板 TL
作者 標題 [筆記] double linked list 實作
時間 2013年01月27日 Sun. PM 06:26:18
看板 C_and_CPP
作者 標題 [問題] double linked 試做....居然compiler過了卻不能run....
時間 Fri Oct 7 04:49:27 2005
就像標題說的...
今天試做了一個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
→ :由於compiler是過的...所以沒有錯誤訊息產生....1F 10/07 04:50
→ :總之自認應該程式碼部分沒問題...可是硬生生不能run...
→ :總之自認應該程式碼部分沒問題...可是硬生生不能run...
推 :還沒細看程式碼,但compiler過只能說語法對,不能保證邏輯沒錯~3F 10/07 09:50
推 :果然犯了大錯誤...感謝指教...4F 10/08 01:30
> -------------------------------------------------------------------------- <
看板 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
↓
┌┬──┬┐ ┌┬──┬┐ ┌┬──┬┐
接 ││ │┼─→││ │┼─→││ │┼─→接
地←─┼│ ││←─┼│ ││←─┼│ ││ 地
└┴──┴┘ └┴──┴┘ └┴──┴┘
首先 檢查L的下一個接不接地 不接地
然後 temp ← L的下一個的下一個 所以
L temp
↓ ↓
┌┬──┬┐ ┌┬──┬┐ ┌┬──┬┐
接 ││ │┼─→││ │┼─→││ │┼─→接
地←─┼│ ││←─┼│ ││←─┼│ ││ 地
└┴──┴┘ └┴──┴┘ └┴──┴┘
再來 free掉L的下一個 所以
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
推 :哇塞 還畫圖耶 真有心 推1F 10/07 09:01
推 :對壓,呵,快偷偷收藏起來:P2F 10/07 09:57
推 :把你們寫的都收到精華區了 :-)3F 10/07 13:59
→ :多謝!!!順利作出deleteList了4F 10/08 01:30
推 :步推不行5F 10/08 14:12
> -------------------------------------------------------------------------- <
看板 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
> -------------------------------------------------------------------------- <
看板 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)
推 :感恩您!!!!提醒我可以這樣檢查程式問題點1F 10/08 03:53
推 :所以我只要malloc出來...就必須每個item都要有初始囉??
→ :因為在這裡makeempty做出來的node我只想當header...
→ :並不想真的放第一筆資料
推 :所以我只要malloc出來...就必須每個item都要有初始囉??
→ :因為在這裡makeempty做出來的node我只想當header...
→ :並不想真的放第一筆資料
> -------------------------------------------------------------------------- <
看板 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
→ :至於其他有bug的function..全部重寫了...都可以run的說~1F 10/08 01:50
→ :再次大感謝!!!!
※ 編輯: sansword 來自: 140.119.191.249 (10/08 01:52)→ :再次大感謝!!!!
※ 編輯: sansword 來自: 140.119.191.249 (10/08 06:13)
推 :L有沒有可能一開始就NULL?3F 10/08 09:08
--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:26:18
※ 看板: TL 文章推薦值: 0 目前人氣: 0 累積人氣: 24
回列表(←)
分享