数据结构第八次 实验Word下载.docx
《数据结构第八次 实验Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构第八次 实验Word下载.docx（16页珍藏版）》请在冰点文库上搜索。
#include<
iostream.h>
stdlib.h>
//清屏函数
malloc.h>
//malloc
conio.h>
//getch函数
#defineMAXSIZE20
#defineOK1
#defineTRUE1
#defineFALSE0
typedefintKeyType;
//整型
typedefstruct
{
KeyTypekey;
}RecordType;
RecordTyper[MAXSIZE+1];
intlength;
}RecordList;
voidinitrecord（RecordList*l）
//还原输入序列
{//287，109，063，930，589，184，505，269,008，083
l->
r[1].key=287;
r[2].key=109;
r[3].key=63;
r[4].key=930;
r[5].key=589;
r[6].key=184;
r[7].key=505;
r[8].key=269;
r[9].key=8;
r[10].key=83;
}
intCreate（RecordList*l）
intk;
for（inti=1;
i<
=l->
length;
i++）
{cout<
<
"
请输入第"
个记录"
;
cin>
>
k;
l->
r[i].key=k;
}
cout<
打印表"
endl;
for（intz=1;
z<
z++）
cout<
l->
r[z].key<
"
returnOK;
}//创建顺序表
voidInsSort（RecordList*l）
//直接插入排序
intj;
for（inti=2;
{
r[0].key=l->
r[i].key;
j=i-1;
while（l->
r[0].key<
r[j].key）
{
l->
r[j+1].key=l->
r[j].key;
j=j-1;
}
r[j+1].key=l->
r[0].key;
for（intm=1;
m<
m++）
cout<
r[m].key<
voidBubbleSort（RecordList*l）
//冒泡排序
inti,j,x;
intchange=TRUE;
for（i=1;
length&
&
change;
++i）
change=FALSE;
for（j=1;
j<
length-i;
++j）
if（l->
r[j].key>
r[j+1].key）
{
x=l->
r[j].key;
l->
r[j].key=l->
r[j+1].key;
r[j+1].key=x;
change=TRUE;
}
"
intQKPass（RecordList*l,intleft,intright）
//一次快速排序
intx=l->
r[left].key;
intlow=left;
inthigh=right;
while（low<
high）
while（low<
high&
r[high].key>
=x）
high--;
if（low<
r[low].key=l->
r[high].key;
low++;
r[low].key<
x）
r[high].key=l->
r[low].key;
}
r[low].key=x;
returnlow;
voidQKSort（RecordList*l,intlow,inthigh）
//快速排序
intpos;
if（low<
=high）
pos=QKPass（l,low,high）;
QKSort（l,low,pos-1）;
QKSort（l,pos+1,high）;
voidSelectSort（RecordList*l）
//简单选择排序
intn=l->
=n-1;
intk;
k=i;
for（intj=i+1;
=n;
r[j].key<
r[k].key）k=j;
if（k!
=i）
intx;
x=l->
r[i].key=l->
r[k].key;
r[k].key=x;
intSeqSearch（RecordList*l）
顺序查找请输入你要查找的值"
inti;
r[0].key=k;
i=l->
while（l->
r[i].key!
=k）
i--;
return（i）;
}//基于顺序结构的查找法
intBinSrch（RecordList*l）
intlow=1,high=l->
折半查找请输入你要查找的值"
cin>
intmid;
mid=（low+high）/2;
if（k==l->
r[mid].key）return（mid）;
elseif（k<
r[mid].key）high=mid-1;
else
low=mid+1;
return（0）;
}//折半查找
voidmain（）
intf=1;
intm;
inte;
chars;
intlocate1;
//顺序查找返回值
intlocate2;
//折半查找返回值
RecordList*l;
l=（RecordList*）malloc（sizeof（RecordList））;
length=10;
//表长
//287，109，063，930，589，184，505，269,008，083
while（f）
{
system（"
CLS"
）;
cout<
你想实现什么功能?
---------------------"
1顺序表的创建"
2直接插入排序"
3冒泡排序"
4快速排序"
5简单选择排序"
6顺序查找"
7折半查找"
输入操作序号：
cin>
s;
switch（s）
case'
1'
:
Create（l）;
cout<
构造顺序表成功!
getch（）;
break;
2'
InsSort（l）;
3'
进行还原：
initrecord（l）;
for（e=1;
e<
e++）
r[e].key<
BubbleSort（l）;
4'
QKSort（l,1,10）;
for（m=1;
5'
SelectSort（l）;
6'
locate1=SeqSearch（l）;
在表中的位置是"
locate1<
7'
locate2=BinSrch（l）;
locate2<
//注意getch函数的应用
4测试数据与实验结果（可以抓图粘贴）
5结果分析与实验体会
每次做实验都会发现不足，这次实验就发现对8进制数处理的困难，对指针的运用不到位，传值和传址理解不透。
升级会员 