单向链表

数据结构与算法 评论

链表是由一系列的结点组成，链表在内存中是非连续的，每一个结点包含两个域，一个保存数据域，一个保存结点关系的指针域。

链表节点

结点包含两个域,一个指向数据,一个指向下一个结点的指针

1
2
3
4
5

typedef struct LINKNODE {
	void*  data;//指向任何类型的数据
	struct LINKNODE* next; //指向下一个链表的结点
}LinkNode;

链表结构体

头结点不保存数据.

1
2
3
4
5

typedef	struct LINKLIST {
	LinkNode* head;	//指向链表头结点
	int size;	//链表长度
}LinkList;

链表操作

初始化链表，指定位置插入，删除指定位置的结点，获得链表的长度

查找，打印链表节点,需要用户提供一个打印函数，返回第一个节点

释放链表内存

初始化链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14

LinkList* Init_LinkList() {
    //创建链表结构体
	LinkList* list = (LinkList *)malloc(sizeof(LinkList));
	list->size = 0;

	//头结点不保存数据信息
	list->head = (LinkNode*)malloc(sizeof(LinkNode));
	list->head->data = NULL;
	list->head->next = NULL;

    //返回链表
	return list;
}

指定位置插入

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

void Insert_LinkList(LinkList* list, int pos, void *data) {


	if (list == NULL)
	{
		return;
	}

	if (list->head == NULL)
	{
		return;
	}
	//友好处理越界问题
	if (pos < 0 || pos > list->size)
	{
		pos = list->size;
	}

	//创建新的结点
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//查找找结点
	//辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//新结点入链表
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

    //结点数量加1
	list->size++;

}

删除指定位置的值

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

