上次的Linked List 程式碼只教你怎麼「插入第一筆資料」和「刪除最後一筆資料」
但是卻沒有辦法「插入資料到兩筆中間」「刪除指定的資料」
這是因為我們還缺乏了走訪 (Traversal)的概念
所謂的走訪，就是從第一筆資料檢查，是否是我們要的對象，如果不是就往下一筆
直到找到正確的位置就往下一個走
而這要怎麼做到呢？
要準備 PreviousPtr 和 CurrentPtr 兩個指標
分別指向「目標的上一個」和「目標」
程式碼如下
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 插入一筆資料
把資料插在第一個位置，及把資料插在兩筆資料中間，程式碼是不相同的
所以必須分別寫兩個副程式
|
|
|
完成以上兩個副程式之後，
接下來就要探討整個程式架構，
流程如下..
整個完整插入的動作流程就是這樣
這個程式碼在最底下的 insert 函式 中
Deletion 刪除一筆資料
刪除資料也會碰上兩種情況
刪除放在第一筆的情況 delete *sPtr; *sPtr=(*sPtr)->nextPtr;
|
刪除放在兩筆資料中間的情況 先走訪，取得走訪結果 (*previousPtr)->nextPtr=newPtr; delete currentPtr; |
同樣地，刪除的流程如下
以下是完整程式碼
有兩個版本，第一個是經典版，比較複雜，但是建議初學者從這裡學起
(這個版本的 (*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;
}
留言列表
趨勢 Trends (1)