1.头文件中的声明:
首先我们需要写一个结构体,双向带头链表的话需要一个前驱指针prev和一个后驱指针next,前驱指针的作用是方便找尾节点,因为头节点的prev指向的就是最后一个节点,后驱指针next的作用是方便插入和找头节点。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; typedef struct Listnode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; LTNode* BuyLTNode(LTDataType x);//创建节点 LTNode* LTInit();//初始化 void LTPrint(LTNode* phead);//打印 void LTPushBack(LTNode* phead, LTDataType x);//尾插 void LTPopBack(LTNode* phead);//尾删 void LTPushFront(LTNode* phead, LTDataType x);//头插 void LTPopFront(LTNode* phead);//头删 int LTSize(LTNode* phead);//求有效数据 LTNode* LTFind(LTNode* phead, LTDataType x); void LTInsert(LTNode* pos ,LTDataType x);//在pos位置之前插入x void LTErase(LTNode* pos);//在pos位置删除 void LTDestroy(LTNode* phead);
2.带头双向链表的实现
2.1创建新节点
创建一个节点比较简单,首先malloc一块空间出来,然后将这个结构体的数据data设置成需要的数据,再将前驱指针和后驱指针全部置空就行,方便后续链接。
LTNode* BuyLTNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
2.2链表初始化
双向带头链表的初始化肯定需要一个头节点,所以使用BuyLTNode创建一个头节点phead,然后将phead的next指向自己,prev也指向自己。
LTNode* LTInit() { LTNode* phead = BuyLTNode(0); phead->next = phead; phead->prev = phead; return phead; }
2.3打印链表
打印链表也很简单,只需要创建一个结构体指针cur来遍历链表就可以了,循环的结束条件是cur为phead,为什么呢?因为尾节点的next不为NULL,而是头指针,如果条件设置为NULL的话,就会陷入死循环,所以当cur走到头节点的话就代表已经遍历完一遍了。
void LTPrint(LTNode* phead) { LTNode* cur = phead->next; printf("phead"); while (cur != phead) { printf("<->%d", cur->data); cur = cur->next; } printf("\n"); }
2.4尾插
假设当前节点是这样的情况,我们要插入一个newnode,怎么尾插呢?这个时候我们就通过头节点phead找到尾节点n3,然后再尾插就可以了。首先定义一个结构体指针tail来找n3,然后将newnode进行链接,首先将newnode与tail进行链接,newnode->prev=tail,tail->next=newnode,再将newnode与phead进行链接,phead->prev=newnode,newnode->next=phead,然后newnode就在这个链表上完成尾插了。
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* tail = phead->prev; LTNode* newnode = BuyLTNode(x); newnode->prev = tail; tail->next = newnode; newnode->next = phead; phead->prev = newnode; }
2.5尾删
尾删的话不仅要找到尾节点,还需要找到尾节点的前一个节点,所以创建一个尾节点tail,尾节点的前一个节点tailprev(tailprev=tail->prev),然后将tailprev与头节点进行链接,phead->prev=tailprev,tailprev->next=phead。
void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* pretail = tail->prev; phead->prev = pretail; pretail->next = phead; }
2.6头插
头插需要找到第一个节点,所以创建一个结构体指针tail指向第一个节点(tail=phead->next),然后将newnode与phead进行链接,phead->nedxt=newnode,newndoe->prev=phead,再将newnode与tail进行链接,newndoe->next=tail,tail->prev=newnode.
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = tail; tail->prev = newnode; }
2.7头删
头删需要找到第一个和第二个节点,所以定义一个结构体指针first来指向第一个节点,second指向第二个节点(second=first->next),然后将第二个节点和phead进行链接,phead->next=second,second->prev=phead,然后释放第一个节点的空间,free(first)。
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next!=phead); LTNode* first = phead->next; LTNode* second = first->next; phead->next =second; second->prev = phead; free(first); }
2.8有效数据
求出链表的有效数据个数就比较简单了,遍历的时候size++就行了。
int LTSize(LTNode* phead) { assert(phead); int size = 0; LTNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; printf("\n"); }
2.9寻找节点
寻找节点也比较简单,在遍历链表的时候判断当前节点的data是否等于x即可。
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; }
2.10在pos位置之前插入x
这里需找到pos和pos前一个节点,所以创建一个结构体指针posprev指向pos的前一个节点(posprev=pos->prev),然后将newnode与posprev进行链接,posprev->next=newnode,newnoe->prev=posprev,再将newnode与pos进行链接,pos->prev=newnode,newnode->next=pos。
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); LTNode* prepos = pos->prev; newnode->next = pos; pos->prev = newnode; newnode->prev = prepos; prepos->next = newnode; }
将这个函数完成之后就可以对头插与尾插进行简化了。
尾插:
这里大家需要了解一下为什么第一个参数是phead,因为LTInsert这个函数是实现pos位置之前的插入,当我们需要尾插,那么尾巴的后一个节点是什么呢?不就是头节点吗!!
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
头插:
头插就比较好理解了,第一个参数就是头节点的下一个节点。
1. void LTPushFront(LTNode* phead, LTDataType x) 2. { 3. assert(phead); 4. 5. LTInsert(phead->next, x); 6. }
2.11删除pos位置的节点
删除pos位置需要找到pos的前一个节点和后一个节点,所以创建一个结构体指针posprev保存pos的前一个节点(posprev=pos->prev),再创建一个结构体指针保存pos的后一个节点(posnext=pos->next),然后将posprev与posnext进行链接,posprev->next=posnext,posnext->prev=posprev,然后free掉pos。
void LTErase(LTNode* pos) { assert(pos); LTNode* posNext = pos->next; LTNode* posPrev = pos->prev; free(pos); posNext->prev = posPrev; posPrev->next = posNext; }
将这个函数完成之后就可以对头删与尾删进行简化了。
头删:
1. void LTPopFront(LTNode* phead) 2. { 3. assert(phead); 4. assert(phead->next!=phead); 5. 6. LTErase(phead->next); 7. }
尾删:
尾节点通过头节点phead的前驱指针来找就好了。
1. void LTPopBack(LTNode* phead) 2. { 3. assert(phead); 4. assert(phead->next != phead); 5. 6. LTErase(phead->prev); 7. }
2.12销毁
销毁链表还是和单链表一样,区别就是循环结束条件是cur走到头节点,还有就是保存cur的后一个节点,最后还要free掉头节点,因为没有走到头节点。
void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }