Linked_List (finished)

Pomni Lv2
  2024-09-19 20:59:42 2024-09-19 20:59:42 Created   2024-09-22 17:35:26 2024-09-22 17:35:26 Updated      2.6k Words  11 Mins  

最近在学习线性表中的链表，正好预习复习一下。
main函数在文末。

直接上代码

不停地翻炒知识，才能收获真正的味道。
虽然现在还是有很多问题，但是在慢慢解决了。 

1
2
3
4
5
6
#结构体定义
typedef struct LNode
{
	int key;
	struct LNode* next;
}LNode;

创建链表

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
#尾接入法
LNode* Create_a_list()
{
	LNode* head = (LNode*)malloc(sizeof(LNode));
	if (head == NULL)
	{
		return NULL;
	}
	//如果head内存分配失败的话，返回NULL。
	//提高代码的健壮性和安全性。

	LNode* tail = head;
	//tail = (LNode*)malloc(sizeof(LNode));
	tail->next = NULL;
	int value;

	while (scanf("%d", &value)==1)//如果输入的是非数值字符将会停止循环
	{
		if (value <= 0)
			break;
		LNode* p = (LNode*)malloc(sizeof(LNode));
		p->key = value;
		p->next = NULL;//最新一个节点的next一定为NULL
		tail->next = p;//将新节点与链表最后一个节点相连
		tail = p;//将指示指针移动到新节点处
	}

	return head->next;//返回的是有效的第一个节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#头接入法
LNode* Create_a_list()
{
	LNode* head = (LNode*)malloc(sizeof(LNode));
	if (head == NULL)
	{
		return NULL;//对head是否成功分配内存进行判断。
	}
	head->next = NULL;
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		int value;
		scanf("%d", &value);
		LNode* p = (LNode*)malloc(sizeof(LNode));
		p->key = value;
		p->next = head->next;
		head->next = p;
	}
	return head->next;
}

💡Tips

  • 当一个结构体指针需要存东西的时候，就要开辟内存空间。如果它只是复制其他的指针，则不需要开辟空间。
  • 此处代码返回的是 LNode* 类型，所以要返回指针。在创建链表中，就要返回头节点指针。此处的 head->next 指向的是有效的第一个节点。
  • 安全性检查。

打印链表

1
2
3
4
5
6
7
8
9
10
11
void Print_a_list(LNode* L)
{
	LNode* p;
	p = L;
	while (p->next != NULL)
	{
		printf("%d->", p->key);
		p = p->next;
	}
	printf("%d\n", p->key);
}

删除链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Delete_a_list(LNode* L)
{
	LNode* p = L;
	while (p != NULL)
	{
		p = L->next;
		free(L);
		L = p;
	}
	if (L == NULL)
	{
		printf("It's done.\n");
	}
}

💡Tips

  • 一般是用两个指针并行移动，一个负责记录和保存，另一个负责删改和变换。此处就是p和L。

返回链表长度

1
2
3
4
5
6
7
8
9
10
11
int Get_length(LNode* L)
{
	LNode* head = L;
	int i = 0;
	while (head != NULL)
	{
		i++;
		head = head->next;
	}
	return i;
}

💡Tips

  • 虽然很简单，但仍要强调一下，避免犯一些蠢钝如猪的错误。🐷🐷🐷
    这里用头节点自身移动没什么太大问题，但是在链表的元素有改动的时候，记得另外定义一个节点复制头节点的值来保存头节点指针。如果直接移动头节点指针，那么整个链表就乱套了。😖😖😖

返回链表节点值

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
int Get_value(LNode* L, int i)
{
	LNode* head = L;
	int j = 0;

	/*
	for (; j < i-1; j++)
	{
		head = head->next;
	}
	*/

	//改进
	while (head != NULL && j < i - 1)
	{
		head = head->next;
		j++;
	}
	if (head == NULL)
	{
		return 0;
	}
	printf("%d\n", head->key);
	return head->key;
}

💡Tips

  • 返回类型据结构体具体内容而定，以及其中的一些细节输出也要视具体的结构体而定。
  • 依旧是注意安全性检查。

