数据结构 - 链表

线性表的链式存储结构

概念

将线性表 L = (a0, a1, … , an-1)中各元素分布在存储器的不同存储块,成为结点,通过地址或指针建立元素之间的联系。
在这里插入图片描述
结点的 data 域存放数据元素 ai ,而 next 域是一个指针指向 ai 的直接后继 ai+1 所在的结点

  • 下图中的首元结点(头结点) A 的 data 不重要next 域指向链表的真正的第一个结点头结点的作用也是为了指明哪个结点是链表的第一个结点。

  • 最后一个结点的 next 域,也就是下图中最后一个结点的那个 ^ 代表的是 NULL

在这里插入图片描述

结点类型描述

typedef struct node
{
	data_t data; //结点的数据域
	struct node *next; //结点的后继指针域
}listnode, *linklist;

则有:

listnode A;
linklist p = &A;

结点声明

在这里插入图片描述
设 P 指向链表中结点 ai
在这里插入图片描述
获取 ai,写作:p->data
获取 ai+1,写作:p->next->data

若指针 p 的值为 NULL,则它不指向任何结点,此时 p->datap->next 是非法操作。

可调用 C 语言中 malloc() 函数向系统申请结点的存储空间:

linklist p;
p = (linklist)malloc(sizeof(listnode));

则创建一个类型为 linklist 的结点,且该结点的地址已存入指针变量 p 中。文章来源地址https://www.uudwc.com/A/PmvmX/

建立单链表

  • 目标:建立单链表
  • 思路:
    1、给头结点分配空间然后判空
    2、初始化头结点(H->data,H->next)
    3、返回头结点
  • 代码:
linklist list_create()
{
	linklist H; //头结点

	//分配空间并判空
	if ((H = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc H failed!\n");
		return NULL;
	}
	
	//初始化头结点
	H->data = 0;
	H->next = NULL;
	
	//返回头结点
	return H;
}

链表尾部插入节点

  • 目标:向单链表的尾部插入新的节点
  • 思路:
    1、建立新节点,给新节点分配空间并初始化
    2、定义指针指示插入节点的位置,这个位置的 next 为空,这样才能在 next 插入新节点,才能保证在链表的结尾插入节点 (从 H 开始,通过 q=q->next 遍历链表直到链表尾部
    3、在指针的 next 插入新节点
  • 代码:
int list_insert_tail(linklist H, data_t value)
{
	linklist p; //要插入的新节点 
	linklist q; //确定插入位置的指针

	//如果头结点为空那么以后的操作也没办法进行
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return -1;
	}

	//给新节点分配空间并判空
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc p failed!\n");
		return -1;
	}
	
	//初始化新节点
	p->data = 0;
	p->next = value;

	q = H;
	//确定插入节点的位置
	while (q->next)
    {
    	q = q->next;
    }

    //在链表尾部插入节点
    q->next = p;

	return 0;
}

根据下标查找节点

  • 目标:根据位置获取链表中的节点
  • 思路:
    1、判头结点是否为空,判下标是否合法;
    2、定义遍历链表的指针和 i 遍历链表直到找到指定位置(注意遍历完链表也没有找到指定节点的情况);
    3、返回要查找的节点或空节点(未找到的情况)
  • 代码:
linklist list_get(linklist H, int pos)
{
	linklist p; //遍历用指针
	int i; //遍历用标记
	
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return NULL;
	}

	if (pos < 0)
	{
		printf("pos is invalid\n");
		return NULL;
	}

	p = H;
	i = -1;
	while (i < pos)
	{
		p = p->next; //指针p向下移动
		//已经遍历完链表但没找到这个位置则break
		if (p == NULL)
		{
			break;
		}
		i++; //i迭代
	}

	return p;
}

在链表指定位置插入新节点

  • 目标:给定链表、位置和新节点的值将这个新节点插入到链表的指定位置
  • 思路:
    1、判头节点是否为空,位置是否合法(初步)
    2、通过指针和 i 遍历链表找到这个要插入节点的前一个节点的位置,让指针指向这个节点
    3、通过改变指针指向插入这个新节点
  • 代码:
int list_insert_between(linklist H, data_t value, int pos)
{
	linklist p; //遍历用指针
	linklist q; //新节点
	int i;
	
	//如果头结点为空那么以后的操作也没办法进行
	if (H == NULL)
	{
		printf("H is NULL!\n");
		return -1;
	}

	//这种位置无效
	if (pos < -1)
	{
		printf("H is invalid!\n");
		return -1;
	}

	//给新节点分配空间并判空
	if ((q = (linklist)malloc(sizeof(listnode))) == NULL)
	{
		printf("malloc p failed!\n");
		return -1;
	}
 	
 	//初始化新节点
 	q->next = NULL;
 	q->data = value;

	//p从头结点开始遍历
	p = H;
	while (i < pos - 1) //注意这里是 pos - 1,一定要在循环结束时让指针指向指定位置的前一个节点
	{
		p = p->next;
		//i还没到pos指针指向节点就空了,证明给定的位置无效
		if (p == NULL)
	    {
	    	printf("the pos not found!\n");
	    	return -1;
	    }
	    i++;
	 }
		
	//此时指针指向指定位置的前一个节点,通过改变指针指向插入新节点
	q->next = p->next;
	p->next = q;

	return 0;
}	

打印链表

  • 目标:打印链表节点
  • 思路:通过指针遍历链表并打印
  • 代码:
int list_show(linklist H) {
    linklist p;
 
    if (H == NULL) {
        printf("H is NULL\n");
        return -1;
    }
 
    p = H;
 
    while (p->next != NULL) {
        printf("%d ", p->next->data);
        p = p->next;
    }
    puts("");
 
    return 0;
}

原文地址:https://blog.csdn.net/qq_44947439/article/details/132794468

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月26日 15:14
如何在Proteus进行STM32F103C8T6模拟以及keil5开发
下一篇 2023年09月26日 15:14