## 問題描述 > 設有一個帶頭結點的循環單鏈表，其結點值均為正整數。設計一個算法，反復找出單鏈表中結點值的最小的結點并輸出，然后將該結點從中刪除，直到單鏈表空為止，最后刪除頭結點 ## 算法思想 > 本題可以借鑒[ 第1章第2節練習題3 刪除最小值結點 ](http://blog.csdn.net/u013595419/article/details/50496681)的算法來實現，但是也應該注意到本題時循環單鏈表，因此判斷是否已經為空表的方法是`head->next==head`也就是頭節點的next域已經指向自身結點。具體的算法描述如下： ## 算法描述 ~~~ //循環調用，直至為空 while(head->next!=head){ pre=FindMin(head); DelMin(pre); } //發現最小值結點，并打印該結點 LinkList FindMin(LNode *head) { LNode *pre=head; LNode *p=head->next; LNode *premin=head; LNode *min=head->next; while(p!=head){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("%4d",min->data); return premin; } //刪除最小值結點 void DelMin(LNode *pre) { LNode *p=pre->next; pre->next=p->next; free(p); } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode *); LinkList FindMin(LNode*); void DelMin(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=head; head=CreatList(head); Print(head); LNode *pre=head; while(head->next!=head){ pre=FindMin(head); DelMin(pre); } Print(head); free(head); return 0; } //頭插法建立單鏈表 LinkList CreatList(LNode* head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //查找最小值結點 LinkList FindMin(LNode *head) { LNode *pre=head; LNode *p=head->next; LNode *premin=head; LNode *min=head->next; while(p!=head){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("%4d",min->data); return premin; } //刪除最小值結點 void DelMin(LNode *pre) { LNode *p=pre->next; pre->next=p->next; free(p); } //打印所有結點 void Print(LNode *head) { LNode *p=head->next; while(head!=p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~