主要问题 在程序中都有所标记

#include<iostream>
#include<ctime>
#include<string>
#include<vector>
using namespace std;

//这个类没有问题

 class Message
 {
     public:
        Message();
        void append();
        string to_string()const;
        void print() const;
    private:
        string name1,name2;
        string article;
        time_t now_time;
 };

 Message::Message()
 {
     cout<<"Please enter the recipient\'s name:"<<endl;
     getline(cin,name1);
     cout<<"Please enter the addresser\'s name:"<<endl;
     getline(cin,name2);
     now_time=time(NULL);
     append();
 }
void Message::append()
 {
     string add_string;
     cout<<"Please enter the add message"<<endl;
     getline(cin,add_string);
     article=article+add_string;
 }
 string Message::to_string()const
 {
     return "**********\nFrom:"+name2+"\nTo:"+name1+"\n"+article;
 }
 void Message::print()const
 {
    cout<<to_string()<<endl;
    cout<<ctime(&now_time)<<"**********" <<endl;
 }

 class Mailbox
 {
     public:
     Mailbox();

    //问题应该在这几个成员函数中
     void add_message(Message mes){MAIL.push_back(mes);}
     void remove_message(int i);
     Message get_message(int i);
     private:
     vector<Message>MAIL;

 };
 void Mailbox::remove_message(int i)//删掉MAIL中的第i个元素
 {
     vector<Message>::iterator pos;
     pos=MAIL.begin();
     MAIL.erase(pos+i);
 }
 Message Mailbox:: get_message(int i)//得到MAIL中的第i个元素
 {
     return MAIL[i];
 }

 int main()
 {
     Message mes1;
     Message mes2;
     Message mes3;
     Mailbox mail;
     mail.add_message(mes1);
     mail.add_message(mes2);
     mail.add_message(mes3);

     mail.remove_message(1);
    Message m1,m2;
    //下面这几句 怎么改  都老是 出错- -。也可能是上面函数体出错  求老师指教
    m1=mail.get_message(0);
    m2=mail.get_message(1);
     cout<<m1.print()<<endl;
     cout<<m2.print()<<endl;
     return 0;
 }

关于这个问题 ，如a*(b+c)+d。我知道当abcd为整数时，整个equation可作为string读入，abcd可作为字符读入；可是当abcd为浮点数时该如何处理这个equation？  abcd该如何读入？

Def. 对于二叉树, 满结点(full node)是指具有两个儿子的结点.

应用.

若某二叉树有 20 个叶子结点, 有 30 个结点仅有一个儿子, 则该二叉树的总的结点数是多少?

a. 通过 buildHeap 最多使用 $2N$ 次比较的事实, 证明堆个数的下界为 $N!/2^{2N}$.

b. 利用 Stirling 公式扩展这个界.

Remark:

关于 Stirling 公式, 参见 问题703

另外,

\[
N! > 2^{2N}=4^N \Leftrightarrow N\geq 9
\]

$N=1$, 只有 1 种

$N=2$, 一种

$N=3$,  两种

$N=4$, 三种

$N=5$, 8 种（$3!+2!$）

$N=6$, 共 $4!-3!+3!+2!=26$ 种

$N=7$,

$N=8$,

$N=9$,

Introduction.

谢尔排序(Shellsort) 的名称源于它的发明者 Donald Shell. 该算法是冲破二次时间屏障的第一批算法之一.

谢尔排序最核心的东西是其采用的增量序列(increment sequence) $1=h_1, h_2,\ldots, h_t$. 一般 $h_t < N/2$. （当然也可以认为是递减序列 $h_t, h_{t-1},\ldots,h_2,h_1=1$.）

依次按 $k=t,t-1,\ldots,2,1$ 的次序, 将要排序的序列 $a_1,a_2,\ldots, a_N$ 中间隔为 $h_k$ 的子序列（共有 $h_k$ 个）进行插入排序.

不同的增量序列, 对于排序的性能有着明显的影响.

一些常见及常用的序列有:

Shell 增量序列(并不好): $h_t=[N/2]$, $h_k=[h_{k+1}/2]$. （此时 $t$ 约为 $[\log N]-1$）

Hibbard 增量序列: $1,3,7,15,31,\ldots,2^t-1$.

Sedgewick 提出了几种增量序列, 其中最好的是 $\{1,5,19,41,109,\ldots\}$, 该序列中的项或者是 $9\times 4^i-9\times 2^i+1$, 或者是 $4^i-3\times 2^i+1$. 确切地,

