【数据结构学习笔记】二、线性表---链表篇（2）

【数据结构学习笔记】二、线性表---链表篇（2）

---

文章目录

• • 链表概念:
  • 链表分类：
  • 单链表的实现：

---

链表概念:

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

注意:
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

---

链表分类： 单向双向 带头不带头 循环非循环

单向与双向、循环和非循环的区别

带头结点和不带头结点的区别

三个维度，总共有 2*2*2 = 8 种结构，其中最常用的为以下两种结构

1.无头单向非循环链表∶结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
⒉.带头双向循环链表︰结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势实现反而简单了，后面我们代码实现了就知道了。

---

单链表的实现：

头文件：SList.h

#pragma once
#include
#include
#include
#include
typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SListNode;

//申请结点
SListNode* CreateSListNode(SLTDataType x);
//打印
void SListPrint(SListNode* pList);
//判空
bool IsEmpty(SListNode* pList);
//求长
int SListLength(SListNode* pList);
//按值查找
SListNode* SListFindByVal(SListNode* pList,SLTDataType x);
//按位置查找
SListNode* SListFindByPos(SListNode* pList, int pos);
//修改
void SListUpdate(SListNode* Node);

//创建
void SListInit(SListNode** pphead);
//销毁
void SListDestory(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//头删
void SListPopFront(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//任意位置插入
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x);
//任意位置删除
void SListEraseAfter(SListNode** pphead, int pos);

---

源文件：SList.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include"SList.h"
//初始化
void SListInit(SListNode** pphead) {
	*pphead = NULL;
}
//销毁
void SListDestory(SListNode** pphead) {
	SListNode* cur = *pphead;
	while (cur) {
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
//申请结点
SListNode* CreateSListNode(SLTDataType x) {
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	if (node == NULL) {
		printf("malloc fail!n");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {
	assert(pphead);
	SListNode* newnode = CreateSListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SListPopFront(SListNode** pphead) {
	assert(pphead);
	if (IsEmpty(*pphead)) {
		printf("SList is empty ,PopFront fail!n");
		return 0;
	}
	SListNode* head = *pphead;
	*pphead = (*pphead)->next;
	free(head);
}
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) {
	assert(pphead);
	//找尾结点
	SListNode* tail = *pphead;
	while (tail && tail->next) {
		tail = tail->next;
	}
	//创建新结点
	SListNode* newnode = CreateSListNode(x);
	if (tail == NULL) {
		*pphead = newnode;
	}
	else {
		tail->next = newnode;
	}
}
//尾删
void SListPopBack(SListNode** pphead) {
	assert(pphead);
	if (IsEmpty(*pphead)) {
		printf("SList is empty ,popBack failed!n");
		return 0;
	}
	SListNode* prev = *pphead;
	SListNode* tail = prev->next;
	if (tail == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		while (tail->next) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
//任意位置插入
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x) {
	assert(pphead);
	SListNode* newnode = CreateSListNode(x);
	SListNode* insert = SListFindByPos(*pphead, pos);
	if (insert) {
		newnode->next = insert->next;
		insert->next = newnode;
	}
	else
	{
		*pphead = newnode;
	}
}
//任意位置删除
void SListEraseAfter(SListNode** pphead, int pos) {
	assert(pphead);
	SListNode* erase = SListFindByPos(*pphead, pos);
	if (erase) {
		SListNode* next = erase->next;
		erase->next = next->next;
		free(next);;
	}
	else
		printf("SList is empty,Erase fail!n");
}
//打印
void SListPrint(SListNode* pList) {
	SListNode* cur = pList;
	while (cur) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}
//判空
bool IsEmpty(SListNode* pList) {
	if (pList == NULL)
		return 1;
	return 0;
}
//求长
int SListLength(SListNode* pList) {
	int length = 0;
	SListNode* cur = pList;
	while (cur) {
		length++;
		cur = cur->next;
	}
}
//按值查找
SListNode* SListFindByVal(SListNode* pList, SLTDataType x);
//按位置查找
SListNode* SListFindByPos(SListNode* pList, int pos) {
	SListNode* cur = pList;
	int length = SListLength(pList);
	if (pos < 0 || pos > length) {
		printf("The position to insert is wrong!n");
		return 0;
	}
	while (pos > 0) {
		cur = cur->next;
		pos--;
	}
	return cur;
}
//修改
void SListUpdate(SListNode* Node);

---

测试函数：Test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include"SList.h"
void TestSList1() {
	SListNode* node1 = (SListNode*)malloc(sizeof(SListNode));
	node1->data = 1;
	SListNode* node2 = (SListNode*)malloc(sizeof(SListNode));
	node2->data = 2;
	SListNode* node3 = (SListNode*)malloc(sizeof(SListNode));
	node3->data = 3;
	SListNode* node4 = (SListNode*)malloc(sizeof(SListNode));
	node4->data = 4;
	SListNode* node5 = (SListNode*)malloc(sizeof(SListNode));
	node5->data = 5;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = NULL;
	SListPrint(node1);

}
void TestSList2() {
	SListNode* pList = NULL;
	SListPushBack(&pList, 111);
	SListPushBack(&pList, 222);
	SListPushBack(&pList, 333);
	SListPushBack(&pList, 444);
	SListPushBack(&pList, 555);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPrint(pList);
}
void TestSList3() {
	SListNode* pList = NULL;
	SListPushFront(&pList, 99);
	SListPushFront(&pList, 88);
	SListPushFront(&pList, 77);
	SListPushFront(&pList, 66);
	SListPushFront(&pList, 55);
	SListPrint(pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPrint(pList);

	SListInsertAfter(&pList, 0, 1);
	SListInsertAfter(&pList, 0, 2);
	SListInsertAfter(&pList, 0, 3);
	SListInsertAfter(&pList, 0, 4);
	SListInsertAfter(&pList, 0, 5);
	SListPrint(pList);

	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListPrint(pList);

	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListPrint(pList);


}
int main()
{
	//TestSList1();
	//TestSList2();
	TestSList3();
	return 0;
}