【数据结构】_以单链表为例分析各种方法实现的特殊情况考虑思路

目录

1. 尾插SLTPushBack

2. 头插SLTPushFront

3. 尾删SLTPopBack

4. 头删SLTPopFront

5. 指定位置前插入

6. 指定位置前删除

对于每一种方法的具体实现，都不能仅简单考虑链表具有多个结点的情况，对于空链表等特殊情况都需特殊情况特殊分析，才能保证不出现空指针解引用等情况。

现以某几个方法为例，分析特殊情况的考虑思路。

1. 尾插SLTPushBack

1、考虑具有若干结点的情况，创建结构体指针变量curNode，令其遍历现有链表直至指向一个后继指针域为NULL的结点为止。令该后继指针域为NULL即可：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    SLTNode* curNode = *pphead;
	while (curNode->next) {
		curNode = curNode->next;
	}
	curNode->next = newNode;
}

2、由于需对pphead进行解引用操作，则需保证其不为空，增加断言：

assert(pphead);

3、由于为增加结点操作，原链表可为空，无需对*pphead进行断言。

4、由于为增加结点操作，考虑当前链表为空的情况，即*pphead=NULL，又将*pphead复制给了curNode，故curNode=NULL，若采取与普通链表即情况1的相同处理模式，则遍历链表找尾结点的while (curNode->next)操作会导致空指针的解引用操作，故需对原链表是否为空进行单独讨论。

讨论逻辑为：直接将创建的新结构体变量赋值给链表的头指针*pphead即可：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newNode = SLTCreatNode(x);
	// 空链表
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	else {
		// 非空链表
		SLTNode* curNode = *pphead;
		while (curNode->next) {
			curNode = curNode->next;
		}
		curNode->next = newNode;
	}
}

2. 头插SLTPushFront

1、考虑具有若干结点的链表：

创建新结点，令新结点的后继指针域指向原头结点，再令新结点为链表的头结点：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* newNode = SLTCreatNode(x);
	newNode->next = *pphead;
	// 令新结点为链表的头结点
	*pphead = newNode;
}

 2、由于需对pphead进行解引用操作，故需保证pphead不为空，增加断言：

assert(pphead);

3、由于为增加结点操作，故原链表可为空，即可无结点，即允许*pphead=NULL，无需断言；

4、由于为增加结点操作，考虑当前链表为空的情况，即*pphead=NULL，若采取与普通链表相同的处理模式，即创建新结点后令其指针域指向空，再令新结点为新的头结点，并无差错，无需单独讨论处理：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newNode = SLTCreatNode(x);
	newNode->next = *pphead;
	// 令新结点为链表的头结点
	*pphead = newNode;
}

3. 尾删SLTPopBack

1、考虑具有若干结点的链表：

遍历找到尾结点及尾结点的前趋结点，释放尾结点并令尾结点的前趋结点的指针域为空；

void SLTPopBack(SLTNode** pphead) {
    SLTNode* tailPrevNode = *pphead;
	SLTNode* tailNode = *pphead;
	while (tailNode->next) {
		tailPrevNode = tailNode;
		tailNode = tailNode->next;
	}
	free(tailNode);
	tailNode = NULL;
	tailPrevNode->next = NULL;
}

2、由于需对pphead进行解引用，需保证pphead不为空：

3、由于要删除结点，故链表不可无结点，需保证*pphead不为空；

结合1、2点，增加断言：

assert(pphead && *pphead);

4、由于要删除结点，考虑删除后链表为空即链表仅有一个结点的情况：

若采取同普通链表相同的处理逻辑，则遍历找尾结点的while (tailNode->next)操作会造成空指针解引用，故而该情况需单独讨论。

处理逻辑为：直接释放链表的唯一结点*pphead，并将其置空。无需遍历查找：

