做网站公司 上海付费wordpress主题
目录
1.双向链表的头插
方法一
方法二
2.双向链表的头删
3.双向链表的销毁
4.双向链表的某个节点的数据查找
5.双向链表的中间插入
5.双向链表的中间删除
6.对比顺序表和链表
承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章
1.双向链表的头插
方法一
头插注意操作顺序:新节点先与头节点的后一个节点建立联系,后与头节点建立联系,反过来会丢失指针
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}方法二
当first保存了头节点的后一个节点的地址,可以反过来,即新节点先与头节点建立联系,后与头节点的后一个节点建立联系
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}
2.双向链表的头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}main.c的部分代码改为
void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}
3.双向链表的销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//保存cur1的下一个节点的地址free(cur);cur = next;}free(phead);phead = NULL;
}注意:从phead的下一个节点开始逐步销毁每个节点,到cur值等于phead值时,停止循环
备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL
4.双向链表的某个节点的数据查找
分为两种情况:找到和找不到
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;//找到返回NULL}cur = cur->next;}return NULL;//找不到返回NULL
}
5.双向链表的中间插入
LTInsertBefore(LTNode* pos)表示在pos指向的节点之前(Before)插入(Insert)新节点
void LTInsertBefore(LTNode* pos,LTDataType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = BuyListNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}有了这个函数,而且有哨兵位的头节点,因此头插函数和尾插函数可以很容易改写
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead->next,x);
}由于是循环链表,因此head的前一个节点为尾节点
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead,x);
}中间插入函数应该和数据查找函数LTFind配合使用
main.c的部分代码改为
void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind = LTFind(plist, 3);LTInsertBefore(pfind, 5);LTPrint(plist);
}
5.双向链表的中间删除
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;
}备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL
中间删除函数应该和数据查找函数LTFind配合使用
main.c中部分代码改为
void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind=LTFind(plist, 3);if (pfind){LTErase(pfind);pfind==NULL;}LTPrint(plist);
}注意要判断pfind是否为NULL!!
有了中间删除函数,头删和尾删函数可以变简洁
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}6.对比顺序表和链表
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持:O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存命中率 | 高 | 低 |
缓存命中率是什么参见第96篇