#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h>
typedef int keytype;
#define MAXSIZE 20
clock_t clock( void );
typedef struct
{
keytype key;//某个元素的一些特征，可以还有其他的
}elemtype;
typedef struct
{
elemtype elem[MAXSIZE];
int length;
}SStable;//顺序表的结构
void Creatlist(SStable *LIST)//创建线性表，注意此处的LIST是指针类型，为了使返回这个线性表
{
int i;
printf("Please input how many the number is:\n");
scanf("%d", &LIST->length);//输入线性表的长度
printf("Please input the count of %d number：\n",LIST->length);
for(i=1;i<=LIST->length;i++)
{
scanf("%d",&LIST->elem[i].key);//注意此处的为LIST->elem而不是LIST.elem
}
printf("\n");
}
/*注意当LIST为指针类型的时候在调用起内部参数的时候要用-> 当LIST不为指针类型的时候用 . */ void SHowLIST(SStable LIST)//显示所构造的线性表内部的数据
{
int i;
printf("The number is:\n");
for(i=1;i<=LIST.length;i++)
printf("%5d",LIST.elem[i].key);
printf("\n");
}
void InsertSort(SStable L)//插入排序
{
int i,j;
for(i=2;i<=L.length;i++)
if(L.elem[i].key<L.elem[i-1].key)//将L.elem[i]插入到有序的子表中
{
L.elem[0]=L.elem[i];//复制为哨兵
for(j=i-1;L.elem[0].key<L.elem[j].key;j--)
L.elem[j+1]=L.elem[j];//记录后移
L.elem[j+1]=L.elem[0];//插入到正确的位置，
/*注意此处为什么是J+1，那是 因为上面的循环后j的值减了一。*/ }
SHowLIST(L);//显示数据
}
/*插入排序的思想是： 从i=2;开始若后面的那个元素的值小于前面的元素的值，则将那个元素复制给哨兵 再从末尾往后移一位，并将元素插入到正确的位置， */ int Search_SEQ(SStable ST,keytype key)//查找与自己想要找的数据的位置
{
int i;
ST.elem[0].key=key;//“哨兵”
for(i=ST.length;ST.elem[i].key!=key;--i);/*注意此处最后有一个分号 ，作用是到了某个地点i，就找到了匹配的那个地点了*/ return i;//返回位置
}
int SelectMaxkey(SStable L,int i)//用选择排序输出最大的值得位置
{
int j,temp,p;
p=i;
for(j=i+1;j<=L.length;j++)
{
if(L.elem[p].key<L.elem[j].key)
{ p=j;
}
}
return p;
}
void Select(SStable &L)//选择排序，从大到小排序
{
int i,j,temp;
for(i=1;i<L.length;i++)
{
j=SelectMaxkey(L,i);//寻找最大的坐标
if(i!=j)
{
L.elem[0]=L.elem[j];
L.elem[j]=L.elem[i];
L.elem[i]=L.elem[0];
}
}
}
int Partition(SStable &L,int low,int high)//快速排序将数字序列分成两部分
{
int pviotkey;
L.elem[0]=L.elem[low];//将第一个数字的位置给哨兵
pviotkey=L.elem[low].key;//将第一个数字设置为中轴数字
while(low<high)
{
while(low<high&&(L.elem[high].key>=pviotkey))
--high;/*注意此部分是若从最后面的数字要大于中轴数字， 则high--，从而找到比中轴数字小的数字*/ L.elem[low]=L.elem[high];//将后面比中轴数字小的数字位置移至前面
while(low<high&&L.elem[low].key<=pviotkey)
++low;/*注意此部分是若从最前面的数字要小于中轴数字， 则low++，从而找到比中轴数字大的数字*/ L.elem[high]=L.elem[low];//将比前面比中轴数字大的位置移至前面
}
L.elem[low]=L.elem[0];
return low;//返回中轴数字的位置
}
void Qsort(SStable &L,int low,int high)//快速排序
{
int part;
if(low<high)
{
part=Partition(L,low,high);//将这串数字以中轴数字分成两部分
Qsort(L,low,part-1);//对中轴线左边的部分进行快速排序
Qsort(L,part+1,high);//对中轴线右边的部分进行快速排序
}
}
void QsortFound(SStable L)//快速排序
{
Qsort(L,1,L.length);
SHowLIST(L);
}
long NOWTime()//时间函数
{
long now;
now=clock();
return now;
}
void main()
{
SStable Found;//注意类型
int number,i,n,function;
long now,end,now1,end1;
begin:
for(i=0;i<=25;i++)
printf("==");
printf("\n");
printf("1.构造线性表。\n");
printf("2.显示出线性表！\n");
printf("3.查找相应数字在线性表中的位置。\n");
printf("4.快速排序!\n");
printf("5.插入排序!\n");
printf("6.选择排序!\n");
for(i=0;i<=25;i++)
printf("==");
printf("\n");
printf("请输入相应操作：");
scanf("%d",&n);
switch(n)
{
case 1:Creatlist(&Found);
Sleep(2000);
system("cls");
goto begin;
case 2:SHowLIST(Found);
Sleep(2000);
system("cls");
goto begin;
case 3:
printf("Please input the Found of number is:\n");
scanf("%d",&number);
function=Search_SEQ(Found,number);
printf("The number of %d' location is\n",number);
printf("%d",function);
printf("\n");
Sleep(2000);
system("cls");
goto begin;
case 4:
now=NOWTime();
printf("快速查找的结果为：\n");
QsortFound(Found);//快速排序
end=NOWTime();
printf("快速排序所用的时间为：%fs\n",(double)(end-now)/CLOCKS_PER_SEC);
Sleep(2000);
system("cls");
goto begin;
case 5:InsertSort(Found);//插入排序
Sleep(2000);
system("cls");
goto begin;
case 6:
now1=NOWTime();
printf("选择排序的结果为：\n");
Select(Found);
SHowLIST(Found);
end1=NOWTime();
printf("选择排序所用的时间为：%fs\n",(double)(end1-now1)/CLOCKS_PER_SEC);
Sleep(2000);
system("cls");
goto begin;
case 0:
goto end;break;
default:printf("输入错误！\n");
}
end:printf("谢谢使用！\n");
}