void SLTPopBack(SLTNode** pphead) {
	assert(pphead && *pphead);
	// 链表只有一个结点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	// 链表有多个结点
	else {
		SLTNode* tailPrevNode = *pphead;
		SLTNode* tailNode = *pphead;
		while (tailNode->next) {
			tailPrevNode = tailNode;
			tailNode = tailNode->next;
		}
		free(tailNode);
		tailNode = NULL;
		tailPrevNode->next = NULL;
	}
}

4. 头删SLTPopFront

1、考虑具有若干结点的链表，创建结构体指针记录链表第二个结点的地址（链表头结点的后继指针域），释放头结点，令第二个结点为新的头结点：

void SLTPopFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* secNode = (*pphead)->next;
	free(*pphead);
	*pphead = secNode;
}

2、由于需对pphead进行解引用，故需保证pphead不为空；

3、由于是删除结点操作，则需保证链表不能无结点，即链表不为空，即*pphead不为空；

结合2、3，增加断言：

	assert(pphead && *pphead);

4、由于是删除结点操作，考虑删除后链表为空（即链表只有一个结点）的情况：

若采取普通链表相同的处理逻辑，则链表头结点的后继指针域为NULL，再将NULL作为链表的新的头指针，并无差错，无需单独讨论，使用普通链表的处理逻辑即可。

5. 指定位置前插入

1、考虑链表具有若干结点的情况：

创建新结点，找到指定结点pos的前驱结点posPrevNode，令posPrevNode结点的后继指针域指向新结点，再令新结点的后继指针域指向pos结点：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	SLTNode* newNode = SLTCreatNode(x)；
    SLTNode* posPrevNode = *pphead;
	while (posPrevNode->next != pos) {
		posPrevNode = posPrevNode->next;
	}
	posPrevNode->next = newNode;
	newNode->next = pos;
}

2、由于需对pphead解引用，故pphead不可为空。

3、由于为指定位置前增加结点，若链表为空或指定位置为空则无意义，故*pphead与pos均不为空。增加断言：

assert(pphead && *pphead && pos);

4、由于为指定位置前增加结点，最特殊的情况是指定位置为头结点，考虑pos=*pphead的情况，若采取与普通链表相同的处理模式，则无法找到某一结点posPrevNode的后继指针域指向*pphead，故而pos=*pphead的情况须单独讨论处理。

处理逻辑为：当pos=*pphead时，即向链表进行头插，调用已完成的头插方法即可：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead && *pphead && pos);
	SLTNode* newNode = SLTCreatNode(x);
	if (pos == *pphead) {
		// 调用头插方法
		SLTPushFront(pphead, x);
	}
	else {
		SLTNode* posPrevNode = *pphead;
		while (posPrevNode->next != pos) {
			posPrevNode = posPrevNode->next;
		}
		posPrevNode->next = newNode;
		newNode->next = pos;
	}
}

6. 指定位置前删除

1、考虑链表具有若干结点的情况：

遍历查找指定位置结点的前驱结点posPrevNode，令其后继指针域指向pos的后继结点，即

posPrevNode->next = pos->next即可：

2、由于需对pphead进行解引用操作，故pphead不可为空。

3、由于为指定位置前删除结点，若链表为空或指定位置为空则无意义，故*pphead与pos均不为空。增加断言：

assert(pphead && *pphead && pos);

4、由于为指定位置前删除结点，最特殊的情况是指定位置为头结点，考虑pos=*pphead的情况，若采取与普通链表相同的处理模式，则无法找到某一结点posPrevNode的后继指针域指向*pphead，故而pos=*pphead的情况须单独讨论处理。

处理逻辑为：当pos=*pphead时，即向链表进行头删，调用已完成的头删方法即可：

void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead && *pphead && pos);
	if (*pphead == pos) {
		// 调用头删方法
		SLTPopFront(pphead);
	}
	else {
		SLTNode* posPrevNode = *pphead;
		while (posPrevNode->next != pos) {
			posPrevNode = posPrevNode->next;
		}
		posPrevNode->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

注：链表的方法还有很多，若仅考虑已有多个结点且增、删时都不影响头结点，或是空链表、仅有一个结点的链表等特殊情况，会使得方法并不完整。此文仅做示例。