插入元素

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
#返回结构体类型
LNode* List_insert(LNode* L, int value, int location)
{
	LNode* head = L;
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p->key = value;

	
	if (location==1)
	{
		p->next = head;
		head = p;
		return head;
	}

	int i = 1;
	while (location > i && head->next!=NULL)
	{
		head = head->next;
		i++;
	}

	p->next = head->next;
	head->next = p;
	return head;
}
  • 注意返回的是指针类型。因为如果头节点被修改，那么该链表的头节点指针需要更新。

但是，返回类型也可以是void。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#返回void类型
void List_insert(LNode** L, int value, int location)
{
	LNode* head = *L;//注意这里指针是指向头节点的指针
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p->key = value;
	if (location == 1)
	{
		p->next = head;
		head = p;
		*L = head;//只需要在location为1的时候更新头节点即可
		return;
	}
	int i = 1;
	while (i < location && head->next != NULL)
	{
		head = head->next;
		i++;
	}
	p->next = head->next;
	head->next = p;	
}

💡Tips

  • 因为你要修改指针，所以要传指针的指针。即你要修改什么，就传那个东西的指针。
  • 传指针和传值的区别：
    🔍传指针：实际上传的是指针指向的某个变量的地址，那么你在函数体内修改指针，就是在修改这个地址储存的内容，是从根本上修改。
    🔍传值：在函数传参中，传值传参只是创建了该变量的副本，在函数体内的修改也只是对副本进行修改，并没有对本体造成实质性的改变。

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LNode* List_delete(LNode* L, int location)
{
	LNode* head = L,*p = L;

	int i = 1;
	while (i < location-1 && p != NULL)
	{
		p = p->next;
		i++;
	}
	LNode* p1 = p->next;
	p->next = p1->next;
	free(p1);
	return head;
}

返回指定位置的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LNode* Get_location(LNode* L, int value)
{
	LNode* p = L;
	
	while (p != NULL && p->key != value)
	{
		p = p->next;
	}
	if (p == NULL)
	{
		printf("该节点不存在\n");
	}
	return p;
}

删除指定值的第一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Delete_pointed_key(LNode** L, int value)
{
	LNode* p = *L;
	LNode* q=NULL;
	while (p->next != NULL && p->key != value)
	{
		q = p;
		p = p->next;
		
	}
	if (q == NULL)
	{
		*L = p->next;
	}
	else 
	{
		q->next = p->next;
	}
	free(p);
}

删除指定值的所有节点

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
void Delete_pointed_key_all(LNode** L, int value)
{
	LNode* p = *L;
	LNode* q = NULL;
	while (p != NULL)
	{
		//检查头节点key是否等于value
		if (p->key == value)
		{
			LNode* tmp = p;
			p = p->next;
			if (q == NULL)//说明此时是头指针
			{
				*L = p;
			}
			else
			{
				q->next = p;
				free(tmp);
			}
			free(tmp);
			//将头节点指针移到下一个节点
		}
		else
		{
			q = p;
			p = p->next;
		}
	}
}

💡Tips

  • （一些心理话）链表的代码其实就是在描述链表移动增删查改的过程。后续如果有机会，做一个链表的动画，这样搭配代码食用更佳。

合并有序数组

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
#改进版
LNode* Merge_linked_list(LNode* L1, LNode* L2)
{
	LNode* p = L1, * q = L2;
	LNode* r=(LNode*)malloc(sizeof(LNode));//创建虚拟头节点
	r->next = NULL;
	while(p != NULL && q != NULL)
	{
		if (p->key < q->key)
		{
			r->next = p;
			p = p->next;
		}
		else if (p->key > q->key)
		{
			r->next = q;
			q = q->next;
		}
		else
		{
			r->next = p;
			LNode* tmp = q;
			p = p->next;
			q = q->next;
			free(tmp);
		}
		r = r -> next;
	}
	if (p == NULL)
	{
		r->next = q;
	}
	else
	{
		r->next = p;
	}
	return L1;
}
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
#原版
LNode* Merge_linked_list(LNode* L1, LNode* L2)
{
	LNode* p = L1, * q = L2, *r = L1;
	while(p != NULL && q != NULL)
	{
		if (p->key < q->key)
		{
			r = p;
			p = p->next;
		}
		else if (p->key > q->key)
		{
			r = q;
			q = q->next;
		}
		else
		{
			r = p;
			LNode* tmp = q;
			p = p->next;
			q = q->next;
			free(tmp);
		}
		r = r -> next;
	}
	if (p == NULL)
	{
		r->next = q;
	}
	else
	{
		r->next = p;
	}
	return L1;
}

