嵌入式（三）-----数据结构---单链表

嵌入式、数据结构、链表相关算法实现

别搞我了飞

320人浏览 · 2023-02-07 19:14:26

别搞我了飞 · 2023-02-07 19:14:26 发布

文章目录

前言

本文章是基于本人在学习嵌入式所做的简单的知识性总结以及相关练习。

链表

顺序表特点：
	优点：存储密度大，存取方便；
	      表的长度容易确定；
	缺点：
	     浪费空间，容易造成大量的空间碎片；
	     插入删除的时候需要大量移动元素，不方便；

链表：逻辑关系：线性；存储关系：链式存储；运算关系：增删改查，排序。

链表相关运算关系代码实现。

link_t *linklist_create();//创建单链表

link_t *linklist_create()

{
    link_t *head = (link_t *)malloc(sizeof(link_t));
    if(NULL == head)
    {
        return NULL;
    }
    head->data = -1;//数据域，头节点不存有效数值
    head->next =  NULL;//指针域,保存下一个节点的地址

    return head;
}

void linklist_show(link_t *head);//遍历链表

void linklist_show(link_t *head)
{
    if(NULL == head)
    {
        return ;
    }
    link_t *p = head->next;

    while(p != NULL)
    {
        printf("%d  ",p->data);
        p = p->next;
    }
    putchar('\n');
    return ;
}

int linklist_insert_pos(link_t *head,int pos,data_t data);//按照位置插入元素

int linklist_insert_pos(link_t *head,int pos,data_t data)
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    int len = linklist_get_length(head);//判断位置是否合法
    if(pos < 0 || pos > len)
    {
        return -1;
    }
                                                        //创建新节点   
    link_t *new = (link_t *)malloc(sizeof(link_t));
    if(NULL == new)
    {
        return -1;
    }
    new->data = data;
    link_t *p = head;
    for(int i = 0;i < pos;i++)
    {
        p = p->next;
    }                                 //寻找寻找插入前的一个节点
    new->next = p->next;       //插入
    p->next = new;
    return 0;
}

int linklist_get_length(link_t *head);//获取长度

int linklist_get_length(link_t *head)//判断链表长度，返回长度
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    int len = 0;
    link_t *p = head;

    while(p->next != NULL)//遍历一次元素，len自加一次
    {
        len++;
        p = p->next;

    }
    return len;
}

int linklist_delete_pos(link_t *head,int pos);//按照位置删除

int linklist_delete_pos(link_t *head,int pos)
{
    if(NULL == head)//判断链表是否存
    {
        return -1;
    }
    if(linklist_is_empty(head) == 0 )//判断表是否为空
    {
        return -1;
    }
    link_t *p = head;
    if(p< ||p>pos-1)
    {
    	return -1;
    }
    for(int i = 0;i < pos;i++)//寻找指定位置的上一个节点
    {
        p=p->next;
    }
    link_t *q=p->next;//删除指定节点
    p->next=q->next;
    free(q);
    q=NULL;
}

int linklist_is_empty(link_t *head);//判断链表是否为空

int linklist_is_empty(link_t *head)
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    return head->next == NULL;
}

link_t linklist_search_pos(link_t head,int pos);//按照位置查找

link_t *linklist_search_pos(link_t *head,int pos)//按照位置查找
{
    if(NULL == head)
    {
        return NULL;
    }
    int len=linklist_get_length(head);
    if(pos < 0 || pos > len-1)
    {
        return NULL;
    }
    link_t *p = head->next;
    for(int i = 0;i < pos;i++)
    {
        p = p->next;
    }
    return p;
}

link_t linklist_search_data(link_t head,data_t data);//按照数据查找

link_t *linklist_search_data(link_t *head,data_t data)//按照数据查找,返回位置
{
    if(NULL == head)//判断链表是否存在
    {
        return NULL;
    }
    link_t *p = head->next;
    while(p != NULL)
    {
        if(p->data == data)
        {
            return p;       
        }
        p=p->next;
    }
    return NULL;
    

}

int linklist_delete_data(link_t *head,data_t data);//按照数据删除

int linklist_delete_data(link_t *head,data_t data)//按照数据删除
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    link_t *p = head;//要找前节点，所以要从头开始（删除）
    while(p->next != NULL)
    {
        if(p->next->data == data)
        {
            link_t *q = p->next;
            p->next=q->next;
            free(q);
            q = NULL;
            return 0;
        }
        p = p->next;
    }
    return -1;

}

int linklist_update_pos(link_t *head,int pos,data_t data);//按照位置修改数据

int linklist_update_pos(link_t *head,int pos,data_t data)//按照位置修改数据
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    //查找元素
    link_t *p = linklist_search_pos(head,pos);
    if(NULL == p)
    {
        return -1;
    }
    p->data = data;
    return 0;

}

