for (int i=1; i <= 10; i++)
{
cout<<"倒数第"<<i<<"个元素为"<<(getKth(headNode, i)->m_nKey)<<endl;
}
return 0;
}
/************************************************************ ************/
/* 函数功能:获取单链表倒数第K个元素 */
/************************************************************************/
ListNode *getKth(ListNode * tnode, int k)
{
ListNode *first, *sencond;
first = sencond = tnode;
for (int i=0; i<k; i++)
{
sencond = sencond->m_pNext;
}
while (sencond != NULL)
{
sencond = sencond->m_pNext;
first = first->m_pNext;
}
return first;
}
/************************************************************************/
/* 函数功能:创建含有n个元素的单链表 */
/************************************************************************/
ListNode *makeList(int n)
{
ListNode *head = NULL;
ListNode *temp = NULL;
for (int i=10; i>0; i--)
{
temp = new ListNode;
temp->m_nKey = i;
temp->m_pNext = head;
head = temp;
}
return head;
}
/************************************************************************/
/* 函数功能:输出链表的元素 */
/************************************************************************/
void printList(ListNode *head)
{
while (head != NULL)
{
cout<<head->m_nKey<<" ";
head = head->m_pNext;
}
cout<<endl;
}
cout<<"原数组为:/n";
copy(arr, arr + n, ostream_iterator<int>(cout, " "));
cout<<endl;
createBSTree(root, arr, n);
cout<<"中序输出:/n";
middleOutPut(root);
cout<<endl;
// mirrorTreeRecursive(root);
mirrorTreeIteration(root);
cout<<"镜像后为:/n";
middleOutPut(root);
cout<<endl;
return 0;
}
/************************************************************************/
/*函数功能:向二叉查找树中插入元素 */
/************************************************************************/
void insertElement(BSTreeNode *&root, int element)
{
if (NULL == root)
{
root = new BSTreeNode;
root->m_nValue = element;
root->m_pLeft = NULL;
root->m_pRight = NULL;
}
else if (root->m_nValue < element)
{
insertElement(root->m_pRight, element);
}
else
{
insertElement(root->m_pLeft, element);
}
}
/************************************************************************/
/* 函数功能:中序输出二叉查找树 */
/************************************************************************/
void middleOutPut(BSTreeNode *root)
{
if(root != NULL)
{
middleOutPut(root->m_pLeft);
cout<<root->m_nValue<<" ";
middleOutPut(root->m_pRight);
}
}
/************************************************************************/
/* 函数功能:创建二叉查找树,参数arr[]为数组, n为数组元素的个数 */
/************************************************************************/
void createBSTree(BSTreeNode *&root, int arr[], int n)
{
for (int i=0; i<n; i++)
{
insertElement(root, arr[i]);
}
}
/************************************************************************/
/* 函数功能:递归方法来产生二元查找树的镜像树
思路:就是递归翻转树,有子树则递归翻转子树*/
/************************************************************************/
void mirrorTreeRecursive(BSTreeNode *root)
{
BSTreeNode *temp = NULL;
if (root != NULL)
{
temp = root->m_pRight;
root->m_pRight = root->m_pLeft;
root->m_pLeft = temp;
}
if (root->m_pLeft != NULL)
{
mirrorTreeRecursive(root->m_pLeft);
}
if (root->m_pRight != NULL)
{
mirrorTreeRecursive(root->m_pRight);
}
}
/************************************************************************/
/* 函数功能:迭代方法产生二叉查找树的镜像树
思路:由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。
首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。
如果它有左子树,把它的左子树压入栈中;
如果它有右子树,把它的右子树压入栈中。*/
/************************************************************************/
void mirrorTreeIteration(BSTreeNode *root)
{
stack<BSTreeNode*> s;
s.push(root);
while (!s.empty())
{
BSTreeNode *top = s.top();
BSTreeNode *temp = NULL;
temp = top->m_pRight;
top->m_pRight = top->m_pLeft;
top->m_pLeft = temp;
s.pop();
if (top->m_pLeft != NULL)
{
s.push(top->m_pLeft);
}
if (top->m_pRight != NULL)
{
s.push(top->m_pRight);
}
}
}
快速求斐波那契数列第N项
char *temp = str;
//查看第一个字符来判断正负
bool fuhao = false;
if (*temp == '-')
{
fuhao = true;
temp++;
}
else if(*temp == '+')
{
temp++;
}
int sum = 0;
while (*temp != '/0')
{
if (*temp >= '0' && *temp <= '9')
{
sum = sum * 10 + (*temp - '0');
temp++;
}
else
{
sum = 0;
break;
}
}
if (fuhao == true)
{
return -sum;
}
else
{
return sum;
}
}
一个单链表的类,实现链表的反转 和链表的合并
}
/************************************************************************/
/* 函数功能:合并两个单链表 */
/************************************************************************/
void SingleList::MergeList(SingleList &other)
{
Node *temp = head;
//找到第一链表的尾部
while(temp->p_Next != NULL)
{
temp = temp->p_Next;
}
temp->p_Next = other.head;
other.head = NULL; //销毁第二个链表
}
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能:在字符串中找出连续最长的数字串,并把这个串的长度返回,并把这个最长数字串付给其中一个函数参数outputstr 所指内存。
例如:"abcd12345ed125ss123456789"的首地址传给intputstr 后,函数将返回9,outputstr 所指的值为123456789
58.从尾到头输出链表。
题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析:这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
不能被继承的类。
题目:用C++设计一个不能被继承的类。
分析:这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外,还能考察反应能力,是一道很好的题目。
在O(1)时间内删除链表结点。
题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下:
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
http://blog.csdn.net/xianliti/archive/2010/06/11/5665179.aspx
54.调整数组顺序使奇数位于偶数前面。
题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
52.二元树的深度。
题目:输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
例如:输入二元树:
10
/ /
6 14
/ / /
4 12 16
输出该树的深度3。
二元树的结点定义如下:
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
分析:这道题本质上还是考查二元树的遍历。
51.和为n连续正数序列。
题目:输入一个正数n,输出所有和为n连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
分析:这是网易的一道面试题。
47.创新工场:
求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}
42.请修改append函数,利用这个函数实现:
两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果,不能修改两个链表的数据。