亚洲最新永久在线观看,家庭优化大师下载,工信部网站备案怎么登录,网站主题 模板一单向链表的插入排序
void insertion_sort_link(link_t* plink)
{ // 如果链表头为空#xff0c;直接返回 if(NULL plink-phead) { return; } // 初始化指针#xff0c;p指向当前已排序部分的最后一个节点 node_t* p plink-phead; // ptemp指向待插入的…一单向链表的插入排序
void insertion_sort_link(link_t* plink)
{ // 如果链表头为空直接返回 if(NULL plink-phead) { return; } // 初始化指针p指向当前已排序部分的最后一个节点 node_t* p plink-phead; // ptemp指向待插入的下一个节点 node_t* ptemp plink-phead-pnext; // 将当前已排序部分的最后一个节点的下一个指针设为NULL p-pnext NULL; node_t* pinsert NULL; // 用于指向待插入的节点 // 遍历待插入的节点 while(ptemp) { pinsert ptemp; // 将待插入节点指向ptemp ptemp ptemp-pnext; // 移动ptemp到下一个节点 // 如果待插入节点的值小于当前已排序部分的头节点的值 if(pinsert-data p-data) { // 将待插入节点插入到链表头部 pinsert-pnext plink-phead; plink-phead pinsert; } else { // 找到待插入节点应该插入的位置 while(p-pnext ! NULL p-pnext-data pinsert-data) { p p-pnext; // 移动p到下一个节点 } // 插入待插入节点 pinsert-pnext p-pnext; // 将待插入节点的下一个指针指向p的下一个节点 p-pnext pinsert; // 将p的下一个指针指向待插入节点 } } return; // 排序完成返回
}
快慢指针
快慢指针是一种常用的算法技巧通常用于链表中以解决一些特定的问题比如寻找链表的中间节点、检测链表是否有环等。以下是快慢指针的基本概念和示例代码。
概念
慢指针slow pointer每次移动一步。快指针fast pointer每次移动两步。
通过这种方式快指针和慢指针的相对速度可以帮助我们在链表中找到特定的节点或判断某些条件。
示例寻找链表的倒数第K个节点
node_t * countdown_k(link_t* plink, int key)
{ node_t *pfast plink-phead; // 快指针初始化为链表头 if (NULL pfast) { return NULL; // 如果链表为空返回NULL } node_t *pslow pfast; // 慢指针初始化为链表头 // 将快指针向前移动key个节点 for (int i 0; i key; i) { if (NULL pfast) { return NULL; // 如果在移动过程中快指针变为NULL返回NULL } pfast pfast-pnext; // 快指针移动到下一个节点 } // 同时移动快指针和慢指针直到快指针到达链表末尾 while (pfast) { pfast pfast-pnext; // 快指针移动到下一个节点 pslow pslow-pnext; // 慢指针也移动到下一个节点 } // 当快指针到达链表末尾时慢指针指向的就是倒数第key个节点 return pslow; // 返回倒数第key个节点
} 二、双向链表
双向链表是一种链表数据结构其中每个节点都有两个指针一个指向下一个节点next另一个指向前一个节点prev。这种结构使得在链表中进行插入和删除操作更加灵活因为可以在 O(1) 的时间复杂度内访问前一个节点。
链表结构
typedef struct node
{ datatype data; // 节点存储的数据 struct node *ppre; // 指向前一个节点的指针 struct node *pnext; // 指向下一个节点的指针
} dnode_t;
双向链表和单向链表的区别
双向链表和单向链表是两种常见的数据结构它们在结构、操作和使用场景上有显著的区别。以下是它们的主要区别和适用场景
1. 结构区别 单向链表: 每个节点包含两个部分数据部分和指向下一个节点的指针next。只能从头到尾遍历链表无法反向遍历。 双向链表: 每个节点包含三个部分数据部分、指向下一个节点的指针next和指向前一个节点的指针prev。可以从头到尾和从尾到头双向遍历。
2. 操作区别 插入和删除: 单向链表: 在插入或删除节点时需要找到前一个节点需要遍历操作相对复杂。双向链表: 可以直接访问前一个节点插入和删除操作更为高效。 内存使用: 单向链表: 每个节点只需存储一个指针内存占用较小。双向链表: 每个节点需要存储两个指针内存占用较大。
3. 使用场景 单向链表: 适用于只需要单向遍历的场景如实现简单的队列、栈等。当内存使用是一个重要考虑因素时单向链表更为合适。 双向链表: 适用于需要频繁插入和删除操作的场景如实现双向队列、LRU缓存等。当需要频繁反向遍历链表时双向链表更为高效。
4. 性能比较
时间复杂度: 插入和删除操作在单向链表中通常需要O(n)的时间复杂度需要遍历找到前一个节点而在双向链表中可以在O(1)的时间内完成直接访问前后节点。空间复杂度: 单向链表的空间复杂度为O(n)双向链表的空间复杂度也是O(n)但由于双向链表每个节点需要额外的指针实际内存占用更高。
双向链表的基本操作
// 创建双向链表
dlink_t* create_dlink() { dlink_t * dlink malloc(sizeof(dlink_t)); // 分配内存 if (NULL dlink) { return NULL; // 内存分配失败 } dlink-phead NULL; // 初始化头指针为空 dlink-clen 0; // 初始化节点计数为0 pthread_mutex_init((dlink-mutex), NULL); // 初始化互斥锁 return dlink; // 返回新创建的链表
} // 检查链表是否为空
int is_empty_dlink(dlink_t * pdlink) { return NULL pdlink-phead; // 如果头指针为空则链表为空
} // 在链表头部插入节点
int push_into_dlink_head(dlink_t* pdlink, datatype data) { dnode_t * pnode malloc(sizeof(dnode_t)); // 分配新节点内存 if (NULL pnode) { return -1; // 内存分配失败 } pnode-data data; // 设置节点数据 pnode-ppre NULL; // 新节点的前指针为空 pnode-pnext NULL; // 新节点的后指针为空 if (is_empty_dlink(pdlink)) { // 如果链表为空 pdlink-phead pnode; // 将新节点设置为头节点 } else { // 如果链表不为空 pnode-pnext pdlink-phead; // 新节点的后指针指向当前头节点 pdlink-phead-ppre pnode; // 当前头节点的前指针指向新节点 pdlink-phead pnode; // 更新头指针为新节点 } pdlink-clen; // 增加节点计数 return 0; // 插入成功
} // 打印链表
int print_link(dlink_t * pdlink, int dir) { dnode_t* p pdlink-phead; // 从头节点开始 if (NULL p) { return -1; // 如果链表为空返回错误 } if (dir) { // 正向打印 while (p) { printf(id:%d,name:%s,score:%d\n, p-data.id, p-data.name, p-data.score); // 打印节点数据 p p-pnext; // 移动到下一个节点 } printf(\n); } else { // 反向打印 while (p-pnext) { p p-pnext; // 移动到最后一个节点 } while (p) { printf(id: %d,name: %s,score: %d\n, p-data.id, p-data.name, p-data.score); // 打印节点数据 p p-ppre; // 移动到前一个节点 } printf(\n); } return 0; // 打印成功
} // 在链表尾部插入节点
int push_into_dlink_tail(dlink_t* pdlink, datatype data) { if (is_empty_dlink(pdlink)) { // 如果链表为空 push_into_dlink_head(pdlink, data); // 直接在头部插入 return 0; // 插入成功 } dnode_t* p pdlink-phead; // 从头节点开始 dnode_t* pnode malloc(sizeof(dnode_t)); // 分配新节点内存 pnode-data data; // 设置节点数据 pnode-ppre NULL; // 新节点的前指针为空 pnode-pnext NULL; // 新节点的后指针为空 if (NULL pnode) { return -1; // 内存分配失败 } while (p-pnext) { // 找到最后一个节点 p p-pnext; } pnode-ppre p; // 新节点的前指针指向最后一个节点 p-pnext pnode; // 最后一个节点的后指针指向新节点 pdlink-clen; // 增加节点计数 return 0; // 插入成功
} // 从链表头部删除节点
int pop_into_dlink_head(dlink_t* pdlink) { if (is_empty_dlink(pdlink)) { return -1; // 如果链表为空返回错误 } dnode_t* p pdlink-phead; // 获取头节点 pdlink-phead pdlink-phead-pnext; // 更新头指针为下一个节点 free(p); // 释放头节点内存 pdlink-clen--; // 减少节点计数 if (pdlink-phead NULL) { return 0; // 如果链表变为空返回成功 } if (pdlink-phead-pnext) { pdlink-phead-ppre NULL; // 更新新头节点的前指针为空 } return 0; // 删除成功
} // 从链表尾部删除节点
int pop_into_dlink_tail(dlink_t* pdlink) { if (is_empty_dlink(pdlink)) { return -1; // 如果链表为空返回错误 } dnode_t* p pdlink-phead; // 从头节点开始 while (p-pnext) { // 找到最后一个节点 p p-pnext; } if (p-ppre NULL) { // 如果只有一个节点 free(p); // 释放节点内存 pdlink-clen--; // 减少节点计数 pdlink-phead NULL; // 更新头指针为空 return 0; // 删除成功 } p-ppre-pnext NULL; // 更新倒数第二个节点的后指针为空 free(p); // 释放最后一个节点内存 pdlink-clen--; // 减少节点计数 return 0; // 删除成功
} // 根据名称搜索节点
dnode_t* search_into_dlink(dlink_t* pdlink, char * name) { if (is_empty_dlink(pdlink)) { return NULL; // 如果链表为空返回NULL } dnode_t* p pdlink-phead; // 从头节点开始 while (p) { if (strcmp(p-data.name, name) 0) { // 如果找到匹配的名称 return p; // 返回找到的节点 } p p-pnext; // 移动到下一个节点 } return NULL; // 未找到匹配的节点
} // 修改节点数据
int change_dlink_node(dlink_t* pdlink, char *name, int dstscore) { if (is_empty_dlink(pdlink)) { return -1; // 如果链表为空返回错误 } dnode_t* p pdlink-phead; // 从头节点开始 while (p) { if (strcmp(p-data.name, name) 0) { // 如果找到匹配的名称 p-data.score dstscore; // 更新节点的分数 } p p-pnext; // 移动到下一个节点 } return 0; // 修改成功
} // 销毁链表
int destory_dlink(dlink_t* pdlink) { while (pdlink-phead) { pop_into_dlink_head(pdlink); // 逐个删除头节点 } print_link(pdlink, 1); // 打印链表此时应为空 free(pdlink); // 释放链表结构体内存 return 0; // 销毁成功
}
