单向链表·初识【c语言】

顺序表和链表的优缺点

入门·增删改查【大佬请路过】

• 本部分相信，很多人都经历过，虽然单纯的增删改查没什么实际的意义。但是这是我们我们的基础，将简单的逻辑思路搞清楚之后，我们才可以更快更好的深入学习。
• 定义的节点

typedef int SLNDataType;
typedef struct SingleListNode {
	SLNDataType data;
	struct SingleListNode* next;
} SLN;
1
2
3
4
5

增

头插·思路·代码

void SLNPushFront(SLN** pphead, SLNDataType x) {
	SLN* newNode = CreateSLN(x);
	//无论链表是否为空，都正确
	newNode->next = *pphead;
	*pphead = newNode;
}
1
2
3
4
5
6

尾插·思路·代码

• 关于为什么使用二级指针，因为函数传递的是一级指针，如果使用同级指针，会造成指针值传递。形参指针不修改实参指针的值。

void SLNPushBack(SLN** pphead, SLNDataType x) {
	SLN* newNode=CreateSLN(x);
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	else {
		//找到尾节点
		SLN* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newNode;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

定位插入·前插入

void SLNInsertBefore(SLN** pphead, SLN* pos, SLNDataType x) {
	SLN* newNode = CreateSLN(x);
	//头节点的情况
	if (*pphead == pos) {
		newNode->next = *pphead;
		*pphead = newNode;
	}
	//非头节点的情况：找到pos的前一个位置
	else {
		SLN* posPrev = *pphead;
		while (posPrev->next != pos) {
			posPrev = posPrev->next;
		}
		posPrev->next = newNode;
		newNode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

定位插入·后插入

void SLNInsertAfter(SLN* pos, SLNDataType x) {
	SLN* newNode = CreateSLN(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
1
2
3
4
5

删

头删

void SLNPopFront(SLN** pphead) {
	if (*pphead == NULL) {
		cout << "空链表" << endl;
		return;
	}
	else {
		SLN* newTail=(*pphead)->next;
		free(*pphead);
		*pphead = newTail;
	}
}
1
2
3
4
5
6
7
8
9
10
11

尾删

void SLNPopBack(SLN** pphead) {
	/*
	删除总共分三种情况：
	1：链表本身是空的
	2：链表只有一个节点
	3：链表有一个以上的节点
	*/
	//1-粗暴的方式
	//assert(*pphead!=NULL);
	//2-温柔的方式
	if (*pphead == NULL) {
		cout << "空链表" << endl;
		return;
	}
	
	else if((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		
	}
	else {
		//找到尾节点和尾节点的前一个节点
		//将尾节点释放，将尾节点的前一个节点的next置为null
		//方法一：
		/*
		SLN* tail = *pphead;
		SLN* prev = NULL;
		while (tail->next != NULL) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
		*/
		//方法二：
		SLN* tail = *pphead;
		while (tail->next->next) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

指定删除·节点

void SLNEase(SLN** pphead, SLN* pos) {
	//要删除的元素是头节点
	if(*pphead == pos) {
		*pphead = pos->next;
		free(pos);
		//方法二：SLNPopFront(pphead);
	}
	else {
		SLN* posPrev = *pphead;
		while (posPrev->next != pos) {
			posPrev= posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
		pos = NULL;//可有可没有，形参没改变实参，防止某些时候错误，顺手写上
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

查

SLN* SLNFindByValue(SLN* phead, SLNDataType x) {
	SLN* cur = phead;
	while (cur != NULL) {
		if (cur->data == x) {
			return cur;
		}
		else {
			cur = cur->next;
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

改

SLN* plist = NULL;
    SLNPushBack(&plist, 1);
    SLNPushBack(&plist, 2);
    SLNPushBack(&plist, 3);
    SLNPushBack(&plist, 2);
    SLNPushBack(&plist, 4);
    SLNPushBack(&plist, 2);
    SLNPushBack(&plist, 5);
    SLNPrint(plist);
    //查找作用
    SLN*pos=SLNFindByValue(plist, 2);
    int i = 1;
    while (pos) {
        cout << "第" << i++ << "个pos节点：" << &pos << "->" << pos->data << endl;
        pos = SLNFindByValue(pos->next, 2);
    }
    //修改作用
    pos = SLNFindByValue(plist, 2);
    while(pos) {
        pos->data = 20;
        pos = SLNFindByValue(pos->next, 2);
    }
    SLNPrint(plist);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

销毁·链表

void SLNDestroy(SLN** pphead) {
	SLN* q = NULL;
	SLN*p = *pphead;//让p指向头节点
	while (p != NULL) {
		q = p->next;//让q指向当前节点的后一个节点
		delete p;//删除当前节点
		p = q;
	}
	//free(*pphead);
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11