php企业网站源码蓝色,正规网站建设商家,东莞网站建设-信科网络,大名县建设局网站目录
1.双向链表的头插
方法一
方法二
2.双向链表的头删
3.双向链表的销毁
4.双向链表的某个节点的数据查找
5.双向链表的中间插入
5.双向链表的中间删除
6.对比顺序表和链表 承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章
1.双向链表的头插
方法…目录
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* pfindLTFind(plist, 3);if (pfind){LTErase(pfind);pfindNULL;}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篇
