一.链表的设计

1.节点的创建

节点采用结构来定义，将结构体内部分为数据和指针域

• 数据域：定义节点要存储的数据
• 指针域：定义用来存储下一个节点指针的指针变量(⚠️数据类型用结构体数据类型)

2.节点的连接

要创建多少个节点就创建多少个结构体对象，数据域那里该存什么数据赋什么值，指针域那块将其手动赋值为下一个节点的地址 连接🔗:

• 数据域： 该存什么存什么
• 指针域： 存储下一个节点的指针

#include 
strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};

int main(void){
	/*创建节点*/
	//默认都将其next设置为NULL，保证其中任意一个为最后一个都可以结束遍历
	strcut stu node1 = {18,"lisi",NULL};
	strcut stu node2 = {19,"lijiu",NULL};
	strcut stu node3 = {20,"ergou",NULL};
	//定义头节点指针，记录第一个节点的地址值
	strcut stu head = &node1;
	//让节点建立连接
	node1.next = &node2;
	node2.next = &node3;
}

3.遍历链表

⚠️不要直接操作记录着头结点地址的指针去遍历，这会造成内存泄露，丢失指针

定义一个指针pd指向存储着第一个节点地址的头节点head 之后用while循环，结束条件为pd != NULL 在循环内将pd指向当前遍历到结构体内存储的指针next。实现一个个节点不断下移 关键点： 指向下一个节点的代码pd = pd -> next 代码：

#include 
strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};

int main(void){
	/*创建节点*/
	//默认都将其next设置为NULL，保证其中任意一个为最后一个都可以结束遍历
	strcut stu node1 = {18,"lisi",NULL};
	strcut stu node2 = {19,"lijiu",NULL};
	strcut stu node3 = {20,"ergou",NULL};
	//定义头节点指针，记录第一个节点的地址值
	strcut stu head = &node1;
	//让节点建立连接
	node1.next = &node2;
	node2.next = &node3;

	/*节点的遍历*/
	//定义一个指针记录头节点的地址(不要直接操作记录头节点的指针)
	strcut stu *p = head;
	while(pd -> next != NULL){
		printf("年龄:%d,名字:%s",pd -> age,pd -> name);
		//⚠️ 将当前指针指向的地址赋值给当前遍历到结构体内记录的地址
		pd = pd -> next;
	}
} 

二.链表头部插入

头部插入： 即是每次新插入的节点都是从头部插入的，每次新插入的节点都是其所插入链表的第一个

1.大体思路

总之，让head始终指向第一个节点，next始终指向下一个节点

先定义一个用于指向第一节点的指针head,并将其赋赋初值为NULL

• 不存在链表： 直接将当前创建的节点地址赋值给head，节点内指向下一个节点的next赋值为NULL
• 存在链表： 1.先让当前创建节点指向下一节点地址的指针赋值为head所指向的值 2.再让head赋值为当前创建节点的地址

2.代码

#include 
strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};

int main(void){
	//创建节点
	strcut stu node1 = {18,"lisi",NULL};
	strcut stu node2 = {19,"lijiu",NULL};
	//定义头节点指针
	strcut stu *head;
	/*进行第一个节点插入*/
	//判断头节点是否为NULL，进而判断是否存在链表
	if(head == NULL){
		//不存在，直接将当前插入节点的地址赋值给head(node1)
		head = &node1;
	}else{
		//存在，先让插入节点的next记录head,再让head记录当前插入节点的地址
		node2.next = head;
		head = &node2;
	}
}

三.链表的尾部插入

1.大体思路

关键点： 就是要找到尾节点，并将当前节点的指针给到尾节点的next,然后其自身的next指向NULL

2.实现

• 第一个节点直接赋值给定义好用来记录头结点的指针head即可
• 其余节点需要从头节点开始遍历，找到尾节点，并将自己的地址值交尾节点

代码：

#include 
strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};

