数据结构-线性结构之链表

什么是链表，链表有哪些分类？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实际中的链表结构非常多样，通过单向、双向，带头、不带头，循环、非循环组合起来有8中链表结构：

但实际中最常用的还是无头单向非循环链表和带头双向循环链表。

链表带头结点和不带头结点的区别？

不带头结点：此时头指针指向第一个节点

带头结点：此时头指针指向头结点

单链表的基本操作

typedef int SDataType;

//链表的节点
typedef struct SListNode {
	SDataType data;
	struct SListNode* pNext;
}Node,* PNode;

// 链表的结构，给一个头指针保存链表第一个节点的地址
typedef struct SList {
	PNode pHead;//指向链表中的第一个节点
}SList;

// 链表的初始化
void SListInit(SList* s) {
	assert(s);
	s->pHead = NULL;
}

// 在链表s最后一个节点后插入值为data的节点 
void SListPushBack(SList* s, SDataType data) {
	assert(s);
	PNode pNewNode = BuySListNode(data);
	if (s->pHead == NULL) {
		//空链表
		s->pHead = pNewNode;
	}
	else {
		//链表非空，找链表中最后一个节点
		PNode pCur = s->pHead;
		while (pCur->pNext)
		{
			pCur = pCur->pNext;
		}
		pCur->pNext = pNewNode;
	}
}

// 删除链表s最后一个节点
void SListPopBack(SList* s) {
	assert(s);
	//空链表
	if (s->pHead == NULL) {
		return;
	}
	//链表中只有一个节点
	else if (s->pHead->pNext == NULL) {
		free(s->pHead);
		s->pHead = NULL;
	}
	//多个节点情况
	else
	{
		PNode pPre = NULL;
		PNode pCur = s->pHead;
		while (pCur->pNext) {
			pPre = pCur;
			pCur = pCur->pNext;
		}
		free(pCur);
		pPre->pNext = NULL;
	}
}

// 在链表s第一个节点前插入值为data的节点
void SListPushFront(SList* s, SDataType data) {
	assert(s);
	PNode pNewNode = BuySListNode(data);
	pNewNode->pNext = s->pHead;
	s->pHead = pNewNode;
}

// 删除链表s的第一个节点
void SListPopFront(SList* s) {
	assert(s);
	if (s->pHead == NULL) {
		return;
	}
	//找到待删除的节点
	else {
		PNode pDelNode = s->pHead;
		s->pHead = pDelNode->pNext;
		free(pDelNode);
	}
}

// 在链表的pos位置后插入值为data的节点
void SListInsert(PNode pos, SDataType data) {
	if (pos == NULL) {
		return;
	}
	PNode pNewNode = BuySListNode(data);
	pNewNode->pNext = pos->pNext;
	pos->pNext = pNewNode;
}

// 删除链表s中pos位置的节点
void SListErase(SList* s,PNode pos) {
	assert(s);
	if (pos == NULL || s->pHead == NULL) {
		return;
	}
	else if(pos == s->pHead) {
		s->pHead->pNext = pos->pNext;
	}
	else {
		PNode pPre = s->pHead;
		while (pPre && pPre->pNext != pos) {
			pPre = pPre->pNext;
		}
		if (pPre) {
			pPre->pNext = pos->pNext;
		}
	}
	free(pos);
}

// 在链表中查找值为data的节点，找到返回该节点的地址，否则返回NULL
PNode SListFind(SList* s, SDataType data) {
	assert(s);
	PNode pCur = s->pHead;
	while (pCur) {
		if (pCur->data == data) {
			return pCur;
		}
		pCur = pCur->pNext;
	}
	return NULL;
}

// 获取链表中有效节点的个数 
size_t SListSize(SList* s) {
	assert(s);
	PNode pCur = s->pHead;
	size_t count = 0;
	while (pCur)
	{
		count++;
		pCur = pCur->pNext;
	}
	return count;
}

// 检测链表是否为空
int SListEmpty(SList* s) {
	assert(s);
	return s->pHead == NULL;
}

// 销毁链表
void SListDestory(SList* s) {
	assert(s);
	PNode pCur = s->pHead;
	while (pCur) {
		s->pHead = pCur->pNext;
		free(pCur);
		pCur = s->pHead;
	}
	s->pHead = NULL;
}