Question

一道C语言难题，没有思路，请教大神怎么做？

一维整型数组，长度为N，随机初始化N-1个元素后采用选择法进行升序排列。然后从键盘输入一个数，将该数插入数组，使数组仍然有序。

Answer 1

定义数组
循环，初始化，可以用random
选择法排序，双重循环搞定，不会的话随便搜一下，一堆样例
输入新值
从后向前循环比较
如果当前位置值比新输入的大，那么后移一位
否则退出循环
退出位置的下一个位置就是插入点
大致就是
for(i=N-2;a[i]>v &&i>=0;i--)
a[i+1]=a[i];

a[i+1]=v;

Answer 2

#include <stdio.h>
#include <conio.h>

#define ARR_LEN 255 /*数组长度上限*/
#define elemType int /*元素类型*/

#define status int	/* 状态型变量 */
#define OVERFLOW -1	/* 溢出状态码 */
#define ERROR 0		/* 错误状态码 */
#define OK 1		/* 正确状态码 */

/* 选择排序 */
/* 1. 将初始数组分为两段，前段为已排序数组，后段为未排序数组 */
/* 2. 在未排序数组中寻找最值元素，将其然后放到已排序数组的末尾 */
/* 3. 对所有元素均重复以上步骤，直至最后一个元素 */
/* elemType arr[]: 排序目标数组; int len: 元素个数 */
void selectionSort (elemType arr[], int len) {
	elemType temp;
	int i, j, k;
	for(i=0; i<len-1; i++) { /*外循为排序趟数，len个数进行len-1趟 */
    	k = i; /* 假设当前趟的第一个数为最小值，其下标记在k中（升序为寻找最小值，逆序反之） */
    	for(j=i+1; j<len; j++) /* 从下一个数到最后一个数之间依次判断 */
			if(arr[j] < arr[k]) /* 若k之后有更小的元素 */
				k = j; /* 则将其下标记更新至k中 */
			if(k != i) { /* 若k不为最初的i值，说明在其后找到比其更小的元素 */
				temp = arr[k];
				arr[k] = arr[i];
				arr[i] = temp;
			} /* 则交换最小值和当前数组第一个元素 */
	}
}

/* 校验数组是否有序 */
int isOrdered (elemType arr[], int len) {
	elemType *p = arr;
	while (p < arr+len-1) { /* 扫描数组至倒数第二个元素 */
		if (*p > *(p+1)) /* 当前元素大于后继元素 */
			return 0;
		p++;
	}
	return 1;
}

/* 有序数组中插入新元素 */
status arrInsert (elemType arr[], int *len, elemType e) {
	elemType *p = arr, *q = arr + *len;
	if (*len >= ARR_LEN) /* 数组空间溢出 */
		return OVERFLOW;
	if (isOrdered (arr, *len) == 0) /* 数组无序 */
		return ERROR;
	while (p < arr+*len) { /* 寻找插入位置 */
		if (*p >= e)
			break;
		p++;
	}
	while (q >= p) { /* p位置及之后的元素均后移一位 */
		*(q+1) = *q;
		q--;
	}
	*p = e; /* e插入p位置 */
	(*len)++; /* 数组长度+1 */
	return OK; 
}

/* 打印数组 */
/* elemType arr[]: 打印目标数组; int len: 元素个数 */
void printArray (elemType arr[], int len) {
	int i;
	for (i=0; i<len; i++)
		printf ("%d\t", arr[i]);
	putchar ('\n');
}

int main (void) {
	elemType arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};
    int len = 10;
    elemType e;
    status insertStatus;
    
	printf ("原始数组：\n");
	printArray (arr, len);
	putchar ('\n');
	
	printf ("排序后数组：\n");
	selectionSort (arr, len);
	printArray (arr, len);
    putchar ('\n');
    
    printf ("输入要插入的元素值：");
    scanf ("%d", &e);
	printf ("插入元素%d：\n", e);
	insertStatus = arrInsert (arr, &len, e);
	if (insertStatus == OK)
		printArray (arr, len);
	else if (insertStatus == OVERFLOW)
		printf ("数组空间溢出！\n");
	else if (insertStatus == ERROR)
		printf ("数组无序！\n");
    
	getch (); /*屏幕暂留*/
	return 0;
}

如有问题，可以点击头像联系我