当前位置：首页 > java >正文

《嵌入式数据结构笔记（一）：数据结构导论与链表》

java 2025/8/7 12:56:47

1.数据结构定义与核心概念

数据结构的本质是数据在计算机中的组织与存储方式，其经典公式为：
程序 = 数据结构 + 算法

2.数据关系的逻辑结构分类

集合结构
数据元素之间仅属于同一集合，无其他明确关系。

线性结构
元素间为一对一关系，包括顺序表、链表、队列、栈等。

树形结构
元素间为一对多关系，典型代表为二叉树。

图形结构
元素间为多对多关系（网状结构）。

3.物理结构对比

顺序存储结构

使用连续内存空间存储数据。

访问时间复杂度为 O(1)。

插入/删除需移动大量数据，效率低。

需预分配内存，可能产生内存碎片。

链式存储结构

使用非连续内存空间，通过指针链接。

访问需遍历，时间复杂度为 O(n)。

插入/删除效率高，无需移动数据。

动态分配内存，灵活性高。

索引存储结构

通过索引表建立关键字与存储位置的映射。

散列存储结构

· 利用哈希函数直接计算存储位置。

4.常见数据结构内容

链式表

单向链表

双向链表

循环链表

内核链表

栈
后进先出（LIFO）结构，支持压栈（push）和弹栈（pop）操作。

队列
先进先出（FIFO）结构，支持入队（enqueue）和出队（dequeue）操作。

二叉树

每个节点最多有两个子节点。

包括二叉搜索树、平衡二叉树等变体。

哈希表

通过哈希函数实现快速查找。

需处理哈希冲突（如开放寻址法、链地址法）。

5.单向链表相关代码

1）创建链表对象

2）插入数据（头插，尾插），尾插要判断是否为空。

3）删除数据（头删，尾删），头删要判断是否为空链表，尾删需要判断是不是空链表和一个结点。

4）查找数据

5）修改数据

6）销毁链表，调用头删，free，最后要给plink置零。

link.h#ifndef _LINK_H
#define _LINK_H/*typedef定义了链表存储数据的类型*/
typedef int Data_type_t;/*节点类型*/
typedef struct node
{Data_type_t data;struct node *pnext;
}Node_t;//链表对象（类型，长度），指向第一个节点的指针
typedef struct link
{Node_t *phead;int clen;
}Link_t;//声明函数
extern Link_t *create_link();
extern int insert_link_head(Link_t *plink, Data_type_t data);
extern void link_for_each(Link_t *plink);
extern Node_t *find_link(Link_t *plink, Data_type_t mydata);
extern int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata);
extern int delete_head(Link_t *plink);
extern int insert_link_tail(Link_t *plink, Data_type_t mydata);
extern int delete_tail(Link_t *plink);
extern void destroyed(Link_t *plink);#endif

link.c#include<stdlib.h>
#include "link.h"
#include <stdio.h>//在堆上创建单向链表
Link_t *create_link()       
{Link_t *plink = malloc(sizeof(Link_t));if(NULL == plink){printf("malloc error!\n");return NULL;}plink->phead = NULL;plink->clen = 0;return plink;
}//单向链表头插
int insert_link_head(Link_t *plink, Data_type_t data)
{//申请结点Node_t *pnode = malloc(sizeof(Node_t));if(NULL == pnode){printf("malloc error!");return -1;}//第一步初始化结点pnode->data = data;pnode->pnext = NULL;//第二步插入结点pnode->pnext = plink->phead;plink->phead = pnode;plink->clen++;return 0;
}//遍历
void link_for_each(Link_t *plink)
{Node_t *ptmp = NULL;ptmp = plink -> phead;while(ptmp){printf("%d\n", ptmp -> data);ptmp = ptmp -> pnext;}
}//查找
Node_t *find_link(Link_t *plink, Data_type_t mydata)
{Node_t *ptmp = plink->phead;while(ptmp != NULL){if(ptmp->data !=  mydata){ptmp = ptmp -> pnext;}else{return ptmp;}}return NULL;
}//修改
int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata)
{Node_t *ptmp = find_link(plink, olddata);if(ptmp == NULL){return -1;}ptmp->data = newdata;return 1; 
}//删除
int delete_head(Link_t *plink)
{if(plink->phead == NULL){return -1;}Node_t *ptmp = plink->phead;plink->phead = ptmp->pnext;free(ptmp);plink->clen--;return 0;
}//尾插
int insert_link_tail(Link_t *plink, Data_type_t mydata)
{Node_t *ptmp = plink->phead;if(NULL == ptmp){ptmp->pnext = NULL;ptmp->data = mydata;}else{while(ptmp->pnext != NULL){ptmp = ptmp->pnext; }Node_t *pnode = malloc(sizeof(Node_t));if(NULL == pnode){printf("malloc error!");return -1;}pnode->pnext = NULL;pnode->data = mydata;ptmp->pnext = pnode;plink->clen++;}return 0;
}//尾删
int delete_tail(Link_t *plink)
{Node_t *ptmp = plink -> phead;if(NULL == ptmp){printf("空链表\n");return -1;}else if(NULL == ptmp->pnext){delete_head(plink);}else{while(NULL != ptmp->pnext->pnext){ptmp = ptmp->pnext;}free(ptmp->pnext);ptmp->pnext = NULL;plink->clen--;}return 0;
}
//销毁链表
void destroyed(Link_t *plink)
{while(NULL != plink->phead){delete_head(plink);}free(plink);plink = NULL;
}

main.c#include <stdio.h>
#include "link.h"int main(int argc, const char *argv[])
{
//创建结点Link_t *plink = create_link();if(NULL == plink){return -1;}
//插入数据（头插）insert_link_head(plink, 1);insert_link_head(plink, 2);insert_link_head(plink, 3);insert_link_head(plink, 4);insert_link_head(plink, 5);insert_link_head(plink, 6);
//遍历link_for_each(plink); Node_t *ret = find_link(plink, 4); if(ret){printf("%p\n", ret);printf("%d\n", ret -> data);}else{printf("error\n");}
//修改int t = change_link(plink, 1, 7);if(t == -1){printf("error\n");}else{printf("success\n");link_for_each(plink);}
//修改delete_head(plink);link_for_each(plink);//delete_head(plink);//link_for_each(plink);
//尾插    /*insert_link_tail(plink, 10);link_for_each(plink);puts("");
//尾删delete_tail(plink);link_for_each(plink);*/
//销毁链表destroyed(plink);return 0;
}

单向链表示意图