链表Linklist操作

发布时间:2023年12月20日

单项链表操作

有头单向链表的函数操作

创建一个空链表:只有一个头节点,指针域赋值为空指针。

在指定位置插入:

在指定位置删除:

1)创建一个新的头节点

//创建一个空的有头单项链表
link_node_t *createEmptyLinkList()
{
    //1.创建节点,作为连表的头节点。
    link_list_t?h?= (link_list_t)malloc(sizeof(link_node_t));
    if (NULL ==?h)
    {
        perror("createEmptyLinkList?malloc?err");
        return NULL;
    }
    //2.初始化
????h->next?= NULL;
    return?h;
}

2)计算链表长度

//计算链表长度
int lengthLinkList(link_node_t *p)
{
    int?len?= 0;
    while (p->next?!= NULL)
    {
????????p?=?p->next;
????????len++;
    }
    return?len;
}

3)单项链表在指定位置插入数据

//单项链表在指定位置插入数据
//p是链表头指针,post是插入位置(从0开始),data插入的数据。
//思想:先记录插入位置的前一个节点。然后先连后面再连前面。
int insertIntoPostLinkList(link_node_t *p, int?post,?datatype?data)
{
    int?i;
    link_list_t?pnew?= NULL;
    //1.容错处理
    if (post?< 0 ||?post?> lengthLinkList(p))
    {
        printf("insertIntoPostLinkList?err");
        return -1;
    }
    //2.将头指针p移动到插入得前一个位置
    for (i?= 0;?i?<?post;?i++)
        {
????????p?=?p->next;
        }
    //3.创建一个新节点,保存插入数据
????pnew?= (link_list_t)malloc(sizeof(link_node_t));
    if (pnew?== NULL)//判断开辟成功
    {
        perror("insertIntoPostLinkList?pnew?malloc?err");
        return -1;
    }
????????pnew->data?=?data;
????????pnew->next?= NULL;
    //4.将新节点插入到链表,先连后面,再连前面。
????????pnew->next?=?p->next;
????????p->next?=?pnew;
    return 0;
}

4)遍历有头单项链表

//遍历单向链表
void showLinkList(link_node_t *p)
{
    while (p->next?!= NULL)
    {
????????p?=?p->next;
        printf("%d?",?p->data);
    }
    printf("\n");
}

  1. 判断链表为空

//判断链表是否为空,为空返回1,非空返回0
int isEmptyLinkList(link_node_t *p)
{
    return?p->next?== NULL;
}

6)删除单向链表中指定位置的数据?post?代表的是删除的位置

//?删除单向链表中指定位置的数据?post?代表的是删除的位置
int deletePostLinkList(link_node_t *p, int?post)
{
    int?i;
    link_list_t?pdel?= NULL;
    //1.容错判断
    if (post?< 0 ||?post?>= lengthLinkList(p) || isEmptyLinkList(p))
    {
        printf("deletePostLinkList?err");
        return -1;
    }
    //2.将头指针移动到要删除节点的前一个位置
    for (i?= 0;?i?<?post;?i++)
????????p?=?p->next;
    //3.删除操作
    //(1)用指针pdel记录要删除节点
????pdel?=?p->next;
    //(2)跨过要删除节点
????p->next?=?pdel->next;
    //(3)释放被删除节点
    free(pdel);
????pdel?= NULL;
    return 0;
}

7)清空链表

//清空链表
//思想:循环删除头节点得下一个节点,直到链表为空。
//?(1)定义一个pdel,指向被删除节点
//?(2)跨过被删除节点
//?(3)让p指向要被删除节点
//?(4)释放被删除节点
void clearLinkList(link_node_t *p)
{
    link_list_t?pdel?= NULL;
    while (p->next?!= NULL)
    {
????????pdel?=?p->next; //每次删除得都是头节点的下一个节点
????????p->next?=?pdel->next;
        free(pdel);
????????pdel?= NULL;
    }
}

8)查找指定数据出现的位置?data被查找的数据