int main(void){
	//创建节点
	strcut stu node1 = {18,"lisi",NULL};
	strcut stu node2 = {19,"lijiu",NULL};
	//定义头节点指针
	strcut stu *head;
	/*进行第一个节点插入*/
	//判断头节点是否为NULL，进而判断是否存在链表
	if(head == NULL){
		//不存在，直接将当前插入节点的地址赋值给head(node1)
		head = &node1;
	}else{
		//存在，从头节点开始往下遍历，找到最后一个节点，并将最后一个节点的next，赋值为当前节点的地址值
		//定义一个新的指针用于遍历(不能动head)
		strcut stu *pd = head;
		while(pd -> next != NULL){
			//让pd指向下一个节点的地址
			pd = pd -> next;
		}
		//遍历完毕，pd就已经是指向最后一个节点了
		//让最后一个节点的next指向要插入节点
		pd -> next = &node2;//假设要插入的节点是node2
		//将插入节点的地址值赋值为NULL
		node2.next = NULL;//就是演示流程，上面已经初始化过了，没必要
	}
}

四.链表的有序插入

有序插入： 即插入时按照节点中的某个信息进行排序，保证顺序

1.实现

1.定义一个参考值

定义节点中的特定值作为参考值，作为排序的依据 2.定义两个指针

two指针的意义，就是在one指针比较值小于下一节点时，用来确定插入点位置的依据

• 一个指针从头节点开始，不断下移，并与设定的参考值进行比较 one
• 一个指针用于记录下移比较的那个指针所指向的上一个节点的地址值 two

3.插入时机

• 当one所指向节点的参考值小于下一个节点的对应参考点的值且two无值时，将插入节点作为头节点 (头部插入) 将其地址值赋值给head，将其next(下节点地址)赋值为之前的头节点
• 当one所指向节点的参考值小于下一个节点的对应参考点的值且two有值时，将插入节点放到two指针指向节点的下一个 (中部插入)
• 当one所指向的值为NULL，即其后面没有节点时，将插入节点插入到链表尾部 (尾部插入)

2.例子

需求： 插入节点时按照学生的年龄为依据进行有序插入

#include 
strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};

int main(void){
	//创建节点
	strcut stu node1 = {18,"lisi",NULL};
	strcut stu node2 = {19,"lijiu",NULL};
	//定义头节点指针
	strcut stu *head;
	/*进行第一个节点插入*/
	//判断头节点是否为NULL，进而判断是否存在链表
	if(head == NULL){
		//不存在，直接将当前插入节点的地址赋值给head(node1)
		head = &node1;
	}else{
		/*存在*/
		//定义两个操作指针
		strcut stu *one = head;//遍历比较的指针
		strcut stu *two = NULL;//记录one的指针
		//进行循环比较排序(假设插入节点是node2)
		while((one -> age < node2 -> age) && (one != NULL) ){
			//大于下一个节点参考值，且其值不为NULL，让one指向下一个节点
			two = one;
			one = one -> next;
		}
		//满足任意条件退出
		if(one -> age < node2 -> age){
			//头部插入
			if(two == NULL){
				//将node的next赋值为head原指向的第一个节点的值
				node2.next = head;
				//让head指向新插入的头节点node2
				head = &node2;
			}else{
			//中部插入
				//将two指向节点的next改为node2的地址
				two -> next = &node2;
				//让插入节点node2的next记录的值修改为one，即下一个节点的地址
				node2.next = one;
			}
		}else{
		//到这里就是尾部插入了
			//因为one已经指向null,所以指向其前一个节点的指针two所拥有的值就是最后一个节点的值，直接让尾节点记录插入节点的值即可完成尾部插入
			two -> next = &node2;
			//将插入节点的next赋值为NULL，标示链表结尾
			node.next = NULL;
		}
		
	}
}

五.查找链表指定节点

1.实现

1.判断链表是否存在，不存在直接返回没找到 2.使用Strcmp函数去循环匹配遍历到节点内要查找的数据，遍历到就返回找到数据

• 这个需要注意判断循环是否到达最后一个节点了，到了记得退出

2.代码

这里我就写一个函数，假设已经存在数据了 实现功能: 传入要查找的姓名，返回该姓名所处的节点

