Tags:

คือผมจำเป็นต้องทำโจทย์ โดยมีเนื้อหาให้รับรหัสเลขเป็นคิวต่อ ๆกัน
จากนั้นให้เราเลือกว่าเราจะให้ตัดคิวที่เท่าไหร่ออกไปทีละคิว ๆ
เช่น ผมมีเลขรหัส 1 3 5 2 4 จากนั้นถ้าให้ลบคิว 2 ออกไปก็จะเป็น 1 5 2 4
ถ้าลบคิว 3 ต่อไปอีกจะเป็น 1 5 4 เป็นต้น

จากโจทย์ข้างต้นซึ่งมีเวลากำหนดอยู่และไม่สามารถใช้ array ได้
ผมได้คำแนะนำมาให้ศึกษาเกี่ยวกับ double-linked list และ structure+pointer

ผมพอมีความรู้ในส่วนของ linked list มาบ้างแต่ยังไม่เข้าใจว่า double-linked list คืออะไร
และ structure มีความจำเป็นยังไง รวมไปถึงอยากให้อธิบายรูปแบบการใช้ pointer คร่าว ๆให้หน่อยได้ไหมครับ
เพราะผมใช้ pointer ไม่ค่อยเป็นอ่ะครับ

ขอความกรุณาผู้รู้ช่วยชี้แนะหรืออธิบายคร่าว ๆให้ผมสามารถนำไปศึกษาต่อยอดได้ จะเป็นพระคุณอย่างสูงเลยครับ
ขอบคุณล่วงหน้าทุกท่านที่มาตอบครับ ^^

Comments

By: korrawit
AndroidUbuntu
korrawit's blog
on 24/11/12 23:26 #510860 toggle
korrawit's picture

double linked list ก็คือ linked list ที่แต่ละตัวจะชี้ไปทั้ง 2 ทาง คือทั้งตัวก่อนหน้าและตัวถัดไปครับ (linked list ธรรมดาเนี่ยจะชี้ไปแค่ทางเดียวคือตัวถัดไป)

struct คือการรวมตัวแปรหลายประเภทเข้าด้วยกันให้เหมือนเป็นตัวเดียว นึกถึง 1 row ใน database ที่จะมีทั้ง ID, ชื่อ, นามสกุล, ที่อยู่ เป็นต้น ซึ่ง 1 row ในที่นี้ก็เหมือน 1 struct นั่นแหละครับ

ทีนี้ถามว่ามีความจำเป็นยังไง? ตัวเก็บข้อมูลของเราแต่ละตัว ก็ต้องมีตัวข้อมูลจริง ๆ (พวก 1, 3, 5) รวมกับ ตัวชี้ไปยังตัวก่อนหน้า และตัวชี้ไปยังตัวถัดไป ใช่มั้ยครับ :)

ตัวชี้ที่ว่าก็คือ pointer นั่นเองครับ pointer เป็น data type ชนิดหนึ่ง ที่เก็บข้อมูลที่อยู่ของหน่วยความจำของตัวแปรอื่นไว้ (เรียกว่า address) คือตัวมันเองไม่ได้เก็บข้อมูลตรง ๆ เหมือนตัวแปรพวก int, float, char น่ะครับ ส่วนวิธีใช้ ลองอ่าน cplusplus tutorial ดูครับ

ไม่รู้ว่าอธิบายตรงตามที่ต้องการรึเปล่านะครับ :)

By: mspire279
mspire279's blog
on 25/11/12 0:43 #510883 toggle
mspire279's picture

ขอบคุณมากเลยนะครับ ผมยังไม่ค่อยเข้าใจวิธีการเขียนเป็น code ออกมาในลักษณะของการ linked ไปที่ node ต่าง ๆซักเท่าไหร่
แต่เดี๋ยวจะลองไปศึกษาดูตามลิ้งที่ให้มานะครับ :D

By: mr_tawan
ContributoriPhoneAndroidWindows
mr_tawan's blog
on 25/11/12 3:21 #510892 toggle
mr_tawan's picture

ผมใบ้นิดนึงละกันครับ คือ double linkedlist มันจะมีโค๊ดหน้าตาประมาณนี้

struct node
{
    *node next;
    *node prev;

int value;

};

struct dlinkedlist
{
*node head;
}

ค่าของ next กับ prev เนี่ย สำหรับ node แรกให้ใส่เป็น NULL ไว้ เวลาที่เราต้องการเพิ่ม node ใหม่ต่อท้ายให้สร้าง node ใหม่ขึ้นมาแล้ว assign ค่า next เป็นตัว address ของ node ใหม่ ประมาณ

