数据结构实验报告全集.doc

数据结构实验报告全集
实验一 线性表基本操作与简单程序
１。　实验目得
（1）掌握使用Ｖisuaｌ Ｃ＋+ 6、0上机调试程序得基本方法;ﻫ(2）掌握线性表得基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构与链表存储结构上得程序设计方法。
2． 实验要求
(１） 认真阅读与掌握与本实验相关得教材内容。
(2) 认真阅读与掌握本章相关内容得程序.
（3） 上机运行程序。
(4） 保存与打印出程序得运行结果,并结合程序进行分析.
（5） 按照您对线性表得操作需要,重新改写主程序并运行，打印出文件清单与运行结果
实验代码：
１)头文件模块
#incｌude iｏｓｔｒeam、h〉//头文件
#incｌｕdｅ＜malloｃ、h〉//库头文件-－--—动态分配内存空间
typｅdｅf　ｉnt ｅlemtype；//定义数据域得类型
typedeｆ strｕcｔ　linknode//定义结点类型
{
eｌemｔype datａ；//定义数据域
ｓtrｕct ｌinkｎoｄe　*next；//定义结点指针
}nｏdｅtype；
2)创建单链表
ｎodｅtyｐe ＊crｅate（）/／建立单链表,由用户输入各结点data域之值,
/／以0表示输入结束
｛
　elemｔype d；//定义数据元素d
　 nodetype ＊h=NUＬL，*s，＊t；//定义结点指针
　iｎｔ　i=1;
couｔ<<"建立一个单链表”〈<endｌ；
　 　 whiｌe（1）
｛
　 couｔ　＜＜”　输入第”〈〈 i <〈"结点data域值：”；
　 　　 　cｉn 〉＞ d;
　　 ｉｆ（d＝＝０) 　breａk；/／以0表示输入结束
　if（i==1)//建立第一个结点
｛
h＝（nodetype＊)mａlｌoc(sizeof(ｎodetype))；//表示指针ｈ
　 　h->dａta=d；h—>ｎｅxt＝ＮULＬ；ｔ=h;／／ｈ就是头指针
}
elsｅ/／建立其余结点
　　{
　 　ｓ=(ｎodetｙpe*) maｌloc(sizeｏf（nodeｔype））;
　 ｓ-＞ｄata＝d;s—〉next＝ＮUＬＬ;t—＞ｎｅxｔ=s；
　 　 　t=s；//t始终指向生成得单链表得最后一个节点
　 　｝
　 i++；
　｝
retuｒn h；
}　 　　 　
３）输出单链表中得元素
ｖoiｄ　disp（nodeｔyｐｅ＊h）／/输出由ｈ指向得单链表得所有ｄａta域之值
｛
　　 nodetype ＊p=h;
　ｃouｔ<〈”输出一个单链表:"<<enｄｌ＜＜” ＂；
　 ｉf(p==ＮULL）ｃoｕt＜〈”空表”；
　 wｈilｅ（p!=NUＬL）
　 {
　 couｔ<〈p-〉ｄａta<〈”　”；p＝ｐ-〉nexｔ；
　　 }
cｏｕt〈＜eｎdl；
｝
4）计算单链表得长度
int len(noｄｅtyｐe ＊ｈ）/／返回单链表得长度
｛
　　　int i＝0；
　 　 ｎｏdｅtype ＊p=h;
　 　wｈile(p!=NULL)
　 {
p＝p—〉nexｔ;i++；
　｝
　　 reｔurn　i；
}
5)寻找第i个节点
nodeｔｙｐｅ *find(nｏdetype *h，int i)//返回第i个节点得指针
{
　 nodｅtyｐe　＊p=h；
　 ｉnt j=1；
if(i〉ｌen（h)｜|i<=0)
rｅtuｒn NULＬ；/／i上溢或下溢c
　 elsｅ
{
　 while (ｐ！＝ＮULL＆&ｊ〈1)//查找第i个节点，并由p指向该节点
　 　 　{
　 j++;ｐ=p-〉next；
　 　}
　　 retuｒｎ p;
　 ｝　 　 　 　 　 　　 　　　　 　　 　 　　 　 　　
}
6）单链表得插入操作
nｏｄeｔｙpe *ｉns（nodeｔｙpｅ　*ｈ,iｎt i，elｅmtype　x）／/在单链表ｈeａd中第i个节点
／/（i〉=0)之后插入一个datａ域为x得节点
{
　 nodetype *ｐ，＊s;
ｓ=(nodetｙpe＊)ｍalloc(siｚeoｆ（noｄetyｐe））；//创建节点s
　　s—〉ｄata＝ｘ；ｓ－>nｅxt＝NＵLL;
　 iｆ（i==0)//i=0：s作为该单链表得第一个节点
　{
　 　 ｓ—>nexｔ=h；ｈ=s;
｝
　 else
　　 {ｐ＝fiｎｄ（h，i）;//查找第i个节点，并由p指向该节点
　　　if（p！=NULＬ)
　 ｛
　 ｓ-＞next=p—〉neｘt；
　　 　　p—〉next=s;
}
　 rｅtuｒn h;
｝
}
7）单链表得删除操作
nodeｔype ＊del（nodｅｔypｅ *h,ｉｎｔ　i)//删除第i个节点
{
　 　ｎodetype ＊p=h, ＊s；
　 　 int　ｊ=１;
if（ｉ=＝1）／／删除第1个节点
{
　 　 ｈ=ｈ—>next；free（p)；
}
else
　 {
　 p＝fiｎd(h，i－1）;//查找第ｉ－1个节点,并由p指向该节点
　 if(p！=ＮUＬL＆&p－>nｅxt！=NULL)
　 　 ｛
　 　 ｓ=p－〉next;／／s指向要删除得节点
　　　 p－>neｘt=s－>nｅxt；
　 　　　 　 free（s)；
　}
　 　 　ｅlｓｅ coｕt＜<"输入ｉ得值不正确”<＜endl；
｝
retuｒn ｈ;
｝
8）释放节点空间
void ｄｉspose（nｏdetｙpe *h)//释放单链表得所有节点占用得空间
｛
　 noｄｅtypｅ ＊pａ=h，＊ｐb;
if（ｐa！=NＵLＬ)
{
　　 pb=pａ—〉ｎexｔ;
　 　 if(pb=＝NULＬ）／/只有一个节点得情况
　　 　 　frｅe(ｐa);
　 　 elｓe
　 {
　　　　　　 whilｅ （pｂ！＝NＵLL）／／有两个及以上节点得情况
　　 {
　 　 　 　 fｒee（pa）；pａ=pb；pb＝pb—〉next；
}
　　 free（pa);
　 ｝
　　 　｝
｝
9）主程序模块：
＃ｉncｌudｅ＂sｌiｎｋ、h”/／包含头文件sliｎk
vｏid main(）
｛
　 noｄeｔｙpｅ ＊heaｄ；//定义节点指针变量
heａd＝cｒｅａtｅ()；//创建一个单链表
disp（heaｄ）;／/输出单链表
　 　 cout〈<"单链表长度：”<〈ｌen(hｅａd）〈〈ｅｎdｌ；
　 ins(ｈeaｄ,　2,0）；//在第二个节点之后插入以0为元素得节点
ｄisp（heａd)；／/输出新链表
　 del（hｅad，２)；/／删除第二个节点
ｄisp(heａd）；//输出新链表
｝
5。实验结果
建立一个单链表：
输入第1结点dａta域值：1
输入第２结点datａ域值：2
输入第3结点ｄata域值:3
输入第4结点daｔa域值：４
输入第5结点ｄaｔａ域值:5
输入第6结点dａtａ域值：６
输入第7结点dａtａ域值：７
输入第8结点dａta域值：８
输入第９结点dａtａ域值:９
输入第10结点data域值０:
输出一个单链表：
１ ２ 3 4 5 ６　7 ８　９
单链表长度：9
输出一个单链表：
1 ０ ２ 3 4　５　６ 7 8　9
输出一个单链表：
1 2 3 4 5 6 7 8
实验二 顺序栈得实现
1、实验目得
掌握顺序栈得基本操作:初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。
2、实验要求
（１） 认真阅读与掌握与本实验相关得教材内容。
(2) 分析问题得要求,编写与调试完成程序.
(3） 保存与打印出程序得运行结果，并分析程序得运行结果。
3、实验内容ﻫ　 利用栈得基本操作实现一个判断算术表达式中包含圆括号、方括号就是否正确配对得程序。具体完成如下：
（１） 定义栈得顺序存取结构。
（２)　分别定义顺序栈得基本操作（初始化栈、判栈空否、入栈、出栈等)。
（3）　定义一个函数用来判断算术表达式中包含圆括号、方括号就是否正确配对。其中,括号配对共有四种情况:左右括号配对次序不正确；右括号多于左括号;左括号多于右括号;左右括号匹配正确.
（4） 设计一个测试主函数进行测试。
(5) 对程序得运行结果进行分析.
实验代码：
＃incluｄe　＜stdio、h　>ﻫ＃dｅfｉne MaxSize　１0０ﻫ
ｔypedｅｆ　sｔruｃｔ
{
    ｉnt　data［ＭaｘＳize]；
    inｔ tｏｐ;
｝SｑＳtack;
voiｄ IniｔSｔack（SqStａck *st） //初始化栈
｛ﻫ    st—>top=—１；ﻫ｝
int SｔackＥｍpｔy（SqStaｃｋ ＊sｔ) ／/判断栈为空
｛ﻫ    ｒeturn （sｔ-〉ｔｏp＝=—1)；ﻫ}
ｖｏid Pusｈ(SｑＳｔack *ｓt,int x） ／/元素进栈ﻫ｛ﻫ   　iｆ（st->top＝＝MａｘＳize-1)
        printf（＂栈上溢出!\n"）；ﻫ    elｓｅﻫ    {
        st-〉top++;ﻫ        ｓt－>ｄata［st－〉top］=x;
   　｝ﻫ}
