江苏龙网

  1. 主页 > 生活百科 > >

如何理解c/c++和php语言的区别(14)

C/C++


解决问题方法思路如下：
方法一、如果我们知道链表的长度n ， 查找倒数第m个元素 ， 也就是查找正序的第（n - m）个元素（这里的序号只是为了分析 ， 可能跟题目不一定正确的符合） 。那么这样来说就简单很多 。首先遍历链表得到链表长度 ， 然后重新遍历一次 ， 查找正数第（n-m）个元素 。时间复杂度大约是O(2n) 。
方法二、我们是不是可以提供一个辅助存储空间 ， 是的我们在遍历到链表结束的时候可以回溯到倒数第m个元素 。比如用一个支持随机访问的容器记录链表每一个节点的地址 。那么这样的就可以只遍历一次链表就能得到结果 。时间复杂度大约是O(n) ， 但是我们是用空间换取时间的 ， 辅助存储空间的大小由m决定 ， 如果m过大也是不可取的 。
方法三、头结点指针为当前指针 ， 尾节点指针为拖后指针 。开始的时候当前指针和拖后指针初始化为链表的头结点 ， 首先我们让当前指针遍历到第m个元素 ， 拖后指针不变；然后同步更新当前指针和拖后指针；直到当前指针为链表结尾 。这样我们就能保证当前指针和拖尾指针之间的距离是m 。
代码如下：
Node* FindMToLastNode(Node* pHead, int m) {
// 查找到第m个元素
Node* pCurrent = pHead;
for (int i = 0; i < m; ++i)
{
if (pCurrent)
{
pCurrent = pCurrent->next;
}
else
{
return NULL;
}
}
Node* pFind = pHead;
while (pCurrent) {
pFind = pFind->next;
pCurrent = pCurrent->next;
}
return pFind;
}
2. 给定一个单向链表（长度未知） ， 请遍历一次就找到中间的指针 ， 假设该链表存储在只读存储器 ， 不能被修改
设置两个指针 ， 一个每次移动两个位置 ， 一个每次移动一个位置 ， 当第一个指针到达尾节点时 ， 第二个指针就达到了中间节点的位置
处理链表问题时 ， ”快行指针“是一种很常见的技巧 ， 快行指针指的是同时用两个指针来迭代访问链表 ， 只不过其中一个比另一个超前一些 。快指针往往先行几步 ， 或与慢指针相差固定的步数 。
node *create() {
node *p1, *p2, *head;
int cycle = 1, x;
head = (node*)malloc(sizeof(node));
p1 = head;
while (cycle)
{
cout << "please input an integer: ";
cin >> x;
if (x != 0)
{
p2 = (node*)malloc(sizeof(node));
p2->data = https://www.isolves.com/it/cxkf/yy/C/2021-12-15/x;
p1->next = p2;
p1 = p2;
}
else
{
cycle = 0;
}
}
head = head->next;
p1->next = NULL;
return head;
}
void findmid(node* head) {
node *p1, *p2, *mid;
p1 = head;
p2 = head;
while (p1->next->next != NULL)
{
p1 = p1->next->next;
p2 = p2->next;
mid = p2;
}
}
3. 将一个数组生成二叉排序树
排序 ， 选数组中间的一个元素作为根节点 ， 左边的元素构造左子树 ， 右边的节点构造有子树 。
4. 查找数组中第k大的数字？
因为快排每次将数组划分为两组加一个枢纽元素 ， 每一趟划分你只需要将k与枢纽元素的下标进行比较 ， 如果比枢纽元素下标大就从右边的子数组中找 ， 如果比枢纽元素下标小从左边的子数组中找 ， 如果一样则就是枢纽元素 ， 找到 ， 如果需要从左边或者右边的子数组中再查找的话 ， 只需要递归一边查找即可 ， 无需像快排一样两边都需要递归 ， 所以复杂度必然降低 。
最差情况如下：假设快排每次都平均划分 ， 但是都不在枢纽元素上找到第k大第一趟快排没找到 ， 时间复杂度为O(n) ， 第二趟也没找到 ， 时间复杂度为O(n/2) ， 第k趟找到 ， 时间复杂度为O(n/2k) ， 所以总的时间复杂度为O(n(1+1/2+....+1/2k))=O(n) ， 明显比冒泡快 ， 虽然递归深度是一样的 ， 但是每一趟时间复杂度降低 。
5. 红黑树的定义和解释？B树的基本性质？
红黑树：
性质1. 节点是红色或黑色 。
性质2. 根节点是黑色 。
性质3. 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵） ， 如果一个结点n的只有一个左孩子 ， 那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子 ， 那么n的左孩子是一个黑哨兵 。


推荐阅读


上一篇：Win10强烈不建议安装这2款软件，严重拖慢电脑运行！旧电脑的噩耗

下一篇：没有了