node* add(dlinkedlist& list, const int& value) { node* current = list.head; for(; head.next!=NULL;head = head.next) ;

current.next = (node*)malloc(sizeof(node));
current.next->value = value;
current.next->prev = current;
current.next->next = NULL;

return current.next;

}

ส่วนที่เหลือคิดว่า ถ้าพอทำความเข้าใจกับโค๊ด (ที่ไม่ค่อยสมบูรณ์) ข้างบนได้ก็น่าจะไปต่อได้แล้วครับ

ปล. ไอ้ตรง for อาจจะดูงง ๆ (และผมก็ไม่แน่ใจว่ามันจะคอมไพล์ผ่านบน C 555 แต่บน C++ ผมใช้ประจำ) มันเป็นการให้หาว่า node ไหนที่มี next เป็น NULL แค่นั้นแหละ


By: gogogokrit
gogogokrit's blog
on 25/11/12 10:59 #510941 Reply to:510892 toggle
gogogokrit's picture

ผมคิดว่าตรง for อาจจะทำให้งงๆ คิดว่าเปลี่ยน

for(; head.next!=NULL;head = head.next)

เป็น


while(head.next!=NULL)
{
head = head.next;
}

น่าจะเข้าใจง่ายกว่า นอกจากนี้เรายังสามารถแก้ไขให้สามารถแทรกกลางลงไปได้อีกด้วย (แต่ยุ่งยากพอสมควร)

ปล. ทำไมให้มันขึ้นบรรทัดใหม่ไม่ได้หว่า

By: mr_tawan
ContributoriPhoneAndroidWindows
mr_tawan's blog
on 28/11/12 1:34 #512197 Reply to:510941 toggle
mr_tawan's picture

I usually use 'for' loop for this kind of code instead of 'while', which I find it's quite often people forget to add the increment part at the end.

Well above is just an excuses, I'm just too lazy to correct the code.


By: KnightBaron
ContributoriPhoneRed HatWindows
KnightBaron's blog
on 26/11/12 18:06 #511549 Reply to:510892 toggle
KnightBaron's picture

ทำไมต้องแยก dlinkedlist ออกมาจาก Node ด้วยน่ะครับ? Head ก็ใช้ *prev->NULL / Tail ก็ใช้ *next->NULL ไปเลยไม่ได้เหรอครับ?


Aosekai

By: mr_tawan
ContributoriPhoneAndroidWindows
mr_tawan's blog
on 28/11/12 1:18 #512198 Reply to:511549 toggle
mr_tawan's picture

It's possible, but it add some overhead. Essentially dlinkedlist is to keep the common information while Node keeps only the data and the pointers to adjacent nodes.

you might try to think about what would be implemented on the list next, and you will know why I prefer separating these two. In fact it would be better to put the node struct inside the dlinkedlist, but it might look confusing for novices.


By: boatboat001
iPhoneWindows
boatboat001's blog
on 26/11/12 13:38 #511415 toggle
boatboat001's picture

ปกติในภาษา C แรกเริ่มเดิมทีมันมีแค่ตัวแปรแบบ primitive ครับ ตัวอย่างเช่นพวก int float หรือ char ไรงี้ครับ
ที่นี่มันไม่เพียงพอที่จะบรรยายสิ่งของโลกจริง (object) ที่มีความซับซ้อนได้ครับ
เค้าก็เลยคิดค้นตัวแปรแบบ structure ขึ้นมาเพื่อทำหน้าที่นี้ครับ

structure ก็คือ โครงสร้างของข้อมูลที่ประกอบไปด้วยตัวแปร primitive ที่เกี่ยวข้องเข้าด้วยกันครับ (หรือจะประกอบด้วย structure อื่นเข้าไปด้วยก็ได้ [structure-ception] ถ้า object นั้นๆ มีความซับซ้อนมากๆ)
ยกตัวอย่างเช่น structure ของ จุด (point) ก็จะประกอบตัวแปร int สำหรับเก็บค่าแกน x กับ ตัวแปร int สำหรับเก็บค่าแกน y ครับ

 
typedef struct Point Point;
struct Point {
    int x;
    int y;
};
 

ตัวอย่างที่ซับซ้อนขึ้นมาหน่อยก็เช่น structure ของ เส้น (line) ก็จะประกอบไปด้วยตัวแปร จุด (point) 2 จุด ที่เป็นตัวแปรแบบ structure ครับกับ ตัวแปร int สำหรับเก็บความยาวของเส้น

 
typedef struct Line Line;
struct Line {
    Point *p1;
    Point *p2;
    int length;
}; 
 

