嵌入式Day18--数据结构

1.数据结构的概念

定义

程序 == 数据结构 + 算法

数据结构：描述数据存储和操作的结构

算法：操作数据对象的方法

2.代码的质量和效率的衡量指标

时间复杂度

数据量的增长与程序运行时间的增长所呈现的比例函数关系，为时间渐进复杂函数，即时间复杂度

​​数据量越大，程序跑得越慢，时间复杂度用来衡量慢的增长程度

O(1)：定程序运行时间与数据量无关，无论输入多大，执行时间基本恒定

O(logn)：运行时间随数据量增长而增长，但增长非常缓慢，经过一定数据量大后趋于平缓

O(n)：运行时间与数据量成正比

O(2^n)：运行时间随数据量呈指数级增长

O(nlogn) O(n^2) O(n^3)

空间复杂度

数据的增长与程序占据空间的增长所呈现的比例函数关系，称为空间复杂度

数据量越大，程序占用的内存越多，空间复杂度用来衡量内存占用的增长趋势

3.分类

3.1逻辑结构

线性结构：表 （一对一）

非线性结构：树（一对多）、图（多对多）

3.2存储结构

顺序存储 链式存储 散列存储 索引存储

3.3常见的数据结构

顺序表 链式表

顺序栈 链式栈

顺序队列 链式队列

邻接表 邻接矩阵

二叉树

4.链表

4.1定义

4.2链表的相关操作

4.2.1定义节点类型

//存储的数据类型 typedef int Datatype_t; //链表结点类型 typedef struct node { Datatype_t data;//链表数据域 struct node* pnext;//链表指针域 }Node_t; //链表对象类型 typedef struct link { Node_t* phead;//链表头结点地址 int clen;//链表当前结点个数 }Link_t;

通过结构体定义链表节点的类型

其中数据 data 定义为 datatype_t，通过再次定义 int 为 datatype_t结点需要修改类型的地方

其中指向下一结点地址 pnext 定义为指针类型，通过指针链接各个结点

4.2.2创建空链表

空链表指链表中不储存实际数据的标点，可以视为头结点，头结点的下一个是真实的第一个数据

空链表可以让后续插入、删除、遍历等操作简便统一，不需要处理链表为空的情况

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; }

• malloc 申请空结点空间
• data 不需要赋值（最好赋值），空白节点不存放数据，主要为了保证链表操作的便利性
• pnext 赋值为 NULL，表示该节点为最后一个节点尾结点
• 返回节点地址

4.2.3插入数据

头插法插入数据

头插法是在链表开头，即第一个有效数字前的位置插入新结点，使其成为新的头结点指向

插入第一个数据和插入中间数据本质一致，其都为将上一节点指向的地址存为新节点指向的地址，只是第一次插入数据的上一节点为空链表，指向为空，而自己本身成为尾结点（插入后自己指向为空）

int insert_link_head(Link_t* plink, Datatype_t data) { Node_t* pnode = malloc(sizeof(Node_t)); if (NULL == pnode) { printf("malloc error\n"); return -1; } pnode->data = data; pnode->pnext = NULL; pnode->pnext = plink->phead; plink->phead = pnode; plink->clen++; return 0; }

• 申请新结点空间
• 将需要插入的数据存放到空间中
• 将上一结点指向的地址存放到空间指向的地址，即下一结点的地址
• 将上一结点指向的地址更新为新结点的地址

尾插法插入数据

尾插法是​​在链表的末尾插入新结点​​。

尾插法保持原有节点顺序不变，新结点成为链表的最后一个元素，即尾结点

int insert_link_tail(Link_t* plink, Datatype_t data) { Node_t* pnode = malloc(sizeof(Node_t)); if (NULL == pnode) { printf("malloc error\n"); return -1; } pnode->data = data; pnode->pnext = NULL; if (is_empty_link(plink)) { plink->phead = pnode; } else { Node_t* ptmp = plink->phead; while (ptmp->pnext != NULL) { ptmp = ptmp->pnext; } ptmp->pnext = pnode; } plink->clen++; return 0; }

尾插法需要在头插法存入数据之前，将前一个结点指向尾结点再开始存入数据

通过遍历改变指针完成到达尾结点，遍历判断条件为 p->next 更便于找到尾结点

4.2.4遍历链表

int bianli_link(Link_t* plink) { Node_t* ptmp = plink->phead; while (NULL != ptmp) { printf("data is %d\n", ptmp->data); ptmp = ptmp->pnext; } printf("\n"); return 0; }

