0.展示PTA总分
1.本章学习总结
1.1二分法查找
1.首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
2.如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。
3.如果某一步数组为空，则表示找不到目标元素。
int binary( int *a, int key, int n )
{
int left = 0, right = n - 1, mid = 0;
mid = ( left + right ) / 2;
while( left < right && a[mid] != key )
{
if( a[mid] < key ) {
left = mid + 1;
}else if( a[mid] > key ) {
right = mid - 1;
}else {
return mid;
}
mid = ( left + right ) / 2;
}
if( a[mid] == key ) return mid;
return -1;
}
1.2数组中插入数据
1.找到数据插入的位置，移动数组并插入数组。
#include <stdio.h>
main()
{
int n,i,j,x,a[11];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&x);
i=0;
while(a[i]<x&&i<n)
i++;
for (j=n-1;j>=i;j--)
{
a[j+1]=a[j];
}
a[i]=x;
for(i=0;i<n+1;i++)
printf("%d ",a[i]);
}
1.3数组中删除数据
完成数组元素的移动功能：假设数组有n个元素，输入一个数x，把数组的第x个位置的元素删除了，后面的元素依次前进一个位置。 重复若干次这样的删除，得到最后的结果。
#include<stdio.h>
int main()
{
int a[101], n, k,t,temp;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
for (int i = 1; i <= k; i++)
{
scanf("%d", &t);
a[t] = 0;
for (int j = t; j <= n; j++)
a[j] = a[j + 1];
}
for (int i = 1; i <= n - k; i++)
if (i == 1)
printf("%d", a[i]);
else
printf(" %d", a[i]);
return 0;
}
1.4排序
1.冒泡排序
从尾部开始比较相邻的两个元素，如果尾部的元素比前面的大，就交换两个元素的位置。往前对每个相邻的元素都做这样的比较、交换操作，这样到数组头部时，第 1 个元素会成为最大的元素。重新从尾部开始第 1、2 步的操作，除了在这之前头部已经排好的元素。继续对越来越少的数据进行比较、交换操作，直到没有可比较的数据为止，排序完成。
#include<stdio.h>
int *bubble_sort(int arr[], int len);
int main() {
int *result, len;
int data[] = {12, 43, 23, 13, 65, 17, 98, 45, 67, 88};
len = (int)sizeof(data) / sizeof(*data);
printf("使用冒泡排序前的原始数据是：");
for (int i = 0; i < len; i++) {
printf("%3d", data[i]);
}
printf("
");
result = bubble_sort(data, len);
printf("使用冒泡排序后的数据是：");
for (int j = 0; j < len; j++) {
printf("%3d", *(result + j));
}
return 0;
}
int *bubble_sort(int arr[], int len) {
int temp;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
printf("第%d次循环排序后结果：", i + 1);
for (int k = 0; k < len; k++) {
printf("%3d", arr[k]);
}
printf("
");
}
return arr;
}
2.选择排序
首先，选出最小的数，放在第一个位置；然后，选出第二小的数，放在第二个位置；以此类推，直到所有的数从小到大排序。
#include<stdio.h>
int main()
{
int array[10];
//输入初始值
for(int i=0;i<10;i++)
{
scanf("%d",&array[i]);
}
for(int i = 0;i<10;i++)
{
for(int j = i;j<10;j++)
{
//如果i位置的之比后面的值大，就交换，通过这样交换后，0-9依次增大
int tmp = 0;
//printf("%d %d
",array[i],array[j]);
if(array[i]>array[j])
{
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
//输出结果
for(int i = 0;i<10;i++)
{
printf("%d ",array[i]);
}
printf("
");
return 0;
}
1.5数组做枚举
统计单词的个数：
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s[1000];
int n=0,t=0;
while((s[n]=getchar())!='
')
{
n++;
}
s[n]=' '; //0-n
for(int i=0;i<=n;i++)
if(s[i]!=' '&&s[i+1]==' ')
t+=1;
printf("%d",t);
return 0;
}
1.6哈希数组
有重复的数据I:
#include<stdio.h>
using namespace std;
int main()
{
int a[100001] = { 0 }, n, t, flag = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &t);
a[t]++;
if (a[t] > 1)
flag = 1;
}
if (flag)
printf("YES");
else
printf("NO");
return 0;
}
2.PTA实验作业
2.1删除重复的字符
#include<bits/stdc++.h>
using namespace std;
int main()
{
int hash[128]={0};
for(char ch=getchar();ch!='
';ch=getchar())
hash[ch]++;
for(int i=0;i<128;i++)
if(hash[i])
cout<<char(i);
return 0;
}
2.2找鞍点
#include <stdio.h>
int main()
{
int flag, i, j, hang, lie, n;
int a[6][6];
int repeat, ri;
scanf("%d", &repeat);
for(ri = 1; ri <= repeat; ri++){
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
hang=0; lie=0; flag=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
if(a[i][j]>=a[i][lie] && j!=lie) lie=j; /*有并列极值元素，最后一个是鞍点*/
flag=1;
for(hang=0;hang<n;hang++){
if(a[hang][lie]<a[i][lie]){
flag=0;
break;
}
}
if(flag) break;
}
if(flag) printf("%d %d",i,lie);
else printf("NONE");
return 0;
}
}
2.3切分表达式
#include<iostream>
using namespace std;
int main()
{
string str;
cin>>str;
for(int i=0;i<str.length();i++){
printf("%c",str[i]);
if(str[i]>='0'&&str[i]<='9'){
if(str[i+1]<'0'||str[i+1]>'9'){
if(str[i+1]!='.'){
printf("
");
}
}
}else if(str[i]=='*'||str[i]=='/'){
printf("
");
}else if(str[i]==')'||str[i]=='('){
printf("
");
}else if(str[i]=='+'||str[i]=='-'){
if(str[i-1]!='('&&i!=0){
printf("
");
}
}
}
return 0;
}