#include<iostream>
#include<Windows.h>
using namespace std;
//锦标赛算法求第二大的数（不考虑数组中存在多数等值情况下）
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
void InsertToBottom(int t,int i,LNode* d){
LinkList p=new LNode;
p->data=d[i].data;
p->next=NULL;
if(d[t].next==NULL||d[t].next->data<d[i].data)d[t].next=p;
}
void championShips(int n,LNode* d){
int t=-1;
for(int i=0;i<n-1;i+=2){
int winner;
if(d[i].data>d[i+1].data){InsertToBottom(i,i+1,d);winner=i;}
else{InsertToBottom(i+1,i,d);winner=i+1;}
d[++t]=d[winner];
}
if(n%2==1)d[++t]=d[n-1];
if(t>=1)championShips(t+1,d);
else cout<<"第二大的数是："<<d[0].next->data<<endl;
}
int main(){
int n=9;
LNode* d=new LNode[n];
int p[n]={4,1,12,412,17,41,178,21,125};
for(int i=0;i<n;++i){
d[i].data=p[i];
d[i].next=NULL;
}
championShips(n,d);
return 0;
}