数据结构 链表3

双向链表头删与单向链表相比需要额外处理前驱指针int insert_doulink_head(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { pnode-pnext pdlink-phead; pdlink-phead-ppre pnode; pdlink-phead pnode; } pdlink-clen; return 0; }双向链表尾删与单向链表相比单向链表需要通过遍历找到倒数第二个节点。必须找到前驱才能修改其pnextint insert_doulink_end(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { DNode_t *pend pdlink-phead; while (NULL ! pend-pnext) { pend pend-pnext; } pend-pnext pnode; pnode-ppre pend; } pdlink-clen; return 0; }查找数据DNode_t *find_node_by_data(DLink_t *pdlink,DataType_t data) { DNode_t *pnode pdlink-phead; while (NULL ! pnode) { if (pnode-data.iddata.id) { return pnode; } pnode pnode-pnext; } return NULL; }修改数据int modify_node_by_value(DLink_t *pdlink, DataType_t old_value, DataType_t new_value) { if (NULL pdlink) { return -1; } if (is_empty_dlink(pdlink)) { return -2; } DNode_t *pnode pdlink-phead; while (NULL ! pnode) { if (pnode-data.id old_value.id) //在C语言中结构体不能直接使用 进行比较 { pnode-data new_value; printf(Modified: %d - %d\n, old_value.id, new_value.id); return 0; } pnode pnode-pnext; } return 0; }销毁void destroy_doulink(DLink_t *pdlink) { while (!is_empty_dlink(pdlink)) { delete_doulink_head(pdlink); } free(pdlink); }删除某个节点注意多种情况某个节点位于头或尾的情况下的条件int delete_point_node(DLink_t *pdlink,char *name) { if(is_empty_dlink(pdlink)) { return -1; } DNode_t *ptmpNULL; ptmp find_node_by_data(pdlink, name); if(NULLptmp) { return -1; } if(NULLptmp-ppre) { delete_doulink_head(pdlink); } else if(NULLptmp-pnext) { delete_doulink_end(pdlink); } ptmp-ppre-pnextptmp-pnext; ptmp-pnext-ppreptmp-ppre; pdlink-clen--; return 0; }内核链表是一种通用链表把链表节点从具体业务数据中抽象了出来本质双向循环链表有头链表普通链表是把数据塞进链表节点内核链表是把链表节点塞进数据。offsetof(type, member)计算成员在结构体中的偏移量container_of宏——通过结构体成员的地址反推出整个结构体的起始地址栈栈是一种具有后进先出LIFO特性的内存区域是数据结构中一种线性存储结构由编译器自动管理。顺序栈空间连续链式栈:非连续空间链式栈链式栈Linked Stack采用链式存储结构的栈通过节点之间的链接关系实现后进先出LIFO的数据存取栈顶为链表的头节点插入和删除都在栈顶进行。