循环链表

数据结构与算法 评论

image-20220106160208492

image-20220106160259094

链表操作:

初始化函数，插入函数，获得第一个结点，根据位置删除，根据值删除

获得链表长度，查找，打印结点，释放内存，判断是否为空

CircleLinkList.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
44
45
46
47
48
49
50
51
52
53
#ifndef CIRCLELINKLIST_H
#define CIRCLELINKLIST_H

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


//真
#define CIRCLELINKLIST_TRUE 1
//假
#define CIRCLELINKLIST_FALSE 0

//结点
typedef struct CIRCLELINKNODE {
	struct CIRCLELINKNODE * next;
}CircleLinkNode;
//链表
typedef struct CIRCLELINKLIST {
	CircleLinkNode head;
	int size;
}CircleLinkList;

//比较函数指针
typedef int(*COMPARENODE)(CircleLinkNode *, CircleLinkNode *);
//打印函数指针
typedef void(*PRINTNODE)(CircleLinkNode *);


//初始化函数
CircleLinkList * Init_CircleLinkList();
//插入函数
void Insert_CircleLinkList(CircleLinkList *clist, int pos, CircleLinkNode * data);
//获得第一个结点
CircleLinkNode * Front_CircleLinkList(CircleLinkList *clist);
//根据位置删除
void RemoveByPos_CircleLinkList(CircleLinkList *clist,int pos);
//根据值删除
void RemoveByValue_CircleLinkList(CircleLinkList *clist, CircleLinkNode* data,COMPARENODE compare);
//获得链表长度
int Size_CircleLinkList(CircleLinkList *clist);
//查找
int Find_CircleLinkList(CircleLinkList *clist, CircleLinkNode * data, COMPARENODE compare);
//打印结点
void Print_CircleLinkList(CircleLinkList *clist, PRINTNODE print);

//释放内存
void FreeSpace_CircleLinkList(CircleLinkList *clist);

//判断是否为空
int IsEmpty_CircleLinkList(CircleLinkList *clist);

#endif

CircleLinkList.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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include"CircleLinkList.h"


//初始化函数
CircleLinkList * Init_CircleLinkList(){
	CircleLinkList *list = (CircleLinkList*)malloc(sizeof(CircleLinkList));
	list->head.next = &(list->head);	//开始先让头结点的next指向自己
	list->size = 0;
	return list;
}
//插入函数
void Insert_CircleLinkList(CircleLinkList *clist, int pos, CircleLinkNode * data) {
	if (clist == NULL)
	{
		return;
	}

	if (data == NULL)
	{
		return;
	}

	if (pos < 0 || pos > clist->size )
	{
		pos = clist->size;
	}
	//查找
	CircleLinkNode * pCurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//插入结点
	data->next = pCurrent->next;
	pCurrent->next = data;
	//结点长度加1
	clist->size++;

}
//获得第一个元素
CircleLinkNode * Front_CircleLinkList(CircleLinkList *clist) {

	return clist->head.next;
}
//根据位置删除
void RemoveByPos_CircleLinkList(CircleLinkList *clist, int pos) {
	if (clist == NULL)
	{
		return;
	}
	if (pos < 0 || pos > clist->size)
	{
		return;
	}

	//查找位置
	CircleLinkNode * pCurrent = &(clist->head);

	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	CircleLinkNode * pNext = pCurrent->next;
	pCurrent->next = pNext->next;

	clist->size--;
}
//根据值删除
void RemoveByValue_CircleLinkList(CircleLinkList *clist, CircleLinkNode* data, COMPARENODE compare) {
	
	if (clist == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	//指向目标结点的前一个结点
	CircleLinkNode *pPrev = &(clist->head);
	//指向目标结点
	CircleLinkNode * pCurrent = clist->head.next; 
	for (int i = 0; i < clist->size; i++)
	{
		if (compare(pCurrent,data) == CIRCLELINKLIST_TRUE)
		{
			//删除结点
			pPrev->next = pCurrent->next;
			break;
		}
		pPrev = pPrev->next;
		pCurrent = pCurrent->next;
	}

	//结点长度减一
	clist->size--;

}
//获得链表长度
int Size_CircleLinkList(CircleLinkList *clist) {
	
	return clist->size;
}
//查找
int Find_CircleLinkList(CircleLinkList *clist, CircleLinkNode * data, COMPARENODE compare) {

	if (clist == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}
	CircleLinkNode *pCurrent = clist->head.next;
	int pos = -1;
	for (int i = 0; i < clist->size; i++)
	{
		if (compare(pCurrent,data) == CIRCLELINKLIST_TRUE)
		{
			pos = i;
			break;
		}
		pCurrent = pCurrent->next;
	}

	return pos;
}
//打印结点
void Print_CircleLinkList(CircleLinkList *clist, PRINTNODE print) {
	
	if (clist == NULL)
	{
		return;
	}
	CircleLinkNode * pCurrent = clist->head.next;
	for (int i = 0; i < clist->size; i++)
	{
		print(pCurrent);
		pCurrent = pCurrent->next;
	}
	printf("\n ==================================\n");
}

//释放内存
void FreeSpace_CircleLinkList(CircleLinkList *clist) {

	if (clist == NULL)
	{
		return;
	}

	free(clist);
}

//判断是否为空
int IsEmpty_CircleLinkList(CircleLinkList *clist) {

	if (clist->size == 0)
	{
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}

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
64
65
66
67
68
69
70
71
#include<stdio.h>
#include"CircleLinkList.h"
#include<string.h>

typedef struct STUDENT {
	CircleLinkNode node;
	char name[64];
	int score;
	int age;
}Student;

//比较函数
int Compare(CircleLinkNode *data1, CircleLinkNode *data2) {

	Student *s1 = (Student*)data1;
	Student *s2 = (Student*)data2;

	if (s1->age == s2->age && s1->score == s2->score && strcmp(s1->name,s2->name) == 0)
	{
		return 1;
	}
	else {
		return 0;
	}

}
//打印函数
void Print(CircleLinkNode * node) {

	Student *s = (Student*)node;
	printf("%s,%d,%d\n",s->name,s->age,s->score);
}

int main() {


	Student s1 = {NULL,"aaa",81,15};
	Student s2 = { NULL,"bbb",82,16};
	Student s3 = { NULL,"ccc",83,17};
	Student s4 = { NULL,"ddd",84,18};
	Student s5 = { NULL,"eee",85,19};
	//创建链表
	CircleLinkList* clist =  Init_CircleLinkList();

	//插入链表
	Insert_CircleLinkList(clist,100,(CircleLinkNode*)&s1);
	Insert_CircleLinkList(clist,100, (CircleLinkNode*)&s2);
	Insert_CircleLinkList(clist,100, (CircleLinkNode*)&s3);
	Insert_CircleLinkList(clist,100, (CircleLinkNode*)&s4);
	Insert_CircleLinkList(clist,100, (CircleLinkNode*)&s5);

	//打印链表
	Print_CircleLinkList(clist,Print);

	//删除第0个元素
	RemoveByPos_CircleLinkList(clist,0);
	//删除s4元素
	RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&s4, Compare);

	//打印链表
	Print_CircleLinkList(clist,Print);
	//查找
	printf("pos:%d\n", Find_CircleLinkList(clist, (CircleLinkNode*)&s5, Compare));
	//返回链表大小
	printf("size:%d\n", Size_CircleLinkList(clist));

	//释放链表
	FreeSpace_CircleLinkList(clist);

	return 0;
}

YanChen

Personal profile