int main(int argc, char const* argv[])
{
  int length = 0;
  cout << "请输入人数：";
  cin >> length;

  vector<SeqList> c(length);  //建立向量c
  SeqList game;               //类的实例
  game.Joseph(c);             //调用成员函数求解
  return 0;
}

SeqList<ElemType>::SeqList(const SeqList<ElemType> &sa)
{
    int saLength = sa.GetLength();
    ElemType e;
    
    maxLength = sa.maxLength;
    elems = new ElemType[maxLength];
    assert(elems);
    length = 0;

    for (int i = 1; i <= saLength; i++) {
        sa.GetElem(i, e);
        InsertTailElem(e);
    }
}

int main(int argc, char* argv[])
{
    cout << sizeof(SeqList<int>) << endl;
    SeqList<int> a;
    a.InsertAtRear(1);
    a.InsertAtRear(2);
    a.InsertAtRear(3);
    a.InsertAtRear(4);

    a.Delete(3);
    cout<<"顺序表长度为："<<a.Length()<<endl;
    a.PrintList();
    return 0;
}

int main(int argc, const char * argv[]) {

    char c='*';
    SeqList<int> *la = new SeqList<int>(6);
    int e = 0, i = 0;
    
    Status status;
    
    while (c != '0') {
        cout << endl << "1. 生成线性表.";
        cout << endl << "2. 显示线性表.";
        cout << endl << "3. 取指定元素.";
        cout << endl << "4. 设置元素值.";
        cout << endl << "5. 删除元素.";
        cout << endl << "6. 插入元素.";
        cout << endl << "7. 元素定位.";
        cout << endl << "8. 求线性表长度.";
        cout << endl << "0. 退出";
        cout << endl << "选择功能(0~8):";
        cin >> c;
        
        switch (c) {
            case '1':
            {
                la->Clear();
                status = SUCCESS;
                cout << endl << "输入e( e = 0时退出):";
                cin >> e;
                while (e != 0 && status != OVER_FLOW) {
                    status = la->InsertTailElem(e);
                    if (status == OVER_FLOW) {
                        cout << "线性表已满。" << endl;
                    }else {
                        cin >> e;
                    }
                }
            }
                break;
                
            case '2':
            {
                la->Traverse(Write<int>);
                //system("clear");
            }
                break;
                
            case '3':
            {
                cout << endl << "输入元素位置：";
                cin >> i;
                if (la->GetElem(i, e) == NOT_PRESENT) {
                    cout << "元素不存在" << endl;
                }else {
                    cout << "元素：" << e <<endl;
                }
                
            }
                break;
                
            case '4':
            {
               cout<< endl << "输入位置：";
                cin >> i;
                cout <<endl<<"输入元素值：";
                cin >> e;
                if (la->SetElem(i, e) == RANGE_ERROR) {
                    cout<<"位置范围错误"<<endl;
                }else {
                    cout<<"设置成功"<<endl;
                }
            }
                break;
                
            case '5':
            {
                cout << endl << "输入位置:";
                cin >> i;
                if (la->DeleteElem(i, e) == RANGE_ERROR) {
                    cout << "位置范围错." << endl;
                }else {
                    cout << "被删除元素值:" << e << endl;
                }
            }
                break;
                
            case '6':
            {
                cout << endl << "输入位置:";
                cin >> i;
                cout << endl << "输入元素值:";
                cin >> e;
                status = la->InsertElem(i, e);
                
                
                if (status == RANGE_ERROR) {
                    cout << "位置范围错." << endl;
                } else if (status == OVER_FLOW) {
                    cout << "线性表已满." << endl;
                }else {
                    cout << "插入成功." << endl;
//.........这里部分代码省略.........

void
check_viterbi()
{
    ensure_hmm_built();
    ensure_hmm_test_seqs_created();

    cout << "******* check_viterbi(): " << test_seqs.size() << " artificial sequences" << endl;

    for (SeqList::const_iterator i = test_seqs.begin(); test_seqs.end() != i; ++i) {

        const size_t num_obs = i->end() - i->begin();

        //doesn't work well without logs on long sequences
        if (num_obs > 20)
        {
            continue;
        }

        index_list_t state_indices;
        ViterbiAlgorithm<false> viterbi_without_logs;
        viterbi_without_logs.viterbi(
            hmm,
            num_obs,
            i->begin(),
            i->end(),
            front_inserter(state_indices));

#ifdef VERBOSE_CHECKING
        cout
                << "Sequence " << (i - test_seqs.begin())
                << " has most likely state sequence (not using logs): ";
        for (index_list_t::const_iterator j = state_indices.begin(); state_indices.end() != j; ++j) {
            cout << *j;
        }
        cout << endl;
#endif

        index_list_t state_indices_using_logs;
        ViterbiAlgorithm<true> viterbi_with_logs;
        viterbi_with_logs.viterbi(
            hmm,
            num_obs,
            i->begin(),
            i->end(),
            front_inserter(state_indices_using_logs));

#ifdef VERBOSE_CHECKING
        cout
                << "Sequence " << (i - test_seqs.begin())
                << " has most likely state sequence (    using logs): ";
        for (index_list_t::const_iterator j = state_indices_using_logs.begin(); state_indices_using_logs.end() != j; ++j) {
            cout << *j;
        }
        cout << endl;
#endif

        BOOST_CHECK_EQUAL(state_indices, state_indices_using_logs);

#ifdef VERBOSE_CHECKING
        cout << endl;
#endif
    }
}

void check_forward_backward() {

    ensure_hmm_built();
    ensure_hmm_test_seqs_created();

    cout << "******* check_forward_backward(): " << test_seqs.size() << " artificial sequences" << endl;

    for (SeqList::const_iterator i = test_seqs.begin(); test_seqs.end() != i; ++i) {

        const size_t num_obs = i->end() - i->begin();

        ForwardBackwardAlgorithm<true> fw_with_scaling;
        fw_with_scaling.forward(
            hmm,
            i->begin(),
            i->end());
        fw_with_scaling.backward(
            hmm,
            i->rbegin(),
            i->rend());

        ForwardBackwardAlgorithm<false> fw_without_scaling;
        fw_without_scaling.forward(
            hmm,
            i->begin(),
            i->end());
        fw_without_scaling.backward(
            hmm,
            i->rbegin(),
            i->rend());

#ifdef VERBOSE_CHECKING
        cout
                << "Sequence " << (i - test_seqs.begin())
                << " (length=" << i->size()
                << ") has probability (with    scaling): "
                << fw_with_scaling.get_probability()
                << endl;
        cout
                << "Sequence " << (i - test_seqs.begin())
                << " (length=" << i->size()
                << ") has probability (without scaling): "
                << fw_without_scaling.get_probability()
                << endl;

        cout
                << "Sequence " << (i - test_seqs.begin())
                << " (length=" << i->size()
                << ") has log probability (with    scaling): "
                << fw_with_scaling.get_log_probability()
                << endl;
        cout
                << "Sequence " << (i - test_seqs.begin())
                << " (length=" << i->size()
                << ") has log probability (without scaling): "
                << fw_without_scaling.get_log_probability()
                << endl;
        cout << endl;
#endif

        //the log probability may underflow to log(0.0) without scaling - allow this in the tests
        if (BIO_FINITE(fw_without_scaling.get_log_probability())) {
            //only do comparison if no underflow
            BOOST_CHECK_CLOSE(fw_with_scaling.get_log_probability(), fw_without_scaling.get_log_probability(), 1.0);
        }
        //in the normal probability case both or neither underflow
        BOOST_CHECK_CLOSE(fw_with_scaling.get_probability(), fw_without_scaling.get_probability(), 1.0);
    }
}

/** Check the Baum-Welch algorithm. */
void
check_baum_welch_multiple(const SeqList & seqs)
{
    ensure_hmm_built();

    cout << "******* check_baum_welch_multiple()" << endl;

    //generate the combined sequence
    const seq_t combined_seq = std::accumulate(seqs.begin(), seqs.end(), string(""));

    //train a hmm on the combined sequence
    hmm_t hmm_single(hmm);
    baum_welch_single(
        hmm_single,
        combined_seq.begin(),
        combined_seq.end(),
        combined_seq.rbegin(),
        combined_seq.rend());
    const prob_t single_log_prob =
        ForwardBackwardAlgorithm<true>()
        .forward(
            hmm_single,
            combined_seq.begin(),
            combined_seq.end()).get_log_probability();


    hmm_t hmm_multiple(hmm);
    prob_t last_multiple_log_prob =
        get_multiple_log_likelihood(hmm_multiple, seqs.begin(), seqs.end());

    //train multiply several times
    for (unsigned i = 0; NUM_BAUM_WELCH_ITERATIONS != i; ++i)
    {
        //train a hmm on all sequences concurrently
        baum_welch_multiple(
            hmm_multiple,
            seqs.begin(),
            seqs.end());

        const prob_t new_log_prob =
            get_multiple_log_likelihood(hmm_multiple, seqs.begin(), seqs.end());

#ifdef VERBOSE_CHECKING
        if (new_log_prob < last_multiple_log_prob)
        {
            cout << new_log_prob << " < " << last_multiple_log_prob << endl;
        }
#endif

        last_multiple_log_prob = new_log_prob;
    }

#ifdef VERBOSE_CHECKING
    cout
            << "Log prob of combined seq after training one at a time: "
            << single_log_prob
            << endl;
    cout
            << "Log prob of combined seq after training all at once: "
            << last_multiple_log_prob
            << endl;
#endif //VERBOSE_CHECKING

}

void graph::showVertex()//显示图的结点
{
	for(i=0;i<Vertices.ListSize();i++)//显示坐标
		cout<<setw(5)<<i;
	cout<<endl;
	for(i=0;i<Vertices.ListSize();i++)//显示数据
		cout<<setw(5)<<Vertices.Getdata(i);
	cout<<endl;
}

char graph::getvalue(const int i)//求取图的某个结点的值
{
	if(i<0||i>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return false;
	}
	else
		return Vertices.Getdata(i);//采用顺序表的操作达成目标
}

int graph::getweight(const int nodestart,const int nodeend)//求两个结点之间的边的权值
{
	if(nodestart<0||nodestart>Vertices.ListSize()||nodeend<0||nodeend>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return false;
	}
	else
		return Edge[nodestart][nodeend];
}

void graph::showgraph()//图的显示函数
{
	for(i=0;i<Vertices.ListSize();i++)//用邻接矩阵来模拟图的边的相关信息
	{
		for(j=0;j<Vertices.ListSize();j++)
		{
			if(getweight(i,j)==maxweight)
				cout<<setw(5)<<"∞";//表示两个结点之间没有边
			else
				cout<<setw(5)<<getweight(i,j);
		}
		cout<<endl;
	}
}

int graph::insertEdge(const int nodestart,const int nodeend,int weight)//添加一条边
{
	if(nodestart<0||nodestart>Vertices.ListSize()||nodeend<0||nodeend>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return 0;
	}
	else
	{
		Edge[nodestart][nodeend]=weight;
		numofedges++;
		return 1;
	}
}

int graph::deleteEdge(const int nodestart,const int nodeend)//删除一条边
{
	if(nodestart<0||nodestart>Vertices.ListSize()||nodeend<0||nodeend>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return 0;
	}
	else
	{
		Edge[nodestart][nodeend]=maxweight;
	    numofedges--;
		return 1;
	}
}

void register_hidden_markov_model_tests(test_suite * test)
{
    ensure_hmm_built();
    ensure_hmm_test_seqs_created();

    test->add(BOOST_TEST_CASE(&check_forward_backward), 0);
    test->add(BOOST_PARAM_TEST_CASE(&check_baum_welch, test_seqs.begin(), test_seqs.end()), 0);
    test->add(BOOST_TEST_CASE(&check_hmm_overfitting), 0);
    test->add(BOOST_TEST_CASE(&check_long_test_seq), 0);
    test->add(BOOST_PARAM_TEST_CASE(&check_baum_welch_multiple, hmm_multiple_seqs.begin(), hmm_multiple_seqs.end()), 0);

    //it is not clear how effective these tests are
    //test->add(BOOST_PARAM_TEST_CASE(&check_more_states_improves_learning, test_seqs.begin(), test_seqs.end()), 0);
    //test->add(BOOST_TEST_CASE(&check_viterbi), 2); //can get 2 underflow problems on long sequences when not using logs
    //test->add(BOOST_TEST_CASE(&generate_test_sequences), 0);
}

int graph::getfirstneighbor(const int v)//求取其第一个相邻结边
{
	if(v<0||v>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return false;
	}
	else
	{
		for(int col=0;col<=Vertices.ListSize();col++)
		{
			if(Edge[v][col]>0 && Edge[v][col]<maxsize)
				return col;//若存在相邻的结点返回其下标
		}
		return -1;//否则返回-1
	}
}

int graph::getnextneighbor(const int nodestart,const int nodeend)//求取其下一条邻接边
{//找结点nodestart的<nodestart,nodeend>邻接边的下一条邻接边
	if(nodestart<0||nodestart>Vertices.ListSize()||nodeend<0||nodeend>Vertices.ListSize())
	{
		cout<<"对不起参数越界出错!"<<endl;
		return false;
	}
	else
	{//使col为nodeend+1因此寻找的边是nodestart的<nodestart,nodeend>邻接边的下一条邻接边
		for(int col=nodeend+1;col<=Vertices.ListSize();col++)
		{
			if(Edge[nodestart][col]>0&&Edge[nodestart][col]<maxsize)
				return col;
		}
		return -1;
	}
}

int graph::deleteVertex(const int v)//删除一个结点
{
	for(int i=0;i<Vertices.ListSize();i++)//删除结点必须把与这个结点相关联的全部的边首先删除
		for(int j=0;j<Vertices.ListSize();j++)
		{
			if(i==v||j==v && Edge[i][j]>0 && Edge[i][j]<maxweight)
			{
				Edge[i][j]=maxweight;
				numofedges--;
			}
		}
	int flag=Vertices.Delete(v);
	if(flag==1)//提供一个标志位为后面的调用方便
		return 1;
	else
		return 0;
}

void graph::initopological()//拓扑排序环境初始化
{
	Vertices.ClearList();					//结点数组清空
	initializationofEdge(maxvertices); 	
	for(j=0;j<maxvertices;j++)				//初始化结果数组、入度数组、删除标志数组
	{
	   topologicalSort[j]=0;
	   Indegree[j]=0;						//用列下标统计入度，便于理解
	   deleflag[j]=0;
	}
}

void graph::inputdata(void)
{
	int nodestart,nodeend,weight;//起始点、终止点、权值
	Vertices.ClearList();//结点数组清空
	initializationofEdge(maxvertices); 
	cout<<"下面添加结点信息!"<<endl;
	cout<<"----------------"<<endl;
	cout<<"请输入结点个数(小于 "<<maxvertices<<"):";
	cin>>inputnodenum;
    nodearray=new char[inputnodenum];//建立字符数组
	cout<<"请输入"<<inputnodenum<<"个结点(单个Ascii码字符)，空格隔开，输入完毕后回车:"<<endl;
	for(i=0;i<inputnodenum;i++)
		{
			cin>>nodearray[i];
			insertVertices(nodearray[i]);	
		}
	cout<<inputnodenum<<"个结点已经添加成功了!字符的的默认编号是:"<<endl;
	for(i=0;i<inputnodenum;i++)//显示对应坐标	
		cout<<setw(5)<<i;
	cout<<endl;
	for(i=0;i<inputnodenum;i++)//显示数组中字符
		cout<<setw(5)<<nodearray[i];
	cout<<endl<<endl;
	cout<<"下面添加边信息!"<<endl;
	cout<<"---------------"<<endl;
	cout<<"请输入边数: ";
	cin>>inputedgenum;
	cout<<"例如:1 2 10 表示添加了一条边(从1号结点到2号结点，权值为10)!:"<<endl;
	for(i=0;i<inputedgenum;i++)
	{
		cout<<"下面添加第"<<i+1<<"条边的信息: "<<endl;
	    cin>>nodestart>>nodeend>>weight;
        flag=insertEdge(nodestart,nodeend,weight);
		if(flag==1)
			cout<<"从"<<nodestart<<"号结点"<<"到"<<nodeend<<"号结点之间已经添加了权值为"
			    <<weight<<"的一条边!"<<endl<<endl;
	}
	cout<<"图已经建立!"<<endl;
	delete[] nodearray;
	build=1;
}

void graph::datafordijkstra()//为求最短路径问题准备数据
{
	Vertices.ClearList();				//结点数组清空
	initializationofEdge(maxvertices); 	//边数组初始化
	inputnodenum=6;						//结点数				
	inputedgenum=8;						//边数
	//                     0   1   2   3   4   5
	char defaultnodes[6]={'a','b','c','d','e','f'};//结点名称
	for(i=0;i<inputnodenum;i++)			
	{		
		insertVertices(defaultnodes[i]);//把结点存入存储结构				
	}		    													           
	insertEdge(0,2,10);					//把边的信息存入存储结构
	insertEdge(0,4,30);
	insertEdge(0,5,100);
	insertEdge(1,2,5);
	insertEdge(2,3,50);
	insertEdge(3,5,10);
	insertEdge(4,3,20);
	insertEdge(4,5,60);
	build=1;
}