C博客作业04--数组

0.展示PTA总分（0----2）

展示2张关于“数组题目集”分数截图。

1.本章学习总结（3分）

1.1 学习内容总结

整理数组这章学习主要知识点，必须包含内容有：

1.1.1数组中如何查找数据，有哪些做法

二分查找

首先将数组元素排为升序排列
将集合中间元素与要查找元素比较，相等则返回
如果中间元素大于要查找元素，则在左半部查找，反之则在右半部查找
重复以上操作

int binarySearch(int* nums, int numsSize, int target)
{
	/** 定义变量low存放左子表 */
	int low = 0;
	/** 定义变量存放右子表 */
	int high = numsSize - 1;
	/** 定义变量存放中间位置 */
	int mid = 0;
	/** 当查找范围不为0时 */
	while(low <= high)
	{
		/** 求中间位置 */
		mid = (low + high)/2;
		/** 目标值大于中间值 */
		if(target > nums[mid])
			low = mid + 1;
		/** 目标值小于中间值 */
		else if(target < nums[mid])
			high = mid - 1;
		else
			return mid;
	}
	/** 目标值不存在 */
	return -1;
}

1.1.2数组中如何插入数据，怎么做，可以写个伪代码或动态图展示方法

可参考PTA7-6简化的插入排序
让要插入的数与每个元素逐一比较，当大于左边小于右边时，则右边的数据循环右移，给要插入的数留出位置。

#include<stdio.h>

int main()
{
    int N, a[100], i, j, X, temp;
    scanf("%d", &N);
    if (N > 0)
    {
        for (i = 0; i < N; i++)
        {
            scanf("%d", &a[i]);

        }
        scanf("%d", &X);
        if (X > a[N - 1])
            a[N] = X;
        else if (X < a[0])
        {
            for (i = N; i >= 0; i--)
            {
                a[i + 1] = a[i];

            }
            a[0] = X;
        }
        else
        {
            for (i = 0; i < N; i++)
            {
                if (a[i] < X&& a[i + 1] >= X)
                {
                    for (j = N; j > i; j--)
                    {
                        a[j + 1] = a[j];

                    }
                    a[i + 1] = X;

                }
            }
        }
        for (i = 0; i < N + 1; i++)
            printf("%d ", a[i]);
    }
    else if(N==0)
    {
        scanf("%d", &X);
    printf("%d ", X);
    }
}

1.1.3数组中如何删除数据，这个有多种做法，请一一展示。

删除一个数据
和上面插入数据类似，只不过循环右移变成了循环左移，填补被删除数据的位置
删除重复数据

1.1.4数组中目前学到排序方法，主要思路？

冒泡排序法
将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。
当初学习冒泡排序时找到的一张动图，很直观地说明问题：

#include<stdio.h>
int main()
{
    int a[100], N, K, i, j, temp, flag = 1;
    scanf("%d%d", &N, &K);
    for (i = 0; i < N; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < K; i++)
    {
        for (j = 0; j < N - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp;
            }
        }
    }
    for (i = 0; i < N; i++)
    {
        if (flag == 1)
        {
            printf("%d", a[i]); flag = 0;
        }
        else
        {
            printf(" %d", a[i]);
        }
    }

    return 0;
}

选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

#include<stdio.h>

int main()
{
    int a[10],i,n,m,min,j,flag=1;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n; i++)
    {
        min = 0;
        for (j = 0; j < n-i; j++)
        {
            
            if (a[j] < a[min])min = j;
        }
        m = a[n - i-1]; a[n - i-1] = a[min]; a[min]=m;
    }
    for (i = 0; i < n; i++)
    {
        if (flag == 1)
        {
            printf("%d", a[i]); flag = 0;
        }
        else
        {
            printf(" %d", a[i]);
        }
    }

    return 0;
}

1.1.5数组做枚举用法，有哪些案例？

7-5 调查电视节目受欢迎程度

#include<stdio.h>

int main() 
{
    int n, a[1000] = { 0 },i,num;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &num);
        a[num - 1]++;
    }
    for (i = 0; i < 8; i++)
        printf("%4d%4d
",i+1,a[i]);
    return 0;
    
}

1.1.6哈希数组用法，目前学过哪些案例，举例展示。

哈希数组适用于在大量数据中查找，删除重复值，其思想是用空间换时间，让每个数都与哈希数组中的下标对应起来。
参考PTA7-8有重复的数据，利用哈希数组法

#include<stdio.h>

int main() 
{
	int n, i, hash[100001] = { 0 }, num,flag=0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &num);
		if (hash[num] == 0)
			hash[num] = 1;
		else if (hash[num] == 1)
		{
			flag = 1;
			break;
		}
	}
		if (flag==1)
			printf("YES");
		else
			printf("NO");

}