带头节点的单链表练习（写加注释花了5小时，已废）

目录

1.LinList.h

2.test.c

3.LinList.c

练习：建立一个单链表，首先依次输入元素1，2，...，10，然后删除元素5，最后依次显示当前表中元素

1.LinList.h

引入头文件，#deifne定义，typedef定义，函数声明

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int DataType;
typedef struct Node
{
	DataType data;
	struct Node* next;
}SLNode;

void ListInitiate(SLNode** head);//初始化链表
bool ListInsert(SLNode* head, int i, DataType x);//在第i个节点前插入x,i>=1
DataType ListDelete(SLNode* head, int i, DataType* x);//删除第i个节点
int ListLength(SLNode* head);//ListLength(head)当前元素个数
bool ListGet(SLNode* head, int i, DataType* x);//取元素
bool Destroy(SLNode** head);//撤销单链表

2.test.c

单链表的操作

#include "LinList.h"
//head->a0(头节点)->a1->...->ai->...->an
int main()
{
	SLNode* head;
	int i;
	DataType x, y;
	ListInitiate(&head);//初始化链表
	for (i = 1; i < 11; i++)
	{
		ListInsert(head, i, (DataType)i);//在第i个节点前插入i,i>=1
	}
	ListDelete(head, 4, &x);//删除第4个节点
	for (i = 1; i <= ListLength(head); i++)//ListLength(head)当前元素个数
	{
		ListGet(head, i, &y);//取元素
		printf("%d ", y);
	}
	Destroy(&head);//撤销单链表
	return 0;
}

3.LinList.c

单链表函数具体实现

#include "LinList.h"

void ListInitiate(SLNode** head)//初始化链表，head的值改变了，所以要传head地址
{
	*head = (SLNode*)malloc(sizeof(SLNode));
	assert(*head);
	(*head)->next = NULL;
}

bool ListInsert(SLNode* head, int i, DataType x)//在第i个节点前插入x,i>=1
{
	SLNode* L = head;
	int j = 0;//当前L指向的第j个节点
	while (L->next != NULL&&j<i-1)//循环结束时L指向第i-1个节点
	{//当L->next = NULL时，L已是最后一个节点，
	 //若j = i-1,在NULL前插入节点，若j != i-1,第i个节点不存在
		L = L->next;
		j++;
	}
	if (j != i - 1)
	{
		printf("插入元素的位置参数出错！\n");
		return false;
	}
	SLNode* s = (SLNode*)malloc(sizeof(SLNode));
	assert(s);
	s->data = x;
	s->next = L->next;
	L->next = s;
	return true;
}

DataType ListDelete(SLNode* head, int i, DataType* x)//删除第i个节点
{
	SLNode* L = head;
	int j = 0;//当前L指向的第j个节点
	while (L->next != NULL&&L->next->next != NULL && j < i-1)//循环结束时L指向第i-1个节点
	{//L->next->next = NULL时，
	 //若j = i-1,删除最后一个节点，若j != i-1,要删除的节点不存在
		L = L->next;
		j++;
	}
	if ((j != i - 1)||(L->next == NULL))//当空列表时，return false;
	{
		printf("要删除的第%d个节点不存在\n",i);
		return false;
	}
	*x = L->next->data;
	SLNode* s = L->next;
	L->next = L->next->next;
	free(s);
	s = NULL;
	return *x;
}

int ListLength(SLNode* head)//ListLength(head)当前元素个数
{
	if (head == NULL)
	{
		return 0;
	}
	SLNode* p = head;//习惯，防止后面找不到头节点
	int count = 0;
	while (p->next != NULL)
	{
		p = p->next;
		count++;
	}
	return count;
}

bool ListGet(SLNode* head, int i, DataType* x)//取元素
{
	SLNode* p = head;//习惯，防止后面找不到头节点
	if (i<1 || i>ListLength(head))
	{
		printf("取元素的位置参数错误！\n");
		return false;
	}
	while (i--)
	{
		p = p->next;
	}
	*x = p->data;
	return true;
}

bool Destroy(SLNode** head)//撤销单链表，head的值改变了，所以要传head地址
{
	int i = ListLength(*head) + 1;//头节点也要撤销
	SLNode* p = *head;
	SLNode* p1 = NULL;
	while (i--)
	{
		p1 = p->next;
		free(p);
		p = p1;
	}
	*head = NULL;
	return true;
}