数据结构

1. 内存泄漏
定义：内存泄漏是指程序在运行过程中动态分配的内存未被释放，导致可用内存逐渐减少，最终可能导致程序崩溃或系统性能下降。

原因：（1）忘记释放不再使用的内存。
（2）失去对动态分配内存的引用（例如，指针被覆盖或丢失）。
（3）循环引用。
解决方法：

(1)确保每次动态分配内存后都有相应的释放操作。
(2)使用智能指针来自动管理内存。
(3)使用内存分析工具（如 Valgrind）检测内存泄漏。
2. 内存碎片
定义：内存碎片是指在动态内存分配过程中，由于频繁的分配和释放操作，导致内存中出现许多小的、不可用的空闲块，从而降低了内存的使用效率。

类型：(1)外部碎片：指在内存中存在多个小的空闲块，无法满足大块内存的分配请求。
(2)内部碎片：指分配的内存块大于实际需要的内存，导致未使用的内存浪费。
解决方法：(1)使用合适的内存分配策略（如最佳适应、最差适应、首次适应等）。
(2)定期整理内存，合并相邻的空闲块。
(3)使用内存池等技术来减少频繁的分配和释放。
二、双向链表
1. 单向链表和双向链表的比较
特性   单向链表   双向链表
结构   每个节点包含数据和指向下一个节点的指针   每个节点包含数据、指向下一个节点和前一个节点的指针
遍历方向   只能从头到尾遍历   可以从头到尾和尾到头遍历
内存使用   较少，只有一个指针   较多，两个指针
插入和删除操作   在头部或尾部插入/删除较快，但在中间插入/删除需要遍历   在任意位置插入/删除都较快，尤其是在已知节点的情况下
实现复杂度   较简单   较复杂
2. 使用场景
单向链表：适用于只需要单向遍历的场景，如栈的实现、简单的队列等。
双向链表：适用于需要频繁插入和删除操作的场景，如浏览器的历史记录、音乐播放器的播放列表等。

3.单向链表的插入排序，快慢指针和链表倒置：

Link_Node_t *seek_counterback_node2(Link_t *plink,int k)//快慢指针法寻找倒数链表；
{if(plink->phead == NULL){return NULL;}else{Link_Node_t *p = plink->phead;Link_Node_t *p2 = p;for(int i = 0;i<k;++i){if(p==NULL){return NULL;}p = p->pnext;}while(p!=NULL){p = p->pnext;p2 = p2->pnext; }return p2;}
}int reversal_link(Link_t *plink) //链表倒置
{if(plink->phead == NULL){return -1;}Link_Node_t *pinsert = NULL;Link_Node_t *ptmp = plink->phead;plink->phead = NULL;while(ptmp!=NULL){pinsert = ptmp;ptmp = ptmp->pnext;pinsert->pnext = plink->phead;plink->phead = pinsert;}return 0;
}void sort_link(Link_t *plink)//插入排序
{Link_Node_t *ptmp = plink->phead->pnext;plink->phead->pnext = NULL;Link_Node_t *p = plink->phead;while(ptmp){Link_Node_t *pinsert = ptmp;ptmp = ptmp->pnext;if(pinsert->data <= plink->phead->data){pinsert->pnext = plink->phead;plink->phead = pinsert;}else{while(p->pnext != NULL && p->pnext->data < pinsert->data){p = p->pnext;}pinsert->pnext = p->pnext;p->pnext = pinsert;}}
}

4.双向链表（头插尾插，头删尾删，寻找，销毁）

DLink_t *doulink_create()
{DLink_t *doulink = (DLink_t *)malloc(sizeof(DLink_t));if(doulink == NULL){perror("doulink creat fail\n");return NULL;}doulink->clen = 0;doulink->phead = NULL;pthread_mutex_init(&doulink->mutex,NULL);return doulink;
}int push_doulink_head(DLink_t *doulink,DataType data)
{DLink_Node_t *pnode = (DLink_Node_t *)malloc(sizeof(DLink_Node_t));if (NULL == pnode){perror("fail malloc\n");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (doulink->phead == NULL){doulink->phead = pnode;}else{pnode->pnext = doulink->phead;doulink->phead->ppre = pnode;doulink->phead = pnode;}doulink->clen++;return 0;
}int push_doulink_tail(DLink_t *doulink,DataType data)
{DLink_Node_t *pnode = (DLink_Node_t *)malloc(sizeof(DLink_Node_t));if(NULL == pnode){perror("fail malloc\n");}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;DLink_Node_t *p = doulink->phead;if (doulink->phead == NULL){doulink->phead = pnode;}else{while(p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}doulink->clen++;}void traverse_link(DLink_t *doulink,int dir)//遍历
{   DLink_Node_t *p = doulink->phead;if(dir){while(p != NULL){printf("%d %s %d\n",p->data.id, p->data.name,p->data.score);p = p->pnext;}}else{while(p->pnext != NULL){p = p->pnext;}while(p != NULL){printf("%d %s %d\n",p->data.id, p->data.name,p->data.score);p = p->ppre;}}
}int pop_doulink_head(DLink_t *doulink)
{if(doulink->phead == NULL){return 0;}DLink_Node_t *p = doulink->phead->pnext;free(doulink->phead);if(p != NULL){p->ppre = NULL;}doulink->phead = p;doulink->clen--;return 1;
}int pop_doulink_tail(DLink_t *doulink)
{if(NULL == doulink->phead){return 0;}else if(doulink->phead->pnext == NULL){pop_doulink_head(doulink);}else{DLink_Node_t *p = doulink->phead;while(p->pnext->pnext != NULL){p = p->pnext;}free(p->pnext);p->pnext = NULL;doulink->clen--;return 1;}
}DLink_Node_t *seek_doulink_node(DLink_t *doulink,char *name)
{DLink_Node_t *p = doulink->phead;if(p == NULL){return NULL;}while(p != NULL){if(strcmp(p->data.name,name)==0){return p;}p = p->pnext;}return NULL;
}int change_doulink_node(DLink_t *doulink,char *name,int newscore)
{DLink_Node_t *p = doulink->phead;if(p==NULL){return -1;}while(p != NULL){if(strcmp(p->data.name,name)==0){p->data.score = newscore;}p = p->pnext;}return 0;
}int destory_link(DLink_t *doulink)//销毁链表
{ while (doulink->phead != NULL) { // 当链表不为空时  pop_doulink_head(doulink); // 逐个删除头节点  }  free(doulink); // 释放链表结构体  return 0; DLink_Node_t *p = doulink->phead;while(p != NULL){pop_doulink_head(doulink);}free(doulink);return 0;
}

数据 结构