数据结构——单向链表（C语言实现）

目录

什么是链表？

什么是单向链表

单向链表的声明和定义

单向链表元素的插入（在pos前插入）

解惑

单向链表元素的插入（在pos后插入）

单向链表节点的建立

单向链表元素的打印

单向链表元素的删除（后元素）

单向链表元素的删除（前元素）

单向链表特定位置的删除

单向链表后一位置的删除

单向链表元素的查找

单向链表元素的删除

测试

---

什么是链表？

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

实则可以看做一个一个车厢连接在一起，车厢里的元素可以看做人，也就是节点里存储的数据，元素。

注意：

1. 链式结构在逻辑上是连续的，但是在物理结构上是不连续的

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续。

---

此篇文章先介绍无头单向非循环链表

什么是单向链表

无头链表：以结点为开头的链式结构——————同时也是非循环链表

单向链表的声明和定义

typedef int SLTDataType;
typedef struct SListNode//定义的是结点的结构
{
	SLTDataType data;//存放数据
	struct SListNode* next;//存放下一个位置的地址
}SLTNode;
 
void SLTPrint(SLTNode* phead);
void SLTPopFront(SLTNode** phead);
void SLTPopBack(SLTNode** phead);
 
SLTNode* STFind(SLTNode* phead, SLTDataType x);
 
void SLInsert(SLTNode* pphead, SLTNode* pos, SLTDataType x);//pos就是节点的指针
void SLInsertAfter(SLTNode* pos, SLTDataType x);
void SLErase(SLTNode* pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);
 
void SLDestroy(SLTNode* phead);

单向链表元素的插入（在pos前插入）

我们要知道，链表本质是一个个结点连接起来的，所以可以看做是多个指针连接起来的。

与顺序表不同：顺序表里定义的指针是指向一个动态开辟的数组

                        链表本身就是由多个指针构成的结点相互连接形成的链式结构。

所以在主函数里定义的时候，顺序表直接定义变量，链表是要定义一个指针变量

void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);//若为初始位置，那么就直接头插
	}
	else 
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;//将newnode后边的接上pos处的数据
	}
}

解惑

1.为什么接收的结构体指针临时变量是用" ** "定义？

——因为我们定义的是一个结构体指针，若是想要改变一个指针本身，那么就需要传入结构体指针的地址，所以我们需要用到二级指针。

2.为什么接收的结构体指针的位置是用" * "定义？

——在顺序表中，我们可以直接用下标来定到要改变元素的位置，但是链表是由指针组成的，因此我们不能用下标来定位。所以需要一个指针来定位，传入，，这里仅是用来定位，所以用一级指针来接收。

3. 插入的具体过程是什么？

——由于链表不能直接用下标定位元素位置，所以我们只能通过指针来定位

——因此要找到插入的位置pos，那我们就需要用一个while循环，直到定位到pos前的一个节点，然后将这个节点定位到新建立的节点上，新建立的节点连接在原pos的节点上。

单向链表元素的插入（在pos后插入）

因为单向链表可以直接定位到下一个节点的位置，所以不需要定位到前一个结点的位置（指针）。因此我们这里不需要传入整个结构体的指针，定位到pos处的指针即可。

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos); 
 
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

单向链表节点的建立

建立一个节点，我们需要给予其一个空间来存放，那怎么建立空间？——malloc函数来建立。

并且节点指向的下一个节点为空

SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    //将这个元素给予一个空间，创建一个结点
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

单向链表元素的打印

我们需要一个接收一个结构体指针来进行遍历。

但是我们不能用原指针来进行遍历，因为这样子遍历到后面，那么头指针就会指向最后一个元素，会导致前面的元素都丢失。

void SLTPrint(SLTNode* phead)//传入的是结构体，所以用一个指针来接收结构体的地址
{
    STNode* cur=phead;//若是*进行了解引用的话，那么就是指向结构体
    while(cur!=NULL)
    {
        printf("%d",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");
}

单向链表元素的删除（后元素）

因为要对链表进行改变，所以我们要传入结构体指针地址，所以需要用一个二级指针来接收地址。

void SLTPopBack(SLTNode** phead)
{
    //因为**phead接收的是地址，所以*phead是结构体的指针
    
	//没有节点（空链表）
	if (*phead == NULL)
	{
		return;
	}
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
			// 找尾部
		while (tail->next->next)//找到倒数第二个,也就是数据中的最后一位数据 
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next=NULL;
	}
}

单向链表元素的删除（前元素）

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);// 链表为空，则pphead也不会为空，所以需要断言——结构体
	assert(*pphead);// 链表为空，不能头删，那么此时需要断言——结构体指针
	SLTNode* del = *pphead;
	*pphead = del->next;//将头指针指向下一个元素的地址
	free(del);
}

单向链表特定位置的删除

void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//判断结构体不为空
	assert(pos);//判断该位置的指针不为空
 
	if (pos == *pphead)//若为起始的结点，那么就直接删除第一个结点
	{
		SLTPopFront(pphead);
	}
	else 
	{
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//下一个不是要查找的位置时
		{
			prev = prev->next;//则往下
		}
		prev->next = pos->next;//把下一个元素的地址直接复制为下两位,等于跳过下一个数字
		free(pos);//释放开辟的空间
	}
}

单向链表后一位置的删除

void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* prve = pos->next;
	pos->next = prve->next;
	free(prve);//释放开辟的内存
}  

单向链表元素的查找

同理，不能用下标锁定，所以只能逐一遍历，并且要返回指针

SLTNode* STFind(STNode* phead,SLTDataType x)
{
    assert(phead);
    STNode* cur=phead;
    while(cur)
    {
        if(cur->data==x)
        {
            return cur;//返回此处地方的指针
        }
        cur=cur->next;
    }
    return NULL;
}

单向链表元素的删除

因为链表是由一个个指针连接的，所以我们仅需要删除指针即可。

void SLDestroy(SLTNode* phead)//接受结构体的地址，结构体的地址就是首元素的地址
{
    assert(phead);
    SLTNode* cur=phead;
    while(cur)
    {
        SLTNode* next=cur->next;
        free(cur);
        cur=next;
    }
    phead=NULL;//最后将头指针定义为空指针，置空
}

测试

void TestSList1()
{
	//phead和newnode都是局部变量，该怎么办？
	SLTNode* plist = NULL;//是个结构体指针
	//改变数据要传入数据地址才能同时改变实参的数据
	SLTPushBack(&plist, 1);//拷贝出的是形参，形参改变后不会改变实参
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
 
	SLTPushBack(&plist, 4);
 
	SLTPopBack(&plist);
    SLTPrint(plist);//这里不需要改变内容，故传入指针（指向的起始内容地址）就行
 
	SLTNode* pos = STFind(plist, 3);//STFind返回的是结构体的指针，故可以通过pos去改变plist
	if (pos)//判断是否为空
	{
		SLInsert(&plist, pos,30);
		//Fine恰好与pos进行协同使用
	}
	SLTPrint(plist);
}

由于此处plist是一个结构体指针，所以

若是想改变结构体的指针，就需要传入结构体指针的地址，所以需要用二级指针来接收

——**pphead

如果只是想进行遍历和结构体的改变，那么就传入结构体的地址即可。

——用一级指针来接收就行了,因为不对指针进行改变，所以不需要用到二级指针。

难点：

主要还是考察了二级指针和一级指针的不同用法，以及在改变链表里的元素时，不同形参的选择

若此处搞懂了，那么单向链表就可以熟练掌握了。