数据结构C语言版（作业）109页

秒速五厘米 2022-04-16 00:50 235阅读 0赞

1）统计字符串中不同字符出现的次数，要求 即使多次查找字符时 时间复杂度仍为O（n）

#include<iostream>
    using namespace std;
    char s;
    int a[62]={0};
    int main(){
    	cout<<"请输入一串字符(#结尾)："; 
    	cin>>s;
    	while(s!='#')
    	{
    	   if(s<='9'&&s>='0')
    		  a[s-'0']++;
    	   else if(s<='Z'&&s>='A')
    		 a[s-'A'+10]++;
    	   else
    		 a[s-'a'+36]++;
    	  cin>>s;
    	}
    	while(1){
    		cout<<"请输入需要查询的字符（#退出）：";
    		char c;
    		cin>>c;
    		if(c<='9'&&c>='0')
    		   cout<<"    "<<c<<"的个数为："<<a[c-'0']<<endl;
    		else if(c<='Z'&&c>='A')
    		   cout<<"    "<<c<<"的个数为："<<a[c-'A'+10]<<endl;
    		else if(c<='z'&&c>='a')
    		   cout<<"    "<<c<<"的个数为："<<a[c-'a'+36]<<endl;
    		else
    		 return 0;
    	}
    	return 0;
    }

2）递归算法实现字符串逆序存储，要求不另设串储存空间（算法设计第二题）

#include<iostream>
    #include<cstring>
    using namespace std;
    char s[1001];
    void reverse(char *s) {
    	int len=strlen(s);//字符长度  每次递归长度减二 
    	if(len>1){
    		char temp=s[0];
    		s[0]=s[len-1];
    		s[len-1]='\0';
    		reverse(s+1);
    		s[len-1]=temp;
    	}
    }
    int main(){
    	cout<<"输入一串字符："; 
    	cin>>s;
    	reverse(s);
    	cout<<"反转之后为："; 
    	for(int i=0;i<strlen(s);i++)
    	 cout<<s[i];
    	 return 0;
    }

3）n个数存放在数组A\[1...n\]中，将所有整数放在所有负数的前面  时间复杂度为O(n)   (算法设计第六题)

#include<iostream>
    using namespace std;
    int a[1001];
    int n,k=0;
    int main(){
    	cout<<"请输入数据个数："; 
    	cin>>n;
    	cout<<"输入数据："; 
    	for(int i=1;i<=n;i++)
    	 cin>>a[i];
    	for(int i=1;i<=n;i++)
    	{
    		if(a[i]>=0) //整数 
    		swap(a[i],a[k++]); //与下标为K的元素交换  每次k++ 
    	}
    	for(int i=1;i<=n;i++)
    	 cout<<a[i]<<" ";
    	 return 0;
    }