c语言之链表

定义：链表是一种物理储存上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种现行储存结构。
特点：
链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc）,每个节点包括两个部分：
（1）存储数据元素的数据域
（2）存储下一个节点地址的指针域

链表的构成：链表由一个个节点构成，每个节点一般采用结构体的形式组织，例如：

typedef struct student
{
int num;
char name[20];
struct student *next;   //与结构体名字一样
}STU;

链表节点分为两个域
数据域：存放实际的数据，如：num,score;
指针域：存放下一个节点的首地址，如:next等。

链表的操作：创建（增删改查）

1.链表的创建
第一步：创建一个节点
第二步：创建第二个节点，将其放在第一个节点的后面（第一个节点的指针域保存第二个节点的地址）
第三步：再次创建节点，找到原本节点的最后一个节点，接着将最后一个节点的指针域保存新节点的地址，以此类推。
代码1：

#include
#include
#pragma warning(disable:4996)

//定义结构体
typedef struct student
{
	//数据域
	int num;
	int score;
	char name[20];
	//指针域
	struct student* next;
}STU;

void link_creat_head(STU** p_head, STU *p_new)
{
	STU* p_mov = *p_head;
	if (*p_head == NULL) //当第一次加入链表为空时，head执行p_new
	{
		*p_head = p_new;
		p_new->next = NULL;
	}
	else //第二次及以后加入链表
	{
		while (p_mov->next != NULL)
		{
			p_mov = p_mov->next; //找到原有链表的最后一个节点
		}
		p_mov->next = p_new;//将新申请的节点加入链表
		p_new->next = NULL;
	}

}
int main()
{
	STU* head = NULL, * p_new = NULL;
	int num, i;
	printf("请输入链表初始个数：");
	scanf("%d", &num);
	for(i=0;inum, &p_new->score, p_new->name);
		link_creat_head(&head, p_new);  //将节点加入新的链表
	}
}

链表的遍历：
第一步：输出第一个结点的数据域，输出完毕后，让指针保存后一个结点的地址
p=p->next
第二步：输出移动地址对应的结点的数据域，输出完毕后，指针继续后移
第三步：以此类推，直到结点的指针域为NULL
代码2：

#include
#include
#pragma warning(disable:4996)

//定义结构体
typedef struct student
{
	//数据域
	int num;
	int score;
	char name[20];
	//指针域
	struct student* next;
}STU;

void link_creat_head(STU** p_head, STU* p_new)
{
	STU* p_mov = *p_head;
	if (*p_head == NULL) //当第一次加入链表为空时，head执行p_new
	{
		*p_head = p_new;
		p_new->next = NULL;
	}
	else //第二次及以后加入链表
	{
		while (p_mov->next != NULL)
		{
			p_mov = p_mov->next; //找到原有链表的最后一个节点
		}
		p_mov->next = p_new;//将新申请的节点加入链表
		p_new->next = NULL;
	}

}

//链表的遍历
void link_print(STU* head)
{
	STU* p_mov;
	//定义新的指针保存链表的首地址，防止使用head改变原本链表
	p_mov = head;
	//当指针保存最后一个结点的指针域为NULL时，循环结束
	while (p_mov != NULL)
	{
		//先打印当前指针保存结点的指针域
		printf("num=%d score=%d name=%s n", p_mov->num, p_mov->score, p_mov->name);

		//指针后移 保存下一个结点的地址
		p_mov = p_mov->next;
	}
}

int main()
{
	STU* head = NULL, * p_new = NULL;
	int num, i;
	printf("请输入链表初始个数：");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		p_new = (STU*)malloc(sizeof(STU));  //申请一个新节点
		printf("请输入学号，分数，名字：n");
		scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
		link_creat_head(&head, p_new);  //将节点加入新的链表
	}
	link_print(head);
}

链表的释放：
重新定义一个指针q,保存p指向的地址，然后p后移保存下一个结点的地址，然后释放q对应的结点，以此类推，直到p为NULL为止。
代码3：

#include
#include
#pragma warning(disable:4996)

//定义结构体
typedef struct student
{
	//数据域
	int num;
	int score;
	char name[20];
	//指针域
	struct student* next;
}STU;

void link_creat_head(STU** p_head, STU* p_new)
{
	STU* p_mov = *p_head;
	if (*p_head == NULL) //当第一次加入链表为空时，head执行p_new
	{
		*p_head = p_new;
		p_new->next = NULL;
	}
	else //第二次及以后加入链表
	{
		while (p_mov->next != NULL)
		{
			p_mov = p_mov->next; //找到原有链表的最后一个节点
		}
		p_mov->next = p_new;//将新申请的节点加入链表
		p_new->next = NULL;
	}

}

