C语言单链表（2）-- 查漏补缺

C语言单链表（2）-- 查漏补缺  链表：

结构体变量通过结构体指针连接在一起。

                
#include 
struct Node{
    int data;               //数据域，可以是任何类型的数据
    struct Node* next;      //指针域
};

分类：

• 静态链表：链表分配在栈上；
• 动态链表：链表分配在堆上。

静态链表：

void test_06()
{
	//节点创建
	struct Node node1 = { 10,NULL };
	struct Node node2 = { 20,NULL };
	struct Node node3 = { 30,NULL };

	//建立节点之间的关系
	node1.next = &node2;
	node2.next = &node3;

	//遍历链表
	struct Node* pCurrent = &node1;
	while (pCurrent != NULL)
	{
		printf("%dn", pCurrent->num);
		pCurrent = pCurrent->next;
	}

}

动态链表：

void test_06()
{
	//节点创建
	struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
	struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));

	//给每个节点建立关系并给数据域赋值
	node1->num = 10;
	node1->next = node2;
	node2->num = 20;
	node2->next = node3;
	node3->num = 30;
	node3->next = NULL;
	//遍历链表
	struct Node* pCurrent = node1;
	while (pCurrent != NULL)
	{
		printf("%dn", pCurrent->num);
		pCurrent = pCurrent->next;
	}
}

链表的基本使用： （1）初始化链表：

具有返回值，该函数的返回值是 创建好的链表的头结点。

//初始化链表
//函数的返回值是 创建好的链表的头结点
struct Node* init_linkList()
{
	struct Node* pHeader = malloc(sizeof(struct Node));
	if (pHeader == NULL)
	{
		return NULL;
	}
	//头结点初始化，一般不需要维护数据域
	//pHeader->num = -1;
	pHeader->next = NULL;

	//创建一个尾结点指针，用于记录当前链表尾部节点的位置，方便做尾插
	struct Node* pTail = pHeader;

	int val = -1;
	while (1)
	{
		printf("请输入数据，-1代表结束n");
		scanf("%d", &val);
		if (val == -1)
		{
			break;
		}
		//创建新节点
		struct Node* newNode = malloc(sizeof(struct Node));
		newNode->num = val;
		newNode->next = NULL;

		//更新节点指向
		pTail->next = newNode;
		pTail = newNode;
	}

	return pHeader;
}

（2）遍历链表：

void foreach_linkList(struct Node* pHeader)
{
	if (pHeader == NULL)  //如果该节点为空，则不遍历
	{
		return;
	}
	//当前节点，指向第一个有真实数据的节点
	struct Node* pCurrent = pHeader->next;
	while(pCurrent != NULL)
	{
		printf("%dn", pCurrent->num);
		pCurrent = pCurrent->next;
	}
}

（3）链表节点的插入：

利用两个辅助指针变量实现链表的插入；

在 oldval 前插入 newvalue，如果 oldval 不存在，则做尾插。

void insert_linklist(struct Node* pHeader, int oldVal, int newVal)
{
	if (pHeader == NULL)
	{
		return;
	}
    //创建两个临时指针事项节点插入
	struct Node* pPrev = pHeader;
	struct Node* pCurrent = pHeader->next;

	while (pCurrent != NULL)
	{
		if (pCurrent->num == oldVal)
		{
			break;
		}
		//两个辅助指针向后移动
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	//创建新节点
	struct Node* newNode = malloc(sizeof(struct Node));
	newNode->num = newVal;
	newNode-> next = NULL;

	newNode->next = pCurrent;
	pPrev->next = newNode; 
}

（4）删除节点

void delete_linkList(struct Node* pHeader, int delVal)
{
	if (pHeader == NULL)
	{
		return;
	}
	struct Node* pPrev = pHeader;
	struct Node* pCurrent = pHeader->next;

	while (pCurrent != NULL)
	{
		if (pCurrent->num == delVal)
		{
			break;
		}
		//移动两个辅助指针来遍历链表
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	if (pCurrent == NULL)
	{
		//没有找到用户需要删除的节点
		return;
	}
	pPrev->next = pCurrent->next;
	free(pCurrent);
	pCurrent = NULL;
}

测试程序：

void test_06()
{
	//初始化链表
	struct Node* pHeader = init_linkList();
	//遍历链表
	printf("遍历结果为：n");
	foreach_linkList(pHeader);
	//测试插入数据
	insert_linklist(pHeader, 20, 100);
	insert_linklist(pHeader, 21, 100);
	printf("插入节点后遍历结果：n");
	foreach_linkList(pHeader);
	//测试删除节点
	delete_linkList(pHeader, 100);
	printf("删除节点后遍历结果：n");
	foreach_linkList(pHeader);

	clear_linkList(pHeader);
	printf("清空节点后遍历结果：n");
	foreach_linkList(pHeader);
}


int main()
{
	test_06();

	system("pause");
	return 0;
}