voiｄ Pｏp（SqSｔaｃk *st）　//退栈ﻫ｛ﻫ    if（st－＞top==-1）ﻫ       　pｒｉｎｔf（＂栈下溢出\n”);ﻫ    elｓe
    st—〉top-—；
｝
int Ｇeｔtop(SqStack ＊st） /／获得栈顶元素
{
    iｆ（st—〉ｔop==—1)ﻫ    ｛
        printｆ（"栈空＼n”）;ﻫ        retｕrn　0；
    }ﻫ    ｅlｓe
        retｕrn st—〉datａ［st－>ｔｏp］;
}
voｉd Diｓpｌay(SqＳtaｃk *st） //打印栈里元素ﻫ{
    ｉｎt i；
    prｉntf（＂栈中元素:"）；
    for(ｉ＝ｓt-〉toｐ;i＞=０；--i）ﻫ       　printf（”％d　",ｓt－＞datａ[i］）；ﻫ    ｐrintf(”\n＂）；ﻫ｝ﻫｉnｔ main() /／测试ﻫ｛ﻫ   　SqStaｃk L；ﻫ    SqStack ＊ｓｔ=＆Ｌ;ﻫ   　IｎitStack（st）；ﻫ    prｉｎｔｆ("栈空：%ｄ\n"，StａckEmpｔy（sｔ））；ﻫ   　foｒ（int ｉ=１；ｉ<1０;++i）ﻫ       　Push（ｓt，i)；ﻫ    Ｄｉｓplay（sｔ)；
    printｆ（"退一次栈\ｎ")；
    Pｏp（ｓt);
    ｐrinｔf("栈顶元素:％d\n＂，Gｅttｏp（ｓｔ)）；ﻫ    Ｐop（st）;ﻫ   　Disｐlａy(st）；ﻫ   　returｎ 0；ﻫ}
实验结果:

实验三 　串得基本操作与简程序
1。 实验目得
掌握串基本操作：初始化、联接、替换、子串等运算在堆分配存储储结构上得程序设计方法。
２． 实验要求
(１) 认真阅读与掌握与本实验相关得教材内容.
(2） 认真阅读与掌握本章相关内容得算法并设计程序序。
（3） 上机运行程序。
(4) 保存与打印出程序得运行结果,并结合程序进行分析.
实验代码：
#incｌude＜stdio、h>
＃dｅfiｎe　MaxSize 50
typeｄef ｓtrｕct
{
ｃhａr data［MaｘSizｅ］；　 //存放字符串
int lenｇｔh；　 //字符串长度
｝SqString；
／/将一个字符串常量赋给串s
ｖoid　StrAssign(SqStrｉnｇ ＆s,cｈaｒ cｓｔr[])
｛
iｎt　i；
for(i＝０;cstr[i]！=＇\0';i++） ／/这个＇\0＇代表字符串结束标志,编译系统自动加上得
ｓ、datａ[i]=csｔr[i];
s、lenｇth=i;
｝
//字符串得复制
voｉd StrCopy（ＳqStrｉng &ｓ，SｑStｒiｎg t)
{
ｉｎt i;
ｆor(i=0;i〈ｔ、ｌｅngtｈ；ｉ++）
s、ｄatａ[i］=t、data[i];
　ｓ、leｎgtｈ=t、ｌength；
　pｒintf(＂字符串复制成功了\n”)；
｝
//判断字符串就是否相等
voｉｄ StｒＥqｕａｌ(SqStrinｇ　s，ＳqStｒiｎg t)
｛
inｔ i,ｓame=１；
ｉf（s、ｌength!=t、ｌenｇth）
　　saｍe=0；
　elｓｅ
{
　 for（i=０；i〈s、length;i++）
　 if(ｓ、daｔa[i］!=t、ｄaｔa［ｉ］）
｛
　 　saｍe＝０;
　 ｂreak；　
｝
｝
ｉf(same==0）
pｒｉnｔf("这两个字符串不相等\n"）;
else
pｒintｆ（"这两个字符串相等\n”)；
｝
/／字符串得长度
ｖoid　ＳtrLeｎgth(SqSｔrｉnｇ　ｓ）
｛
　prｉnｔf（”此字符串长度为：％d\n"，s、ｌengｔｈ)；
｝
//合并字符串
SqＳtring Coｎcat（ＳqString　s,SqＳtring t)
{
ＳqSｔriｎｇ　sｔｒ；
inｔ i；
　ｓtr、ｌｅｎgth=s、lenｇth+t、ｌenｇth;
for(ｉ=0；ｉ＜s、leｎgtｈ；i++）
　 　 str、dａtａ［i]＝s、data［i］;
　for(i=0；ｉ〈t、ｌengｔh;i++)
　 str、ｄaｔa［ｓ、lｅngtｈ＋i]＝ｔ、data［i];
　 　ｒeturn str;
｝
/／求子字符串
void　SubStr（ＳｑSｔriｎg s，inｔ i，ｉnｔ j)
｛
　SqStrｉng　ｓtｒ;
ｉnt　ｋ；
ｓtr、lｅngth=０；
iｆ(i〈=0|｜i〉s、lenｇtｈ|｜j<0｜|i+j-１>ｓ、ｌength)
　priｎtf("子字符串复制失败＼n＂);
ｆor（k=ｉ－1;k〈i+j-1；k＋+）
stｒ、datａ［k—i＋1]=s、dａta[k]；
ｓｔr、ｌength=j;
printf（"子字符串复制成功 长度为：%d\ｎ＂,ｊ)；
　printｆ(”下面输出此子字符串：＼n＂);
fｏr（ｉ=0；ｉ<j；i++)
ｐrｉntf（”％ｃ”,ｓtｒ、data[i］)；
printf(”\ｎ”）；
}
//插入字符串
ＳqStriｎg ＩnsｅrStr(SｑStrｉｎｇ s1，int ｉ,SqSｔring s２)
{
　int　j；
SqＳtrｉnｇ str;
ｓtr、length=0；
if（i〈=０｜｜i>s1、length+1)
{
prｉnｔf（”字符串插入失败＼n"）;
retuｒｎ str；
　}
for（j=０;ｊ<i-1；ｊ++）
　 ｓｔr、ｄata［ｊ］＝s1、ｄａta[j];
for（j=0;ｊ〈ｓ2、lengtｈ；j++)
　sｔr、datａ[i-1＋j］=s2、dａta[j］；
　ｆoｒ（ｊ=i－1；j＜s１、ｌengｔh;j++）
stｒ、daｔａ[s2、ｌｅngtｈ+j]＝s1、data［j];
　ｓtr、lengｔh＝ｓ1、leｎｇth+ｓ2、lｅｎｇth；
printf（"插入字符串成功 长度为：％d\n”，sｔｒ、ｌｅngth）；
retuｒn stｒ;
｝
/／删除字符串
SqＳｔring DeleSｔｒ（SqStriｎg s，int ｉ，ｉnt　ｊ）
｛
ｉnt k；
ＳqＳtｒiｎｇ　sｔr；
sｔr、ｌengｔh＝0;
if（i<=0｜|i>s、ｌengtｈ｜｜i+ｊ>s、leｎｇｔh+1)
　{
ｐｒiｎtf（＂字符串删除失败＼n”）； return　str;
｝
fｏr(ｋ=０；k〈i-１；k＋+)
　　ｓtr、daｔa[k]＝s、ｄata［ｋ];
　for（k=i+j—１；ｋ〈ｓ、lengｔh；k++）
sｔｒ、data［k－ｊ]=s、data[k］；
str、length=s、lｅngtｈ—j；
priｎtｆ(＂删除子字符串成功 剩余长度为:％d＼n",ｓtr、leｎgth)；
　reｔｕrn str；
｝
//替换字符串
voiｄ RｅｐStr(SqStrｉｎg s,int　i,iｎt　j,ＳqString t)
｛
iｎt　ｋ；
SｑString　str；
　sｔｒ、length＝0；
if(i<=０｜｜i〉s、leｎｇth||i+j—1>s、ｌengｔh）
　priｎtf（"字符串替换失败了\n＂）;
ｆor(k=0;k＜i—1;ｋ＋＋）
stｒ、datａ[k］=ｓ、ｄａtａ［k］；
for(ｋ=0;k<t、lｅｎgｔh；ｋ＋+）
str、ｄatａ［i+k-１］=t、dａta［k］；
for（k=i＋j－１;ｋ<s、leｎgtｈ；k++)
str、data［t、ｌength+k-j］=s、ｄata[k］；
sｔｒ、lｅｎgｔh=ｓ、leｎgth-j+t、lｅnｇth；
　pｒiｎtｆ(”替换字符串成功 新字符串长度为：％d\n”，str、length)；
｝
//字符串得输出
ｖoiｄ　DiｓｐStｒ（SqString　s）
｛
int i；
if(ｓ、ｌｅngｔh>０)
　｛
ｐｒｉntｆ（＂下面输出这个字符串\n＂)；
　 foｒ（i＝0;i〈s、ｌeｎgｔh;i＋+）
　pｒintf("％ｃ＂，ｓ、daｔa［ｉ］）;
　ｐriｎtｆ(＂\n”)；
}
ｅｌse
printｆ（＂目前空字符串 无法输出＼n"）；
}
void main（）
{
　SｑSｔring s;
　char a［]＝{＂weｎ xｉａn　ｌｉａng＂}；　//字符串常量ａ
ＳtｒＡssigｎ（s，ａ）；
ＤispSｔr(s）；
　StrLｅｎｇtｈ（s);
SqSｔrｉng　s１,s2,t;　//s1就是待复制得字符串变量
ｐrｉnｔf("请输入一个字符串ｔ：\n”)；
scanｆ("％s＂,t、ｄata）；
StrAssiｇｎ(t，t、ｄaｔa);
SｔrCopy(s1，t）；　 //复制字符串
ＳtｒＬeｎｇｔh（s1)；
　DisｐStr(s１)；
pｒinｔf("下面判断字符串s1与字符串s就是否相等＼ｎ＂）；
StrEｑuaｌ（s，s1)；
printf("下面将字符串s１与字符串s合并一起＼ｎ"）；
　SqＳtrinｇ　str；
　sｔr＝Concat(s，s1)；　　／/合并字符串
　DispStr(stｒ）；
　StrLength（str)；
ＳuｂＳtr（stｒ,２2，7）； /／求子字符串
sｔr＝DeleSｔｒ(stｒ,1５,4)； //删除字符串
ＤiｓpＳtr（stｒ）;
StｒLength（str)；
　pｒiｎtf("请插入一个字符串ｓ2\n”）;
　sｃanf（”％ｓ",s２、dａtａ)；
StｒAsｓigｎ(s2,ｓ２、datａ);
　ｓｔｒ＝InsｅrSｔr(sｔｒ，15，s2）; ／/插入字符串
DｉspSｔr(stｒ）；
StrＬength（stｒ）;
　printf(＂顺序字符串得基本运算到此结束了\ｎ”)；
｝
实验结果：

实验四  编程建立二叉树,对树进行插入删除及遍历得程序
1、实验目得
（1） 进一步掌握指针变量得用途与程序设计方法。
（2） 掌握二叉树得结构特征,以及链式存储结构得特点及程序设计方法。
(３） 掌握构造二叉树得基本方法。
(４） 掌握二叉树遍历算法得设计方法.
3． 实验要求
（1)认真阅读与掌握与本实验相关得教材内容。
(2）掌握一个实际二叉树得创建方法.
(3）掌握二叉链存储结构下二叉树操作得设计方法与遍历操作设计方法。
4。　实验内容
(1）定义二叉链存储结构.
（2)设计二叉树得基本操作（初始化一棵带头结点得二叉树、左结点插入、右结点插入、中序遍历二叉树等)。
（3）按照建立一棵实际二叉树得操作需要,编写建立二叉树、遍历二叉树得函数.
(4）编写测试主函数并上机运行。打印出运行结果,并结合程序运行结果进行分析。
实验代码:
＃ｉncluｄe<iｏsｔreａm、h＞
ｔypedeｆ　sｔrucｔ biｔnodｅ｛
　　　ｃhａr ｄaｔａ;
　　　ｓtrｕｃt bitnodｅ *ｌchiｌd,＊rchiｌd；
}binoｄe，*ｂitreｅ；
void createbitｒee(bitrｅe ＊Ｔ）｛
　ｃｈar ｃh;
cｉn>>ch；
if(ch＝='0＇）
(*T）＝NULL；
　 else｛
ﻩ（＊Ｔ）＝neｗ ｂitｎode;
（*T)->ｄａｔａ=ｃｈ；
creaｔebitree（&(＊T)—〉lｃhild)；
createｂｉtreｅ(＆（＊T）—〉rｃhilｄ）;
ﻩ}
｝
void ｉnｏrdｅrout（ｂitrｅe T)｛
　 if（Ｔ){
ﻩinordｅroｕt(T->ｌcｈｉｌd）;
ﻩﻩcｏut＜＜T->data＜<endｌ;
ﻩﻩinorderout（Ｔ-〉rchiｌd）；
ﻩ}
}
void pｏsｔordｅr（bitree T)｛
if(T)｛
poｓtorder(T->lｃhiｌd)；
postorｄeｒ(T—＞rｃhilｄ)；
cout<<T－〉data〈<endl；
｝
｝
ｉnｔ countleaf（bitｒee　ｂｔ){
　iｆ（!bt)
ﻩreｔurn ０；
ｉf（bｔ－>lcｈiｌｄ==NＵLL&&ｂt->rchild==NULＬ）
retｕｒn　1；
rｅturn (ｃounｔleaｆ（ｂｔ-〉lcｈiｌd）+ｃｏuntｌeaf（bｔ-＞ｒcｈｉld））;
}
voiｄ　ｍaiｎ(）{
　 ｂitｒｅｅ ｂt;
　 　creatｅbitｒee（＆ｂt）；
　 inｏrdｅｒout(ｂt)；
couｔ<<" ＂<〈endl；
　　postorder（bt)；
　 countleaｆ(ｂt）；
｝

实验五 建立有序表并进行折半查找
1、　实验目得
掌握递归算法求解问题得基本思想与程序实现方法.
2.实验要求ﻫ（1)认真阅读与掌握本实验得算法思想.
(2）编写与调试完成程序.
（3)保存与打印程序得运行结果,并对运行结果进行分析。
3、实验内容
（１) 分析掌握折半查找算法思想,在此基础上,设计出递归算法与循环结构两种实现方法得折半查找函数.
（2）　编写程序实现:在保存于数组得100０个有序数据元素中查找数据元素ｘ就是否存在。数据元素ｘ要包含两种情况:一种就是数据元素x包含在数组中；另一种就是数据元素x不包含在数组中
（3） 数组中数据元素得有序化既可以初始赋值时实现,也可以设计一个排序函数实现。
（４) 根据两种方法得实际运行时间，进行两种方法时间效率得分析对比。
实验代码:
＃iｎclude＜stdｉo、h>
#incluｄｅ<stｄlib、ｈ>
＃defiｎe MAX＿LENGTＨ 　100
typeｄｅf　int KｅyＴype；
ｔｙpedｅf sｔｒucｔ
{
int　ｋｅy；
}EleｍＴype；
tｙｐｅdef　struct
｛
ﻩＥlｅｍType　elｅm[ＭAX_LＥＮGTH]； 　 ／/ 0号单元空出
　 　 iｎt lｅnｇｔｈ;
}SSTable;
int Searｃh＿Bin(SSＴabｌe SＴ,KeyType　kｅy)
｛
int low,higｈ，miｄ;
loｗ = 1；hｉgh = ST、leｎgtｈ；
　 　ｗｈile（low　＜=ｈiｇｈ）
　 ｛
mｉd =　(lｏw+ｈigh)/2；
ﻩﻩ if(key ==ST、elem[mｉｄ］、ｋeｙ)
ﻩ retｕｒn mｉd；
ﻩ eｌsｅ
ﻩ ﻩ if(kｅy〈ST、elｅm[mid]、key）
ﻩ ﻩ 　higｈ = mid—1;
ﻩﻩ ｅlse
ﻩ lｏw=ｍiｄ+１;
ﻩ　 }
　 　　 　retuｒｎ 0;
｝
voiｄ ｍain（)
｛
iｎt i，ｒeｓult；
ﻩSSTａｂｌe ST；
ﻩＫeyType　keｙ；
printf（＂plｅasｅ inｐｕt lｅngｔh:＂);
scanｆ(＂%d",＆ST、ｌeｎgtｈ）；
ﻩfｏｒ（i=1；ｉ＜=ST、ｌeｎgｔh;ｉ+＋）
ﻩ{
ﻩpｒinｔf（"plｅaｓe iｎｐｕｔ　ＳT、eｌｅm："）;
scanf（"％d＂，＆ST、elｅｍ［i]）;
｝
ｐrｉntf("pｌｅase　iｎput keywｏrd:"）;
scａｎf("%ｄ"，&kｅy);
result=Search_Ｂｉｎ（SＴ，key);
ﻩiｆ(rｅsｕlｔ＝＝０)
pｒiｎｔf（”Ｄoｎ't ｆｉnｄ\n"）;
ﻩelse
ｐrｉntf(”Fiｎd the kｅｙ，thｅ　positiｏn iｓ ％d＼n＂，resｕlｔ)；
}
实验结果:

实验六
建立一组记录并进行插入排序
1、 实验目得
（1）　掌握插入排序算法得思想.
（2） 掌握顺序队列下插入排序算法得程序设计方法。
2、 实验要求ﻫ(1） 认真阅读与掌握教材中插入排序算法得思想。
（3) 编写基于顺序队列得插入排序排序算法并上机实现。
３、 实验内容
（1) 编写基于顺序队列得插入排序函数。
（2) 设计一个测试主函数，实现对基于顺序队列结构得插入排序算法得测试.
（３） 分析程序得运行结果。
实验代码:
＃include〈sｔｄiｏ、h>
#ｉncluｄe〈sｔdliｂ、ｈ>
＃definｅ MAＸSIZE １0０
typｅdef struｃt
｛
　iｎt　kｅｙ;
}sｏrｔkeｙ；
typedef stｒuct
｛
ｓortkｅy elem[ＭAＸＳIZE];
ｉｎt lengｔh；
｝sortelｅｍ;
vｏiｄ InsｅrtSort（sorteleｍ *ｐ)
｛
　 ｉnt ｉ，j;
　ｆｏｒ(i=2；ｉ<=ｐ-〉length；i＋＋)
　｛
　 iｆ（ｐ-＞eleｍ［i]、ｋｅｙ＜ｐ－＞elem［i-1］、key）／＊小于时，需将eｌeｍ［i］插入有序表＊/
｛
p—>eleｍ[0]、key=ｐ—>ｅlem［i］、ｋｅy； /＊为统一算法设置监测＊/
for（j=ｉ—1；p－>eｌeｍ[0］、key〈p－>elem［j］、ｋeｙ；j—－）
　　　　 p->ｅleｍ[ｊ+1］、key=p—〉eｌｅｍ[j］、ｋeｙ;/＊记录后移＊/
　 p-〉eｌｅm[j+1]、kｅy＝p－>eｌｅm[0］、ｋeｙ； /*插入到正确位置＊／
　 }
　}
}
void main（)
{
　　 sｏrteｌem ＊ｐ;
int　i;
int b[6]={45,23,54,6，4，46};
p＝（sorteｌem *)mａllｏｃ（sｉｚeof(sorteleｍ)）;
ｐ—〉lenｇth=０；
foｒ(i=1；ｉ＜7；i++）
｛
p—>elｅm［i]、key=b[i—1］；
ｐ->length+＋;
}
InｓeｒｔSorｔ（ｐ）;
for(i=1;i＜７；i++)
｛
　prinｔｆ（”%d 　"，p—>elem［i］、ｋey）；
｝
sｙstem（"pause"）；
}
实验结果:

实验七  建立一组记录并进行快速排序
1、 实验目得
（１） 掌握快速排序算法得思想.
（2) 掌握顺序队列下快速排序算法得程序设计方法。
2、 实验要求ﻫ(1） 认真阅读与掌握教材中快速排序算法得思想。
（3）　编写基于顺序队列得快速排序排序算法并上机实现。
3、 实验内容
（1) 编写基于顺序队列得快速排序函数。
（2) 设计一个测试主函数，实现对基于顺序队列结构得快速排序算法得测试.
(3） 分析程序得运行结果。
实验代码:
＃includｅ〈iostｒeam、h〉
ｖｏｉd quick_sｏrt(int a［],int loｗ， ｉnｔ higｈ）
｛　　
　 ｉnt　i,j,pivｏt； 　
if （low < ｈiｇh）
｛
　 　 piｖot　＝ a［low］； 　
　 ｉ　= lｏw; 　
　 　　 　 ｊ =　ｈiｇh； 　
　 　 whiｌe (i　< j） 　
　 　｛　
　　 　//从顶端开始比较值，如果小于标准值，停止
　 　 　 ｗhiｌe （i <　j　＆＆ a[ｊ］ ＞= pｉｖot)
　 　　　 　 ｛ 　　
　　 　 　　　 j－-;　 　
　 ｝ 　
　　 /／将比pivot小得元素移到低端，下标加加　 　
　 　 　　　if (ｉ ＜　j)
　　 　 　　　 　 　a[ｉ＋+] = a[j];
　 //从底端开始比较值，如果大于标准值，停止 　
　　while （i < j　&＆ a[i］ <＝ pivot）
　 ｛　
　　 　 　 ｉ+＋; 　
　　 　 ｝ 　
　　 ／/将比pivot大得元素移到顶端,下标减减 　
　 　　 if (i 〈 j)
　 　 　　　　 a［ｊ--] =　ａ[i]； 　 　
　 ｝　　　
/／pivot移动到最终位置　
　　 　 a［ｉ] ＝ ｐivｏｔ；
　　 　/／对左区间进行递归排序
　 　 　　 quick_ｓort(a，　loｗ， ｉ—１）；
　 ／/对右区间进行递归排序 　　
　 qｕick_sｏrt（a，　i＋1， hｉgｈ)； 　
}
}
voｉｄ print＿array（int a[］，　int ｎ） 　
｛
　　　　ｆoｒ（inｔ i = 0;　ｉ 〈　ｎ；　i++） 　
｛ 　
cｏut <〈 a[i] 〈< ",";
　}
｝
inｔ ｍaiｎ（) 　
｛
int ｄaｔa［9］ = {54，3８，96,２3,１5，72,６0，4５,８3｝；
ｑｕick_ｓort（dａta, 0， ８）；　
　 　ｐｒint_arrａy(data，9）； 　
reｔｕrｎ 0； 　
}
实验结果：