//查找指定数据出现的位置?data被查找的数据
int searchDataLinkList(link_node_t *p,?datatype?data)
{
    int?post?= 0;           //记录查找位置
    while (p->next?!= NULL) //遍历有头链表
    {
????????p?=?p->next;
        if (p->data?==?data)
            return?post;
????????post++;
    }
    return -1;
}

9)修改链表中指定位置的数据

//修改链表中指定位置的数据
int changePostLinkList(link_node_t *p, int?post,?datatype?data)
{
    int?i;
    //1.容错判断
    if (post?< 0 ||?post?>= lengthLinkList(p))
    {
        printf("changePostLinkList?err\n");
        return -1;
    }
    //2.将头指针移动到要修改的位置
    for (i?= 0;?i?<=?post;?i++)
????????p?=?p->next;
    //3.修改数据
????p->data?=?data;
    return 0;
}

10)删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除

//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//思想:p始终指向被删除节点的前一个节点,q从头节点的下一个节点开始遍历,相当于遍历无头链表。pdel始终指向被删除的节点。
int deleteDataLinkList(link_node_t *p,?datatype?data)
{
    link_list_t?pdel?= NULL; //用于指向被删除的节点
    //1.定义一个指针q,指向头节点的下一个节点,此时q可以看作遍历无头链表。
    link_list_t?q?=?p->next;
    //2.让q来遍历无头链表,让每一个节点中数据域都与传进来的data做比较,如果相同就删除,如果不同就继续向后遍历
    while (q?!= NULL)
    {
        if (q->data?==?data) //判断q所指节点中的数据域是否和data一致,如果一致就删除。否则向后移动。
        {
            //(1)将pdel指向被删除节点
????????????pdel?=?q;
            //(2)跨过被删除节点
????????????p->next?=?pdel->next;
            //(3)释放被删除节点
            free(pdel);
????????????pdel?= NULL;
            //(4)让q指向此时p的下一个节点,也就是之前删除的节点的下一个节点
????????????q?=?p->next;
        }
        else
        {
????????????p?=?p->next; //将p指针向后移动一个单位
????????????q?=?p->next; //始终保持p指向q的前一个节点
        }
    }
}

11)链表转置

//?链表转置?
//?解题思想:
//?1)将头节点与当前链表断开,断开前保存下头节点的下一个节点,保证后面链表能找得到,定义一个q保存头节点的下一个节点,断开后前面相当于一个空的链表,后面是一个无头的单向链表。
//?2)遍历无头链表的所有节点,将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)。
void reverseLinkList(link_node_t *p)
{
    link_list_t?temp=NULL; //用来临时保存q节点的下一个节点
    //1.断开前,用q保存头节点得下一个节点,用作遍历无头链表。
    link_list_t?q?=?p->next;
    //2.将头节点和链表断开
????p->next?= NULL;
    //3.遍历无头链表,用头插法将遍历的节点插入头节点后面。
    while (q?!= NULL)
    {
        //(1)提前将q所指节点得下一个节点用temp保存
????????temp?=?q->next;
        //(2)先连后面,再连前面,插入头节点后面。
????????q->next?=?p->next;
????????p->next?=?q; //执行完这样代码后,q无法再找到下一个节点,所以需要在此行执行之前将q的下一个节点的地址提前保存起来
        //(3)将q移动,指向temp保存得位置。
????????q?=?temp;
    }
}

操作综合代码

#include?<stdio.h>
#include?<stdlib.h>
typedef int?datatype;
typedef struct node
{
????datatype?data;     //数据域,用来存放数据。
    struct node *next; //指针域,用来存放下一个节点的地址。
} link_node_t, *link_list_t;

//创建一个空的有头单项链表
link_node_t *createEmptyLinkList()
{
    //1.创建节点,作为连表的头节点。
    link_list_t?h?= (link_list_t)malloc(sizeof(link_node_t));
    if (NULL ==?h)
    {
        perror("createEmptyLinkList?malloc?err");
        return NULL;
    }
    //2.初始化
????h->next?= NULL;
    return?h;
}

