เป็นการเอาโหนดใหม่ไปแทรกในลิสต์ให้ถูกที่

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

แนวทางการวิเคราะห์ปัญหา

หากลิงค์ลิสต์มีการเรียงลำดับโหนดตามรายชื่อดังนี้

 

 

 

 

 

root

 

 

                      การนำโหนดใหม่เข้าไปแทรกในลิงค์ลิสต์ข้างต้นย่อมขึ้นอยู่กับโหนดใหม่ที่จะนำไปแทรกว่ามีชื่ออะไร  หากโหนดใหม่เก็บชื่อ  anant การนำโหนด  anant  ไปแทรกในลิสต์ย่อมต้องแทรก้านหน้าสุดของลิสต์  เพราะในทำนองเดียวกัน  หากโหนดใหม่มีชื่อ  satit  โหนด  satit  ก๊ต้องถูกแทรกหน้าโหนด suda แต่หลัง  malee  หรือหากโหนดใหม่มีชื่อ  yupin  แน่นอน  การแทรกย่อมเกิดที่ปลายจุด

ขั้นตอนวิธี

1.        ให้ใช้พอยเตอร์ 2 ตัว คือ  start  กับ  prev   โดยที่  prev  ตามติดโหนด start  ใช้  start  เป็นพอยเตอร์เพื่อท่องเข้าไปในลิงค์ลิสต์เพื่อหาตำแหน่งของโหนดที่สามารถนำโหนดใหม่  ซึ่งมี  p ชี้อยุ่เข้าไปแทรกยังด้านหน้าของโหนดที่มี start ชี้อยู่โดยวนลูปด้วยคำสั่ง  while ((strcmp(start->name, p -> name)<0&& (start->next !=NULL))

2.        เมื่อรู้ตำแหน่งที่จะแทรกแล้ว  ก็พิจารณาดูว่า  โหนดใหม่ที่จะแทรกนั้นเป็นการแทรกด้านหน้าหรือที่ปลายระหว่างโหนดสองโหนด

ตัวอย่าง   การเขียนฟังก์ชั่นชื่อ  insertNode  เพื่อนำโหนดใหม่ที่ชี้โดย p  ไปแทรกในลิงค์ลิสต์ที่มี  root ชี้อยู่ที่หัว  ลิสต์นี้ได้มีการเรียงโหนดเรียงลำดับชื่อจากน้อยไปมาก

 

                    Void  insertNode(ptr  **root , Ptr  *p)

                     }

                              Ptr  *start,  *prev ;

                              If  (*root  = = NULL )                             /*กรณีลิงค์ลิสต์ว่างเปล่า*/

                                         *root = p ;

                              else

                               {

                                            start = *root ;                                   /*ใช้startเป็นตัวท่องเข้าไปในลิสต์*/

                                       whaile ((strcmp (start->name, p->name)   <  0 ) &&

                                                                   (start -> next   ! = NULL))

                                        {

                                                        prev = start ;                            */ให้ prev ตามติดอยู่หลัง start*/

                                                         start =sart ->next ;

                                                }

                                                if (strcmp (start->name, p ->name = =0)           /* กรณีชื่อซ้ำๆ*/

                                                    printf (“Record already exists ! ”) ;

                                                else

                                                            if (strcmp(start->name,p->name)  <0) ;

                                                     {

                                                                   start -> next = p ;

                                                                   p -> next =NULL

                                                                }

                                                                else

                                                                                if (start = = *root)

                                                                     {

                                                                                      p-> next  = *root ;

                                                                                                *root = p ;

                                                                                  }

                                                                                else

                                                                                {

                                                                                                p -> next = start ;

                                                                                                prev - > next = p ;

                                                                                }

                                                }  /* else  ของ  if  (*root  = = NULL ) */

                                }    /*  insertNode */