首页 > 代码库 > 第1章第2节练习题3 删除最小值结点
第1章第2节练习题3 删除最小值结点
问题描写叙述
试编写在带头结点的单链表L中删除一个最小值结点的高效算法(如果最小值结点是唯一的)
算法思想
在链表中删除最小值的前提是必须找到最小值元素是哪个结点,因此设置指针p对全部结点进行遍历,使用指针min指向最小值结点。可是由于涉及到删除操作,明显在仅仅有指针min和指针p的条件下删除操作是极为不方便的。
若单纯的删除指针p指向的结点会造成断链。若採用2.5.2删除自身结点的方法,又会出现多次赋值操作。
因此直接引入两个分别指向其前驱结点的指针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=http://www.mamicode.com/x;"hljs-built_in">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");
}
第1章第2节练习题3 删除最小值结点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。