💡Tips

原版的问题主要出于逻辑上的漏洞。

  • 原版想实现的逻辑是将两个链表合并到其中一个链表中。
    • r=p 或者 r=q都是想将当前节点赋给链表r中，但因为后续有 r=r->next ，上述赋值会导致r向p或者q的链表移动，不太准确。
  • 改进版同样实现了这个逻辑，但语法更健壮。
    • 先初始化r为虚拟头节点，注意此时r后续会连接节点，即要存储内容，所以r要初始化且开辟内存空间。
    • 将原版改成了 r->next=p 以及 r->next=q ，就不会出现r沿p或者q的链表移动的情况。因为r始终在两个节点的前一个节点，用 r->next 的话只需要置身“链”外选择下一个节点，而不会让自身处在两个链表里干涉选择。

main函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{

	LNode* list = Create_a_list();
	Print_a_list(list);
	int length=Get_length(list);
	printf("%d\n",length);
	Get_value(list, 3);
	Delete_a_list(list);
	LNode* list2 = Create_a_list();
	list2=List_insert(list2, 7, 1);
	list_insert(&list2,7,1);
	Print_a_list(list2);
	list2=List_delete(list2, 3);
	Print_a_list(list2);
	Delete_pointed_key(&list2, 7);
	Print_a_list(list2);
	Delete_pointed_key_all(&list2, 3);
	Print_a_list(list2);
	list=Merge_linked_list(list, list2);
	Print_a_list(list);
	return 0;
}

💡Tips

  • 返回类型不为空时，要有相同类型的对象“去接住这个函数的返回结果”。e.g. list2=List_insert(list2, 7, 1);中的list2。

啰哩巴嗦的总结

以下几点是链表中最常出错的地方：

  • 创建链表时是否保留了虚拟头节点。因为本文创建链表返回的是有效而非虚拟头节点指针，所以在链表的其他操作中有时会预先定义虚拟头节点。（一通写下来似乎有虚拟头节点更方便🤔）
  • 如果创建的指针有内容要存储（例如该指针会插入链表），那么一定要初始化分配内存空间。如果只是复制其他头节点指针，则不需要开辟空间。
  • 特别注意不要直接移动链表原初的头节点，先复制保存头结点指针值，再进行操作（例如删除节点）。直接移动指针值的话就很容易意识不到头节点的改变。
  • 用两个指针并行移动，一个负责记录和保存，另一个负责删改和变换。
  • 在对链表元素有增删时，有两种方式，一种是传头节点指针的指针，返回类型为空；一种是传头节点指针，返回类型为指针（返回改动后链表的头节点指针）。（详见插入元素。）
  • 安全性检查十分重要。当遍历链表时很容易超出链表范围，用上判断条件 p!=NULL 就会有保障得多。
  • 哦对了，还有一个小点，传指针的指针时，要记得取指针的地址！！！

心得

心得就是没有心得。
感觉自己在有些方面还是考虑不周，或者思路十分怪异导致代码实现起来很拧巴。
还有就是链表的范围取定，很容易报错呢哈哈哈。
Anyway，温故常新。
要想学得好，多做多思考！（向刘红salute🫡）

  • Title: Linked_List (finished)
  • Author: Pomni
  • Created at : 2024-09-19 20:59:42
  • Updated at : 2024-09-22 17:35:26
  • Link: https://redefine.ohevan.com/2024/09/19/Linked-List/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Linked_List (finished)
  1. 直接上代码
    1. 创建链表
      1. 💡Tips
    2. 打印链表
    3. 删除链表
      1. 💡Tips
    4. 返回链表长度
      1. 💡Tips
    5. 返回链表节点值
      1. 💡Tips
    6. 插入元素
      1. 💡Tips
    7. 删除节点
    8. 返回指定位置的元素
    9. 删除指定值的第一个节点
    10. 删除指定值的所有节点
      1. 💡Tips
    11. 合并有序数组
      1. 💡Tips
    12. main函数
      1. 💡Tips
  2. 啰哩巴嗦的总结
  3. 心得