void RemoveByPos_LinkList(LinkList* list, int pos) {
	if (list == NULL)
	{
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	//查找删除结点的前一个结点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//缓存删除的结点
	LinkNode* pDel = pCurrent->next;
    //使当前结点的next指向下下个结点
	pCurrent->next = pDel->next;
	//释放删除结点的内存
	free(pDel);

    //结点数量减一
	list->size--;

}

获得链表的长度

1
2
3
4
int Size_LinkList(LinkList* list) {

	return list->size;
}

查找结点,需要用户提供

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

int Find_LinkList(LinkList* list, void* pData, PEQUALNODE equal){
	if (list == NULL)
	{
		return -1;
	}
	if (pData == NULL) {
		return -1;
	}

	//遍历查找
	LinkNode* pCurrent = list->head->next;
    //记录当前位置
	int pos = 0;
	while (pCurrent != NULL)
	{
        //使用用户提供的equal函数判断结点是否相等
		if (equal(pCurrent->data,pData) == 0) {
			break;//跳出循环
		}
        
		pos++;//当前位置加1
        //指向下一个结点
		pCurrent = pCurrent->next;
	}

    //返回结点位置,pos等于size表示查找失败
	return pos;
}

打印链表节点,需要用户提供一个打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Print_LinkList(LinkList* list, PRINTLINKNODE print) {

	if (list == NULL) {
		return;
	}
	//辅助指针变量
	LinkNode* pCurrent = list->head->next;
	//判断当前结点是否为空
	while (pCurrent != NULL)
	{
        //使用用户提供的print函数打印结点
		print(pCurrent->data);
        //指向下一个指针
		pCurrent = pCurrent->next;
	}
}

返回第一个节点

1
2
3
4
void* Front_LinkList(LinkList* list) {

	return list->head->next;
}

释放链表内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void FreeSpace_LinkList(LinkList* list) {
	if (list == NULL)
	{
		return;
	}

	LinkNode *pCurrent = list->head;
    //判断当前结点是否为空
	while (pCurrent != NULL)
	{
        //缓存当前结点的下一个结点
		LinkNode *pNext = pCurrent->next;
        //释放当前结点
		free(pCurrent);
        //指向下一个结点
		pCurrent = pNext;

	}
	list->size = 0;
    //释放list链表结构
	free(list);
}

LinkList.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#ifndef LINKLIST_H
#define LINKLIST_H
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
//链表节点
typedef struct LINKNODE {
	void*  data;//指向任何类型的数据
	struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef	struct LINKLIST {
	LinkNode* head;
	int size;
}LinkList;
//打印函数指针
typedef void(*PRINTLINKNODE)(void *);
//判断函数指针
typedef int(*PEQUALNODE)(void* vp1, void *vp2);
//初始化链表
LinkList* Init_LinkList();

//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void *data);

//删除指定位置的结点
void RemoveByPos_LinkList(LinkList* list, int pos);

//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list, void* pData, PEQUALNODE equal);
//打印链表节点,需要用户提供一个打印函数
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//返回第一个节点
void* Front_LinkList(LinkList* list);

//释放链表内存
void FreeSpace_LinkList(LinkList* list);

#endif

LinkList.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include"LinkList.h"
//初始化链表
LinkList* Init_LinkList() {
	LinkList* list = (LinkList *)malloc(sizeof(LinkList));
	list->size = 0;

	//头结点不保存数据信息
	list->head = (LinkNode*)malloc(sizeof(LinkNode));
	list->head->data = NULL;
	list->head->next = NULL;

	return list;
}

//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void *data) {


	if (list == NULL)
	{
		return;
	}

	if (list->head == NULL)
	{
		return;
	}
	//友好处理越界问题
	if (pos < 0 || pos > list->size)
	{
		pos = list->size;
	}

	//创建新的结点
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//查找找结点
	//辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//新结点入链表
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	list->size++;

}

//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos) {
	if (list == NULL)
	{
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	//查找删除结点的前一个结点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//缓存删除的结点
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	//释放删除结点的内存
	free(pDel);

	list->size--;

}

//获得链表的长度
int Size_LinkList(LinkList* list) {

	return list->size;
}
//查找
int Find_LinkList(LinkList* list, void* pData, PEQUALNODE equal){
	if (list == NULL)
	{
		return -1;
	}
	if (pData == NULL) {
		return -1;
	}

	//遍历查找
	LinkNode* pCurrent = list->head->next;
	int pos = 0;
	while (pCurrent != NULL)
	{
		if (equal(pCurrent->data,pData) == 0) {
			break;
		}
		pos++;
		pCurrent = pCurrent->next;
	}

	return pos;
}
//打印链表节点,需要用户提供一个打印函数
void Print_LinkList(LinkList* list, PRINTLINKNODE print) {

	if (list == NULL) {
		return;
	}
	//辅助指针变量
	LinkNode* pCurrent = list->head->next;

	while (pCurrent != NULL)
	{
		print(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}
//返回第一个节点
void* Front_LinkList(LinkList* list) {

	return list->head->next;
}

//释放链表内存
void FreeSpace_LinkList(LinkList* list) {
	if (list == NULL)
	{
		return;
	}

	LinkNode *pCurrent = list->head;
	while (pCurrent != NULL)
	{
		LinkNode *pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;

	}
	list->size = 0;
	free(list);
}

main.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
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include"LinkList.h"

typedef struct PERSON {
	char name[20];
	int age;
	int score;
}Person;

int Equal(void* pv1, void* pv2) {
	Person* p1 = (Person *)pv1;
	Person* p2 = (Person *)pv2;

	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
void print(void* pv) {
	Person *p1 = (Person *)pv;
	printf("%s,%d,%d\n", p1->name, p1->age, p1->score);
}
int main() {

	Person p1 = { "aaa",10,100 };
	Person p2 = { "bbb",11,111 };
	Person p3 = { "ccc",12,20 };
	Person p4 = { "ddd",13,150 };
	Person p5 = { "eee",14,120 };

	//初始化链表
	LinkList *list = Init_LinkList();
	//在链表指定位置添加结点
	Insert_LinkList(list,0,&p1);
	Insert_LinkList(list,1,&p2);
	Insert_LinkList(list,2,&p3);
	Insert_LinkList(list,3,&p4);
	Insert_LinkList(list,4,&p5);

	//打印链表
	Print_LinkList(list, print);
	//查找结点位置
	printf("%d\n", Find_LinkList(list, &p4, Equal));
	//返回链表第一个结点
	LinkNode *ret = (LinkNode*)Front_LinkList(list);
	printf("%s,%d,%d\n",((Person*)(ret->data))->name, ((Person*)(ret->data))->age, ((Person*)(ret->data))->score);

	//获取链表长度
	printf("size:%d \n", Size_LinkList(list));

	//删除指定位置结点
	RemoveByPos_LinkList(list, 4);
	printf("---------------");
	printf("size:%d \n", Size_LinkList(list));
	Print_LinkList(list, print);
	//释放链表内存
	FreeSpace_LinkList(list);
	return 0;
}

YanChen

Personal profile