旅游的便宜的网站建设,wordpress主题知乎,老版本hao123上网导航,WordPress 蜘蛛池我们先来看看带头双向循环链表的结构#xff1a;看到这里我们可能会产生一个想法#xff1a;这个链表看起来好复杂的样子#xff0c;是不是它的增删改查比单链表更难写呢#xff1f;嘿嘿#xff0c;还真的不是这样的#xff0c;双向链表的增删改查是很好写的哦#xff0…我们先来看看带头双向循环链表的结构看到这里我们可能会产生一个想法这个链表看起来好复杂的样子是不是它的增删改查比单链表更难写呢嘿嘿还真的不是这样的双向链表的增删改查是很好写的哦函数接口一览初阶数据结构我们学习的一般都是增删改查这四种操作// 2、带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* next;struct ListNode* prev;
} ListNode;
// 创建返回链表的头结点.
ListNode* BuyListNode(LTDataType x);
// 双向链表销毁
void ListDestory(ListNode* phead);
//双向链表的初始化
ListNode* ListInit();
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);2. 函数接口的实现2.1 ListNode* BuyListNode(LTDataType x)这个函数存在的意义和单链表中的BuyListNo的函数一样哈。因为在尾插头插指定位置插入都需要向堆区申请空间开辟节点所以我们把它封装成一个函数。参数x用来给新的节点赋初值。代表你要开辟节点的data是多少。//开辟新的节点
ListNode* BuyNewNode(LTDataType x)
{//malloc新的节点ListNode* newNode (ListNode*)malloc(sizeof(ListNode));//开辟失败退出程序if (newNode NULL){perror(BuyNewNode::malloc);exit(-1);}else{//初始化新的节点然后返回newNode-data x;newNode-prev NULL;newNode-next NULL;return newNode;}
}2.2 void ListDestory(ListNode* phead)因为链表的节点都是在堆区开辟的所以在使用完链表后需要将其释放。释放空间的方式就是遍历整个链表注意在释放一个节点时需要找到该节点的下一个节点否则会导致内存泄漏注意phead不可传入空指针因此需要对phead进行断言。这里的phead就是传说中的哨兵位的头结点好处在写完整个双向链表后就能够和好的理解啦哨兵位的头结点不存储任何数据的。你可以把他理解为一个很大的官他是不需要亲自上战场的负责指挥他的兵有了他他的兵能够更好的实现各种操作。或者你可以把他理解为王者荣耀中的辅助有了他才能更好的取得游戏的胜利。//销毁链表
void ListDestory(ListNode* phead)
{//断言pheadassert(phead);ListNode* cur phead-next;//遍历链表while (cur ! phead){//找到下一个节点ListNode* next cur - next;//释放节点free(cur);//记录下一个要释放的节点cur next;}//释放哨兵位的头结点free(phead);phead NULL;
}2.3 ListNode* ListInit()初始化链表的函数就是开辟一个节点让他作为哨兵位的头结点。然后让他的nextprev都指向自己。好处的话还需写代码的时候自己体会的哦这样做的目的其实就是为了是头插头删等操作统一化还记得单链表写头插头删函数时需要对特殊情况进行处理的痛苦吧//链表的初始化
ListNode* ListInit()
{//因为哨兵位的头节点是不需要存储数据的这个参数随便是啥都行ListNode* phead BuyNewNode(0);//prev,next均指向自己phead-next phead;phead-prev phead;//返回哨兵位的头结点return phead;
}2.4 void ListPrint(ListNode* phead)这个函数的实现也是很简单的哦我们只需要遍历链表然后打印数据即可同样不允许传入空指针不然会发生空指针的解引用哦这个不同于我们前面写过的单链表单链表传入空指针说明链表为空但这个双向链表经过初始化后就有一个哨兵位的头结点了链表为空说明phead -next phead或者phead-prev phead。双链表为空的情况//双向链表的打印
void ListPrint(ListNode* phead)
{//断言assert(phead);//如果是空链表可以打印一个空判断空链表的方法上面降到了//这里的话空链表就不做任何打印了ListNode* cur phead-next;while (cur ! phead){//用cur遍历双链表打印数据printf(%d , cur-data);cur cur-next;}printf(\n);
}2.5 void ListPushBack(ListNode* phead, LTDataType x)还记得单链表尾插的痛苦嘛需要对特殊情况进行处理我们来看看谁双向链表需不需要对特殊情况进行处理尾插肯定是要找到尾节点的撒双链表找尾节点就直接phead-prev 就可以了当双向链表为空时尾节点tail phead-prev phead 哈。当双向链表不为空时同样地找到尾节点 tail phead-prev用上面同样的方式画图我们发现双链表不为空时也是找到尾节点然后进行上面的四步操作这就是双向链表哨兵位的头结点这样初始化链表的好处//双链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);//调用接口申请节点即可ListNode* newNode BuyNewNode(x);//找到尾节点ListNode* tail phead-prev;//链接新的节点tail-next newNode;newNode-prev tail;newNode-next phead;phead-prev newNode;
}2.6 void ListPopBack(ListNode* phead)删除节点时同单链表没有数据不允许删除双向链表判断为空的条件就是phead-next phead或者phead-prev prev我们只需要暴力断言即可尾删的时候有两种删除方式哈记录尾节点并且记录尾节点的前一个节点。这样做就比较方便的删除和链接不需要有任何的顺序。只记录尾节点那么就需要有一定的顺序啦假设找到的尾节点是tail删除顺序 1tail-prev-next phead。2phead-prev tail-prev。3释放尾节点tail。我个人是比较喜欢第一种的哈//双向链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);//空链表不允许删除数据assert(phead-next ! phead);//找到两个节点ListNode* tail phead-prev;ListNode* pTail tail-prev;//链接pTail-next phead;phead-prev pTail;//释放free(tail);tail NULL;
}2.7 void ListPushFront(ListNode* phead, LTDataType x)双向链表的头插也是比较简单的哈也不需要考虑特殊情况如果不理解可以画画图就能够理解啦//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newNode BuyNewNode(x);//找到哨兵位的头结点的下一个节点ListNode* next phead-next;//找到next节点就随便链接就行phead-next newNode;newNode-next next;newNode-prev phead;next-prev newNode;
}2.8 void ListPopFront(ListNode* phead)双向链表真的挺简单的哈哈不懂的话就画画图。//双链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);//链表没有数据不允许删除assert(phead-next ! phead);//依然找到要删除的节点以及他的下一个节点ListNode* delNode phead-next;ListNode* next delNode-next;//找到这个节点之后随便链接就行next-prev phead;phead-next next;free(delNode);delNode NULL;
}
2.9 ListNode* ListFind(ListNode* phead, LTDataType x)查找的函数和单链表的一模一样遍历链表找到data值相同的节点即可这个函数主要是配合指定位置删除和插入的函数使用的//双链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{asset(phead);//用cur遍历链表ListNode* cur phead-next;while (cur ! phead){if (cur-data x)return cur;cur cur-next;}//没找到返回空指针return NULL;
}2.10 void ListInsert(ListNode* pos, LTDataType x)这个函数是在指定节点的位置之前插入一个新的节点哈pos位置的节点通过LIstFind函数找到。我们只需要找到pos位置之前的那个节点然后与newNode进行连接即可当然不用找到pos的前一个节点也行的//双链表指定位置之前插入新节点
void ListInsert(ListNode* pos, LTDataType x)
{//如果ListFind函数返回的空指针pos就是空指针需要断言assert(pos);//开辟新节点ListNode* newNode BuyNewNode(x);//找到前一个节点ListNode* prev pos-prev;//连接prev-next newNode;newNode-prev prev;newNode-next pos;pos-prev newNode;
}2.11 void ListErase(ListNode* pos)和指定位置之前的插入一样ListErase函数也是需要ListFind函数配合使用的我们只需要找到pos位置的前一个节点后一个节点然后连接即可//删除指定位置的节点
void ListErase(ListNode* pos)
{//如果ListFind函数返回的空指针是不允许删除的assert(pos);//找到前一个和后一个节点ListNode* prev pos-prev, * next pos-next;//链接prev-next next;next-prev prev;//释放节点free(pos);pos NULL;
}3. 一个小小的技巧在我们有了指定位置之前插入和删除的函数之后头插头删尾插尾删都可以使用这两个函数来替代啦头插就是在phead-next 位置之前插入。头删就是删除 phead-next位置的节点。尾插就是在phead的位置插入一个新节点。尾删就是删除phead-prev位置所在的节点。有了这个小技巧20min手撕双向带头循环链表4. 顺序表链表总结不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