//计算链表长度
int lengthLinkList(link_node_t *p)
{
    int?len?= 0;
    while (p->next?!= NULL)
    {
????????p?=?p->next;
????????len++;
    }
    return?len;
}

//单项链表在指定位置插入数据
//p是链表头指针,post是插入位置(从0开始),data插入的数据。
//思想:先记录插入位置的前一个节点。然后先连后面再连前面。
int insertIntoPostLinkList(link_node_t *p, int?post,?datatype?data)
{
    int?i;
    link_list_t?pnew?= NULL;
    //1.容错处理
    if (post?< 0 ||?post?> lengthLinkList(p))
    {
        printf("insertIntoPostLinkList?err");
        return -1;
    }
    //2.将头指针p移动到插入得前一个位置
    for (i?= 0;?i?<?post;?i++)
        {
????????p?=?p->next;
        }
    //3.创建一个新节点,保存插入数据
????pnew?= (link_list_t)malloc(sizeof(link_node_t));
    if (pnew?== NULL)//判断开辟成功
    {
        perror("insertIntoPostLinkList?pnew?malloc?err");
        return -1;
    }
????????pnew->data?=?data;
????????pnew->next?= NULL;
    //4.将新节点插入到链表,先连后面,再连前面。
????????pnew->next?=?p->next;
????????p->next?=?pnew;
    return 0;
}

//遍历单向链表
void showLinkList(link_node_t *p)
{
    while (p->next?!= NULL)
    {
????????p?=?p->next;
        printf("%d?",?p->data);
    }
    printf("\n");
}

//判断链表是否为空,为空返回1,非空返回0
int isEmptyLinkList(link_node_t *p)
{
    return?p->next?== NULL;
}

//?删除单向链表中指定位置的数据?post?代表的是删除的位置
int deletePostLinkList(link_node_t *p, int?post)
{
    int?i;
    link_list_t?pdel?= NULL;
    //1.容错判断
    if (post?< 0 ||?post?>= lengthLinkList(p) || isEmptyLinkList(p))
    {
        printf("deletePostLinkList?err");
        return -1;
    }
    //2.将头指针移动到要删除节点的前一个位置
    for (i?= 0;?i?<?post;?i++)
????????p?=?p->next;
    //3.删除操作
    //(1)用指针pdel记录要删除节点
????pdel?=?p->next;
    //(2)跨过要删除节点
????p->next?=?pdel->next;
    //(3)释放被删除节点
    free(pdel);
????pdel?= NULL;
    return 0;
}

//清空链表
//思想:循环删除头节点得下一个节点,直到链表为空。
//?(1)定义一个pdel,指向被删除节点
//?(2)跨过被删除节点
//?(3)让p指向要被删除节点
//?(4)释放被删除节点
void clearLinkList(link_node_t *p)
{
    link_list_t?pdel?= NULL;
    while (p->next?!= NULL)
    {
????????pdel?=?p->next; //每次删除得都是头节点的下一个节点
????????p->next?=?pdel->next;
        free(pdel);
????????pdel?= NULL;
    }
}

//查找指定数据出现的位置?data被查找的数据
int searchDataLinkList(link_node_t *p,?datatype?data)
{
    int?post?= 0;           //记录查找位置
    while (p->next?!= NULL) //遍历有头链表
    {
????????p?=?p->next;
        if (p->data?==?data)
            return?post;
????????post++;
    }
    return -1;
}

//修改链表中指定位置的数据
int changePostLinkList(link_node_t *p, int?post,?datatype?data)
{
    int?i;
    //1.容错判断
    if (post?< 0 ||?post?>= lengthLinkList(p))
    {
        printf("changePostLinkList?err\n");
        return -1;
    }
    //2.将头指针移动到要修改的位置
    for (i?= 0;?i?<=?post;?i++)
????????p?=?p->next;
    //3.修改数据
????p->data?=?data;
    return 0;
}

