单向无头节点链表

| 分类于

前言

链表的维护方式有两种，一种是以定义一个头节点的方式来维护链表，此头节点也分为指针域和数据域，作为维护链表的头节点使用时我们不使用它的数据域，只使用指针域；还有一种维护方式是直接定义一个头指针，这个指针指向链表的第一个节点。此处文采用第二种维护方式来实现一条单向链表，即所有的操作都是单向的，只能从前往后的进行操作

SList.h

链表的所有接口及节点的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;

//此结构体不同于顺序表，顺序表中结构体便是顺序表，而此处的结构体则表示的是一个节点
typedef struct Node
{
	DataType data;  //数据域
	struct Node *next;  //指针域（存放下一个节点的地址，如果为NULL，则代表后面再无节点）
}Node;

void SListInit(Node **ppfirst); //链表的初始化
void SListPrint(Node* first); //打印
void SListDestroy(Node **ppfirst); //链表销毁
void SListPushBack(Node **ppfirst, DataType data); //尾插
void SListPopBack(Node **ppfirst); //尾删
void SListPushFront(Node **ppfirst,DataType data);//头插
void SListPopFront(Node **ppfirst);//头删
int SListGetLength(Node *first);//链表长度计算
Node* SListFind(Node* first, DataType data);//查找链表元素
void SListInsert(Node** ppfirst, int pos, DataType data);//在节点pos之前插入新的元素
void SListErase(Node** ppfirst, int pos);//删除pos这个节点

SList.c

链表的初始化

1
2
3
4
5
void SListInit(Node **ppfirst)   //二级指针ppfirst里放的是实参结构体指针first的地址，first里放的是结构体的地址
{
	assert(ppfirst);
	*ppfirst = NULL;   //解引用得到指针变量ppfirst，即所指向的结构体
}

此处需要注意接收实参的是一个二级指针，这是因为实参是通过传址的方式带入到函数内部的，为什么要通过址的方式呢？

链表的销毁

