王道数据结构C语言单链表基本操作实现

一、头插

头插流程示意图：注意是先连后断

#define _CRT_SECURE_NO_WARNINGS
#include
//单链表定义
//链表结点
typedef struct {//定义单链表结点类型
	int data;//数据域
	struct LNode *next;//指针域
}LNode, *LinkList;

void MyPrint(LinkList L) {
	LNode* i = L->next;//用i指针遍历整个链表
	while (i != NULL) {
		printf("%d ", i->data);
		i = i->next;
	}
}


//头插法建立单链表
LinkList list_HeadInsert(LinkList* L) {
//为了能影响到原先的链表，我们这里是用LinkList*
//LinkList本身是一个指针，LinkList*是指针的指针，它指向存放头指针的地址
	LNode* s ;//新插入的结点
	int x;//结点值
	*L = (LinkList)malloc(sizeof(LNode));//创建头结点
	//L是指向原先头指针的地址，对它解引用(*L)就是原先的头指针
	(*L)->next = NULL;//初始为空链表
	scanf("%d", &x);//输入结点的值
	while (x != 9999) {
		LNode* s = (LNode*)malloc(sizeof(LNode));//创建新结点
		s->data = x;
		s->next = (*L)->next;
		(*L)->next = s;
		scanf("%d", &x);//输入新结点的值
	}
	return L;
}

int main() {
	LinkList L = NULL;
	list_HeadInsert(&L);
	MyPrint(L);
	return 0;
}
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

测试用例如下

注意，因为头插法是先插的排后面去了，所以头插法生成的数是逆序

二、尾插

尾插流程示意图：注意是先连后断
这里我们设置一个指向链表尾部的指针rear
（不设尾指针的话，你要尾插每次都要从前往后找，比较麻烦）

//尾插法建立单链表
LinkList List_TailInsert(LinkList* L) {
	LNode*s;//新插入结点
	int x;//结点值
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;
	LNode* rear = *L;
	//尾结点指针rear，这里赋值时注意对L解引用，L是指向头结点的指针，解引用才是头结点
	scanf("%d", &x);
	while (x != 9999) {//输入9999视为结束标志
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = NULL;
		rear->next = s;
		rear = s;
		scanf("%d", &x);
	}
	return L;
}

int main() {
	LinkList L = NULL;
	List_TailInsert(&L);
	MyPrint(L);
	return 0;
}
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

三、查找

3.1按序号插

//按序号查找——这里是按位序，位序从1开始
LNode* GetElem(LinkList* L, int i) {
	if (i < 1) {
		return NULL;
	}
	LNode*s=(*L)->next;//用s来遍历链表
	for (int j = 1;j < i&&s!=NULL;j++) {
		s = s->next;
	}
	return s;
}

int main() {
	LinkList L = NULL;
	printf("请插入链表元素,以9999为结束标志:");
	List_TailInsert(&L);
	MyPrint(L);
	printf("\n");

	printf("请输入要查的链表元素位序:");
	int i = 0;
	scanf("%d", &i);
	printf("指定位序结点值为：%d", GetElem(&L, i)->data);
	return 0;
}
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

3.2按值查

LNode* LocateElem(LinkList* L, int i) {
	LNode* s = (*L)->next;
	while (s != NULL) {
		if (s->data == i) {//找到就返回，不用继续找了
			return s;
		}
		s = s->next;
	}
	return NULL;//上面while走完都没返回，则返回NULL
}

int main() {
	LinkList L = NULL;
	printf("请插入链表元素,以9999为结束标志:");
	List_TailInsert(&L);
	MyPrint(L);
	printf("\n");

	printf("请输入要查的链表元素值:");
	int i = 0;
	scanf("%d", &i);
	if (LocateElem(&L, i)!=NULL) {
		printf("指定结点值为：%d", LocateElem(&L, i)->data);
	}
	else {
		printf("链表中无该值的结点");
	}
	return 0;
}
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

查找成功用例：

查找失败用例：

四、任意位置插入

将值为x的结点插到单链表第i个位置
其实就是找到第i-1个位置，在它后面进行一个插入

p=GetElem(&L,i-1);//找到第i-1位置的结点
s->next=p->next;//先连
p->next=s;//后断
1
2
3

五、删除结点

要删掉链表第i个位置元素

也是先找到第i-1个位置元素，直接把第i-1个元素连上要删元素的下一个
再把要删元素free掉即可

p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(q);
1
2
3
4