做网站的地方,河南省干部任免最新公示,西安网站建设培训班,小程序快速搭建1. 双向链表的结构 注意#xff1a;这里的“带头”跟单链表的“头结点”是两个概念#xff0c;实际上在单链表阶段称呼不太严谨#xff0c;但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点#xff0c;实际为“哨兵位”#xff0c;哨兵位结点不存储任何有…1. 双向链表的结构 注意这里的“带头”跟单链表的“头结点”是两个概念实际上在单链表阶段称呼不太严谨但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这里“放哨的”。
“哨兵位”存在的意义
遍历循环链表避免死循环。
2. 双向链表的实现
2.1 双向链表结构体
typedef int LTDataType;
// 定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
2.2 申请结点
// 申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next node-prev node;return node;
}
2.3 初始化
// 初始化
void LTInit(LTNode** pphead)
{// 给链表创建一个哨兵位*pphead LTBuyNode(-1);
}
2.4 链表的销毁
// 销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}// 此时pcur指向phead而phead还没有被销毁free(phead);phead NULL;
}
2.5 链表的打印
// 打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
2.6 链表的尾插
// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode LTBuyNode(x);// 旧的尾结点就是phead-prev// 先让新的尾结点的前指针指向旧的尾结点newNode-prev phead-prev;newNode-next phead; // 再让新的尾结点的下一级指针指向头结点哨兵位// 旧的尾结点下一级指针指向新的尾结点phead-prev-next newNode;phead-prev newNode; // 再让头结点哨兵位的下一级指针指向新的尾结点
}
2.7 链表的头插
// 头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode LTBuyNode(x);// 要改变的结点phead newNode phead-nextnewNode-next phead-next; // 先让新的尾结点的下一级指针指向头结点的下一级指针的结点newNode-prev phead; // 让新的尾结点的前指针指向头结点//phead-next-prev newNode; // 指向头结点的下一级指针的结点的下一级指针指向新的结点//phead-next newNode; // 头结点的下一级指针指向新的结点// 这样也是可行的phead-next newNode; // 头结点的下一级指针指向新的结点newNode-next-prev newNode; // 指向头结点的下一级指针的结点的下一级指针指向新的结点}
2.8 链表的尾删
// 尾删
void LTPopBack(LTNode* phead)
{// 链表必须有效且链表不能为空只有一个哨兵位assert(phead phead-next ! phead);LTNode* del phead-prev;// 影响的指针phead del-prev deldel-prev-next phead;phead-prev del-prev;// 删除del节点free(del);del NULL;
}
2.9 链表的头删
// 头删
void LTPopFront(LTNode* phead)
{// 链表必须有效且链表不能为空只有一个哨兵位assert(phead phead-next ! phead);LTNode* del phead-next;// 影响的指针phead del del-nextphead-next del-next;del-next-prev phead;// 删除del节点free(del);del NULL;
}
2.10 链表查找数据
// 查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}// 没有找到return NULL;
}
2.11 在pos位置之后插入数据
// 在 pos 位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode LTBuyNode(x);// 影响的指针pos newNode pos-nextnewNode-next pos-next;newNode-prev pos;pos-next-prev newNode;pos-next newNode;
}
2.12 删除pos结点
// 删除 pos节点
void LTErase(LTNode* pos)
{// pos理论上来说不能为phead但是没有参数phead无法增加校验assert(pos);// 影响的指针pos-prev pos pos-nextpos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}
