第1章第2节练习题21 输出并删除最小值结点
最后更新于：2022-04-01 19:51:23
## 问题描述
> 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值的最小的结点并输出，然后将该结点从中删除，直到单链表空为止，最后删除头结点
## 算法思想
> 本题可以借鉴[ 第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
#include
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");
}
~~~
';