[C数据结构]单链表（草稿中）

以下是函数声明：

#pragma once
#include
#include
#include

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//打印链表
void SListPrint(SLTNode* phead);

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//头删
void SListPopFront(SLTNode** pphead);

//尾删
void SListPopBack(SLTNode** pphead);

//查找结点
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

//在pos之前插入结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos位置的结点
void SListErase(SLTNode** pphead, SLTNode* pos);

以下是函数实现：

#include"SList.h"

//打印链表
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;//phead保留第一个数据的地址
	while (cur != NULL)//cur不为NULL说明cur有具体指向的结构体变量，结点结构体变量在创建好后就会被赋值的。
	{
		printf("%d->", cur->data);
		cur=cur->next;
	}
	printf("NULLn");
}

//尾插
void SListPushBack(SLTNode** pphead,SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)//pphead是plist的地址，通过地址pphead找到plist（NULL），从而改变plist的值。
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;//*pphead是plist（头结点的地址）
		while (tail->next!=NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
	//如果使用的是一级指针，当链表一个结点都没有的时候，传过来的结构体指针变量是空指针，因为是空指针所以不能通过访问结构体指针变量去改变成员变量的值。
	//如果使用的是一级指针，直接将newnode赋值给phead，那么仅仅是在这个函数中改变了指针phead的值，并没有通过phead存的地址去改变结构体变量的成员变量值。
	//传址调用本质也是拷贝数据，只不过拷贝的是地址，而将地址拷贝到新的指针变量中去，其唯一的意义就是通过指针变量存的地址去改变对应内存中的数据。如果一开始就改变了指针变量的值，那么传址的意义将不复存在！
}

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = *pphead;
	*pphead = newnode;
}

//头删
void SListPopFront(SLTNode** pphead)//要改变plist就必须传plist的指针即二级指针。
{
	assert(pphead);
	assert(*pphead);//判是否为空链表
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead=next;
}

//尾删
void SListPopBack(SLTNode** pphead)//如果传的是首结点地址
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;//想要跨函数改变一个局部变量的值，必须拿到它的地址。所以这里用二级指针是为了修改存第一个结点地址的plist。
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* tailPrev = NULL;
		while (tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
	}
}

//查找函数
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur->data != x)
	{
		if (cur->next == NULL)
		{
			return NULL;
		}
		else
		{
			cur = cur->next;
		}
	}
	return cur;
}

//在pos之前插入结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* cur = *pphead;
	if (cur == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
		assert(newnode);
		newnode->data = x;
		newnode->next = cur->next;
		cur->next = newnode;

	}
}

//删除pos位置的结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);//*pphead为NULL,pos不可能不为NULL.
	SLTNode* cur = *pphead;
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

以下是测试文件：

#include"SList.h"

void TestSList1()//检测打印
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n1);
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n2);
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n3);
	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n4);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	SListPrint(n1);
}

void TestSList2()//检测尾插
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
}

void TestSList3()//检测头插
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 1);
	SListPrint(plist);
}
void TestSList4()//测试头删
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	//SListPopFront(&plist);//断言：无数据可删
	SListPrint(plist);
}
void TestSList5()//测试尾删
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
}
void TestSList6()//测试查找结点函数,并修改该结点。
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SLTNode* ret=SListFind(plist, 3);//查找结点
	if (ret)
	{
		printf("找到结点n");
		ret->data = 30;// 修改结点的数据
		SListPrint(plist);
	}
	else
	{
		printf("未找到结点n");
	}
}
void TestSList7()//测试在地址pos前面插入结点
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SLTNode* ret = SListFind(plist, 3);
	SListInsert(&plist, ret, 30);
	SListPrint(plist);
	ret = SListFind(plist, 1);
	SListInsert(&plist, ret, 10);
	SListPrint(plist);
}
void TestSList8()//测试删除pos位置的结点函数
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SLTNode* ret = SListFind(plist, 1);
	SListErase(&plist, ret);
	SListPrint(plist);
	ret = SListFind(plist, 4);
	SListErase(&plist, ret);
	SListPrint(plist);
}
int main()
{
	TestSList8();
	return 0;
}

[C数据结构]单链表（草稿中）

C/C++/C#相关栏目本月热门文章