4.2.5删除数据

头删法删除数据

int delete_link_head(Link_t* plink) { if (is_empty_link(plink)) { return 0; } Node_t* pfree = plink->phead; plink->phead = pfree->pnext; free(pfree); plink->clen--; return 0; }

尾删法删除数据

int delete_link_tail(Link_t* plink) { if (is_empty_link(plink)) { return 0; } else if (1 == plink->clen) { delete_link_head(plink); } else { Node_t* pfree = plink->phead; while (pfree->pnext->pnext != NULL) { pfree = pfree->pnext; } free(pfree->pnext); pfree->pnext = NULL; plink->clen--; } return 0; }

在删除链表时还有其他情况需要考虑在内，即删除时链表是否为空，所以我们应该在删除时先判断一下链表是否为空

int is_empty_link(Link_t* plink) { if (NULL == plink->phead) { return 1; } return 0; }

4.2.6销毁链表

void destroy_link(Link_t* plink) { while(!is_empty_link(plink)) { delete_link_head(plink); } free(plink); }

4.2.7查找链表

查找链表中某一个结点

Node_t *find_link_node(Link_t* plink,Datatype_t data) { if(is_empty_link(plink)) { return NULL; } Node_t* ptmp=plink->phead; while(ptmp!=NULL) { if(ptmp->data == data) { return ptmp; } ptmp=ptmp->pnext; } return NULL; }

查找链表的中间结点

Node_t *find_mid_node(Link_t *plink) { if (is_empty_link(plink)) { return NULL; } Node_t *pfast = plink->phead; Node_t *pslow = pfast; while (pfast != NULL) { pfast = pfast->pnext; if (NULL == pfast) { break; } pfast = pfast->pnext; pslow = pslow->pnext; } return pslow; }

此处使用了快慢指针法，快指针的速度是慢指针的两倍，当快指针遍历完链表之后，慢指针的位置即为中间结点的位置。

查找链表倒数第K个结点

Node_t *find_k_node(Link_t* plink,int k) { if(is_empty_link(plink)) { return NULL; } Node_t* pfast=plink->phead; Node_t* pslow=pfast; for(int i=0;i<k;i++) { if(NULL == pfast) { return NULL; } pfast=pfast->pnext; } while(pfast!=NULL) { pfast=pfast->pnext; pslow=pslow->pnext; } return pslow; }

此处原理类似于查找链表的中间结点，快指针先走K步，然后快指针和慢指针以相同的速度遍历链表，当快指针遍历完链表后，慢指针所处的位置即为链表倒数第K个结点的位置。

4.2.8修改链表某一个结点的值

int change_link(Link_t *plink, Datatype_t new, Datatype_t old) { Node_t *ptmp = NULL; ptmp = find_link_node(plink, old); if (ptmp != NULL) { ptmp->data = new; return 0; } return -1; }

4.2.9链表的倒置

void reverse_link(Link_t* plink) { if(is_empty_link(plink)) { return ; } Node_t* pinsert=NULL; Node_t* ptmp=plink->phead; plink->phead=NULL; while(ptmp!= NULL) { pinsert=ptmp; ptmp=ptmp->pnext; pinsert->pnext=plink->phead; plink->phead=pinsert; } return ; }

4.2.10链表的排序

此处选择的是插入排序的算法

void sort_link_insert(Link_t* plink) { if(is_empty_link(plink) || 1 == plink->clen) { return ; } Node_t* pinsert=NULL; Node_t* ptmp=plink->phead->pnext; plink->phead->pnext=NULL; while(ptmp!=NULL) { pinsert=ptmp; ptmp=ptmp->pnext; if(pinsert->data<=plink->phead->data) { pinsert->pnext=plink->phead; plink->phead=pinsert; } else { Node_t* p=plink->phead; while(p->pnext!=NULL && p->pnext->data<pinsert->data) { p=p->pnext; } pinsert->pnext=p->pnext; p->pnext=pinsert; } } }

4.2.11判断链表是否有环

int is_loop_link(Link_t* plink) { Node_t* pfast=plink->phead; Node_t* pslow=pfast; while(pfast!=NULL) { pfast=pfast->pnext; if(NULL == pfast) { return 0; } pfast=pfast->pnext; pslow=pslow->pnext; if(pslow == pfast) { return 1; } } return 0; }