//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//思想:p始终指向被删除节点的前一个节点,q从头节点的下一个节点开始遍历,相当于遍历无头链表。pdel始终指向被删除的节点。
int deleteDataLinkList(link_node_t *p,?datatype?data)
{
    link_list_t?pdel?= NULL; //用于指向被删除的节点
    //1.定义一个指针q,指向头节点的下一个节点,此时q可以看作遍历无头链表。
    link_list_t?q?=?p->next;
    //2.让q来遍历无头链表,让每一个节点中数据域都与传进来的data做比较,如果相同就删除,如果不同就继续向后遍历
    while (q?!= NULL)
    {
        if (q->data?==?data) //判断q所指节点中的数据域是否和data一致,如果一致就删除。否则向后移动。
        {
            //(1)将pdel指向被删除节点
????????????pdel?=?q;
            //(2)跨过被删除节点
????????????p->next?=?pdel->next;
            //(3)释放被删除节点
            free(pdel);
????????????pdel?= NULL;
            //(4)让q指向此时p的下一个节点,也就是之前删除的节点的下一个节点
????????????q?=?p->next;
        }
        else
        {
????????????p?=?p->next; //将p指针向后移动一个单位
????????????q?=?p->next; //始终保持p指向q的前一个节点
        }
    }
}

//?链表转置?
//?解题思想:
//?1)将头节点与当前链表断开,断开前保存下头节点的下一个节点,保证后面链表能找得到,定义一个q保存头节点的下一个节点,断开后前面相当于一个空的链表,后面是一个无头的单向链表。
//?2)遍历无头链表的所有节点,将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)。
void reverseLinkList(link_node_t *p)
{
    link_list_t?temp=NULL; //用来临时保存q节点的下一个节点
    //1.断开前,用q保存头节点得下一个节点,用作遍历无头链表。
    link_list_t?q?=?p->next;
    //2.将头节点和链表断开
????p->next?= NULL;
    //3.遍历无头链表,用头插法将遍历的节点插入头节点后面。
    while (q?!= NULL)
    {
        //(1)提前将q所指节点得下一个节点用temp保存
????????temp?=?q->next;
        //(2)先连后面,再连前面,插入头节点后面。
????????q->next?=?p->next;
????????p->next?=?q; //执行完这样代码后,q无法再找到下一个节点,所以需要在此行执行之前将q的下一个节点的地址提前保存起来
        //(3)将q移动,指向temp保存得位置。
????????q?=?temp;
    }
}

int main(int?argc, char const *argv[])
{
    link_list_t?p?= createEmptyLinkList();
    insertIntoPostLinkList(p, 0, 1);
    insertIntoPostLinkList(p, 1, 2);
    insertIntoPostLinkList(p, 2, 3);
    insertIntoPostLinkList(p, 3, 4);
    insertIntoPostLinkList(p, 4, 2);
    reverseLinkList(p);
    showLinkList(p);
    deletePostLinkList(p, 2);
    showLinkList(p);
    printf("len=%d\n", lengthLinkList(p));
    deleteDataLinkList(p, 2);
    showLinkList(p);
    printf("1?post?is:%d\n", searchDataLinkList(p, 1));
    return 0;
}

链表合并

递增有序的链表A 1 3 5 7 9 10

递增有序的链表B 2 4 5 8 11 15

新链表:1 2 3 4 5 5 7 8 9 10 11 15

