DHU数据结构

数据结构"/>

DHU数据结构

目录

1.题目

2.题解

3.代码实现

1.题目

顺序表ADT模板简单应用算法设计：在给定的顺序表中找出最大和最小的元素

作者: 冯向阳 时间限制: 1S 章节: DS:线性表

问题描述 :

目的：使用自行设计的顺序表ADT或STL的vector模板设计并实现顺序表应用场合的一些简单算法设计。

应用8：试设计一个算法，找出顺序表A中最大和最小的元素（输出在屏幕上），并保持原顺序表不变。

（1）顺序表ADT版本

参考函数原型：

template<class ElemType>
bool Search_Max_Min( const SqList<ElemType> &A, ElemType &max, ElemType &min );

（2）vector版本

参考函数原型：

template<class ElemType>
bool Search_Max_Min( const vector<ElemType> &A, ElemType &max, ElemType &min );

输入说明 :

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）

第二行：顺序表A的数据元素（数据元素之间以空格分隔）

输出说明 :

如第一行输入值为0、1、2、3之外的值，直接输出“err”

否则：

第一行：顺序表A的遍历结果

第二行：最大值max

第三行：最小值min

输入范例 :

0
1 10 -30 20 -30 30

输出范例 :

1,10,-30,20,-30,30
30
-30

2.题解

• 读题：造表+找最值
• 造表：stringstream就是牛哈
• 找最值：就遍历一遍同时在线比较找最值

3.代码实现

• 造表和找最值都很简单，所以直接上完整代码

  #include <iostream>
  #include <cstring>
  #include <vector>
  #include <sstream>using namespace std;
  int n;
  string s;template<class T>
  void print(vector<T> &A)
  {auto it=A.begin();for(;it!=A.end()-1;it++)cout<<*it<<",";cout<<*it<<endl;
  }
  template<class T>
  void find_m(stringstream &in,vector<T> &A)
  {T str;while(in>>str)A.push_back(str);print(A);T ma=A.front();//给最值赋为初始值T mi=A.front();auto it=A.begin();while(it!=A.end()){if(ma<*it)ma=*it;if(mi>*it)mi=*it;it++;}cout<<ma<<endl<<mi<<endl;
  }
  int main()
  {cin>>n;getchar();getline(cin,s);stringstream in(s);if(n==0){vector<int> a;find_m(in,a);}else if(n==1){vector<double> b;find_m(in,b);}else if(n==2){vector<char> c;find_m(in,c);}else if(n==3){vector<string> d;find_m(in,d);}else cout<<"err"<<endl;return 0;
  }
  

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>using namespace std;
int n;
string s;template<class T>
void print(vector<T> &A)
{int i;for(i=0; i<A.size()-1; i++){cout<<A[i]<<",";}cout<<A[i]<<endl;
}
template<class T>
void find_m(vector<T> &A, T &ma, T & mi)
{print(A);ma=A.front();mi=A.front();typename std::vector<T>::iterator it=A.begin();while(it!=A.end()){if(ma<*it) ma=*it;if(mi>*it) mi=*it;it++;}cout<<ma<<endl<<mi<<endl;
}int main()
{cin>>n;getchar();getline(cin,s);if(n==0){vector<int> a;int num=0;int max0,min0,f=0;for(int i=0; i<s.size(); i++){if(s[i]==' '){if(f==1)num=-num;a.push_back(num);num=0,f=0;}else if(s[i]=='-') f=1;else{num=num*10+s[i]-'0';}}if(f==1)num=-num;a.push_back(num);find_m(a,max0,min0);}else if(n==1){vector<double> b;double num=0;double max1,min1;int flag=0,t=0,judg=0;for(int i=0; i<s.size(); i++){if(s[i]==' '){num=num/pow(10,t);if(judg==1)num=-num;b.push_back(num);t=0,num=0,flag=0,judg=0;}else if(s[i]=='.'){flag=1;}else if(s[i]=='-')judg=1;else{num=num*10+s[i]-'0';if(flag==1)t++;}}num=num/pow(10,t);if(judg==1)num=-num;b.push_back(num);find_m(b,max1,min1);}else if(n==2){vector<char> c;char max2,min2;for(int i=0; i<s.size(); i++){if(s[i]!=' ')c.push_back(s[i]);}find_m(c,max2,min2);}else if(n==3){vector<string> d;string str,max3,min3;str.clear();for(int i=0; i<s.size(); i++){if(s[i]==' '){d.push_back(str);str.clear();}elsestr+=s[i];}d.push_back(str);find_m(d,max3,min3);}elsecout<<"err"<<endl;return 0;
}