? ? 通过C语言实现插入排序算法：对于少量排序的元素,插入排序是一个有效的算法,其操作过程类似于手中的扑克牌,从第二个元素从左往右循环检查比较,满足A[i]A[i-1],则交换A[i]与A[i-1]的值.往复循环直到最后一个元素比较完成.具体程序如下：
#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;
? ? ? ? ? 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++;
? //use insert_sort
? insert_sort(A,i+1); //A length is i+1
? return 0;
/*---test------------
* ------------------*/
以上程序使用的是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在数组上实现.具体算法描述如下：
从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素,将该元素移到下一位置
将新元素插入到该位置后
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目.该算法可以认为是插入排序的一个变种,称为二分查找排序.
范例程式码
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;
#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 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++)//输出排序后的结果
return 0;
主要是看懂这个函数 void InserSort(int a[],int n）
//C++课程设计---学生成绩管理系统
#include string.h
#include iostream.h
#include stdlib.h
#include windows.h
typedef struct studentinfo //结构体定义
int num;//学号
int sex;//性别,1为男性,0为女性
float math;//数学
float english;//英语
float politic;//政治
float chinese;//语文
float total;//总成绩
struct studentinfo *next;
}STUDENT;
#define FILENAME "D:\\1.txt"
//定义默认的数据库文件
//显示信息,延时
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)
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;
while(1)
system("cls");
cout"\t\t学生成绩管理系统\n";
cout"##########################################\n";
cout"#\t\t 1.新增学生信息\t\t #\n";
cout"请输入操作编号：";
cinmenu_Num;
switch (menu_Num)
case '1':
free_link(head);//释放链表空间
head=new_student();//新增学生信息
break;
cout"请输入要加载的数据库文件的路径"endl;
cinfile_name;
head=create_linkbyfile(file_name);//读取数据文件
if(head!=NULL)
cout"数据库"file_name"已加载"endl;
Sleep(DELAYTIME);
del_info(head);//删除学生信息
if (head==NULL)
cout"请先生成学生信息"endl;
else
cout"想将学生信息保存到哪个数据库文件?";
cout"请选择保存方式：0追加到文件末尾 1覆盖文件\n";
if(save_info(file_name,head,menu_Num-'0')==0)//0表示追加,1表示覆盖
cout"信息保存失败\n";
cout"数据已保存到"file_nameendl;
find_infile_printf(FILENAME);//数据库查询
pri_whole_link(head);
cout"返回主菜单? Y/N\t";
do
cinch;
}while(ch!='Y'ch!='y');
if((head=printf_sort(head))==NULL)
cout"数据库未加载"endl;
cout"选择其他方式排序? Y/N\t";
}while(ch=='Y'||ch=='y');
exit(0);
default:
cout"输入有误！请重新输入！"endl;
STUDENT * new_student()
//功能：创建学生信息（通过链表）
//返回值：头结点指针
STUDENT *pnew,*p,*head;
float *pfloat;
head=NULL;
pnew=(STUDENT *)malloc(sizeof(STUDENT)*1);
cout"请输入学生的学号(0表示取消)： ";
cinpnew-num;
if(0=pnew-num)
cout"请输入学生的姓名：";
cinpnew-name;
cout"请输入学生的性别：0/1\t";
cinpnew-sex;
if(pnew-sexpnew-sex-1)
cout"性别输入错误,0表示女性,1表示男性,请重新输入"endl;
cout"请依次输入学生的数学、英语、政治、语文成绩："endl;
cin*pfloat;
pnew-total+=*pfloat;
pfloat++;
head=pnew;
p-next=pnew;
p=pnew;
pnew-next=NULL;
cout"##########################该学生信息已生成#########################\n";
cout"建立另一个学生的信息? Y/N\t";
return head;
STUDENT* create_linkbyfile(char *filename)
//功能：读取文件,创建链表
//参数：如果filename不为空,则打开该文件,如果filename为空,要求输入文件位置
//创建的链表的所有结点的next全部修改,指向物理地址上的下一个结点
FILE *fp;
STUDENT *head,*ptemp,*pnew;
head=NULL;//初始化head为空
if(filename==NULL)//若filename为空,要求输入文件绝对地址
cout"请输入数据库文件的路径："endl;
if(NULL==(fp=fopen(file_name,"rb")))
cout"数据库连接失败\n";
if(NULL==(fp=fopen(filename,"rb")))
for(ptemp=NULL;;)
if(fread(pnew,sizeof(STUDENT),1,fp)!=NULL)
if(ptemp!=NULL)
ptemp-next=pnew;
ptemp=pnew;
ptemp-next=NULL;
free(pnew);
fclose(fp);
STUDENT *del_info(STUDENT *head)
//根据学号,删除链表的结点
int num;
cout"请输入要删除学生的学号：";
cinnum;
for(p1=head;p1!=NULL;)
if(p1-num==num)//找到
if(p1==head)//要删除的结点是头结点
head=p1-next;
cout"成功删除！！";
p1=p1-next;
int save_info(char *filename,STUDENT *head,int flag)
//功能：将链表按Binary写入文件末尾
//参数：
//1.filename文件名,绝对地址
//返回值：失败则返回0
STUDENT *p;
if(flag==0)
strcpy(openmethod,"ab+");//追加
strcpy(openmethod,"w");//覆盖
if(NULL==(fp=fopen(filename,openmethod)))//
cout"数据库连接失败"endl;
for(p=head;p;p=p-next)
if((fwrite(p,sizeof(STUDENT),1,fp))==NULL)
cout"数据库创建失败"endl;
int find_infile_printf(char *filename)
//功能：根据学号和姓名来查询某个学生
//参数：filename数据库文件
//返回值：失败返回0
//直接搜索文件,缺点是速度慢
//也可先根据文件创建链表,再搜索链表,缺点是如果文件较大,占用内存多
STUDENT stu;
if(filename==NULL)
memset(stu_name,0,sizeof(stu_name));
cout"查询学号或查询姓名? 1查询学号 0查询姓名";
//flag=1根据学号来查询,flag=0根据姓名来查询
if(num==1)
cout"输入要查询的学号：";
cout"正在为您查询学号为"num"的学生......"endl;
else if(num==0)
cout"输入要查询的姓名：";
cinstu_name;
cout"正在为您查询姓名为"stu_name"的学生......"endl;
cout"输入有误"endl;
if(NULL==(fp=fopen(filename,"rw")))
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";
int pri_whole_link(STUDENT *head)
//功能：显示整条链表的学生信息
//参数：head 头结点指针,如果head为空,返回空
STUDENT* p;
coutp-num"\t"p-name"\t"p-sex"\t"p-math"\t"p-english"\t"p-politic"\t"p-chinese"\t"p-totalendl;
STUDENT* printf_sort(STUDENT *head)
//功能：根据学号|某科目成绩|总成绩对链表进行排序,然后输出
//参数：head链表头指针,如果head为空,返回空
//返回值：返回新的链表的头结点指针
char num;
char flag;
cout"升序/降序输出? 0.降序1.升序";
cinflag;
if(flag'1'||flag'0')
cout"输入有误,请重新输入 0~1"endl;
for(p1=head;p1-next!=pfinished;)//对链表进行从大到小排序（这里用冒泡法）
//p1使之总是指向头结点,pfinished使之总是指向已排序好的最前面的结点
ptemp=p1;
if(flag=='1')
p1=reverse(p1);
pri_whole_link(p1);
cout"##########################信息显示完毕#########################\n";
return p1;
void free_link(STUDENT *head)
//释放链表空间,如果head,什么都不做
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("分配空间失败");
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;//代表插入成功