## 問題描述 > 試編寫在帶頭結點的單鏈表L中刪除一個最小值結點的高效算法（假設最小值結點是唯一的） ## 算法思想 > 在鏈表中刪除最小值的前提是必須找到最小值元素是哪個結點，因此設置指針p對所有結點進行遍歷，使用指針min指向最小值結點。但是因為涉及到刪除操作，明顯在只有指針min和指針p的條件下刪除操作是極為不方便的。若單純的刪除指針p指向的結點會造成斷鏈，若采用[2.5.2刪除自身結點](http://blog.csdn.net/u013595419/article/details/50481785#t12)的方法，又會出現多次賦值操作。因此直接引入兩個分別指向其前驅結點的指針pre和premin，如此，刪除操作過程會更加通俗易懂。 ## 算法描述 ~~~ void DelMin(LNode *head) { LNode *pre=head,*p=head->next; LNode *premin=pre,*min=p; while(p){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("Deleted Node: %4d\n",min->data); premin->next=min->next; free(min); } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); void DelMin(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; head=CreatList(head); Print(head); DelMin(head); Print(head); return 0; } //頭插法創建單鏈表 LinkList CreatList(LNode *head) { LNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=head->next; head->next=s; scanf("%d",&x); } return head; } //查找并刪除最小值結點 void DelMin(LNode *head) { LNode *pre=head,*p=head->next; LNode *premin=pre,*min=p; while(p){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("Deleted Node: %4d\n",min->data); premin->next=min->next; free(min); } //打印所有結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~