递增顺序表插入

目录

问题描述 

程序设计

运行结果

程序分析

本节文章

问题描述 

【问题描述】

设有递增有序顺序表，实现其插入元素后依然有序。

【输入形式】

第一行输入一个N(N不大于100)；

第二行输入N个整数（假设输入序列按照递增顺序，以空格分隔）；

第三行输入一个整数M（欲插入数据）；

【输出形式】

输出插入M后的顺序表。

【样例输入】

5

12 25 35 98 125

77

【样例输出】

12 25 35 77 98 125

程序设计

#include
#include
#define SIZE 10
#define INCREAM 10
typedef struct list{int *data;int len;int size;
}list,*Plist;
int init_list(Plist L){L->data=(int *)malloc(sizeof(int)*SIZE);L->len=0;L->size=SIZE;return 1;
}
int creat_list(Plist L,int n){int i;if(L->len==L->size){L->data=(int*)realloc(L->data,(L->size+INCREAM)*sizeof(int));L->size+=INCREAM;}for(i=0;idata[i]);L->len++;}return 1;
}
int insert_sort_list(Plist L,int x){int i;if(L->len==L->size){L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));L->size+=INCREAM;}for(i=L->len-1;i>=0&&L->data[i]>x;i--){L->data[i+1]=L->data[i];}L->data[i+1]=x;L->len++;return 1;
} 
int print_list(Plist L){int i;for(i=0;ilen;i++){printf("%d ",L->data[i]);}printf("\n");return 1;
}
int main(){int n,x;list L;scanf("%d",&n);init_list(&L);creat_list(&L,n);scanf("%d",&x);insert_sort_list(&L,x);print_list(&L);
}

运行结果

程序分析

这是一个使用动态数组实现的插入排序的代码。主要思路是定义一个结构体用来存储动态数组，使用malloc函数初始化数组，并设置数组长度和大小。接下来使用scanf函数读入n个数字，并使用realloc函数对数组进行动态扩展，插入排序将新数字插入到数组中合适的位置。最后使用printf函数输出排序后的结果。

具体函数分析如下：

1. init_list函数：初始化动态数组。

2. creat_list函数：创建动态数组，先判断数组是否已满，若已满则使用realloc函数进行动态扩展。读入用户输入的n个数字，并将长度加1。

3. insert_sort_list函数：插入排序，先判断数组是否已满，若已满则使用realloc函数进行动态扩展。从数组最后一个元素开始往前寻找比插入元素x小的元素，将它们依次向后移动一个位置，最后将x插入到合适的位置，再将长度加1。

4. print_list函数：循环输出数组中的元素。

在主函数中，首先读入n，然后使用init_list函数初始化动态数组，接着使用creat_list函数读入n个数字，并使用insert_sort_list函数将新数字插入到数组中，最后使用print_list函数循环输出结果。

本节文章

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！