将链表AB合并,形成一个递增有序的新链表

 link_list_t?ptail?=?pa;//将ptail永远指向新链表的尾巴,此时把pa头节点当做新链表的头
    link_list_t?h?=?pa;//记录链表pa的头节点地址,用于查看每轮节点合并情况
	pa?=?pa->next;//跨过头结点,pa相当于无头表的头指针
	pb?=?pb->next;//跨过头结点,pb相当于无头表的头指针
	//同时遍历pa和pb
	while(pa?!= NULL &&?pb?!= NULL)//相当于遍历无头
	{
        //判断两个链表内节点数据的大小
		if(pa->data?<?pb->data)
		{
			ptail->next?=?pa;//pa节点小,将pa节点链接到新链表尾
			pa?=?pa->next;//继续遍历pa表,pa指向下一个节点,用于下一轮比较以及合并
			ptail?=?ptail->next;//继续将尾指针指向新链表的尾巴
            printf("A段\n");//确定输出的段
            Show(pa);//输出合并后pa段剩余的节点
            Show(ptail);//输出pa合并的节点及剩余的节点
            Show(h);//输出新列表
            puts("?");
		}
		else//pa->data?>=?pb->data
		{
			ptail->next?=?pb;//pb节点小,将pb节点链接到新表尾?
			pb?=?pb->next; //继续遍历pb表,pb指向下一个节点,用于下一轮比较以及合并
			ptail?=?ptail->next;//继续让ptail指向新表的尾
            printf("B段\n");//确定输出的段
            Show(pb);//输出合并后pb段剩余的节点
            Show(ptail);//输出pb合并的节点及剩余的节点
            Show(h);//输出新列表
            puts("?");
        }
	}
	//循环结束后,有可能pa先全部遍历完,也有可能是pb表,剩余的链表赋到新链表后面
    //剩余链表可能没有排序
	if(pa?== NULL)//pa遍历没了,pb有剩余
		ptail->next?=?pb;//将剩余的pb接在新表的尾?
	else
		ptail->next?=?pa;//将圣墟的pa接在新表的尾

单向循环链表

单向循环链表:约瑟夫环问题,是一个经典的循环链表问题,题意是:已知?n?个人(分别用编号?1,2,3,…,n?表示)围坐在一张圆桌周围,从编号为?k?的人开始顺时针报数,数到?m?的那个人出列;他的下一个人又从?1?开始,还是顺时针开始报数,数到?m?的那个人又出列;依次重复下去,直到圆桌上剩余一个人。

用解决约瑟夫环问题进行杀猴子:

思想:用头指针移动到要杀的猴子的前一个,然后跨过指向猴子的节点。

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

typedef struct node_t
{
	int?data;
	struct node_t *next;
}link_node_t,*link_list_t;

int main(int?argc, const char *argv[])
{
	int?i;
	link_list_t?pdel?= NULL;//用于指向被删除节点
	link_list_t?ptail?= NULL;//永远指向当前链表的尾?
	link_list_t?pnew?= NULL;//永远指向新创建的节点
	link_list_t?h?= NULL;
	int?all_num?= 7;//猴子总数?
	int?start_num?= 2; //从几号猴子开始数
	int?kill_num?= 3;//数到几杀死猴
	printf("请您入猴子总数?起始号码?数到几杀死:\n");
	scanf("%d%d%d",&all_num,&start_num,&kill_num);
	//1.创建出一个单向循环链表
	//(1)创建有all_num个节点的单向链表
	h?= (link_list_t)malloc(sizeof(link_node_t));
	if(NULL ==?h)
	{
		perror("malloc?failed");
		return -1;
	}
	h->data?= 1;
	h->next?= NULL;
	ptail?=?h;//尾指针指向当前的第一个节点
	for(i?= 2;?i?<=?all_num;?i++)
	{
		//创建新的节点
		pnew?= (link_list_t)malloc(sizeof(link_node_t));
		if(NULL ==?pnew)
		{
			perror("malloc?failed");
			return -1;
		}
		//将新节点装上数据
		pnew->data?=?i;
		pnew->next?= NULL;
		//将新节点链接到链表尾?
		ptail->next?=?pnew;//链接到链表的尾
		ptail?=?pnew;//尾指针继续指向当前链表的尾?
	}
	//(2)将头指针保存到链表的尾形成单向循环链表
	ptail->next?=?h;//形成单向循环链表?
#if?0?//用于调试程序
	while(1)
	{
		printf("%d\n",h->data);
		h?=?h->next;
		sleep(1);
	}
#endif
	//2.开始杀猴子?
	//(1)将头指针移动到开始猴子的号码处?
	for(i?= 1;?i?<?start_num;?i++)
		h?=?h->next;
        printf("start?:%d\n",h->data);
	//(2)循环进行杀猴子
	while(h?!=?h->next)//条件不成的时候,就剩一个猴子,只有一个节点
	{
		//将头指针移动到即将删除节点的前一个节点
		for(i?= 1;?i?<?kill_num-1;?i++)
			h?=?h->next;

		pdel?=?h->next;
		//跨过删除节点
		h->next?=?pdel->next;
		printf("kill?is?-------------%d\n",pdel->data);
		free(pdel);
		pdel?= NULL;
		//杀死猴子猴,从下一个节点开始继续开始数,将头指针移动到开始数的地方
		h?=?h->next;
	}
	printf("king?is===================?%d\n",h->data);
	return 0;
}	


