问题描写叙述

试编写在带头结点的单链表L中删除一个最小值结点的高效算法（如果最小值结点是唯一的）

算法思想

在链表中删除最小值的前提是必须找到最小值元素是哪个结点，因此设置指针p对全部结点进行遍历，使用指针min指向最小值结点。可是由于涉及到删除操作，明显在仅仅有指针min和指针p的条件下删除操作是极为不方便的。

若单纯的删除指针p指向的结点会造成断链。若採用的方法，又会出现多次赋值操作。

因此直接引入两个分别指向其前驱结点的指针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
      
       #include
       
        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");}