int linklist_update_data(link_t *head,data_t olddata,data_t newdata);//按照位置修改数据

int linklist_update_data(link_t *head,data_t olddata,data_t newdata)//按照位置修改数据
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    link_t *p = linklist_search_data(head,olddata);
    if(NULL == p)
    {
        return -1;
    }
    p->data = newdata;
    return 0;

}

int linklist_clear(link_t *head);//清空链表

int linklist_clear(link_t *head)//清空链表
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    while(head->next != NULL)
    {
        linklist_delete_pos(head,0);
    }
    return 0;

}

int linklist_destory(link_t **head);//摧毁链表

int linklist_destory(link_t **head)//摧毁链表
{
    if(NULL == *head)//判断链表是否存在
    {
        return -1;
    }
    linklist_clear(*head);
    free(*head);
    *head = NULL;
    return 0;

}

int linklist_revert(link_t *head);//倒置链表

int linklist_revert(link_t *head)//倒置链表
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    if(linklist_is_empty(head))
    {
        return -1;
    }
    link_t *p = head->next;
    head->next = NULL;
    link_t *q;
    while(p != NULL)
    {
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
    return 0;
}

int linklist_sort(link_t *head);//链表排序

int linklist_sort(link_t *head)//链表排序
{
    if(NULL == head)//判断链表是否存在
    {
        return -1;
    }
    if(linklist_is_empty(head))
    {
        return -1;
    }
	link_t *p = head->next;
	link_t *r = NULL, *q = NULL;
	head->next = NULL; //将链表断开
	while(p != NULL){
		r = head;//r始终在头结点
		q = p->next;//保存待插入节点的下一个节点
		while(r->next != NULL && r->next->data > p->data){//r->next != NULL 当插入第一个节点的时候，r->next == NULL,不需要进入循环。直接插入在r的后面;
			//r->next->data > p->data 时候说明从大到小排列，要插入的元素应该从后面放，所有r需要循环偏移.直到r->next->data < p->data的时候就插入在r的后面;
			r = r->next;
		}
		p->next = r->next;//将p插入在r的后面
		r->next = p;
		p = q;//将q保存的节点赋值给p，继续下一次循环;
	}
    return 0;

}

头文件代码

#ifndef _LINKLIST_H
#define _LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
typedef int data_t;
typedef struct node{

    data_t data;
    struct node *next;
}link_t;

link_t *linklist_create();//创建单链表
void linklist_show(link_t *head);//遍历链表
int linklist_insert_pos(link_t *head,int pos,data_t data);//按照位置插入元素
int linklist_get_length(link_t *head);//获取长度
int linklist_delete_pos(link_t *head,int pos);//按照位置删除
int linklist_is_empty(link_t *head);//判断链表是否为空
link_t *linklist_search_pos(link_t *head,int pos);//按照位置查找
link_t *linklist_search_data(link_t *head,data_t data);//按照数据查找
int linklist_delete_data(link_t *head,data_t data);//按照数据删除
int linklist_update_pos(link_t *head,int pos,data_t data);//按照位置修改数据
int linklist_update_data(link_t *head,data_t olddata,data_t newdata);//按照位置修改数据
int linklist_clear(link_t *head);//清空链表
int linklist_destory(link_t **head);//摧毁链表
int linklist_revert(link_t *head);//倒置链表
int linklist_sort(link_t *head);//链表排序




#endif

技术共进，成长同行——讯飞AI开发者社区

更多推荐

[深度学习]卷积神经网络

本实验基于Python和PyTorch框架比较了LeNet、AlexNet、VGG和ResNet四种经典CNN模型在FashionMNIST数据集上的表现，并重点研究了超参数调整对模型性能的影响。实验结果表明：1）对于所有模型，SGD优化器普遍比Adam表现更好；2）学习率在0.05左右时模型性能最佳；3）增加训练轮数可以提高准确率但会延长训练时间；4）批量大小对模型性能影响相对较小。此外，通过简

讯飞AI开发者社区

华为云Flexus+DeepSeek征文｜基于华为云Flexus云服务的Dify一键部署

讯飞AI开发者社区

基于嵌入式系统的智能宠物行为模式预测模型

这种设计使系统在持续运行72小时后仍保持98%的在线率（Table 1）。数据采集系统整合了六类传感器网络：运动传感器（加速度计+陀螺仪）、环境传感器（温湿度+光照）、生物传感器（心率+皮肤电）、视觉传感器（RGB摄像头）、音频传感器（麦克风阵列）和定位传感器（GPS+蓝牙信标）（Figure 1）。数据预处理采用三级流水线：原始数据经过滑动窗口截断（窗口长度5s）、小波变换去噪（db6小波基）和