[2022/2/25]希冀实验一 顺序表的插入
- 题目详情
【问题描述】实现在顺序存储的有序表中插入一个元素(数据类型为整型),使表仍然有序。
【输入形式】第一行输入原线性表元素个数,第二行输入有序表中的元素,元素间空格分开,第三行输入要插入的元素值 。
【输出形式】输出插入后的有序序列。
【样例输入】7
3 5 6 8 11 30 66
22
【样例输出】
3 5 6 8 11 22 30 66
本题可基于以下文章的代码进行修改
- 题目主要步骤
1.定义顺序表
2.初始化顺序表
3.插入数据
4.添加数据
5.数据排序
6.输出数据
步骤1,2,3请前往顺序表的删除
- 添加数据
void add(list *a, int num)
{
a->data[a->length] = num;
a->length++;
}
- 排序
下面使用3种常用排序进行演示,同学们可以自行选取
1.选择排序
void sort(list *a)
{
int save = 0;
for(int i = 0;i < a->length; i++)
{
for(int j = i + 1;j < a->length; j++ )
{
if(a->data[i] > a->data[j])
{
save = a->data[i];
a->data[i] = a->data[j];
a->data[j] = save;
}
}
}
}
2.冒泡排序
void sort2(list *a)
{
int save = 0;
while(1)
{
short flag = 1;
for(int i = 0;i < a->length - 1; i++)
{
if(a->data[i] > a->data[i+1])
{
save = a->data[i];
a->data[i] = a->data[i+1];
a->data[i+1] = save;
flag = 0;
}
}
if(flag)
{
break;
}
}
}
3.插入排序
void sort3(list *a)
{
int tmp = 0;
for(int i = 1; i < a->length; i++)
{
for(int j = i; j > 0; j--)
{
if(a->data[j] < a->data[j-1])
{
tmp = a->data[j];
a->data[j] = a->data[j-1];
a->data[j-1] = tmp;
}
else
{
break;
}
}
}
return;
}
第一二种排序大一上已经学习过,大家应该比较熟悉了
如果仍有疑问的同学可以自行查阅相关资料进行巩固
冒泡排序
选择排序
第三种排序方式在本学期的数据结构课程中会出现
同时也是笔者认为最适合本题的排序方式
为什么这么说?
插入排序是将一个记录插入到已经有序的序列中,得到一个新的元素加一的有序序列,实现上即将第一个元素看成一个有序的序列,从第二个元素开始逐个插入得到一个完整的有序序列
根据本题题目要求
【问题描述】实现在顺序存储的有序表中插入一个元素(数据类型为整型),使表仍然有序。
可知原表本身就是已经排号续的数组,因此采用插入排序更合适
如果你对插入排序感兴趣,可以点击这里
在实现了对顺序表的排序后,本题也就没有什么难度了
- 源代码下载
顺序表插入.c
code by WWQ
作者:贡献者