//链表的遍历
void link_print(STU* head)
{
	STU* p_mov;
	//定义新的指针保存链表的首地址，防止使用head改变原本链表
	p_mov = head;
	//当指针保存最后一个结点的指针域为NULL时，循环结束
	while (p_mov != NULL)
	{
		//先打印当前指针保存结点的指针域
		printf("num=%d score=%d name=%s n", p_mov->num, p_mov->score, p_mov->name);

		//指针后移 保存下一个结点的地址
		p_mov = p_mov->next;
	}
}

//链表的释放
void link_free(STU** p_head)
{
//定义一个指针变量保存头指针的地址
	STU* pb = *p_head;

	while (*p_head!=NULL)
	{
		//先保存p_head指向的结点的地址
		pb = *p_head;
		//p_head保存下一个结点的地址
		*p_head = (*p_head)->next;
		//释放结点并防止野指针
		free(pb);
		pb = NULL;
	}
}

int main()
{
	STU* head = NULL, * p_new = NULL;
	int num, i;
	printf("请输入链表初始个数：");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		p_new = (STU*)malloc(sizeof(STU));  //申请一个新节点
		printf("请输入学号，分数，名字：n");
		scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
		link_creat_head(&head, p_new);  //将节点加入新的链表
	}
	link_print(head);
	link_free(&head);
}

链表结点的查找
先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个结点，如果到达最后一个结点就没有匹配的数据，说明要查找的数据不存在。
代码4：

#include
#include
#pragma warning(disable:4996)

//定义结构体
typedef struct student
{
	//数据域
	int num;
	int score;
	char name[20];
	//指针域
	struct student* next;
}STU;

void link_creat_head(STU** p_head, STU* p_new)
{
	STU* p_mov = *p_head;
	if (*p_head == NULL) //当第一次加入链表为空时，head执行p_new
	{
		*p_head = p_new;
		p_new->next = NULL;
	}
	else //第二次及以后加入链表
	{
		while (p_mov->next != NULL)
		{
			p_mov = p_mov->next; //找到原有链表的最后一个节点
		}
		p_mov->next = p_new;//将新申请的节点加入链表
		p_new->next = NULL;
	}

}

//链表的遍历
void link_print(STU* head)
{
	STU* p_mov;
	//定义新的指针保存链表的首地址，防止使用head改变原本链表
	p_mov = head;
	//当指针保存最后一个结点的指针域为NULL时，循环结束
	while (p_mov != NULL)
	{
		//先打印当前指针保存结点的指针域
		printf("num=%d score=%d name=%s n", p_mov->num, p_mov->score, p_mov->name);

		//指针后移 保存下一个结点的地址
		p_mov = p_mov->next;
	}
}

//链表的释放
void link_free(STU** p_head)
{
//定义一个指针变量保存头指针的地址
	STU* pb = *p_head;

	while (*p_head!=NULL)
	{
		//先保存p_head指向的结点的地址
		pb = *p_head;
		//p_head保存下一个结点的地址
		*p_head = (*p_head)->next;
		//释放结点并防止野指针
		free(pb);
		pb = NULL;
	}
}

//链表的查找
//按照学号查找
STU* link_search_num(STU* head, int num)
{
	STU* p_mov;
	//定义一个指针变量保存第一个结点的地址
	p_mov = head;
	//当没有到达最后一个结点的指针域时循环继续 
	while (p_mov != NULL)
	{
		//如果找到是当前结点的数据，则返回当前结点的地址
		if (p_mov->num == num)  //找到了
		{
			return p_mov;
		}
		//如果没有找到 则继续对比下一个结点的指针域
		p_mov = p_mov->next;
	}
	//当循环结束的时候还没有找到 说明要查找的数据不存在 返回NULL进行标识
	return NULL;  //没有找到
}

//按照姓名查找
STU* link_search_name(STU* head, char *name)
{
	STU* p_mov;
	//定义一个指针变量保存第一个结点的地址
	p_mov = head;
	//当没有到达最后一个结点的指针域时循环继续 
	while (p_mov != NULL)
	{
		//如果找到是当前结点的数据，则返回当前结点的地址
		if (strcmp(p_mov->name,name) ==0)  //找到了
		{
			return p_mov;
		}
		//如果没有找到 则继续对比下一个结点的指针域
		p_mov = p_mov->next;
	}
	//当循环结束的时候还没有找到 说明要查找的数据不存在 返回NULL进行标识
	return NULL;  //没有找到
}

int main()
{
	STU* head = NULL, * p_new = NULL, * pb=NULL;
	int num, i;
	printf("请输入链表初始个数：");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		p_new = (STU*)malloc(sizeof(STU));  //申请一个新节点
		printf("请输入学号，分数，名字：n");
		scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
		link_creat_head(&head, p_new);  //将节点加入新的链表
	}
	link_print(head);
	//link_free(&head);
	//查学号
	while (1)
	{
		printf("输入您要查找的学生的学号：n");
		scanf("%d", &num);
		pb = link_search_num(head, num);
		if (pb != NULL)
		{
			printf("找到了 num=%d score=%d name=%s", pb->num, pb->score, pb->name);
		}
		else
		{
			printf("没有找到");
		}
	}
}

