2021-10-31【数据结构练习题】【删除表中值大于min且小于max的节点】

题目描述：已知单链表L是一个递增有序表，试编写一高效算法删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删除结点的空间，这里min和max是两个参数。请分析算法的时间复杂度。定义结构体struct LNode{int data;//数据域struct LNode *next;};typedef struct LNode LNode,* LinkList;初始化链表LinkL

Eternity_GQM

4129人浏览 · 2021-10-31 18:22:50

Eternity_GQM · 2021-10-31 18:22:50 发布

题目描述：

已知单链表L是一个递增有序表，试编写一高效算法删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删除结点的空间，这里min和max是两个参数。请分析算法的时间复杂度。

定义结构体

struct LNode{
	int data;//数据域
	struct LNode *next; 
};
typedef struct LNode LNode,* LinkList;

初始化链表

LinkList InitLNode(void){
	LinkList head;
	head = (LinkList)malloc(LEN);//生成有一个结构体大小的动态存储空间
	if(!head){
		printf("内存空间申请失败！\n");
		exit(ERROR);
	}
	head->data = 0;//头结点的数据域用来存放实际表长
	head->next = NULL;
	return head; 
}

创建一个链表

int CreatList(LinkList head){
	LinkList pleft,pright;
	pleft = head;
	pright = (LinkList)malloc(LEN);//指向新开辟的一段内存空间 要保证pleft和pright一前一后 
	printf("请按照递增的顺序向链表中赋值:(输入-1认为输入终止)\n");
	scanf("%d",&pright->data);
	while(pright->data!=-1){
		head->data++;//表长加1 
		pleft->next = pright;//pleft永远指向当前链表的最后一个结点 pright指向当前新生成的一个结点 
		pleft = pright;
		pright = (LinkList)malloc(LEN);
		scanf("%d",&pright->data);
	}
	pleft->next = NULL;
	free(pright);//pright的数据域是-1指针域没有赋值 也就是说pright所指结点并未链入到链表中 没有用了
	return OK;
}

删除结点

int delLNode(LinkList head,int num){
	if(!head->next){
		printf("空链表！\n");
		return ERROR;
	}
	LinkList pleft,pright;
	pleft = head;//指向头结点 
	pright = head->next;//指向第一个结点
	while(pright->data!=num&&pright!=NULL){
		pleft = pright;
		pright = pright->next;
	}
	if(pright->data==num){
		pleft->next = pright->next;//pleft = head避免了讨论如果删除的位置在第一个结点的情况 
		free(pright);
		head->data--;//表长减1 
	}else{
		printf("\n没有找到该数据!\n");
	}
	return OK;
}

删除介于MIN&MAN之间的结点

int delLink(LinkList head,float mink,float maxk){
	LinkList pleft,pright;
	pright = pleft = head->next;//指向第一个结点
	while(pright->data<=mink&&pright){
		pleft = pright;
		pright = pright->next;
	}
		
	if(!pright){
		printf("没有介于%g和%g之间的数据\n",mink,maxk);
		return ERROR;
	}
	while(pright->data<maxk&&pright){//跳出上个循环说明p->data > mink 再来判断一下与max的关系
		delLNode(head,pright->data);//删除这个结点之后pright所指的这个结点已经被free了 所以pright是一个野指针 没有具体的指向 
		pright = pleft->next;//所以要根据它的前一个指针重新定位指向
	}
	return OK;
}

遍历输出链表

int PrintLNode(LinkList head){
	if(!head->next){
		printf("空链表！\n");
		return ERROR;
	}
	LinkList p;//指向输出位置的结点 
	p = head->next;//首先指向第一个结点 p = head是初始指向了头结点
	printf("\n结果如下:\n");
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
	return OK;
}

完整code:

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define LEN sizeof(struct LNode) 
 
struct LNode{
	int data;//数据域
	struct LNode *next; 
};
typedef struct LNode LNode,* LinkList;
//初始化一个链表 
LinkList InitLNode(void){
	LinkList head;
	head = (LinkList)malloc(LEN);//生成有一个结构体大小的动态存储空间
	if(!head){
		printf("内存空间申请失败！\n");
		exit(ERROR);
	}
	head->data = 0;//头结点的数据域用来存放实际表长
	head->next = NULL;
	return head; 
}
//创建一个链表
int CreatList(LinkList head){
	LinkList pleft,pright;
	pleft = head;
	pright = (LinkList)malloc(LEN);//指向新开辟的一段内存空间 要保证pleft和pright一前一后 
	printf("请按照递增的顺序向链表中赋值:(输入-1认为输入终止)\n");
	scanf("%d",&pright->data);
	while(pright->data!=-1){
		head->data++;//表长加1 
		pleft->next = pright;//pleft永远指向当前链表的最后一个结点 pright指向当前新生成的一个结点 
		pleft = pright;
		pright = (LinkList)malloc(LEN);
		scanf("%d",&pright->data);
	}
	pleft->next = NULL;
	free(pright);//pright的数据域是-1指针域没有赋值 也就是说pright所指结点并未链入到链表中 没有用了
	return OK;
} 
//输出链表
int PrintLNode(LinkList head){
	if(!head->next){
		printf("空链表！\n");
		return ERROR;
	}
	LinkList p;//指向输出位置的结点 
	p = head->next;//首先指向第一个结点 p = head是初始指向了头结点
	printf("\n结果如下:\n");
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
	return OK;
}
//删除链表
int delLNode(LinkList head,int num){
	if(!head->next){
		printf("空链表！\n");
		return ERROR;
	}
	LinkList pleft,pright;
	pleft = head;//指向头结点 
	pright = head->next;//指向第一个结点
	while(pright->data!=num&&pright!=NULL){
		pleft = pright;
		pright = pright->next;
	}
	if(pright->data==num){
		pleft->next = pright->next;//pleft = head避免了讨论如果删除的位置在第一个结点的情况 
		free(pright);
		head->data--;//表长减1 
	}else{
		printf("\n没有找到该数据!\n");
	}
	return OK;
}
//删除介于两数之间的元素
int delLink(LinkList head,float mink,float maxk){
	LinkList pleft,pright;
	pright = pleft = head->next;//指向第一个结点
	while(pright->data<=mink&&pright){
		pleft = pright;
		pright = pright->next;
	}
		
	if(!pright){
		printf("没有介于%g和%g之间的数据\n",mink,maxk);
		return ERROR;
	}
	while(pright->data<maxk&&pright){//跳出上个循环说明p->data > mink 再来判断一下与max的关系
		delLNode(head,pright->data);//删除这个结点之后pright所指的这个结点已经被free了 所以pright是一个野指针 没有具体的指向 
		pright = pleft->next;//所以要根据它的前一个指针重新定位指向
	}
	return OK;
}
 
main(){
	LinkList head;
	float mink,maxk;
	head = InitLNode();
	CreatList(head);
	PrintLNode(head);
	printf("\n想删除介于哪两者之间的数据?\n");
	scanf("%f%f",&mink,&maxk);
	delLink(head,mink,maxk);
	PrintLNode(head);
}

INPUT:

请按照递增的顺序向链表中赋值:(输入-1认为输入终止)
1 3 5 7 9 -1

OUTPUT:

结果如下:
1 3 5 7 9
想删除介于哪两者之间的数据?
3 9

结果如下:
1 3 9

数据结构知识点

线性表

栈&队列

串

二叉树

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。