企业链表

数据结构与算法 评论

img

不开辟结点的空间，用户定义的结构体包含指向下一个结点的指针。

链表小结点

1
2
3
typedef struct LINKNODE {
	struct LINKNODE* next; //指向一个结点的指针变量
}LinkNode;

链表结点

1
2
3
4
typedef struct LINKLIST {
	LinkNode head;	//头结点,不保存数据
	int size;	//结点长度
}LinkList;

企业链表操作

初始化链表，插入，删除，查找，返回链表大小，打印，释放链表内存

初始化链表

1
2
3
4
5
6
7
8
//初始化链表
LinkList* Init_LinkList() {

	LinkList * list = (LinkList*)malloc(sizeof(LinkList));
	list->head.next = NULL;
	list->size = 0;
	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
//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data) {
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	if (pos < 0 || pos >= list->size)
	{
		pos = list->size;
	}

	//查找插入位置
	LinkNode * pCurrent = &(list->head);
	for (int i = 0; i < pos; i++) {
		pCurrent = pCurrent->next;
	}
	//插入新结点
	data->next = pCurrent->next;
	pCurrent->next = data;

	list->size++;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//删除
void Remove_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;
	}
	pCurrent->next = pCurrent->next->next;

	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
//查找
int Find_LinkList(LinkList* list, LinkNode * data, COMPARENODE compare) {
	if (list == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}

	//辅助指针变量
	LinkNode *pCurrent = list->head.next;
	int flag = -1, pos = 0;
	while (pCurrent != NULL)
	{
		if (compare(pCurrent,data) == 0)
		{
			return (flag = pos);
			break;
		}
		pos++;
		pCurrent = pCurrent->next;
	}
	return flag;
}

返回链表大小

1
2
3
4
5
//返回链表大小
int Size_LinkList(LinkList* list) {

	return list->size;
}

打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//打印
void Print_LinkList(LinkList* list, PRINTNODE print) {
	if (list == NULL)
	{
		return;
	}

	//辅助指针
	LinkNode* pCurrent = list->head.next;
	while (pCurrent != NULL)
	{
		print(pCurrent);
		pCurrent = pCurrent->next;
	}
}

释放链表内存

1
2
3
4
5
6
7
8
9
//释放链表内存
void FreeSpace_LinkList(LinkList* list) {
	if (list == NULL)
	{
		return;
	}

	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
43
#ifndef LINKLIST_H
#define LINKLIST_H
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//链表小结点
typedef struct LINKNODE {
	struct LINKNODE* next;
}LinkNode;

//链表结点
typedef struct LINKLIST {
	LinkNode head;
	int size;
}LinkList;
//用户提供的打印函数指针
typedef void(*PRINTNODE)(LinkNode *);
//用户提供的比较函数指针
typedef int(*COMPARENODE)(LinkNode*, LinkNode*);
//初始化链表
LinkList* Init_LinkList();

//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);

//删除
void Remove_LinkList(LinkList* list, int pos);
//查找
int Find_LinkList(LinkList* list, LinkNode * data, COMPARENODE compare);

//返回链表大小
int Size_LinkList(LinkList* list);


//打印
void Print_LinkList(LinkList* list, PRINTNODE print);

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



#endif

ListLink.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
#include"LinkList.h"


//初始化链表
LinkList* Init_LinkList() {

	LinkList * list = (LinkList*)malloc(sizeof(LinkList));
	list->head.next = NULL;
	list->size = 0;
	return list;
}

//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data) {
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	if (pos < 0 || pos >= list->size)
	{
		pos = list->size;
	}

	//查找插入位置
	LinkNode * pCurrent = &(list->head);
	for (int i = 0; i < pos; i++) {
		pCurrent = pCurrent->next;
	}
	//插入新结点
	data->next = pCurrent->next;
	pCurrent->next = data;

	list->size++;
}

//删除
void Remove_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;
	}
	pCurrent->next = pCurrent->next->next;

	list->size--;

}
//查找
int Find_LinkList(LinkList* list, LinkNode * data, COMPARENODE compare) {
	if (list == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}

	//辅助指针变量
	LinkNode *pCurrent = list->head.next;
	int flag = -1, pos = 0;
	while (pCurrent != NULL)
	{
		if (compare(pCurrent,data) == 0)
		{
			return (flag = pos);
			break;
		}
		pos++;
		pCurrent = pCurrent->next;
	}
	return flag;
}

//返回链表大小
int Size_LinkList(LinkList* list) {

	return list->size;
}


//打印
void Print_LinkList(LinkList* list, PRINTNODE print) {
	if (list == NULL)
	{
		return;
	}

	//辅助指针
	LinkNode* pCurrent = list->head.next;
	while (pCurrent != NULL)
	{
		print(pCurrent);
		pCurrent = pCurrent->next;
	}
}

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

	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
#include<stdio.h>
#include"LinkList.h"
#include<string.h>
typedef struct PERSON {
	LinkNode node;
	char name[64];
	int age;
}Person;

void MyPrint(LinkNode* data) {
	Person *p = (Person*)data;

	printf("%s,%d\n", p->name, p->age);
}

int compare(LinkNode* d1, LinkNode *d2)
{
	Person *p1 = (Person*)d1;
	Person *p2 = (Person*)d2;

	if (strcmp(p1->name,p2->name) == 0 && p1->age == p2->age)
	{
		return 0;
	}
	return -1;
}
int main() {
	//初始化
	LinkList * list = Init_LinkList();
	//创建数据
	Person p1 = { NULL,"aaa",11 };
	Person p2 = { NULL,"bbb",12 };
	Person p3 = { NULL,"ccc",13 };
	Person p4 = { NULL,"ddd",14 };
	Person p5 = { NULL,"eee",15 };
	//插入数据
	Insert_LinkList(list,0,(LinkNode *)&p1);
	Insert_LinkList(list,0,(LinkNode *)&p2);
	Insert_LinkList(list,0,(LinkNode *)&p3);
	Insert_LinkList(list,0,(LinkNode *)&p4);
	Insert_LinkList(list,0,(LinkNode *)&p5);

	//打印链表
	Print_LinkList(list, MyPrint);

	//查找
	int ret = Find_LinkList(list, (LinkNode*)&p1, compare);
	printf("Find:%d\n", ret);
	//返回链表长度
	printf("Size:%d\n", Size_LinkList(list));

	printf("--------------------\n");
	//删除
	Remove_LinkList(list,4);

	//打印链表
	Print_LinkList(list, MyPrint);
	//释放链表
	FreeSpace_LinkList(list);
	return 0;
}

YanChen

Personal profile