## 问题描述 > 试编写在带头结点的单链表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"); } ~~~