假设以顺序结构存储线性表: (1) 编写一具有"查找该线性表中是否存在两个相邻的

1、假设以顺序结构存储线性表：
（1） 编写一具有“查找该线性表中是否存在两个相邻的元素值也相等”功能的算法。
（2） 分析该算法的平均时间复杂度（假设线性表中一定存在相邻的元素值也相等的情况）。

typedef struct Sequece{
int *data;

int length;

}Seq,*PSQ;

//如果存在返回1，否则返回1
int search_equal_ele( Seq seq ){
if( seq.length <= 1 )
return 0;

int i = 0;

while( i < seq.length - 1 ){

if( seq.data[i] == seq.data[++i] )

return 1;

}

return 0;

}

时间复杂度，得从相等元素出现的位置考虑，假如有n个元素；位置出现在1,2,3，，，n-1的位置总的比较次数：1+2+3+。。。+(n-1) = n(n-1)/2；除以n-1，故平均比较次数为n/2

#include<iostream.h>

template<class t> class a { t *a; int n; public: a(t *a,int s) { this->a=a; n=s; } void order(t a[]); int locate(t a[],t x); t sum(t a[]); };

template<class t> void a<t>::order(t a[]) { t t; for(int i=0;i<n-1;i++) for(int j=i+1;j<=n-1;j++) if(a[i]>a[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } for(int k=0; k<=n-1;k++) cout<<a[k]<<endl;

}

template<class t> int a<t>::locate(t a[],t x ) { for(int i=0;i<=n-1;i++) { if(a[i]==x) return i+1;

} return 0; }

template<class t> t a<t>::sum(t a[]) { t s=0; for(int i=0; i<=n-1; i++) s=s+a[i]; return s; }

void main() { int i; int a[]={11,12,32,22,1,5,8,2,9,10};

a<int> a1(a,10);

cout<<"输入要查找的元素"<<endl; cin>>i; cout<<"查找元素的位置为："<<a1.locate(a,i)<<endl;

a1.order(a);

cout<<"数组的和为："<<'\t'; cout<<a1.sum(a)<<endl;

}