ตัวแปรแบบ pointer ก็เหมือน remote control ครับ ทำหน้าที่ชี้ไปที่อะไรก็ได้ที่เราต้องการครับ

แต่เราต้องไม่สับสนกับตัวแปร primitive นะครับ เพราะในขณะที่ตัวแปรแบบ primitive นั้นเก็บค่าที่เราใช้เอาไว้ในตัวของมันเอง ตัวแปรแบบ pointer จะไม่เก็บค่าไว้ในตัวโดยตรงครับ แต่มันจะเก็บที่อยู่ในหน่วยความจำของค่านั้นเอาไว้แทนครับ แล้วพอเราจะเรียกใช้ตัวแปร pointer มันก็จะทำการชี้ไปยังค่าในตัวแปรของเรา โดยการบอกที่อยู่ในหน่วยความจำให้เราแทนครับ

ยกตัวอย่างให้เห็นภาพหน่อยก็เช่น สมมุติว่าเราต้องการเก็บเลข 32 ถ้าเป็นตัวแปรแบบ primitive มันก็จะเก็บเลข 32 เอาไว้ในตัวมันเลย ในขณะที่ตัวแปรแบบ pointer จะทำการเก็บค่าที่อยู่ของเลข 32 ในหน่วยความจำไว้ครับ

 
ตัวแปรแบบ primitive --เก็บ--> 32
ตัวแปรแบบ pointer   --เก็บ--> 0x3E8FA0 (ที่อยู่ในหน่วยความจำที่เก็บเลข 32 เอาไว้ครับ) --ชี้ไปที่--> 32
 

ในภาษา C ปกติเราจะใช้ตัวแปร pointer กับ array หรือพวกตัวแปรที่ซับซ้อนแบบ structure หรือไม่ก็พวกกรณีพิเศษอื่นๆ ครับ
สังเกตง่ายๆ ที่ตัวแปรจะมีเครื่องหมาย * ติดอยู่ครับ ในตัวอย่าง structure ของ line ที่ผมยกให้ดูข้างต้นก็ได้ใช้ตัว pointer เป็นที่เรียบร้อยแล้วครับ :)

ในภาษา C นั้น linked list กับ double linked list ก็คือ structure ดีๆ นี่เองครับ วิธี implement ก็ตาม comment ข้างบนเลยครับ

แนวคิดของ linked list ก็คือ โครงสร้่างที่ประกอบไปด้วย node หลายๆ node ครับ (คล้ายๆ array) โดยที่แต่ละ node จะเก็บค่าไว้ในตัวมัน แล้วก็มี pointer ที่ชี้ไปยัง node ตัวถัดไป (next) ครับ ทำให้เราสามารถเดินผ่านแต่ละ node ที่มีอยู่ได้ เพียงแค่เดินไปตาม pointer ที่เก็บ node ตัวถัดไป ไปเรื่อยๆ ครับ

ส่วนของ double linked list ก็เพียงแค่ต่อยอดมาจาก linked list แบบปกติเองครับ โดยเพิ่มตัวแปร pointer สำหรับชี้ไปยัง node ตัวก่อนหน้า (previous) ครับ ทำให้เราสามารถเดินกลับได้ด้วย แค่นั้นเองครับ

หวังว่าคงเข้าใจขึ้นนะครับ :)


~ Always Wondering ~

By: BLiNDiNG
AndroidUbuntuWindowsIn Love
BLiNDiNG's blog
on 26/11/12 22:29 #511633 Reply to:511415 toggle
BLiNDiNG's picture

เสริมนิดนึงครับ

เพื่อกันการเรียกใช้ข้อมูลผิดประเภท จึงมีการกำหนดให้ใช้ type ของ pointer ให้ตรงกับ type ของข้อมูลที่จะไปชี้

char a;
char* pntr_a;

int b;
int* pntr_b;

node c;
node* pntr_c;

เวลาอ้าง address จะใช้เครื่องหมาย &

pntr_a = &a;

pntr_b = &b;

pntr_c = &c;

สังเกตว่าพอยเตอร์ก็มี type ที่ต้องใช้ให้ตรง


หา honeypot เจอหมีพูกอดไห......

By: mspire279
mspire279's blog
on 29/11/12 0:31 #512594 toggle
mspire279's picture

ขอบคุณทุกความคิดเห็นมากนะครับ เดี๋ยวผมจะค่อย ๆทดลองพยายามทำดูต่อไปนะครับ ^^