湘潭大学 数据结构实验7 实验报告 源代码 查找和排序算法Word文件下载.docx
《湘潭大学 数据结构实验7 实验报告 源代码 查找和排序算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《湘潭大学 数据结构实验7 实验报告 源代码 查找和排序算法Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
if（!
L.elem）exit（OVERFLOW）;
L.listsize=LIST_INIT_SIZE;
L.length=0;
returnOK;
}
statusBuild（SqList&
L）//建立表
{inti;
printf（"
请输入元素个数n和n个元素\n"
）;
scanf（"
%d"
&
n）;
if（n>
LIST_INIT_SIZE）//如果n大于当前空间
{L.elem=（ElemType*）realloc（L.elem,（n+LISTINCREMENT）*sizeof（ElemType））;
L.listsize=n+LISTINCREMENT;
for（i=0;
i<
n;
i++）
L.elem+i）;
L.length=n;
voidSort（SqList&
L）//冒泡排序（升序）
{inti,j,t;
for（i=1;
L.length;
for（j=0;
j<
L.length-i;
j++）
{if（*（L.elem+j）>
*（L.elem+j+1））
{t=*（L.elem+j）;
*（L.elem+j）=*（L.elem+j+1）;
*（L.elem+j+1）=t;
}}}
voidsunxv（SqList&
L,intx）//顺序查找函数
{inti,k=0;
{if（x==*（L.elem+i））
{printf（"
已找到您查找的元素:
%d\n"
x）;
k=1;
break;
}}
if（k==0）
未找到您查找的元素\n"
interfen（SqList&
L,intx）//二分法查找函数
{intleft,mid,right;
left=0;
right=n-1;
while（left<
=right）
{mid=（left+right）/2;
if（*（L.elem+mid）<
x）
left=mid+1;
elseif（*（L.elem+mid）>
right=mid-1;
else
return0;
}}
intmain（）
{intop,x,sign=1;
SqListL,Lb;
InitList（L）;
Build（L）;
Sort（L）;
while（sign）
请选择要执行的查找方式：
\n【1】顺序查找\n【2】二分查找\n【0】退出\n"
op）;
if（op==0）
{sign=0;
continue;
请选择要查找的元素：
\n"
x）;
if（op==1）
sunxv（L,x）;
elseif（op==2）
erfen（L,x）;
输入错误\n"
2.几种排序算法：
#defineQ1000
typedefstruct{
char*base;
intstacksize;
intlength;
}SqList1;
voidzj（FILE*fp）//插入排序
{SqList1r;
inti,j;
chartemp,*p;
r.base=（char*）malloc（Q*sizeof（char））;
r.stacksize=Q;
r.length=0;
while（!
feof（fp））
{fscanf（fp,"
%c"
r.base）;
r.base++;
r.length++;
if（r.length==r.stacksize）
{r.base=r.base-r.length;
r.base=（char*）realloc（r.base,（r.stacksize+Q）*sizeof（char））;
if（!
r.base）
{printf（"
ERROR"
return;
}
r.base=r.base+r.stacksize;
r.stacksize+=Q;
r.length--;
r.base--;
r.base=r.base-r.length;
for（i=1;
i<
r.length;
++i）
for（j=0;
j<
i;
++j）
if（r.base[i]<
r.base[j]）
{temp=r.base[i];
//保存待插入记录
for（i=i;
i>
j;
--i）
r.base[i]=r.base[i-1];
//记录后移
r.base[j]=temp;
//插入到正确的为位置
}
r.base[r.length]='
\0'
;
rewind（fp）;
fprintf（fp,"
%s"
fclose（fp）;
free（r.base）;
}SqList3;
voidxe（FILE*fp）//希尔排序
{SqList3r;
inti,j,k,m;
chartemp;
r.base=（char*）malloc（1000*sizeof（char））;
r.stacksize=1000;
for（k=0;
k<
10;
k++）
{m=10-k;
for（i=m;
r.length;
i++）
if（r.base[i]<
r.base[i-m]）
{temp=r.base[i];
//保存待插记录
for（j=i-m;
j>
=0&
&
temp<
r.base[j];
j-=m）
r.base[j+m]=r.base[j];
//记录后移，查找插入位置
r.base[j+m]=temp;
//插入
}}
rewind（fp）;
fprintf（fp,"
fclose（fp）;
free（r.base）;
}SqList7;
voidmp（FILE*fp）//冒泡排序
{SqList7r;
inti,j,m;
r.base=（char*）malloc（1000*sizeof（char））;
while（!
{fscanf（fp,"
{r.base=r.base-r.length;
{printf（"
}}
for（i=0;
i++）//i为排好序的数的下标，依次往后存放排好序的数；
{m=1;
for（j=r.length-2;
j>
=i;
j--）//从后往前依次两两比较，较小的被调换到前面；
if（r.base[j+1]<
r.base[j]）//比较相邻两个数，如果后面的小于前面的，向下执行；
{temp=r.base[j+1];
//将后面的较小的数保存起来；
r.base[j+1]=r.base[j];
//将前面的较大的数放在后面较小的数的位置；
r.base[j]=temp;
//将较小的数放在前面的较大的数的位置；
m=0;
if（m）break;
r.base[r.length]='
}SqList5;
voidHeapAdjust（char*r,ints,intm）;
voiddp（FILE*fp）//堆排序
{SqList5r;
chartemp,*k;
r.base+=1;
while（!
if（r.length==（r.stacksize-1））
{r.base=r.base-r.length-1;
r.base=r.base-r.length-1;
for（i=r.length/2;
=1;
--i）//把r.base[1...r.length]建成大顶堆
HeapAdjust（r.base,i,r.length）;
for（i=r.length;
=2;
--i）
{temp=r.base[1];
r.base[1]=r.base[i];
r.base[i]=temp;
HeapAdjust（r.base,1,i-1）;
//将r.base[1...i-1]重新调整为大顶堆
k=（char*）malloc（（r.length+1）*sizeof（char））;
for（i=r.length,j=0;
i>
=1;
i--,j++）
k[j]=r.base[i];
k[j]='
k）;
free（k）;
voidHeapAdjust（char*r,intk,intm）
{inti,j;
charx;
i=k;
x=r[i];
j=2*i;
//沿key较大的孩子节点向下筛选
while（j<
=m）//j为key较大的记录的下标
{if（（j<
m）&
（r[j]>
r[j+1]））
j++;
if（x>
r[j]）//插入字符比当前的大，交换
{r[i]=r[j];
i=j;
j*=2;
else//否则比较停止
j=m+1;
}
r[i]=x;
//把字符x插入到该位置，元素插入实现
}SqList6;
voidmerge（SqList6r,inth,intm,intw,SqList6t）//对相邻两组数据进行组合排序；
{inti,j,k;
i=h;
j=m+1;
k=h-1;
//j为合并的第二组元素的第一个数位置,k为存入t中的数的位置
while（（i<
=m）&
（j<
=w））//依次排列两组数据
{k++;
=r.base[j]）//将第一组数据与第二组数据分别比较；
t.base[k]=r.base[i++];
else
t.base[k]=r.base[j++];
if（i>
m）//第一组数据先排完的情况
while（j<
=w）t.base[++k]=r.base[j++];
while（i<
=m）t.base[++k]=r.base[i++];
voidtgb（ints,intn,SqList6r,SqList6t）//对数据进行每组s个数的归并排序；
{inti=1;
//i为要合并两组元素的第一个数位置；
while（i<
=（n-2*s+1））
{merge（r,i,i+s-1,i+2*s-1,t）;
//i+s-1为要合并的第一组元素的最后一个数位置、i+2*s-1为要合并的两组元素最后一个数位置
i=i+2*s;
if（i<
（n-s+1））//考虑n不能被s整除，如果余下的数少于2*s但大于s，也就是余下的数不能凑成两组，凑一组有余,则把余下的数进行组合，并对其进行排序；
merge（r,i,i+s-1,n,t）;
else//如果余下的数少于s，则余下的数进行组//合，并进行排序；
while（i<
=n）
t.base[i]=r.base[i++];
voidgb（FILE*fp）//归并主函数；
{SqList6r;
r.base=r.base-r.length-2;
inti,j,n,s=1;
n=r.length;
SqList6t;
t.base=（char*）malloc（r.stacksize*sizeof（char））;
//给待排序的数组t申请内存；
while（s<
n）//每组元素不断增加循环进行合并排序；
{tgb（s,n,r,t）;
//s为每组元素的个数、n为元素总个数、r为原数组，t为待排序的数组，进行归并排序；
把元素个数相同的两组合并并进行重新定义成新的一组，此组元素个数为2*s；
s*=2;
if（s<
n）{tgb（s,n,t,r）;
s*=2;
}//当元素个数小于n时，对其进行合并排序；
else//当元素个数大于n时，对剩下的数排序；
{i=0;
while（i<
{r.base[i]=t.base[i+1];
i++;
}}}
free（t.base）;
{FILE*fp;
intsign=1;
while（sign!
=0）
{printf（"
请选择：
printf（"
%6c[1]直接插入排序\n"
'
'
%6c[2]希尔排序\n"
%6c[3]堆排序\n"
%6c[4]归并排序\n"
%6c[5]冒泡排序\n"
%6c[0]退出\n"
请输入：
"
scanf（"
sign）;
if（（fp=fopen（"
xuexinsheng.txt"
"
r+"
））==NULL）
{printf（"
Fileopenerror!
return0;
switch（sign）
{case1:
zj（fp）;
case2:
xe（fp）;
break;
case3:
dp（fp）;
case4:
gb（fp）;
case5:
mp（fp）;
case0:
break;
if（sign!
=0）
printf（"
排序已完成\n\n"
}}
三.运行结果：
（排序算法运行结果如上，由于几种排序方法的运行结果相同，故只演示其中一种的截图。
）
四.实验心得：
通过本次课程设计，我们小组的每个成员都学到了很多东西。
首先要说的是我们的编程能力，在这一次的课程设计中我们的编程能力均得到了一定程度的提升。
并且通过这次课程设计，我们更加熟悉了如何使用HeaderFile文件。
本次课程设计，让我们对于直接插入排序，希尔排序，堆排序，归并排序，冒泡排序等五种排序算法的思想有了进一步的认识，同时对五种算法的应用有了更进一步的掌握。
通过这次课程设计，我们对于解决实际问题的能力有了进一步提高。
最重要的是，这次课程设计大大的训练了我们的小组团队协作能力。
通过这次课程设计我们小组各成员的团队协作能力都有了很大的提升。
这种团队协作能力对于我们学编程的来说是极其重要的，同时也是必不可少的。
升级会员 