上次的Linked List 程式碼只教你怎麼「插入第一筆資料」和「刪除最後一筆資料」

但是卻沒有辦法「插入資料到兩筆中間」「刪除指定的資料」

這是因為我們還缺乏了走訪 (Traversal)的概念

l22.PNG

所謂的走訪,就是從第一筆資料檢查,是否是我們要的對象,如果不是就往下一筆

直到找到正確的位置就往下一個走

而這要怎麼做到呢?

要準備 PreviousPtr 和 CurrentPtr 兩個指標

分別指向「目標的上一個」和「目標」

llll.PNG

程式碼如下

if ( (*currentPtr).nextPtr != NULL ) //如果目標的下一個不是NULL才繼續做

{
      previousPtr = currentPtr;
      currentPtr = (*currentPtr).nextPtr;
} //註解同上圖

 

當然你也可以替走訪增加停止條件 (這裡的條件都設定成相反條件)

例如插入的情況

while ( (*currentPtr).nextPtr != NULL && (*currentPtr).data > 使用者輸入值 )

{
      previousPtr = currentPtr;
      currentPtr = (*currentPtr).nextPtr;
}

( 這樣的話,你的List,後面的值永遠比前面的大 )


例如刪除的情況

if ( (*currentPtr).nextPtr != NULL && (*currentPtr).data != 使用者輸入值 )

{
      previousPtr = currentPtr;
      currentPtr = (*currentPtr).nextPtr;
}

( 這樣的話,找到使用者輸入值之後,就會停止走訪 )


 


Insertion 插入一筆資料

 

把資料插在第一個位置,及把資料插在兩筆資料中間,程式碼是不相同的

所以必須分別寫兩個副程式

 
   (*newPtr).nextPtr=*sPtr;   
   *sPtr=newPtr


middle.GIF    
          先走訪,取得走訪結果
 (*previousPtr)->nextPtr=newPtr;
 (*newPtr)->nextPtr = currentPtr

 

 


完成以上兩個副程式之後,

接下來就要探討整個程式架構,


流程如下..

proc.GIF

整個完整插入的動作流程就是這樣

這個程式碼在最底下的 insert 函式 中

 


Deletion 刪除一筆資料

刪除資料也會碰上兩種情況

刪除放在第一筆的情況

    delete *sPtr;
    *sPtr=(*sPtr)->nextPtr;

 

 

刪除放在兩筆資料中間的情況
middle2.GIF
   先走訪,取得走訪結果
   (*previousPtr)->nextPtr=newPtr;
   delete currentPtr;

 

      同樣地,刪除的流程如下

proc2.GIF

 


以下是完整程式碼

有兩個版本,第一個是經典版,比較複雜,但是建議初學者從這裡學起

(這個版本的 (*currentPtr).nextPtr 一律用 currentPtr->nextPtr來表示,特別註明以免看不懂)

第一版本

#include<stdio.h>
#include<stdlib.h>

struct listNode{
       int data;
       struct listNode *nextPtr;
       };

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *sPtr,int value);
void result(ListNodePtr currentPtr);
int del(ListNodePtr *sPtr, int value);