结构体嵌套法杀猴子

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

typedef int?datatype;
typedef struct node_t
{
	datatype?data;
	struct node_t *?prior;
	struct node_t *?next;
}link_node_t,*link_list_t;

typedef struct doublelinklist
{
	link_list_t?head;
	link_list_t?tail;
}double_node_t,*double_list_t;


int main(int?argc, const char *argv[])
{
	int?i;
	int?all_num?= 8;//猴子总数
	int?start_num?= 3;//从3号猴子开始数
	int?kill_num?= 3;//数到几杀死猴子?
	link_list_t?h?= NULL;
	link_list_t?pdel?= NULL;//用来指向被杀死猴子的节点
	printf("请您输入猴子的总数,开始号码,出局号码:\n");
	scanf("%d%d%d",&all_num,&start_num,&kill_num);
	//1.创建一个双向的循环链表
	double_list_t?p?= (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针
	if(NULL ==?p)
	{
		perror("malloc?failed");
		return -1;
	}
	p->head?=?p->tail?= (link_list_t)malloc(sizeof(link_node_t));
	if(NULL ==?p->tail)
	{
		perror("p->tail?malloc?failed");
		return -1;
	}
	p->head->data?= 1;
	p->head->prior?= NULL;
	p->head->next?= NULL;
	//将创建n个新的节点,链接到链表的尾
	for(i?= 2;?i?<=?all_num;?i++)
	{
		link_list_t?pnew?= (link_list_t)malloc(sizeof(link_node_t));
		if(NULL ==?pnew)
		{
			perror("pnew?malloc?failed");
			return -1;
		}
		pnew->data?=?i;
		pnew->prior?= NULL;
		pnew->next?= NULL;
		//(1)将新的节点链接到链表的尾
		p->tail->next?=?pnew;
		pnew->prior?=?p->tail;
		//(2)尾指针向后移动,指向当前链表的尾
		p->tail?=?pnew;
	}
	//(3)形成双向循环链表?
	p->tail->next?=?p->head;
	p->head->prior?=?p->tail;
	//调试程序?
#if?0
	while(1)
	{
		printf("%d\n",p->head->data);
		p->head?=?p->head->next;
		sleep(1);
	}
#endif
	//2.循环进行杀死猴子
	h?=?p->head;
	//(1)先将h移动到start_num处,也就是开始数数的猴子号码处
	for(i?= 0;?i?<?start_num-1;?i++)
		h?=?h->next;
	while(h->next?!=?h)//当h->next?==?h?就剩一个节点了,循环结束
	{
		//(2)将h移动到即将杀死猴子号码的位置
		for(i?= 0;?i?<?kill_num-1;?i++)
			h?=?h->next;
		//(3)进行杀死猴子,经过上面的循环后,此时的h指向即将杀死的猴子
		h->prior->next?=?h->next;
		h->next->prior?=?h->prior;
		pdel?=?h;//pdel指向被杀死猴子的位置
		printf("kill?is?-------%d\n",pdel->data);
		h?=?h->next;//需要移动,从杀死猴子后的下一个位置开始数
		free(pdel);
	}
	printf("猴王是%d\n",h->data);
	return 0;
}	

总结:顺序表和单向链表比较

  1. 顺序表在内存当中连续存储的(数组),但是链表在内存当中是不连续存储的,通过指针将数据链接在一起。
  2. 顺序表的长度是固定的,但是链表长度不固定
  3. ?顺序表查找方便,但是插入和删除效率低,链表,插入和删除方便,查找效率低。

文章来源:https://blog.csdn.net/m0_74937538/article/details/132773183
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。