/*
返回值：节点指针
传入值：节点指针，用于接收要查找的链表 char指针，用于接收要查找的名字
*/
struct str *PIN search(struct str *head,char *name){
	//先判断传入链表是否为存在
	if(head == NULL){
		printf("链表不存在");
		return NULL;
	}
	//循环遍历链表，匹配要查找的值，找到或遍历完毕就退出循环
	struct str *pd = head;
	while((strcmp(pd -> name,name) != 0 )&& (pd -> next == NULL)){
		//让pd获取第二个节点的地址值
		pd = pd -> next;
	}
	if(strcmp(pd -> name,name) == 0){
		//找到的搜索名字对应的节点，对其进行返回
		return pd;
	}
	return NULL;
	
}

六.删除指定节点

1.实现

(1)思路

删除一个节点，就将这个节点的上一个节点的指针域的值修改为删除节点的下一个节点的指针，然后释放要删除的节点即可

(2)步骤

• 判断存不存在链表，不存在直接返回"链表不存在"
• 判断要删除的节点是不是头节点，是则将head = head -> head再释放头节点即可
• 不是头节点，则让这个节点的上一个节点的指针域指向要删除节点的下一个节点，之后释放这个节点即可

(3)代码

假设节点都存储在堆区，即存储在动态内存申请的区域的

实现： 根据传入的ID删除对应的节点
节点结构体：

strcut stu {
	//数据域
	int age;
	int id;//学号，用于判断删除对象的
	char name[30];
	//指针域
	strcut stu *next;
};

业务代码：

STU *delete_link delete(STU*head,int id){
	//判断链表是否存在
	if(head == NULL){
		printf("链表不存在");
		return head;//没删掉,返回原来的头节点指针
	}
	/*根据ID查找要删除的节点*/
	STU *pd = head;//用来移动遍历的指针
	STU *dp = NULL;//用来记录遍历指针位置的指针
	
	while((pd -> id != id) && (pd -> next != NULL)){
		dp = pd;//记录pd的值
		pd = pd -> next;//让pd获取第二个节点的地址值
	}
	
	//找到了的情况
	if(pd -> id == id){
		//要删除的节点是第一个节点
		if(pd == head){
			//让记录第一个节点的指针指向第一个节点的next，即将第二个节点作为第一个节点
			head = head -> next;
			//释放第一个节点，这里是假设节点是在堆区的情况
			free(pd);//释放要删除的节点
			return head;//返回新的头节点
		}else{
			/*中间节点或尾节点删除*/
			//将上一个节点的next赋为删除节点的下一个节点
			dp -> next = pd -> next;
			free(pd);//释放待删除节点	
			//依旧是返回原来的head,因为变动的不是头部，而是链表内部
			return head;
		}
		
	}else{
		//没找到
		printf("没有找到要删除的节点");
		return head;
	}
}

七.释放整个链表

1.整体思路

释放每一个节点前，要让该head指向下一个节点，且最后要为head赋值NULL，避免head指针泄露，无法再次对该链表进行赋值

STU* free_link(STU* head){
	//判断链表是否存在
	if(head == NULL){
		printf("链表不存在");
	}else{
		STU *pb = head;
		while(pb != NULL){
			head = pb -> next;
			free(pb);
			pb = head;
		}
	}
	return NULL;
}

八.typedef

1.用途

• 给结构体起别名
• 创建结构体变量的指针

(1)起别名

总的记住一个原则，先创建遍历再起别名 至于遍历是在创建结构体时创建的，还是后面创建的，都行，都可以用来起别名

方式一: 创建结构体的同时创建一个变量，并用这个变量来起别名

typedef strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
}DATA;

方式二: 先创建结构体再给其起别名

strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
};
//起别名
typedef strcut stu DATA;

(2)创建结构体遍历指针

⚠️ 不单单只有这一种方式可以创建，你可以用普通的方式创建

简单说就是将变量变成指针变量，这样就可以创建结构体的指针了，就可以用这个指针方便的接受结构体变量了 代码：

typedef strcut stu {
	//数据域
	int age;
	char name[30];
	//指针域
	strcut stu *next;
} *DATA_POIN;

使用：

strcut stu stu1 = {18,"zhangsan"};
DATA_POIN = &stu1;