深圳网站seo优化公司,手机网站关键词快速排名,建立多多少钱,农资销售网站建设方案文章目录 前言双向链表链表头结点的创建节点尾插与尾删节点头插与头删特定位置插入或删除节点链表节点查找双向链表的销毁 链表的打印 前言
假期时间因为为学校开学考试做准备所以一直没更新博客#xff0c;今天开始博客会陆续更新。
双向链表
之前我们说过了顺序表和单链表… 文章目录 前言双向链表链表头结点的创建节点尾插与尾删节点头插与头删特定位置插入或删除节点链表节点查找双向链表的销毁 链表的打印 前言
假期时间因为为学校开学考试做准备所以一直没更新博客今天开始博客会陆续更新。
双向链表
之前我们说过了顺序表和单链表这次介绍双向链表双向链表在使用上要比单链表简单结构比单链表复杂一些需要两个指针域其结构如下图其中头结点数据域不动不要存放指针长度一类因为有时候我们不确定链表节点数据类型如果是char类型而节点数大于128那么就会出现bug带有头结点可方便对其操作。
双向链表节点代码如下
typedef int LTDataType;
typedef struct ListNode {struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;与单链表相同无非是双向链表的增删改查。
链表头结点的创建
ListNode* ListCreate()
{ListNode* head (ListNode*)malloc(sizeof(ListNode));head-next head;head-prev head;return head;
}这里别忘了是双向链表要给两个指针都赋值因为是头结点PS头结点数据域一般是垃圾值所以就指向自己。
节点尾插与尾删
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListNode* tail pHead-prev;ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;tail-next newnode;newnode-prev tail;newnode-next pHead;pHead-prev newnode;
}这里就体现出双向链表的优势我们不用遍历就可以直接找到链表的尾结点。
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{ListNode* tail pHead-prev;ListNode* TailPrev tail-prev;free(tail);TailPrev-next pHead;pHead-prev TailPrev;
}尾插时不要忘了让节点指向头结点。
节点头插与头删
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;newnode-next pHead-next;pHead-next-prev newnode;pHead-next newnode;newnode-prev pHead;
}这里注意哈链表的头插与头删是在头结点之后位置进行这里例出一幅头插图作为参考艺术细胞为0后续可能解锁画图软件这里先凑合看。
// 双向链表头删
void ListPopFront(ListNode* pHead)
{ListNode* cur (ListNode*)malloc(sizeof(ListNode));cur pHead-next;pHead-next cur-next;cur-next-prev pHead;free(cur);
}头插和头删要注意顺序否则可能找不到头结点的下一个节点。
特定位置插入或删除节点
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-data x;newnode-next pos;newnode-prev pos-prev;pos-prev-next newnode;pos-prev newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);
}这里还是注意一下代码顺序无其他重点。
链表节点查找
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x)return cur;cur cur-next;}return pHead;
}若最后没有找到该数值则返回头结点。
双向链表的销毁
// 双向链表销毁
void ListDestory(ListNode* pHead)
{ListNode* newhead pHead-next;ListNode* cur newhead-next;while (cur-next!pHead){free(newhead);newhead cur;cur newhead-next;}free(pHead);pHead NULL;
}这里别忘了最后删除并置空头结点置空头结点的原因是使用者在主函数还有头结点的地址但此时头结点已被释放野指针若再次调用头结点则可能出现bug。
链表的打印
// 双向链表打印
void ListPrint(ListNode* pHead)
{ListNode* newnode pHead-next;while (newnode!pHead){printf(%d , newnode-next-data);newnode newnode-next;}
}比较简单不做赘述。 双向链表许多函数的while循环是判断其节点是否与头结点相等而不是其节点是否为空这里要注意与单链表区分最后代码其实还应该加上断言assert函数判断是否为空但博主这里没有加是故意的还是不小心的。 这里纯粹是懒得加了这个习惯不是很好大家不要学我最好还是自己加一下。 最后期待你的三连若有错误欢迎私信或评论区指出。
