【数据结构】C语言实现单链表的基本操作

//定义单链表数据类型
typedef struct LNode{
	int data;//数据域
	struct LNode* next;//指针域
}LNode, * LinkList;//结点与单链表数据类型
//初始化单链表
bool InitList(LinkList* L)//二级指针接收头指针的地址
{
	*L = (LNode*)calloc(1, sizeof(LNode));//为头结点申请空间
	if (!(*L)){
		return false;
	}
	(*L)->next = NULL;//将头结点定义域初始化为空指针，防止出现野指针
	return true;
}
//尾插法创建单链表
LinkList List_TailInsert(LinkList* L)
{
	assert(*L);//通过assert断言确保链表头指针不是空指针
	LNode* r = *L;//指向新结点的指针
	LNode* l = *L;//指向尾结点的指针
	int x = 0;//存储数据域元素的变量
	while (scanf("%d", &x) == 1)//通过scanf获取数据域存放的数据，这里采用多组输入简化代码
	{
		r = (LNode*)calloc(1, sizeof(LNode));//为新结点申请空间
		assert(r);//通过assert断言确保新结点成功申请了空间
		r->data = x;//将数据信息存放进新结点的数据域中
		r->next = l->next;//将尾节点指针域存放的地址信息存放进新结点的指针域中
		l->next = r;//将尾节点的指针域指向新节点的起始地址
		l = r;//新结点变成尾结点
	}
	return (*L);//返回链表
}
//打印链表
void Print_LinkList(LinkList L)
{
	printf("\n打印链表数据域的各个元素:>");
	LNode* p = L;//指向前一个节点的指针
	LNode* q = L;//指向后一个节点的指针
	while (q->next)//当q的指针域指向空指针时，表示q此时为表尾结点，不需要继续打印，直接退出循环
	{
		q = p->next;//将指针p的指针域存储的下一个节点的地址信息赋值给q
		printf("%d ", q->data);//此时指针q指向的需要打印的节点起始地址
		p = q;//将指针p指向已经打印过的节点
	}
	printf("\n");
}
int main()
{
	LinkList L;//指向单链表的指针L——头指针
	//初始化单链表
	if (InitList(&L)){
		L = List_TailInsert(&L);//创建单链表——尾插法
		Print_LinkList(L);//打印单链表
	}
	else{
		printf("初始化失败\n");//对初始化失败进行错误提示
	}
	return 0;
}

//按位查找
LNode* GetElem(LinkList L, int i)
{
	if (i < 1)
		return NULL;//当位序<1时，此时的位序不合理，返回空指针
	LNode* p = L->next;//寻找目标结点的指针,从表头结点开始查找
	int j = 1;//寻找的结点位序
	while (p && j < i)//当位序j与i相等时表示找到了对应的结点，退出循环
   //当p为空指针时，表示查找完成，没有找到对应的结点，退出循环
	{
		p = p->next;//指针p指向下一个结点
		j++;//查找下一个位序
	}
	return p;//查找结束后返回指针p
}

//按值查找
LNode* LocateElem(LinkList L, int e)
{
	LNode* p = L->next;//寻找目标结点的指针，从表头结点开始寻找
	while (p && p->data != e)//当结点数据域存放的值与目标值相等时，表示找到了对应结点，退出循环
	//当p为空指针时表示查找完全部结点，没有找到对应结点，退出循环
	{
		p = p->next;//指针p指向下一个节点
	}
	return p;//完成查找后返回指针p
}

//插入操作
New_LNode->next = Ahead_LNode->next;//将前一个位序的结点的指针域指向的内容存放入新结点的指针域中
Ahead_LNode->next = New_LNode;//将新结点的位置信息存放入前一个结点的指针域中

//插入过程
Ahead_LNode = GetElem(L, i - 1);//通过调用按位查找函数来找到位序为i-1的节点
New_LNode->next = Ahead_LNode->next;//将前一个位序的结点的指针域指向的内容存放入新结点的指针域中
Ahead_LNode->next = New_LNode;//将新结点的位置信息存放入前一个结点的指针域中

//后插操作
bool InsertNextNode(LinkList L,int i, ElemType e)
{
	LNode* p = GetElem(L, i - 1);//通过按位查找找到前驱结点p
	if (!p)
		return false;//如果前驱结点为空指针，则返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//为新结点申请空间
	assert(s);//如果空间申请失败，则报错
	s->data = e;//将要插入的元素存放入新结点的数据域中
	s->next = p->next;//将新结点的指针域指向前驱结点的指针域指向的空间
	p->next = s;//将新结点的地址存放入前驱结点的指针域中
	return true;//完成插入操作则返回true
}

//前插操作
bool InsertPriorNode( LNode* p, ElemType e)//需要指向前插操作的指针p与需要插入的数据e
{
	if (!p)
		return false;//如果需要指向前插操作的指针p为空指针，则无法执行前插操作
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//插入的新结点
	assert(s);//如果新结点申请空间失败，则报错
	s->data = p->data;//将p结点的数据域中的数据放置到新结点中
	s->next = p->next;//将p结点的指针域中的数据放置到新结点中
	p->next = s;//将新结点的位置信息放置到p结点的指针域中
	p->data = e;//将需要插入的数据信息放入到p结点的数据域中
	return true;//完成插入操作后返回true
}

//删除操作
bool ListDelete(LinkList* L, int i, ElemType* e)
{
	if (i < 1)
		return false;//当位序不合法时，返回false
	LNode* p = GetElem(*L, i - 1);//通过按位查找找到前驱结点
	assert(p);//当未找到前驱结点时，将会报错
	if (!(p->next))
		return false;//如果前驱结点p为表尾结点，则无法删除位序为i的结点，因此返回false
	LNode* q = p->next;//当位序i的结点合法且存在时，将该结点的信息存放进指针q中
	*e = q->data;//将需要删除的元素存放进变量e中
	p->next = q->next;//修改前驱结点p的指针域指向的对象
	free(q);//释放删除结点的内存空间
	return true;//完成删除后返回true
}