一个线性表有个元素(n-MAXsIZE,MAXSIZE 指线性表的最大长度)且递增。现有一元素工要插入到线性表的适当位置上,并保持线性表原有的顺序不变。设计程序实现。要求:(1)采用顺序存储表示实现:(2)n个元素用随机数生成():实现递增的方法:a[j]=a[i-1]r(代表一个较小的随机增量)
时间: 2024-03-01 19:52:22 浏览: 123
好的,根据您的要求,我来为您编写一个用于在递增有序的顺序存储线性表中插入元素的程序。以下是程序的思路和代码实现:
思路:
1. 首先读入线性表的长度n和插入元素x。
2. 然后利用随机数生成算法,生成n个随机数,存储到数组a中。
3. 对数组a进行冒泡排序,得到一个递增有序的线性表。
4. 利用二分查找算法,在递增有序的线性表中找到插入元素x的位置。
5. 将插入元素x插入到线性表中,并将线性表中的元素向后移动一位。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 100
int a[MAXSIZE];
int main()
{
int n, x, i, j, temp, low, high, mid;
// 读入线性表的长度n和插入元素x
printf("请输入线性表的长度n和插入元素x: \n");
scanf("%d%d", &n, &x);
// 生成n个随机数存储到数组a中
srand(time(NULL));
for (i = 0; i < n; i++)
{
a[i] = rand() % 100;
}
// 对数组a进行冒泡排序,得到一个递增有序的线性表
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
// 利用二分查找算法,在递增有序的线性表中找到插入元素x的位置
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (x <= a[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
// 将插入元素x插入到线性表中,并将线性表中的元素向后移动一位
for (i = n; i > low; i--)
{
a[i] = a[i - 1];
}
a[low] = x;
// 输出插入元素后的线性表
printf("插入元素后的线性表:\n");
for (i = 0; i < n + 1; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
```
注意:为了方便起见,本程序中生成的随机数的范围为0~99。如果需要生成更大的随机数,可以根据需要修改rand() % 100这一行代码。
阅读全文