欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构——链表——不带头节点的单链表

程序员文章站 2022-03-15 18:13:44
...

不带头节点的单链表

/*
	功能:创建一个链表
	参数:无
	返回值:
		返回链表的第一个节点的地址
*/
Node * createLkList()
{

	ElemType data;
	Node * p = NULL;//用来保存新节点的地址
	Node * first = NULL;//用来保存 链表的第一个元素的 地址
	Node * last = NULL;//用来保存 链表的最后一个元素的 地址
	Node n;
	while(1)
	{
		//0,获取用户输入
		scanf("%d",&data);
		if(data == 0)//约定,用户输入0代表结束
		{
			break;
		}


		//不是0就把data加入 链式线性表 (链表)
		//1,分配空间
		p = (Node *)malloc(sizeof(Node));

		
		//为什么不像下面这样分配命名空间,而要用malloc动态分配
		/*
		p = &n;
		p->data = data;
		p->next = NULL;
		*/
		//2,保存数据
		p->data = data;
		p->next = NULL;

		//3,把该节点加入到 链表 中
		if(first == NULL)//当前是第一个节点
		{
			first = p;
			//p是右值,那就是 新分配的节点地址
			//first 在这是左值 ,整个的意思就是把新分配的节点的地址保存到指针变量first中去
			//那么我们就是 first指向了这个节点
			last = p;
		}
		else
		{
			#if 1
			//尾插法:每次把用户新输入的数据节点插入到链表的末尾
			//尾插法完成之后,链表的顺序就是用户输入的顺序
			//1 2 3
			//1----> 2 ----> 3
			last->next = p;//原来的last的指针域保存新节点的地址
			last = p;//新的节点就是last了
			#else
			//头插入:每次把用户新输入的数据节点插入到链表的头
			//头插法完成之后,链表的顺序就是用户输入顺序的逆序

			//1 2 3
			//3----> 2 ----> 1
			p->next = first;
			first = p;
			#endif
		}
	}

	return first;//返回此链表的第一个节点的地址,不然的话,找不到这个链表

}

/*
	功能:输出一个链表的所有节点数据
	参数:
		@first 这个链表的首地址 
	返回值:
		无
*/
void printfLkList(Node * first)
{
	Node * p = first;
	while(p != NULL)
	//while(p->next != NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}



void freeLkList(Node * first)
{
	Node * p = first;

	while(p!=NULL)
	{
		first = p->next;//保存p下一个地址
		p->next = NULL;//free只是表示这段空间不是我的了,别人可以用了,但是里面的内容并没有
					//清空,也就是说还可以通过它的next找到下一个节点,比较危险
					//为了避免这种清空,free之前需要把它的指针域清空
		free(p);//释放当前这个节点p
		p = first;//指向新的first,准备下一次循环
	}
	
}


/*
	功能:在一个链表中查找是否存在值为 x的元素
	参数:
		@first 链表的首地址
		@x需要查找的元素
	返回值
		查到返回1
		没查到返回0
		
*/
int find(Node * first,ElemType x)
{
	
	while(first)
	{
		if(first->data == x)
		{
			return 1;
		}
		first = first->next;
	}

	return 0;

}

/*
	功能:往有序链表中插入一个元素,使之仍然有序
	参数:
		@first 链表的首地址
		@x 需要插入的元素
	返回值:
		
*/
Node* insert(Node * first,ElemType x)
{
	Node * q = first;//用来循环
	Node * r = NULL;//用来保存q前面的那个节点
	//1,构造新节点
	Node * p = (Node *)malloc(sizeof(Node));
	p->data = x;
	p->next = NULL;

	//2,先找位置
	while(q)
	{
		if(q->data > x)
		{
			break;//找到了break,如果一直找不到,靠 q == NULL 结束while循环
		}
		r = q;
		q = q->next;
	}


	//3,判断是否找到
	if(q == NULL)//没找到,插入到末尾
	{
		r->next = p;
		//p->next = NULL;
	}
	else if(r == NULL)//找到了,并且第一个就比我大,插入到第一个前
	{
		p->next = first;
		first = p;
	}
	else
	{
		r->next = p;
		p->next = q;
	}

	//因为有插入在第一个节点前的情况,所有first是改变了的,需要返回新的first
	return first;
}


/*
	功能:删除链表中第一个值为x的元素
	参数:
		@first 链表首地址
		@x		要删除的节点的值
	返回值
		返回新链表的first
*/
Node * delete(Node * first,ElemType x)
{
	Node * p = first;//p保存要删除的那个节点
	Node * r = NULL;//用来保存p前面的那个节点
	//1,查找
	while(p)
	{
		if(p->data == x)
		{
			break;
		}
		r = p;
		p = p->next;
	}

	//2,判断找没找到
	if(p == NULL)//没找到
	{
		return first;
	}
	else//找到了
	{
		//分情况讨论
		if(p == first)//p是第一个节点
		{
			//删除第一个节点
			first = first->next;//保存新的first
			p->next = NULL;//释放一个节点之前,把它的指针域清空
			free(p);
		}
		else if(p->next == NULL)//p是最后一个节点
		{
			//最后一个节点已经删除,r就是最后一个节点
			r->next = NULL;
			p->next = NULL;
			free(p);
		}
		else
		{
			r->next = p->next;
			p->next = NULL;
			free(p);
		}
	}

	return first;
}


/*
	功能:删除链表中所有值为x的元素
	参数:
		@first 链表首地址
		@x		要删除的节点的值
	返回值
		返回新链表的first
*/
Node * deleteAll(Node * first,ElemType x)
{
	Node * p = first;//p保存要删除的那个节点
	while(1)
	{
		Node * r = NULL;//用来保存p前面的那个节点
		//1,查找
		while(p)
		{
			if(p->data == x)
			{
				break;
			}
			r = p;
			p = p->next;
		}

		//2,判断找没找到
		if(p == NULL)//没找到
		{
			return first;
		}
		else//找到了
		{
			//分情况讨论
			if(p == first)//p是第一个节点
			{
				//删除第一个节点
				first = first->next;//保存新的first
				p->next = NULL;//释放一个节点之前,把它的指针域清空
				free(p);
			}
			else if(p->next == NULL)//p是最后一个节点
			{
				//最后一个节点已经删除,r就是最后一个节点
				r->next = NULL;
				p->next = NULL;
				free(p);
			}
			else
			{
				r->next = p->next;
				p->next = NULL;
				free(p);
			}
		}

		if(r!=NULL)
		{
			p = r->next;
		}
		else
		{
			p = first;
		}
	}
	//return first;
}