当前位置：首页 > article >正文

C语言模拟实现简单链表的复盘

article 2025/2/6 17:11:41

代码引用自下面这个链接

https://blog.csdn.net/liyuanyue2017/article/details/83214908?fromshare=blogdetail&sharetype=blogdetail&sharerId=83214908&sharerefer=PC&sharesource=lfm147258369&sharefrom=from_link

自己实现

#include <stdio.h>
#include <malloc.h>

typedef int ElementType;//ElementType可以是任意类型
typedef struct LNode* List;
typedef struct LNode
{
	ElementType data;//数据域
	List next;//链表下一个元素地址
}LNode;
List L;

List Empty();//初始化链表
int Lenth(List L);//以遍历的方式求表长
List FindKth(int k, List L);//按序号查找
List Find(ElementType X, List L);//按值查找
List Insert(ElementType X, int i, List L);//插入第i个元素
List Delete(int i, List L);//删除第i个节点
void Print(List L);//打印链表
//初始化链表
List Empty()
{
	List L = (List)malloc(sizeof(struct LNode));
	L = NULL;
	return L;
}

//求表长
int Length(List L)
{
	List p = L;
	int count = 0;
	while (p)//当p不为空
	{
		p = p->next;
		count++;
	}
	return count;
}
//按序查找
List FindKth(int k, List L)
{
	List p = L;
	int i = 1;//从第一个元素开始找
	while (p && i < k)
	{
		p = p->next;
		i++;
	}
	if (i == k)
	{
		return p;//找到了
	}
	else
	{
		return NULL;//找不到
	}
}

//按值查找
List Find(ElementType X, List L)
{
	List p = L;
	while (p && p->data != X)
	{
		//如果找到了就返回那个元素的地址为p
		//找不到那个元素也就没有它的地址，所以返回的就是NULL
		p = p->next;
	}
	return p;

}

//插入第i个元素
List Insert(ElementType X, int i, List L)
{
	List p;
	List s;

	if (i == 1)//新节点插入在表头
	{
		List s = (List)malloc(sizeof(struct LNode));
		s->data = X;
		s->next = L;
		return s;//此时插入的节点s为头节点
	}
	else
	{
		p = FindKth(i - 1, L);//查找要删除的前一个元素
		if (!p)//如果p不存在
		{
			printf("节点错误\n");
			return NULL;
		}
		else
		{
			s = (List)malloc(sizeof(LNode));
			s->data = X;
			s->next = p->next;
			p->next = s;
			return L;
		}
	}
}

List Delete(int i, List L)
{
	List p;
	List s;
	if (i == 1)
	{
		s = L;
		if (L)//如果头节点不为空
			L = L->next;
		else
			return NULL;
		free(s);
		return L;
	}
	p = FindKth(i - 1, L);
	if (!p || !p->next)
	{
		printf("节点错误\n");
		return NULL;
	}
	else
	{
		s = p->next;
		p->next = s->next;
		free(s);
		return L;
	}

}

void Print(List L)
{
	List t;
	int flag = 1;
	printf("当前链表为:");
	for (t = L; t; t = t->next)
	{
		printf("%d ", t->data);
		flag = 0;
	}
	if (flag == 1)
	{
		printf("NULL\n");
	}
}


int main()
{
	L = Empty();
	Print(L);
	L = Insert(11, 1, L);
	Print(L);

	L = Insert(25, 1, L);
	Print(L);

	L = Insert(33, 2, L);
	Print(L);

	L = Insert(77, 3, L);
	Print(L);

	Print(L);
	printf("当前链表长度为：%d\n", Length(L));
	printf("此时链表中第二个结点的值是：%d\n", FindKth(2, L)->data);
	printf("查找22是否在该链表中：");
	if (Find(22, L))
		printf("是！\n");
	else
		printf("否！\n");
	printf("查找33是否在该链表中：");
	if (Find(33, L))
		printf("是！\n");
	else
		printf("否！\n");
	L = Delete(1, L);
	L = Delete(3, L);
	printf("----------删除后-----\n");
	Print(L);
	return 0;
}