链表学习（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

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

struct STU
{
	int nums;
	char name[10];
	struct STU *next;//这里的next虽然拼写一样，但是在每一个节点的结构体里指向的都是他后面那个结构体
};					//这里新建结构体，一定要放在前面，不然后面的函数调用报错

void opdata(struct STU *student)//传进来一个结构体指针，该指针指向一个结构体
{
	puts("input the nums: ");
	scanf("%d", &student->nums);
	puts("input the name: ");
	scanf("%s", student->name);
}								//这个指针指向的结构体赋值成功

void addnode(struct STU **student)//这里传递的是“指向指针的指针”，
{
	struct STU *temp, *new_stu;
	if (*student != NULL)		//这里说如果传进来的节点不是最后一个
	{							//*student是内容所在的地址，student存放的是*student的地址
		new_stu = (struct STU*)malloc(sizeof(struct STU));//新建一个节点，并申请一个空间
		opdata(new_stu);

		temp = *student;	//先将原先指向数据的地址保存为temp
		*student = new_stu;	//指针更新成新的指针
		new_stu->next = temp;//新的节点的next指针指向原来的节点
	}
	else		//传进来的是最后一个节点，也就是说链表是空的，这样直接在后面加就可以
	{
		new_stu = (struct STU*)malloc(sizeof(struct STU));
        opdata(new_stu);
		*student = new_stu;
	}
}

void PrintData(struct STU *student)//传进来一个指向结构体的指针
{
	struct STU *stu;				//新建中间人，这里是为了防止参数被改变，使后面的释放函数出错
	stu = student;
	while(stu != NULL)				//等于NULL的话就说明到最后一个了，
	{
		printf("xuehao is %u\n", stu->nums);
		printf("name is %s\n", stu->name);
		stu = stu->next;			//不断指向next
		printf("\n");
	}
}

void releaseMem(struct STU **student)
{
	struct STU  *temp;		//找第三方替换，不然直接free的话 只能free一个，剩下的free不了
	while( *student != NULL )//内容所在的地址不是空的
	{
		temp = *student;	//中间变量接受地址
		*student = (*student)->next;	//内容的地址指向下一组内容
		free(temp);			//free掉刚刚的内存空间
	}
}

int main()
{
	struct STU* student = NULL;

	puts("test");

	printf("the addr of (*student) is %p\n",student);
	printf("the addr of (&student) is %p\n",&student);
	addnode(&student);			//这里把这个结构体指针的地址传进去，让一个新的节点指向这个地址
	PrintData(student);			//这里就正常的传递一个结构体指针
	releaseMem(&student);		//也是把这个结构体指针的地址传进去
	
	puts("successful");

	return 0;
}

关于程序中指向指针的指针我理解为

image-20220106192242683

这里addnode和releaseMem函数的参数均是二级指针，这个指针指向了 “指向数据内容的一级指针”

尾插法

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
#include<stdlib.h>
#include<stdio.h>

struct stu
{
	char name[20];
	int score;
	struct stu *next;
};

void OpStu(struct stu *student)
{
	printf("name : ");
	scanf("%s", student -> name);
	printf("\n");
	printf("Score : ");
	scanf("%d", &student -> score);
}
//主要不同之处就在于这里的节点插入
void AddStu(struct stu **student)
{
	struct stu *new_stu = (struct stu*)malloc(sizeof(struct stu));
    //为新节点分配空间
	static struct stu *end_node;
	//创建静态变量来存储尾节点
	OpStu(new_stu);
    
	if (*student == NULL)//如果是一个空链表
	{
		*student = new_stu;//直接把头的指针指向新生成的数据
		new_stu->next = NULL;//最后在他后面补上NULL，或者可以是
        //(*student) -> next = NULL 解引用和->的优先级不一样
	}
	else//不是空链表
	{
		end_node->next = new_stu;//尾节点的下一项是新节点
		new_stu->next = NULL;//封底
	}
	end_node = new_stu;//尾接点指向新节点的
}

void PrintNode(struct stu *students)
{
	struct stu *temp;
	temp = students;
	while(temp->next != NULL)
	{
		printf("name is %s, got %d scores\n", temp->name, temp->score);
		temp = temp->next;
	}
	printf("FINISH\n");
}


void ReleasMem(struct stu **students)
{
	struct stu *temp;
	//temp = *students;
	while(*students != NULL)
	{
		temp = *students;
		*students = (*students)->next;
		free(temp);
	}
	puts("free end\n");
}

int main()
{
	struct stu *student = NULL;
	int i=5;
	while(i!=0)//用五组数据进行测试
	{
		AddStu(&student);
		i--;
	}
	PrintNode(student);
	ReleasMem(&student);
	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
void InsertNode(int addr, struct stu *student)
{
	//int count=0;
	struct stu *stu = student;
	struct stu *newstu = NULL;
	struct stu *temp;
	for(;addr-1!=0;addr--)//先通过循环找到要插入的节点的位置
	{
		stu = stu->next;
	}
	//printf("insert location---> %s,%d\n\n",stu->name,stu->score);
	newstu = (struct stu*)malloc(sizeof(struct stu));
	OpStu(newstu);//准备好要插入的新节点

	temp = stu->next;//将前一个节点的next指针用temp保存
	stu->next = newstu;//前一个节点的next指针指向新的插入的节点
	newstu->next = temp;//新节点的next指针指向原来的节点
}

void DeletNode(int addr, struct stu* student)
{
	struct stu *under, *stu, *pre;
	stu = student;
	for(;addr!=1;addr--)
	{
		if (addr == 2)
		{
			pre = stu;//将要删除节点的前一个节点保存
		}
		stu = stu->next;//找到要删除的节点
	}
	//printf("delete location---> %s,%d\n\n",stu->name,stu->score);
	under = stu->next;//保存要删除节点的后一个节点
    pre->next = under;//将删除节点的前一个节点指向后一个节点
	//printf("pre location---> %s,%d\n\n",pre->name,pre->score);
	//printf("under location---> %s,%d\n\n",under->name, under->score);
	free(stu);//free掉删除的节点的内存空间
	puts("delete success");

}

插入：

image-20220107123357566