通过C语言实现插入排序算法：对于少量排序的元素，插入排序是一个有效的算法，其操作过程类似于手中的扑克牌，从第二个元素从左往右循环检查比较，满足A[i]A[i-1],则交换A[i]与A[i-1]的值。往复循环直到最后一个元素比较完成。具体程序如下：
成都创新互联公司主要为客户提供服务项目涵盖了网页视觉设计、VI标志设计、营销推广、网站程序开发、HTML5响应式网站建设公司、手机网站开发、微商城、网站托管及网站维护、WEB系统开发、域名注册、国内外服务器租用、视频、平面设计、SEO优化排名。设计、前端、后端三个建站步骤的完善服务体系。一人跟踪测试的建站服务标准。已经为成都汽车玻璃修复行业客户提供了网站建设服务。
#include stdio.h
#includeconio.h
/*----------
*INSERT_SORT
*
* args
* A[] int[],the number of A arrary
* len int ,A length
*
------------*/
void insert_sort(int A[],int len){
int i,j,key;
//printf("A length %d\n",len); //output arrary length
for(j=1;jlen;j++){
key=A[j];
i=j-1;
while (i-1A[i]key) { //i from 0 to 5,so i-1
A[i+1]=A[i];
i=i-1;
A[i+1]=key;
}
}
//output A arrary
for(i=0;ilen;i++)
printf("%d ",A[i]);
}
int main()
{
int A[10];
int i=0;
char c;
while(1){
scanf("%d",A[i]); //input unmbers
c=getchar();
if(c=='\n')
break;
i++;
}
//printf("%d %d %d %d %d %d %d %d\n",A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7]);
//use insert_sort
insert_sort(A,i+1); //A length is i+1
return 0;
}
/*---test------------
* input 5 2 4 6 1 3
*
* output 1 2 3 4 5 6
* ------------------*/
以上程序使用的是Qt Creator 工具，用C语言实现，经调试已经通过。
但依然有个问题：在main（）函数中调用insert_sort(int A[])时，若单传数组参数A[]，再在insert_sort(int A[])函数里面调用len=sizeof(A)/sizeof(int)计算数组实际输入长度，但是得不到实际输入的数组长度，所以只能采用实参的方式将具体数字通过len传到insert_sort(int A[],int len )；在insert_sort(int A[])接收到A数组后直接计算A[]实际输入长度，有什么办法可以实现？
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
范例程式码
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i=last;i++)
{
temp = array[i];
j=i-1;
while((j=first) (array[j] temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
#include stdio.h
#include "4-1 CreateData.c" //生成随机数的函数
#define ARRAYLEN 10 //需要排序的数据元素数量
void InserSort(int a[],int n)//直接插入排序
{
int i,j,t;
for(i=1;in;i++)
{
t=a[i]; //取出一个未排序的数据
for(j=i-1;j=0 ta[j];--j) //在排序序列中查找位置
a[j+1]=a[j]; //向后移动数据
a[j+1]=t; //插入数据到序列
}
}
int main()
{
int i,a[ARRAYLEN]; //定义数组
for(i=0;iARRAYLEN;i++) //清空数组
a[i]=0;
if(!CreateData(a,ARRAYLEN,1,100)) //判断生成随机数是否成功
{
printf("生成随机数不成功!\n");
getch();
return 1;
}
printf("原数据:"); //输出生成的随机数
for(i=0;iARRAYLEN;i++)
printf("%d ",a[i]);
printf("\n");
InserSort(a,ARRAYLEN); //调用插入排序函数
printf("排序后:");
for(i=0;iARRAYLEN;i++) //输出排序后的结果
printf("%d ",a[i]);
printf("\n");
getch();
return 0;
}
主要是看懂这个函数 void InserSort(int a[],int n）
//C++课程设计---学生成绩管理系统
#include stdio.h
#include string.h
#include iostream.h
#include stdlib.h
#include windows.h
typedef struct studentinfo //结构体定义
{
int num;//学号
char name[64];//姓名
int sex;//性别，1为男性，0为女性
float math;//数学
float english;//英语
float politic;//政治
float chinese;//语文
float total;//总成绩
struct studentinfo *next;
}STUDENT;
#define FILENAME "D:\\1.txt"
//定义默认的数据库文件
#define DELAYTIME 1500
//显示信息，延时
void create_menu();
STUDENT * new_student();
STUDENT* create_linkbyfile(char *);
STUDENT *del_info(STUDENT *);
int save_info(char *,STUDENT *,int);
int find_infile_printf(char *);
int pri_whole_link(STUDENT *);
STUDENT* printf_sort(STUDENT *);
void free_link(STUDENT *);
void main() //主函数
{
create_menu();
}
STUDENT * reverse(STUDENT *head)
//功能：链表反转顺序
//参数：head链表头结点指针
{
STUDENT *ptemp,*p1;
if(head==NULL)
{
return 0;
}
p1=head;//p1使之永远指向排好序的第一个结点，初值为head，head使之永远是已经排好序的最后一个结点
while(head-next!=NULL)//本次循环使ptemp排好序
{
ptemp=head-next;//ptemp指向未排好序的第一个结点
head-next=ptemp-next;//
ptemp-next=p1;//ptemp也排好序了，ptemp变成排好序的第一个结点了
p1=ptemp;//再次让p1成为第一个排好序的结点
}
return p1;//头结点为第一个结点
}
void create_menu()
//功能：输出功能菜单，提供人-机接口
{
char menu_Num;
STUDENT *head=NULL;
char ch;
char file_name[256];
while(1)
{
system("cls");
cout"\t\t学生成绩管理系统\n";
cout"##########################################\n";
cout"#\t\t 1.新增学生信息\t\t #\n";
cout"#\t\t 2.加载数据库\t\t #\n";
cout"#\t\t 3.删除学生信息\t\t #\n";
cout"#\t\t 4.保存学生信息\t\t #\n";
cout"#\t\t 5.数据库查询\t\t #\n";
cout"#\t\t 6.原序输出\t\t #\n";
cout"#\t\t 7.排序输出\t\t #\n";
cout"#\t\t 8.退出\t\t\t #\n";
cout"##########################################\n";
cout"请输入操作编号：";
cinmenu_Num;
switch (menu_Num)
{
case '1':
free_link(head);//释放链表空间
head=new_student();//新增学生信息
break;
case '2':
free_link(head);//释放链表空间
cout"请输入要加载的数据库文件的路径"endl;
cinfile_name;
head=create_linkbyfile(file_name);//读取数据文件
if(head!=NULL)
{
cout"数据库"file_name"已加载"endl;
Sleep(DELAYTIME);
}
break;
case '3':
del_info(head);//删除学生信息
break;
case '4'://保存学生信息
if (head==NULL)
{
cout"请先生成学生信息"endl;
Sleep(DELAYTIME);
}
else
{
cout"想将学生信息保存到哪个数据库文件？";
cinfile_name;
cout"请选择保存方式：0追加到文件末尾 1覆盖文件\n";
cinmenu_Num;
if(save_info(file_name,head,menu_Num-'0')==0)//0表示追加，1表示覆盖
{
cout"信息保存失败\n";
}
else
{
cout"数据已保存到"file_nameendl;
Sleep(DELAYTIME);
}
}
break;
case '5':
find_infile_printf(FILENAME);//数据库查询
break;
case '6'://原序输出信息
pri_whole_link(head);
cout"返回主菜单？ Y/N\t";
do
{
cinch;
}while(ch!='Y'ch!='y');
break;
case '7'://排序输出信息
do
{
if((head=printf_sort(head))==NULL)
{
cout"数据库未加载"endl;
Sleep(DELAYTIME);
break;
}
else
{
cout"选择其他方式排序？ Y/N\t";
cinch;
}
}while(ch=='Y'||ch=='y');
break;
case '8':
free_link(head);//释放链表空间
exit(0);
break;
default:
cout"输入有误！请重新输入！"endl;
Sleep(DELAYTIME);
break;
}
}
}
STUDENT * new_student()
//功能：创建学生信息（通过链表）
//返回值：头结点指针
{
STUDENT *pnew,*p,*head;
float *pfloat;
char ch;
head=NULL;
do
{
system("cls");
pnew=(STUDENT *)malloc(sizeof(STUDENT)*1);
cout"请输入学生的学号(0表示取消)： ";
cinpnew-num;
if(0=pnew-num)
{
break;
}
cout"请输入学生的姓名：";
cinpnew-name;
while(1)
{
cout"请输入学生的性别：0/1\t";
cinpnew-sex;
if(pnew-sexpnew-sex-1)
{
cout"性别输入错误，0表示女性，1表示男性，请重新输入"endl;
}
else
{
break;
}
}
cout"请依次输入学生的数学、英语、政治、语文成绩："endl;
for(pnew-total=0,pfloat=pnew-math;pfloatpnew-math+4;)
{
cin*pfloat;
if(*pfloat0||*pfloat150)
{
cout"成绩输入错误，只能为0~150"endl;
}
else
{
pnew-total+=*pfloat;
pfloat++;
}
}
if(head==NULL)
{
head=pnew;
}
else
{
p-next=pnew;
}
p=pnew;
pnew-next=NULL;
cout"##########################该学生信息已生成#########################\n";
cout"建立另一个学生的信息？ Y/N\t";
cinch;
}while(ch=='Y'||ch=='y');
return head;
}
STUDENT* create_linkbyfile(char *filename)
//功能：读取文件，创建链表
//参数：如果filename不为空，则打开该文件，如果filename为空，要求输入文件位置
//创建的链表的所有结点的next全部修改，指向物理地址上的下一个结点
{
system("cls");
FILE *fp;
STUDENT *head,*ptemp,*pnew;
head=NULL;//初始化head为空
if(filename==NULL)//若filename为空，要求输入文件绝对地址
{
char file_name[256];
cout"请输入数据库文件的路径："endl;
cinfile_name;
if(NULL==(fp=fopen(file_name,"rb")))
{
cout"数据库连接失败\n";
return 0;
}
}
else
{
if(NULL==(fp=fopen(filename,"rb")))
{
cout"数据库连接失败\n";
return 0;
}
}
for(ptemp=NULL;;)
{
pnew=(STUDENT *)malloc(sizeof(STUDENT)*1);
if(fread(pnew,sizeof(STUDENT),1,fp)!=NULL)
{
if(ptemp!=NULL)
{
ptemp-next=pnew;
}
else
{
head=pnew;
}
ptemp=pnew;
}
else
{
if(ptemp!=NULL)
{
ptemp-next=NULL;
}
else
{
head=NULL;
}
free(pnew);
break;
}
}
fclose(fp);
return head;
}
STUDENT *del_info(STUDENT *head)
//根据学号，删除链表的结点
{
system("cls");
STUDENT *p1,*p2;
int num;
if (head==NULL)
{
cout"数据库未加载"endl;
Sleep(DELAYTIME);
return 0;
}
cout"请输入要删除学生的学号：";
cinnum;
for(p1=head;p1!=NULL;)
{
if(p1-num==num)//找到
{
if(p1==head)//要删除的结点是头结点
{
head=p1-next;
}
else
{
p2-next=p1-next;
}
cout"成功删除！！";
}
p2=p1;
p1=p1-next;
}
return head;
}
int save_info(char *filename,STUDENT *head,int flag)
//功能：将链表按Binary写入文件末尾
//参数：
//1.filename文件名，绝对地址
//2.head指向链表的头结点
//3.flag 0追加或1覆盖数据
//返回值：失败则返回0
{
system("cls");
FILE *fp;
STUDENT *p;
char openmethod[8];
if(flag==0)
{
strcpy(openmethod,"ab+");//追加
}
else
{
strcpy(openmethod,"w");//覆盖
}
if(NULL==(fp=fopen(filename,openmethod)))//
{
cout"数据库连接失败"endl;
Sleep(DELAYTIME);
return 0;
}
else
{
for(p=head;p;p=p-next)
{
if((fwrite(p,sizeof(STUDENT),1,fp))==NULL)
{
cout"数据库创建失败"endl;
return 0;
}
}
}
fclose(fp);
return 1;
}
int find_infile_printf(char *filename)
//功能：根据学号和姓名来查询某个学生
//参数：filename数据库文件
//返回值：失败返回0
//直接搜索文件，缺点是速度慢
//也可先根据文件创建链表，再搜索链表，缺点是如果文件较大，占用内存多
{
system("cls");
FILE *fp;
STUDENT stu;
int num;
char stu_name[64];
char ch;
if(filename==NULL)
{
return 0;
}
do
{
memset(stu_name,0,sizeof(stu_name));
cout"查询学号或查询姓名？ 1查询学号 0查询姓名";
//flag=1根据学号来查询，flag=0根据姓名来查询
cinnum;
if(num==1)
{
cout"输入要查询的学号：";
cinnum;
cout"正在为您查询学号为"num"的学生……"endl;
}
else if(num==0)
{
cout"输入要查询的姓名：";
cinstu_name;
cout"正在为您查询姓名为"stu_name"的学生……"endl;
}
else
{
cout"输入有误"endl;
return 0;
}
if(NULL==(fp=fopen(filename,"rw")))
{
cout"数据库连接失败\n";
return 0;
}
else
{
while(fread(stu,sizeof(STUDENT),1,fp)!=NULL)
{
if(strcmp(stu.name,stu_name)==0||stu.num==num)
{
cout"学号\t姓名\t性别\t数学\t英语\t政治\t语文\t总成绩\n";
//输出该学生的所有信息
coutstu.num"\t"stu.name"\t"stu.sex"\t"stu.math"\t"stu.english"\t"stu.politic"\t"stu.chinese"\t"stu.totalendl;
//不加break;可支持多个相同数据的索引
}
}
}
cout"##########################查询完毕#########################\n";
cout"查询另一个学生的信息？ Y/N\t";
cinch;
}while(ch=='Y'||ch=='y');
fclose(fp);
return 1;
}
int pri_whole_link(STUDENT *head)
//功能：显示整条链表的学生信息
//参数：head 头结点指针，如果head为空，返回空
{
system("cls");
STUDENT* p;
if (head==NULL)
{
cout"数据库未加载"endl;
Sleep(DELAYTIME);
return 0;
}
cout"学号\t姓名\t性别\t数学\t英语\t政治\t语文\t总成绩\n";
for(p=head;p;p=p-next)
{
coutp-num"\t"p-name"\t"p-sex"\t"p-math"\t"p-english"\t"p-politic"\t"p-chinese"\t"p-totalendl;
}
return 1;
}
STUDENT* printf_sort(STUDENT *head)
//功能：根据学号|某科目成绩|总成绩对链表进行排序，然后输出
//参数：head链表头指针，如果head为空，返回空
//返回值：返回新的链表的头结点指针
{
system("cls");
STUDENT *p1,*p2,*ptemp,*pfinished=NULL;
char num;
char flag;
if (head==NULL)
{
return 0;
}
cout"选择排序依据 0.数学成绩1.英语成绩2.政治成绩3.语文成绩4.总成绩\n";
while(1)
{
cinnum;
if(num'4'||num'0')
{
cout"输入有误，请重新输入 0~4"endl;
}
else
{
break;
}
}
cout"升序/降序输出？ 0.降序1.升序";
while(1)
{
cinflag;
if(flag'1'||flag'0')
{
cout"输入有误，请重新输入 0~1"endl;
}
else
{
break;
}
}
for(p1=head;p1-next!=pfinished;)//对链表进行从大到小排序（这里用冒泡法）
//p1使之总是指向头结点，pfinished使之总是指向已排序好的最前面的结点
//ptemp作为中介，保存p2的上一个结点
{
for(p2=p1;p2-next!=pfinished;)
{
if(*((p2-math)+num-'0')*((p2-next-math)+num-'0'))//p2的值小于p2-next的值，交换 ptemp p2 p2-next
{
if(p2==p1)//头结点要交换
{
p1=p2-next;
p2-next=p1-next;
p1-next=p2;
ptemp=p1;
}
else
{
ptemp-next=p2-next;
ptemp=p2-next;
p2-next=ptemp-next;
ptemp-next=p2;
}
}
else//不需要交换，则p2、ptemp前进1位
{
ptemp=p2;
p2=p2-next;
}
}
pfinished=p2;
}
if(flag=='1')
{
p1=reverse(p1);
}
pri_whole_link(p1);
cout"##########################信息显示完毕#########################\n";
return p1;
}
void free_link(STUDENT *head)
//释放链表空间，如果head，什么都不做
{
STUDENT *p1,*p2;
for(p1=head;p1;p1=p2)
{
p2=p1-next;//先保存,否则
free(p1);//free后 p1-next数据丢失
}
}
这是数据结构中标准的线性表插入程序，但是它不是真正的c语言，而是类c哦。
status Insertlist(Sqlist L,int i,Elemtype e){
Elemtype *p; //在这里定义了一个*p的指针，目的是找到链表中每个结点的首地址就可以了，不用找一个结点的所用地址啊
int j;
if(L.length==L.listsize) //L.listsize是代表的表的上限值，是事先设定好的
printf("内存分配空间已不够，请重新分配:\n");
p=L.elem;//这条语句应该写在下一条语句的后面，也就是分配后的地址给到临时指针变量p中
L.elem=(Elemtype *)realloc(p,(LISTSIZE+L.listsize)*sizeof(Elemtype));
//这条语句是想一下子分配足够大的线性表空间，realloc在C中不认可的，实现时还要用malloc，这里只是设计实现的，而分配成功后L.elem只是得到分配单元的首地址，不成功则是空值。
if(!p){
printf("分配空间失败");
exit(0);
}
L.elem=p;//这条语句应该没用吧
L.length++;//这条语句应该放在成功插入的后面，也就是return 1;语句之前才对
L.listsize=L.listsize+LISTSIZE_INCE;
if(i1||iL.length){ //这里用到的是运算符||，代表是“或”，也就是说i1代表输入时误操作造成，而iL.length代表输入的位置超出表中数据的个数，位置找不到。
printf("插入位置输入不正确，请重新操作:\n");
return 0;//代表插入失败
}
else{
for(j=L.length-1;j=i;j--)//从i到最后表尾顺次下移，腾出i的位置
L.elem[j+1]=L.elem[j];
L.elem[i]=e;//将数据插入到i的位置中
return 1;//代表插入成功
}
return 1;
}