Remark:

使用 Hibbard 增量序列的谢尔排序的平均情形运行时间基于模拟的结果被认为是 $O(N^{5/4})$, 但是没有人能够证明该结果.

Pratt 已经证明, $\Theta(N^{3/2})$ 的界适用于广泛的增量序列.

谢尔排序的性能在实践中是完全可以接受的, 即使是对于数以万计的 $N$ 仍是如此. 编程的简单特点使得它成为对适度的大量输入数据经常选用的算法. 不过相较于快速排序, 谢尔排序仍有不足. 具体参见下面wiki上的描述.

References:

Mark Allen Weiss, 数据结构与算法分析 C++描述（第三版），张怀勇等译.

http://en.wikipedia.org/wiki/Shellsort

介绍

选择问题(selection problem)是指: 在集合 $S$ 中查找第 $k$ 个最大（或最小）的元素.

基于快速排序算法的快速选择(quickselect)的基本步骤如下:

(1) 如果 $|S|=1$, 那么 $k=1$, 并将 $S$ 中的元素作为结果返回. 如果正在使用小数组的截止方法, 并且 $|S|\leq CUTOFF$, 则将 $S$ 排序并返回第 $k$ 个最小元.

(2) 选取一个枢纽元 $v\in S$.

(3) 将集合 $S-\{v\}$ 分割成 $S_1$ 和 $S_2$, 就像快速排序中所做的那样.

(4)

• 如果 $k\leq |S_1|$, 那么第 $k$ 个最小元必然在 $S_1$ 中. 在这种情况下, 返回 quickselect($S_1,k$).
• 如果 $k=1+|S_1|$, 那么枢纽元就是第 $k$ 个最小元;
• 否则, 第 $k$ 个最小元就在 $S_2$ 中, 它是 $S_2$ 中的第 $(k-|S_1|-1)$ 个最小元. 我们进行一次递归调用并返回 quickselect($S_2,k-|S_1|-1$).

与快速排序对比, 快速选择只进行了一次递归调用而不是两次.
快速选择的最坏情形和快速排序相同, 也是 $O(N^2)$.
直观开来, 这是因为快速排序的最坏情形发生在 $S_1$ 和 $S_2$ 有一个是空的时候; 于是, 快速选择也就不是真的节省一次递归调用.
 

但可以证明, 快速选择的平均运行时间是 $O(N)$. 具体分析类似于快速排序的分析.

References:

Mark Allen Weiss, 数据结构与算法分析 C++ 描述（第三版），张怀勇等译.  [P.213, $\S$7.7.6]

注: 左式树(leftist tree) 即为左式堆(leftist heap). Leftist tree 亦被翻译为左偏树 (参见 http://zh.wikipedia.org/wiki/左偏树 ).

Hint: 使用归纳法证明.

考虑下述算法(称为 Horner 法则)， 用于计算 $f(x)=\sum\limits_{i=0}^{n}a_i x^i$ 的值.

poly = 0;
for( i=n; i>=0; i--)
	poly = x * poly + a[i];

a) 对于多项式 $f(x)=4x^4+8x^3+x+2$, 求 $x=3$. 指出该算法的各步是如何进行的.

b) 解释该算法为什么能够解决这个问题.

c) 该算法的运行时间是多少?

请编写程序并完成上面的问题.

References:

Mark Allen Weiss 著, 张怀勇等译, 《数据结构与算法分析 C++ 描述》, 人民邮电出版社, 2012. 6. 【Exer 2.14】

设函数 $f(n)$ 返回正整数 $n$ 的二进制表示中 1 的个数.

证明: 若 $n=2k+1$, 则 $f(n)=f(k)+1$; 若 $n=2k$, 则 $f(n)=f(k)$.

Hint:

\[k=a_0 2^m+a_1 2^{m-1}+\cdots+a_{m-1}2+a_m\]

\[N=2k+1=a_0 2^{m+1}+a_1 2^{m}+\cdots+a_{m-1} 2^2+ a_m 2+ 1\]

请编程实现.

Hint: 用归纳法证明.

回忆:

一个二叉树的任意一个结点最多有两个 childs, 所以可以使用 双向链表 的结构直接链接 childs.

struct BinaryNode
{
	Object	element;	// The data in the node
	BinaryNode	*left;	// Left child
	BinaryNode	*right;	//right child
}