链表结点的删除：
如果链表为空，不需要删除
如果删除的是第一个结点，则需要保存链表首地址的指针保存第一个结点的下一个结点的地址
如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结点的后一个地址即可。
代码5：

#include
#include
#pragma warning(disable:4996)

//定义结构体
typedef struct student
{
	//数据域
	int num;
	int score;
	char name[20];
	//指针域
	struct student* next;
}STU;

void link_creat_head(STU** p_head, STU* p_new)
{
	STU* p_mov = *p_head;
	if (*p_head == NULL) //当第一次加入链表为空时，head执行p_new
	{
		*p_head = p_new;
		p_new->next = NULL;
	}
	else //第二次及以后加入链表
	{
		while (p_mov->next != NULL)
		{
			p_mov = p_mov->next; //找到原有链表的最后一个节点
		}
		p_mov->next = p_new;//将新申请的节点加入链表
		p_new->next = NULL;
	}

}

//链表的遍历
void link_print(STU* head)
{
	STU* p_mov;
	//定义新的指针保存链表的首地址，防止使用head改变原本链表
	p_mov = head;
	//当指针保存最后一个结点的指针域为NULL时，循环结束
	while (p_mov != NULL)
	{
		//先打印当前指针保存结点的指针域
		printf("num=%d score=%d name=%s n", p_mov->num, p_mov->score, p_mov->name);

		//指针后移 保存下一个结点的地址
		p_mov = p_mov->next;
	}
}

//链表的释放
void link_free(STU** p_head)
{
//定义一个指针变量保存头指针的地址
	STU* pb = *p_head;

	while (*p_head!=NULL)
	{
		//先保存p_head指向的结点的地址
		pb = *p_head;
		//p_head保存下一个结点的地址
		*p_head = (*p_head)->next;
		//释放结点并防止野指针
		free(pb);
		pb = NULL;
	}
}

//链表的查找
//按照学号查找
STU* link_search_num(STU* head, int num)
{
	STU* p_mov;
	//定义一个指针变量保存第一个结点的地址
	p_mov = head;
	//当没有到达最后一个结点的指针域时循环继续 
	while (p_mov != NULL)
	{
		//如果找到是当前结点的数据，则返回当前结点的地址
		if (p_mov->num == num)  //找到了
		{
			return p_mov;
		}
		//如果没有找到 则继续对比下一个结点的指针域
		p_mov = p_mov->next;
	}
	//当循环结束的时候还没有找到 说明要查找的数据不存在 返回NULL进行标识
	return NULL;  //没有找到
}

//按照姓名查找
STU* link_search_name(STU* head, char *name)
{
	STU* p_mov;
	//定义一个指针变量保存第一个结点的地址
	p_mov = head;
	//当没有到达最后一个结点的指针域时循环继续 
	while (p_mov != NULL)
	{
		//如果找到是当前结点的数据，则返回当前结点的地址
		if (strcmp(p_mov->name,name) ==0)  //找到了
		{
			return p_mov;
		}
		//如果没有找到 则继续对比下一个结点的指针域
		p_mov = p_mov->next;
	}
	//当循环结束的时候还没有找到 说明要查找的数据不存在 返回NULL进行标识
	return NULL;  //没有找到
}

//链表结点的删除
void link_detele_num(STU** p_head, int num)
{
	STU* pb, * pf;
	pb = pf = *p_head;
	if (*p_head == NULL)  //链表为空 不用删
	{
		printf("链表为空，没有您要删的结点");
		return;
	}
	while (pb->num!=num && pb->next!=NULL)  //循环找，要删除的结点
	{
		pf = pb;
		pb = pb->next;
	}
	if (pb->num == num) //找到了一个结点的num和num相同
	{
		if (pb == *p_head)  //要删除的是头结点
		{
			//让保存头结点的指针保存后一个结点的地址
			*p_head = pb->next;
		}
		else
		{
			//前一个结点的指针域保存要删除的后一个结点的地址
			pf->next = pb->next;
		}
		//释放空间
		free(pb);
		pb = NULL;
	}
	else //没有找到
	{
		printf("没有你要删除的结点n");
	}


}

int main()
{
	STU* head = NULL, * p_new = NULL, * pb=NULL;
	int num, i;
	printf("请输入链表初始个数：");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		p_new = (STU*)malloc(sizeof(STU));  //申请一个新节点
		printf("请输入学号，分数，名字：n");
		scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
		link_creat_head(&head, p_new);  //将节点加入新的链表
	}
	link_print(head);
	//link_free(&head);
	printf("请输入你要删除结点的学号:n");
	scanf("%d", &num);
	link_detele_num(&head, num);
	link_print(head);
	link_free(&head);
}

c语言之链表

C/C++/C#相关栏目本月热门文章