## 問題描述 > 設計一個遞歸算法，刪除不帶頭節點的單鏈表L中所有值為x的結點。 ## 算法思想 因為題目要求使用遞歸的方式刪除指定結點，那么我們可以先列出遞歸的基本模型： > 指針p指向要刪除的結點，指針q則為要刪除結點的后繼結點。 遞歸出口： ~~~ if(p==NULL){ return; } ~~~ 遞歸主體： ~~~ if(p->data==x){ p->data=q->data; p->next=q->next; free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } ~~~ 因為本題中，沒有設置頭節點，當刪除的時候必須從第一個結點開始刪除，因此我們參考[第1章第2節線性表的鏈式表示(1)](http://blog.csdn.net/u013595419/article/details/50481785)中的[2.5.2刪除自身結點](http://blog.csdn.net/u013595419/article/details/50481785#t12)來實現該算法。應當注意到如果最后一個結點的數據域為x時，需要區別對待。此時，指針q為空，如果繼續執行`p->data=q->data`時明顯會出錯，但也因為是最后一個結點，此時只需將指針p直接賦值為NULL便可。 算法描述如下： ## 算法描述 ~~~ void DelNodeX(LNode *p, ElemType x) { if(p==NULL){ return; } LNode* q=p->next; if(p->data==x){ if(q!=NULL){ p->data=q->data; p->next=q->next; }else{ p=NULL; } free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } } ~~~ 具體代碼見附件 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(); void DelNodeX(LNode*,ElemType); void Print(LNode*); int main(int argc,char* argv[]) { ElemType e=3; LNode *p; p=CreatList(); Print(p); DelNodeX(p,e); Print(p); return 0; } //尾插法建立單鏈表 LinkList CreatList() { LNode *p; LNode *s; ElemType x; scanf("%d",&x); p=(LNode*)malloc(sizeof(LNode)); p->data=x; LNode *r=p; while(1){ scanf("%d",&x); if(x==999){ break; } s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; } r->next=NULL; return p; } //刪除指定節點 void DelNodeX(LNode *p, ElemType x) { if(p==NULL){ return; } LNode* q=p->next; if(p->data==x){ if(q!=NULL){ p->data=q->data; p->next=q->next; }else{ p=NULL; } free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } } //打印所有節點 void Print(LNode *p) { while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~ 注：此種解法存在一個Bug，當最后一個或最后多個連續結點均為數據域為x的結點時，會留下一個數據域為x的結點，目前個人暫沒想到解決辦法，改天再想。