又来博客留下我的足迹了,哈哈哈,这次是对于双向链表的理解
目录
创建双向链表:
申请结点:
双向链表初始化:
双向链表插入结点:
双向链表删除结点:
双向链表的打印:
双向链表的查找:
双向链表的销毁:
结语:
在双向链表中有头双向循环,无头双向循环,有头双向不循环,无头双向不循环,而我将要介绍的是有头双向循环,别看名字长,其实就是只纸老虎,只要我们理解它的结构,问题自然迎刃而解了结构图如下:
创建双向链表:
从上面的结构图我们不然发现,我们创建需要定义什么指针域和数据域
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//指针域struct ListNode* next;//指针域LTDataType data;//数据域
}LTNode;
申请结点:
与单链表代码差不多,将其指针域置空,就不再过多赘述
LTNode* BuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;//赋值newnode->next = NULL;newnode->prev = NULL;return newnode;//返回创建的结点
}
双向链表初始化:
我们只需将自己连向自己,下一个指向上一个,上一个指向下一个,如图:
LTNode* LTInit()
{LTNode* phead = BuyNode(-1);//传空,为phead申请空间phead->next = phead->prev;phead->prev = phead->next;return phead;//返回头结点
}
双向链表插入结点:
头插:
我们先将新结点的后指针指向第一个结点的数据域,第一个结点的前指针指向新结点的数据域,新结点的前指针亦然,可能文字可能形容有点模糊,所以我们看下图:
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* Next = phead->next;//保存下一个结点的地址,防止丢失//新结点与后结点链接newnode->next = Next;Next->prev = newnode;//新结点与头节点链接newnode->prev = phead;phead->next = newnode;
}
温馨提示:如果没有保存下一个结点的地址,则需先跟后结点链接,在与头结点相连
尾插:
双链表尾插相对于单链表的尾插来说要容易许多,因为我们可以轻松找到尾,然后改变指针指向即可,如下图:
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);//创建新结点LTNode* tail = phead->prev;//找尾//尾结点与新结点相连newnode->prev = tail;tail->next = newnode;//新结点与头结点相连newnode->next = phead;phead->prev = newnode;
}
在指定位置插入:
我们通常会在指定位置之前插入,找到指定位置前一个,然后改变指针方向即可,如图:
void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);LTNode* front = pos->prev;//找到指定位置前一个结点//新结点与指定结点相连newnode->next = pos;pos->prev = newnode;//新节点与指定结点前一个结点相连front->next = newnode;newnode->prev = front;
}
双向链表删除结点:
头删:
我们先要判断链表是否为空,如果为空就不用删除了;因为之后要释放删除的结点,所以我们还需保存一下,这样就可以了
bool LTEmpty(LTNode* phead)
{return phead == phead->next;
}
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//判断链表是否为空LTNode* del = phead->next;LTNode* Next = phead->next->next;//第一结点的下一个结点与头结点相连Next->prev = phead;phead->next = Next;free(del);//释放掉这个结点del = NULL;
}
尾删:
尾删就比较容易了,将尾结点释放,然后改变指针指向,就这样完成了^ - ^
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead != phead->next);//或assert(!LTEmpty(phead))LTNode* tail = phead->prev;LTNode* Pretail = tail->prev;//头节点与尾结点的前一个结点相连Pretail->next = phead;phead->next = Pretail;free(tail);//释放尾结点tail = NULL;
}
在指定位置删除:
找到要删除结点的前一个和后一个,然后两个结点相互链接,这样就能够删除了,如图:
void LTErase(LTNode* phead, LTNode* pos)
{assert(phead);LTNode* front = pos->prev;//找到前结点LTNode* back = pos->next;//找到后结点//前结点和后结点相连front->next = back;back->prev = front;free(pos);//释放指定节点pos = NULL;
}
双向链表的打印:
提到打印,我们会用到遍历循环,那循环结束的标志是什么呢?有一个好主意,我们可以先从第一个结点开始打印,然后向后循环遍历,直至遍历到头结点,循环结束^_^,如下图:
void LTPrint(LTNode* phead)
{LTNode* begin = phead->next;while (begin != phead)//循环继续条件{printf("%d<=>", begin->data);begin = begin->next;}printf("\n");
}
双向链表的查找:
遍历一遍链表,然后找要查找的元素
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;//没找到
}
双向链表的销毁:
将动态申请的空间释放掉,并循环释放每一个结点,防止内存泄漏的风险
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;LTNode* next = cur->next;while (cur != phead){LTNode* next = cur->next;//防止找不到下一个结点free(cur);cur = next;}free(phead);//释放头结点
}
结语:
纸短情长,不尽依依,谢谢观看!