数据结构:2.链式表

2026-01-31 05:13:59 栏目：最新资讯 2 阅读

几乎全是代码，概念配合代码，可以多打几遍熟练

缺的地方后续会补

1.链表分类

2.单向链表

3.双向链表

4.循环链表

1.链表分类

单向链表
双向链表
循环链表

2.单向链表

单向链表又分有头链表和无头链表
有头链表（又称带头节点的链表）是在链表的第一个元素之前增加一个特殊的"头节点"，这个节点不存储实际数据，只作为链表的入口
无头链表是指链表的第一个节点就是实际存储数据的节点，没有额外的头节点
由于无头链表要用到大量二级指针，过于麻烦，有头链表更为常用
多文件编程makefile

makefile

mu:=main
lai+=lian.c
lai+=main.c
$(mu):$(lai)
    gcc $^ -g -o $@                                                         

.PHONY:
clean:
    rm $(mu)
//查看是否有内存泄漏
cha:
    valgrind --tool=memcheck --leak-check=full ./$(mu)

下为单向链表的创建，插入值(头插)，打印，删除值，寻找值，修改值，插入值(尾插)，销毁链表，查找中间节点，查找倒数第n个，倒置链表，冒泡排序，选择排序，lian.c文件

#include"lian.h"
Node_t *chuanglian(void)
{
	Node_t *pnewnode = NULL;
	pnewnode = malloc(sizeof(Node_t));
	if(NULL == pnewnode)
	{
		perror("失败");
		return NULL;
	}
	pnewnode->pnext = NULL;

	return pnewnode;
}
int chalian(Node_t *ptou,datatype data)
{
	Node_t *pnewnode = NULL;
	pnewnode = malloc(sizeof(Node_t));
	if(NULL == pnewnode)
	{
		perror("失败");
		return -1;
	}
	pnewnode->data = data;
	pnewnode->pnext = ptou->pnext;
	ptou->pnext = pnewnode;
	return 0;
}
void showlian(Node_t *ptou)
{
	Node_t * pzhong = NULL;
	pzhong = ptou->pnext;
	while(pzhong != NULL)
	{
		printf("%d ",pzhong->data);
		pzhong = pzhong->pnext;
	}
	putchar('
');
}
int shanlian(Node_t *ptou,datatype a)
{
	int cnt = 0;
	Node_t *pqian = NULL;
	Node_t *phou = NULL;
	pqian = ptou->pnext;
	phou = ptou;
	while(pqian != NULL)
	{
		if(pqian->data == a)
		{
			phou->pnext = pqian->pnext;
			free(pqian);
			pqian = phou->pnext; 
			cnt++;
		}
		else
		{
			pqian = pqian->pnext;
			phou = phou->pnext;
		}
	}
	return cnt;
}
Node_t * zhaolian(Node_t *ptou,datatype a)
{
	Node_t *pzhong = NULL;
	Node_t *pfu = NULL;
	pzhong = ptou->pnext;
	while(pzhong != NULL)
	{
		if(a == pzhong->data)
		{
			pfu = pzhong;
			return pfu;
		}
		pzhong = pzhong->pnext;
	}
	return NULL;
}
int gailian(Node_t *ptou,datatype jiu,datatype xin)
{
	int cnt = 0;
	Node_t *pzhong = NULL;
	pzhong = ptou->pnext;
	while(pzhong != NULL)
	{
		if(pzhong->data==jiu)
		{
			pzhong->data = xin;
			cnt++;
		}
		pzhong = pzhong->pnext;
	}
	return cnt;
}
int weichalian(Node_t *ptou,datatype data)
{
	Node_t *pnewnode = NULL;
	//如果Node_t *pzhong = ptou;当只有一个头时，会出现段错误，NULL
	Node_t *pzhong = ptou;
	pnewnode = malloc(sizeof(Node_t));
	if(NULL == pnewnode)
	{
		perror("失败");
		return -1;
	}
	pnewnode->data = data;
	while(pzhong->pnext != NULL)
	{
		pzhong=pzhong->pnext;
	}
	//此时，pzhong->pnext == NULL
	pnewnode->pnext = NULL;//pnewnode->pnext = pzhong->pnext;
	pzhong->pnext = pnewnode;
	return 0;
}
void hui(Node_t **pptou)
{
	Node_t *pqian = NULL;
	Node_t *phou = NULL;
	pqian = *pptou;
	phou = *pptou;
	while(pqian != NULL)
	{
		pqian = pqian->pnext;
		free(phou);
		phou = pqian;
	}
	*pptou = NULL;
}
Node_t *zhaozhlian(Node_t *ptou)
{
	Node_t *pkuai = NULL;
	Node_t *pman = NULL;
	pkuai = pman = ptou->pnext;
	while(pkuai != NULL)
	{
		pkuai = pkuai->pnext;
		if(pkuai == NULL)
		{
			return pman;
		}
		pkuai = pkuai->pnext;
		pman = pman->pnext;
	}
	return pman;
}
Node_t *zhaoalian(Node_t *ptou,int a)
{
	Node_t *pkuai = NULL;
	Node_t *pman = NULL;
	pkuai = pman = ptou->pnext;
	int x = 0;
	for(x = 0;xpnext;
	}
	while(pkuai != NULL)
	{
		pkuai = pkuai->pnext;
		pman = pman->pnext;
	}
	return pman;
}
void daozhilian(Node_t *ptou)
{
	Node_t *pqian = NULL;
	Node_t *phou = NULL;
	pqian = phou = ptou->pnext;
	ptou->pnext = NULL;
	while(pqian != NULL)
	{
		pqian = pqian->pnext;
		phou->pnext = ptou->pnext;
		ptou->pnext = phou;
		phou = pqian;

	}
}
int maopaolian(Node_t *ptou)
{
	Node_t *pqian = NULL;
	Node_t *phou = NULL;
	Node_t *pend = NULL;
	datatype zhong;
	if(ptou->pnext==NULL || ptou->pnext->pnext==NULL )
		return 0;
	while(1)
	{
		pqian = ptou->pnext->pnext;
		phou = ptou->pnext;
		if(pend == pqian)
			break;
		while(pqian != pend)
		{
			if(pqian->data < phou->data)
			{
				zhong = phou->data;
				phou->data = pqian->data;
				pqian->data = zhong;
			}
			pqian = pqian->pnext;
			phou = phou->pnext;
		}
		pend = phou;
	}
	return 0;
}
int xuanzelian(Node_t *ptou)
{
	Node_t *pqian = NULL;
	Node_t *phou = NULL;
	Node_t *pmax = NULL;
	datatype zhong;
	if(ptou->pnext==NULL || ptou->pnext->pnext==NULL )
		return 0;
	phou = ptou->pnext;
	while(phou->pnext != NULL)
	{
		pqian = phou->pnext;
		pmax = phou;
		while(pqian != NULL)
		{
			if(pmax->data < pqian->data)
				pmax = pqian;
			pqian = pqian->pnext;
		}
		if(pmax->data != phou->data)
		{
			zhong = phou->data;
			phou->data = pmax->data;
			pmax->data = zhong;
		}
		phou = phou->pnext;
	}
	return 0;
}

main.c文件

#include"lian.h"
int main()
{
	Node_t *plian = NULL;
	plian = chuanglian();
	Node_t *pliana = chuanglian();
	chalian(plian,1);
	chalian(plian,2);
	chalian(plian,3);
	chalian(plian,3);
	chalian(plian,4);
	chalian(plian,2);
	chalian(plian,5);
	printf("头插：1、2、3、3、4、2、5
");
	showlian(plian);
	int a=shanlian(plian,3);
	printf("删了%d个3
",a);
	showlian(plian);
	Node_t *fu = zhaolian(plian,4);
	printf("找4：%p %d 
",fu,fu->data);
	int b=gailian(plian,2,9);
	printf("9换2：");
	showlian(plian);
	weichalian(plian,0);
	weichalian(plian,1);
	weichalian(plian,2);
	weichalian(plian,3);
	weichalian(plian,4);
	weichalian(plian,5);
	printf("尾插：0、1、2、3、4、5
");
	showlian(plian);
	maopaolian(plian);
	printf("lian冒泡排序：");
	showlian(plian);
	xuanzelian(plian);
	printf("lian选择排序：");
	showlian(plian);
	weichalian(pliana,0);
	weichalian(pliana,1);
	weichalian(pliana,2);
	weichalian(pliana,3);
	weichalian(pliana,4);
	weichalian(pliana,5);
	printf("尾插：0、1、2、3、4、5
");
	showlian(pliana);
	daozhilian(pliana);
	printf("倒置：");
	showlian(pliana);
	fu = zhaozhlian(pliana);
	printf("pliana中间：%d
",fu->data);
	fu = zhaoalian(pliana,2);
	printf("pliana倒数第二个值：%d
",fu->data);
	hui(&plian);
	printf("lian = %p
",plian);
	hui(&pliana);
	printf("liana = %p
",pliana);
	return 0;
}

lian.h文件

#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#include
#include
typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *pnext;
}Node_t;
//创建链表
extern Node_t *chuanglian(void);
//插入值（头插）
extern int chalian(Node_t *ptou,datatype data);
//打印链表
extern void showlian(Node_t *ptou);
//删除值
extern int shanlian(Node_t *ptou,datatype a);
//查找值
extern Node_t *zhaolian(Node_t *ptou,datatype a);
//修改值
extern int gailian(Node_t *ptou,datatype jiu,datatype xin);
//插入值（尾插）
extern int weichalian(Node_t *ptou,datatype data);
//销毁链表
extern void hui(Node_t **pptou);
//找中间值
extern Node_t *zhaozhlian(Node_t *ptou);
//找倒数第a个值
extern Node_t *zhaoalian(Node_t *ptou,int a);
//倒置链表
extern void daozhilian(Node_t *ptou);
//冒泡排序
extern int maopaolian(Node_t *ptou);
//选择排序
extern int xuanzelian(Node_t *ptou);
#endif