释放每一个节点，并将头指针置为空，使用两个指针，一个用来记录下个节点的位置，一个用来删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SListDestroy(Node **ppfirst)
{
	assert(ppfirst);
	Node* cur = NULL;  //记录下一个节点的位置
	Node* del = NULL;   //删除节点
	cur = *ppfirst;
	while (cur)
	{
		del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	*ppfirst = NULL;
}

新节点的建立

1
2
3
4
5
6
7
8
9
10
11
12
Node* creatNode(DataType d)
{
	Node* ptr = (Node*)malloc(sizeof(Node));
	if (ptr == NULL)
	{
		perror("SLlistPushBack::malloc()");
		return;
	}
	ptr->data = d;         //数据域
	ptr->next = NULL;       //指针域
	return ptr;
}

链表打印

1
2
3
4
5
6
7
8
9
10
void SListPrint(Node* first)
{
	Node* cur = first;
	while (cur)
	{
		printf("%d  ", cur->data);
		cur = cur->next;    //相当于cur++，但绝不能写成cur++
	}
	printf("\n");
}

尾插

找到指针域为空的节点，将其指针域保存为新加节点的地址即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SListPushBack(Node **ppfirst, DataType d)
{
	assert(ppfirst);
	Node *newNode = creatNode(d);
	//无节点
	if (*ppfirst == NULL)
	{
		*ppfirst = newNode;
	}
	//有节点
	else
	{
		Node* cur = *ppfirst;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newNode;
	}
}

尾删

找到链表中倒数第二个元素，将其指针域指为NULL，同时释放掉最后一个节点，注意分类讨论不同情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void SListPopBack(Node **ppfirst)
{
	assert(ppfirst);
	//空链表
	if (*ppfirst == NULL)
	{
		printf("没有节点可以删除\n");
		return;
	}
	else if ((*ppfirst)->next == NULL)  //只有一个节点
	{
		free(*ppfirst);
		*ppfirst = NULL;
	}
 	//两个以上节点
	else
	{
		Node* cur = *ppfirst; 
		while (cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur -> next = NULL;
	}
}

头插

新节点的指针域保存原链表首节点的地址，头指针指向加入的新节点

1
2
3
4
5
6
7
8
9
10
11
12
void SListPushFront(Node **ppfirst, DataType d)
{
	assert(ppfirst);
	Node* newNode = creatNode(d);
	if (*ppfirst == NULL)
	{
		*ppfirst = newNode;
		return;
	}
	newNode->next = *ppfirst;
	*ppfirst = newNode;
}

头删

使头指针保存第二个节点地址，销毁第一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SListPopFront(Node **ppfirst)
{
	assert(ppfirst);
	if (*ppfirst == NULL)
	{
		printf(" 空链表，无可删除元素\n");
		return;
	}
	else if ((*ppfirst)->next == NULL)
	{
		free(*ppfirst);
		*ppfirst = NULL;
		return;
	}
	else
	{
		Node* del = *ppfirst;
		*ppfirst = (*ppfirst)->next;
		free(del);
	}
}

求链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int SListGetLength(Node *first)
{
	if (first == NULL)
	{
		printf("链表为空，长度为0\n");
		return 0;
	}
	int count = 0;
	Node* cur = first;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

查找某个指定的元素

此处指定的是具体的元素数字，返回的是该元素所在的地址

1
2
3
4
5
6
7
8
9
10
Node* SListFind(Node* first, DataType data)
{
	Node* cur = first;
	for (cur = first; cur != NULL; cur = cur->next)
	{
		if (cur->data == data)
			return cur;
	}
	return NULL;
}

在查找到的元素前面插入一个新的元素

三种情况，分类讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void SListInsert(Node** ppfirst, Node* pos, DataType data)
{
	assert(ppfirst);
	if (*ppfirst == NULL)
	{
		printf("链表为空，不进行插入\n");
		return ;
	}

	Node* newNode = creatNode(data);
	if (*ppfirst == pos)   //pos为链表头部
	{
		newNode->next = pos;
		*ppfirst = newNode;
	}
	else                   //pos为一般位置
	{
		Node* cur = *ppfirst;
		while (cur != NULL && cur->next != pos )
		{
			cur = cur->next;
		}
		if (cur)
		{
			newNode->next = pos;
			cur->next = newNode;
		}
	}
}

删除查找的元素

此处是直接删除该元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SListErase(Node** ppfirst, Node* pos)
{
	assert(ppfirst);
	assert(*ppfirst);  //链表为空则不进行删除

	if (*ppfirst == pos)  //删除的位置为链表的头部
	{
		Node* del = *ppfirst;
		*ppfirst = ((*ppfirst)->next);
		free(*ppfirst);
	}
	else   //一般删除位置
	{
		Node* cur = *ppfirst;
		while (cur && cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

测试函数test.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "SList.h"

void test()
{
	Node *first;  //专门记录第一个节点的地址（头指针的维护方式）

	SListInit(&first);
	printf("尾插5个数字：\n");
	SListPushBack(&first, 1);
	SListPushBack(&first, 2);
	SListPushBack(&first, 3);
	SListPushBack(&first, 4);
	SListPushBack(&first, 5);
	SListPrint(first);
	int len = SListGetLength(first);
	printf("链表长度为：%d\n", len); 
	printf("查找元素：\n");
	Node* ret = SListFind(first, 3);
	if (ret != NULL)
	{
		printf("找到了所要查找的元素%d\n", ret->data);
	}
	else
	{
		printf("未找到所查元素\n");
	}
	printf("在节点pos前插入元素：\n");
	SListInsert(&first, ret, 10);
	SListPrint(first);
	printf("删除pos这个节点\n");
	SListErase(&first, ret);
	SListPrint(first);
	printf("头插:\n");
    SListPushFront(&first, 0);
	SListPrint(first);
	printf("尾删：\n");
	SListPopBack(&first);	
	SListPrint(first);
	//SListDestroy(&first);
	printf("头删：\n");
	SListPopFront(&first);
	SListPrint(first);
		
}


int main()
{
	test();
	system("pause");
	return 0;
}

运行结果