【吉大刘大有数据结构绿皮书】例3.16：已知非空线性链表第一个结点的指针为list，写一算法，删除线性链表中的第i个结点。

P.S 本栏目所有文章均使用C语言，和书中的ADL语言以及C++语言有区别。

题目

例3.16：已知非空线性链表第一个结点的指针为list，写一算法，删除线性链表中的第i个结点。

思路及解答

题中说非空线性链表第一个结点的指针为list，说明这是个无头链表，有头链表都从哨位结点开始，先写出无头链表的基本 *** 作

#include 
#include
//无头链表结点结构体
typedef struct LinkNode {
	int data;//数据域
	struct LinkNode* next;//指针域
}LinkNode;
//无头链表结构体
typedef struct LinkList {
	LinkNode* list;//指向第一个结点的指针
}LinkList;
//初始化无头链表
void InitLinkList(LinkList* L)
{
	//最开始链表中无元素，所以front指针和tail指针都是NULL
	L->list = NULL;
}
//尾插法
void InsertTail(LinkList* L, int elem)
{
	//如果最开始链表是空的，则直接为front指针开辟内存空间
	if (L->list == NULL)
	{
		L->list = (LinkNode*)malloc(sizeof(LinkNode));
		if (L->list == NULL)
		{
			printf("内存不足！\n");
			return;
		}
		L->list->data = elem;
		L->list->next = NULL;
		return;
	}
	//如果链表非空，则需要先找到最后一个结点
	LinkNode* p = L->list;//获取第一个结点
	while (p->next != NULL)
	{
		p = p->next;
	}
	//创建新结点准备尾插
	LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));
	if (q == NULL)
	{
		printf("内存不足！\n");
		return;
	}
	q->data = elem;
	q->next = NULL;
	p->next = q;
	return;
}
//打印无头链表
void printLinkList(LinkList* L)
{
	//链表有元素才打印
	if (L->list != NULL)
	{
		LinkNode* p = L->list;//获取第一个元素
		while (p != NULL)
		{
			printf("%d\t", p->data);
			p = p->next;
		}
		printf("\n");
	}
}

题中所说的序号是和链表中的结点一一对应的，不是和下标一样从0开始，而是从1开始。接下来是本题的C语言版的答案：

//按序号删除结点，其中list为第一个结点
void DeleteByNumber(LinkList* L,LinkNode* list,int i)
{
	//检查输入是否合乎规定
	if (i < 1)
	{
		printf("序号不能小于1！\n");
		return;
	}
	//先处理删除第一个结点的情况，因为第一个结点删除后，链表即空，没有哨位结点，需要做特殊处理
	if (i == 1)
	{
		//先取第一个结点
		LinkNode* p = list;
		list = list->next;
		L->list = list;
		free(p);//删除内存空间，防止脏数据生成
		return;
	}
	//删除不是第一个结点的情况
	LinkNode* p = list;//找到第一个结点
	LinkNode* node = NULL;//获取前一个结点的临时变量
	//遍历找到要删除结点的前一个结点，条件k
	for (int k = 1; k < i; k++)
	{
		node = p;//先获取每次循环遍历之前的结点（这样能保证最后一次遍历,node是要删除结点的前一个结点，而p经历了一次p=p->next后变成了要删除的结点）
		//符合差分方程node=H(n-1)，p=H(n)
		p = p->next;
		if (p == NULL)
		{
			printf("链表中不存在第%d个结点！\n", i);
			return;
		}
	}
	//获取要删除的结点
	LinkNode* q = node->next;
	//孤立要删除的结点
	node->next = node->next->next;
	//释放删除结点的内存空间
	free(q);
}

完整的测试用代码如下（注释已经给出详细的实现思路）：

#include 
#include
//无头链表结点结构体
typedef struct LinkNode {
	int data;//数据域
	struct LinkNode* next;//指针域
}LinkNode;
//无头链表结构体
typedef struct LinkList {
	LinkNode* list;//指向第一个结点的指针
}LinkList;
//初始化无头链表
void InitLinkList(LinkList* L)
{
	//最开始链表中无元素，所以front指针和tail指针都是NULL
	L->list = NULL;
}
//尾插法
void InsertTail(LinkList* L, int elem)
{
	//如果最开始链表是空的，则直接为front指针开辟内存空间
	if (L->list == NULL)
	{
		L->list = (LinkNode*)malloc(sizeof(LinkNode));
		if (L->list == NULL)
		{
			printf("内存不足！\n");
			return;
		}
		L->list->data = elem;
		L->list->next = NULL;
		return;
	}
	//如果链表非空，则需要先找到最后一个结点
	LinkNode* p = L->list;//获取第一个结点
	while (p->next != NULL)
	{
		p = p->next;
	}
	//创建新结点准备尾插
	LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));
	if (q == NULL)
	{
		printf("内存不足！\n");
		return;
	}
	q->data = elem;
	q->next = NULL;
	p->next = q;
	return;
}
//打印无头链表
void printLinkList(LinkList* L)
{
	//链表有元素才打印
	if (L->list != NULL)
	{
		LinkNode* p = L->list;//获取第一个元素
		while (p != NULL)
		{
			printf("%d\t", p->data);
			p = p->next;
		}
		printf("\n");
	}
}
//按序号删除结点，其中list为第一个结点
void DeleteByNumber(LinkList* L,LinkNode* list,int i)
{
	//检查输入是否合乎规定
	if (i < 1)
	{
		printf("序号不能小于1！\n");
		return;
	}
	//先处理删除第一个结点的情况，因为第一个结点删除后，链表即空，没有哨位结点，需要做特殊处理
	if (i == 1)
	{
		//先取第一个结点
		LinkNode* p = list;
		list = list->next;
		L->list = list;
		free(p);//删除内存空间，防止脏数据生成
		return;
	}
	//删除不是第一个结点的情况
	LinkNode* p = list;//找到第一个结点
	LinkNode* node = NULL;//获取前一个结点的临时变量
	//遍历找到要删除结点的前一个结点，条件k
	for (int k = 1; k < i; k++)
	{
		node = p;//先获取每次循环遍历之前的结点（这样能保证最后一次遍历,node是要删除结点的前一个结点，而p经历了一次p=p->next后变成了要删除的结点）
		//符合差分方程node=H(n-1)，p=H(n)
		p = p->next;
		if (p == NULL)
		{
			printf("链表中不存在第%d个结点！\n", i);
			return;
		}
	}
	//获取要删除的结点
	LinkNode* q = node->next;
	//孤立要删除的结点
	node->next = node->next->next;
	//释放删除结点的内存空间
	free(q);
}
int main()
{
	LinkList* L = (LinkList*)malloc(sizeof(LinkList));
	if (L == NULL)
	{
		printf("内存不足！\n");
		return 0;
	}
	InitLinkList(L);
	InsertTail(L, 1);
	InsertTail(L, 2);
	InsertTail(L, 3);
	InsertTail(L, 4);
	InsertTail(L, 5);
	InsertTail(L, 6);
	printLinkList(L);
	DeleteByNumber(L,L->list, 6);
	printLinkList(L);
	DeleteByNumber(L,L->list, 1);
	printLinkList(L);
	DeleteByNumber(L, L->list, 2);
	printLinkList(L);
	DeleteByNumber(L, L->list, 4);
	printLinkList(L);
}

测试结果