int main()
{
    ListNodePtr startPtr = NULL;
    int item;
    int choice=0;

    printf("使用說明:\n任何時候都可以1)輸入99進入刪除模式 2)輸入88返回插入模
式");

    while(item==item)
    {
      while(item!=99)
      {
        printf("\n請輸入一個數值來插入 : ");
        scanf("%d",&item);
        insert(&startPtr,item);/*丟給insert函式「第一個Node」和「插入值」*/
        result(startPtr);

      }

      while(item!=88)
      {
        printf("\n請輸入一個數值來刪除 : ");
        scanf("%d",&item);
        del(&startPtr,item);/*丟給del函式「第一個Node」和「刪除值」*/
        result(startPtr);}}

    system("pause");

    return 0;

}

void insert(ListNodePtr *sPtr,int value){

     ListNodePtr newPtr;
     ListNodePtr previousPtr;
     ListNodePtr currentPtr;

     /* 去和電腦要一塊記憶體給newPtr */
     newPtr=(ListNodePtr)malloc(sizeof(ListNode));

     if(newPtr!=NULL){ /*有要到記憶體才能繼續做下去*/
       /* 把新插入的Node初始化 */
       newPtr->data=value;
       newPtr->nextPtr=NULL;

       previousPtr=NULL;

       currentPtr=*sPtr; /*先把currentPtr設為第一個Node....*/

       while(currentPtr!=NULL && value > currentPtr->data)  /*...再從第一項逐
項找到空的Node為止...*/
       {                        /*....就可以查出要插入的位子(currentPtr)*/
          previousPtr = currentPtr; /*走到...*/
          currentPtr = currentPtr->nextPtr;   /*...下一個Node*/


       }
       /*( ↑副產品:previousPtr和currentPtr的設置 )*/

       if(previousPtr==NULL)/*處理  插在第一個位置  的情況*/
       {
          newPtr->nextPtr=*sPtr;
          *sPtr=newPtr;
       }
       else /* 處理  插在previousPtr和currentPtr兩個Node之間  的情況 */
       {
          previousPtr->nextPtr=newPtr;
          newPtr->nextPtr = currentPtr;
       }
     }else{
     /*如果沒有要到記憶體的情況*/
       printf("孩子,記憶體不足,不能再插啦!");
     }

}

void result(ListNodePtr currentPtr){ /*其實接受的是第一個Node...*/
                                     /*....因為要從第一個Node顯示*/

     while(currentPtr!=NULL){

        printf("%d -> ",currentPtr->data); /*顯示目前所在Node*/
        currentPtr = currentPtr->nextPtr;   /*走到下一個Node*/


     }
     printf("NULL");

}

int del(ListNodePtr *sPtr, int value)
{
     ListNodePtr tempPtr;
     ListNodePtr previousPtr;
     ListNodePtr currentPtr;

     if(value == (*sPtr) -> data ) /*如果要刪除的是第一個Node*/
     {
          tempPtr=*sPtr; /*紀錄一下待會誰的記憶體要被釋放*/
          (*sPtr)=(*sPtr)->nextPtr; /*這句才是重點!!*/
          free(tempPtr); /*釋放吧記憶體!*/
          return 0; /*刪除完畢 收工!*/

     }
     else /*如果要刪除的並不是第一個node,在此準備處理第二個Node的變數*/
     {
         previousPtr = (*sPtr);
         currentPtr = (*sPtr)->nextPtr;
     }

     /*以下從第二個Node開始處理*/
     if(currentPtr!=NULL){ /*如果第二個Node不是空的 才做 */

        while(currentPtr!=NULL && currentPtr->data != value ) /*搜尋要被刪除
的Node*/
        {  /*之所以有 currentPtr!=NULL 這個條件,是怕你給了一個資料沒有的值,
會無止境的搜尋 */

          previousPtr = currentPtr; /*走到...*/
          currentPtr = currentPtr->nextPtr;   /*...下一個Node*/
        }

        if(currentPtr!=NULL)
        {
          tempPtr=currentPtr; /*紀錄等等哪個Node的記憶體要釋放*/
          previousPtr->nextPtr = currentPtr -> nextPtr; /*重點在此*/

          free(tempPtr); /*釋放吧記憶體*/
        }

     }

}

 


 

第二個版本是作者自己的風格

特色是把走訪丟給一個叫做traversal的函式去做

#include<iostream>

class listNode{
     
      public:
             int data;
             class listNode *nextPtr;
     
};


listNode *currentPtr;
listNode *PreviousPtr;

void traverse(listNode **sPtr,int request)
{
    
     PreviousPtr=NULL;
     currentPtr = *sPtr; //初始化,使其從頭找起


     //開始走訪
     //停止條件為 (1)currentPtr的next為NULL 或 (2)currentPtr已指到目標    

     while( currentPtr != NULL && (*currentPtr).data < request )
     { 
         PreviousPtr = currentPtr;
         currentPtr = (*currentPtr).nextPtr;
     }

}

void insert(listNode **sPtr,int get_data){
   
    listNode *newPtr;
    newPtr= new listNode; //給予newPtr指標所指的地方一個記憶體位置
    (*newPtr).data=get_data;

    currentPtr = *sPtr;
   
    traverse(sPtr,get_data);  //先走訪一次
   
    if(PreviousPtr==NULL){ //如果插入位置在第一格
        (*newPtr).nextPtr=*sPtr;    //插入的Node,nextPtr指向原本的startPtr
        *sPtr=newPtr; //startPtr指向新插入的Node
    }
    else{ //如果插入位置不在第一格
       (*PreviousPtr).nextPtr=newPtr;  //PreviousNode的nextPtr指向新插入的Node
       (*newPtr).nextPtr=currentPtr; //新插入的Node的Next指向currentPtr
    }
      
}


void del(listNode **sPtr,int get_data)
{
    currentPtr = *sPtr;//初始化
   
    if((*currentPtr).data == get_data)
    {
       delete *sPtr;
       *sPtr=(*sPtr)->nextPtr;
    }
    else
    {
       traverse(sPtr,get_data);
       (*PreviousPtr).nextPtr = (*currentPtr).nextPtr;
       delete currentPtr;
    }

}

void display(listNode *currentPtr){
    

     while(currentPtr!=NULL){
        std::cout<< currentPtr->data <<" -> "; /*顯示目前所在Node*/
        currentPtr = currentPtr->nextPtr;   /*走到下一個Node*/

     }
     printf("NULL\n");
    
}

int main(){
   
    listNode *startPtr=NULL;
   
    int num,counter=0;
   
    std::cout<<"使用說明"<<std::endl<<"平常時候輸入的資料會依照大小插入串列"<<std::endl;
    std::cout<<"但輸入次數逢三的倍數,就會變成刪除"<<std::endl<<"刪除的時候要注意刪除的值務必存在,以免當機"<<std::endl;
   
    while(1){
      if(counter%3!=2){
          std::cout<<"請輸入要插入的資料 : ";
          std::cin>>num;
          insert(&startPtr,num);
      }
      else{
          std::cout<<"請輸入要刪除的資料 : ";
          std::cin>>num;
          del(&startPtr,num);
      }
      if(num==7777){break;}
      counter++;
      display(startPtr);
    }
   
    system("pause");
   
    return EXIT_SUCCESS;
   
}


arrow
arrow
    全站熱搜

    finalfrank 發表在 痞客邦 留言(1) 人氣()