九江学院 数据结构 实验报告 完整答案文档格式.docx
《九江学院 数据结构 实验报告 完整答案文档格式.docx》由会员分享，可在线阅读，更多相关《九江学院 数据结构 实验报告 完整答案文档格式.docx（63页珍藏版）》请在冰点文库上搜索。
7.1实验目的43
7.2实验准备43
7.3实验任务43
实验8排序53
8.1实验目的53
8.2实验准备53
8.3实验任务53
实验9综合实验59
9.1实验目的59
9.2实验预习59
9.3实验任务59
实验1函数、指针、结构体复习
院（系）：
信息科学与技术学院课程名称：
数据结构教师签名：
班级
B1131
学号
实验室
专业
姓名
计算机号
实验名称
所用软件
实验成绩
1.1实验目的
1．掌握C语言的语法并由算法形成相应的程序。
2．熟练掌握C语言函数调用的相关知识点。
3．熟练掌握C语言的指针和结构体相关知识点。
4．理解数据结构的基本概念。
1.2实验准备
1．复习C语言的函数调用、指针、结构体的相关知识点。
2．算法的概念和算法分析等知识。
3．C语言程序设计有关函数及数组等的知识及编程环境的使用方法。
4．复习课堂讲解的理论内容。
1.3实验任务
1．在提示**********blank**********下面填写合适的内容完成程序设计。
编写一个程序，判断一个字符串是否为“回文”（顺序和倒读都一样的字符串称为“回文”），并分析算法的时间复杂度。
提示：
实现本程序需要设计两个函数。
①主函数main，数据的输入和输出在该函数中完成。
②自定义函数func，判断串s是否为回文。
采用的方法是：
用flag表示是否为回文。
用i从左向右扫描字符串s，用j从右向左扫描字符串s，若s[i]与s[j]不相等，则flag=0（表示不是回文）并退出循环，否则，继续比较直到i<
j不成立。
*判断指定字符串是否回文*
#include<
stdio.（str）;
for（i=0,j=t-1;
i<
=t2;
i++,j--）
{
if（str[i]==str[j]）continue;
else
{flag=0;
break;
}
}
if（i>
=t2）flag=1;
returnflag;
}
voidmain（）
{
********************blank********************
char*s;
intflag;
*填空位置1，变量定义*
scanf（"
%s"
s）;
*填空位置2，从键盘输入需要判定的字符串*
flag=func（s）;
*填空位置3，调用func函数*
if（flag==0）printf（"
NO\n"
）;
elseprintf（"
YES\n"
*填空位置4，根据返回值flag的值，输出判定结果*
该算法的时间复杂度是：
_______O_____________。
2．定义函数intf（char*x,chary）判断x所指的字符串是否包含字符y，若是则函数返回1，否则返回0。
写出完整的源程序代码。
stdio.flag;
char*str,ch;
intt;
gets（str）;
scanf（"
%c"
&
ch）;
t=f（str,ch）;
printf（"
t=%d\n"
t）;
3．用结构体类型编写一个程序，输入一个学生的学号、姓名及3门课的成绩，计算并输出其平均成绩。
stdio.（）*写出main函数的函数体部分，实现函数功能*
inti,j;
floatsum=0.0,aver;
printf（"
Pleaseinputtheid:
"
scanf（"
%d"
s.id）;
Pleaseinputthename:
s.name）;
Pleaseinputthethreescore:
for（i=0;
3;
i++）
%f"
s.score[i]）;
sum=sum+s.score[i];
aver=sum3;
averageis:
%f\n"
aver）;
实验2线性表
2.1实验目的
1．掌握顺序表的基本特点。
2．熟练掌握顺序表的建立、查找、插入和删除等操作。
3．掌握单链表的基本特点。
4．熟练掌握单链表的建立、插入、删除等基本操作。
5．理解循环链表、双向链表的含义及其特点。
6．了解循环链表、双向链表的基本操作。
2.2实验准备
1．线性表顺序存储结构的表示。
2．顺序表的基本操作：
顺序表的建立、查找、插入、删除。
3．线性表链式存储结构的表示。
4．链表的基本操作：
链表的建立、查找、插入、删除。
2.3实验任务
1．实现顺序表的各种基本操作。
（1）源程序代码。
stdio.;
*定义线性表的实际长度*
}seqlist;
voidcreate（seqlist*L）*建立一个顺序存储的线性表*
inti;
Pleaseinputthelenoftheseqlist:
"
*从键盘输入当前顺序表的实际长度*
（*L）.len）;
Pleaseinputtheeveryelementoftheseqlist:
for（i=0;
（*L）.len;
i++）*从键盘输入顺序表的每个元素*
（*L）.list[i]）;
Outputtheeveryelementoftheseqlist:
\n"
i++）*顺序表建立成功后，输出整个顺序表*
%5d"
（*L）.list[i]）;
*运行结果
（1）*
voidaccess（seqlist*L,inti）*根据指定位置访问线性表*
if（（i<
0）||（i>
（*L）.len-1））*判断给定位置是否为合法取值*
printf（"
Theplaceisnotcorrect!
else
%d\n"
*运行结果
（2）*
voidbefore_after（seqlist*L,inti）*根据指定位置寻找其前趋元素和后继元素*
（*L）.len-1））
elseif（i==0）
（*L）.list[i+1]）;
elseif（i==（*L）.len-1）
（*L）.list[i-1]）;
elseif（（i>
0）&
&
（i<
%d,%d\n"
（*L）.list[i-1],（*L）.list[i+1]）;
*运行结果（3）*
voidsearch（seqlist*L,intkey）*根据给定元素key查找顺序表*
intm;
for（m=0;
m<
m++）
{
if（（*L）.list[m]!
=key）
continue;
Seachingisseccessful!
Theplaceofthesearchkeyis:
m）;
break;
if（m>
=（*L）.len）
Theseqlist"
*运行结果（4）*
voiddelete（seqlist*L,inti）*删除顺序表的元素*
Outputtheeveryelementoftheseqlistbeforedeleting:
*删除前输出顺序表中的所有元素*
（*L）.list[m]）;
*运行结果（5）*
for（m=i;
m++）*删除位置之后的所有元素依次左移一位*
（*L）.list[m]=（*L）.list[m+1];
（*L）.len--;
Outputtheeveryelementoftheseqlistafterdeleting:
*删除后输出顺序表中的所有元素*
*运行结果（6）*
voidinsert（seqlist*L,inti,inte）*在顺序表指定位置i后插入元素e*
Outputtheeveryelementoftheseqlistbeforeinserting:
*插入前输出顺序表中的所有元素*
*运行结果（7）*
（*L）.len++;
for（m=（*L）.len-1;
m>
=i;
m--）*插入位置之后的元素依次右移一位*
（*L）.list[m+1]=（*L）.list[m];
（*L）.list[i]=e;
*在指定位置i上插入元素e*
Outputtheeveryelementoftheseqlistafterinserting:
*插入后输出顺序表中的所有元素*
*运行结果（8）*
staticseqlist*L;
inti,e;
\nfunction:
create\n"
create（L）;
*调用函数create建立一个顺序表*
access\n"
Pleaseinputtheposition:
i）;
*从键盘输入访问位置i*
access（L,i）;
*调用函数access根据指定位置访问顺序表*
before_after\n"
*从键盘输入指定位置i*
before_after（L,i）;
*调用函数before_after根据位置i确定前趋元素和后继元素*
search\n"
Pleaseinputthesearchkey:
e）;
*从键盘输入查找元素e*
search（L,e）;
*调用函数search根据关键字e查找顺序表*
delete\n"
Pleaseinputthedeleteposition:
*从键盘输入删除位置i*
delete（L,i）;
*调用函数delete删除指定位置i的元素*
insert\n"
Pleaseinputtheinsertposition:
*从键盘输入插入位置i*
Pleaseinputtheinsertelement:
*从键盘输入插入元素e*
insert（L,i,e）;
*调用函数insert在插入位置i上插入元素e*
（2）上机调试上面的源程序，并根据下列原始数据记录程序的运行结果。
原始数据
顺序表的实际长度
10
顺序表的元素
1，2，3，4，5，6，7，8，9，10
访问顺序表的位置i
5
寻找前趋、后继元素的指定位置i
7
查找关键字e
58
删除位置i
插入位置i
插入元素e
28
（3）运行结果记录。
①Outputtheeveryelementoftheseqlist:
12345678910
②6
③7,9
Theseqlist;
voidcreate（seqlist*L）*根据已知条件建立一个有序的顺序表*
\n\nPleaseinputthelengthoftheorderedseqlist:
**********blank**********
*从键盘输入有序表的实际长度，已知（*L）.len=10*
\n\nPleaseinputtheeveryelementoftheorderedseqlist:
**********blank**********
scanf（"
*从键盘输入有序表中的每个元素，{9}*
voidinsert（seqlist*L,inte）*在顺序表指定位置i后插入元素e*
inti,j,m,n;
\n\nOutputtheeveryelementoftheseqlistbeforeinserting:
for（n=0;
n<
n++）
（*L）.list[n]）;
for（i=（*L）.len-2;
i>
=0;
i--）
**********blank**********
If（e<
（*L）.list[i]）*确定插入位置*
（*L）.list[i+1]=（*L）.list[i];
*插入位置之后的元素依次右移一位*
j=i;
（*L）.list[j]=e;
*在确定的插入位置j上插入元素e*
\n\nOutputtheeveryelementoftheseqlistafterinserting:
\n\n"
staticseqlist*L;
inte=25;
create（L）;
*调用函数create建立有序表*
insert（L,e）;
*调用函数insert在有序表中插入元素e*
3．实现单链表的各种基本操作。
#include"
DataTypee;
H=（NODEPTR）malloc（LEN）;
*为头结点H分配存储空间*
H->
next=NULL;
*从头结点开始建立单链表*
q=H;
Pleaseinputthelengthofthelinklist:
*根据实际情况从键盘输入表长*
n）;
Pleaseinputtheeveryelement:
*从键盘输入线性表的每个元素*
for（i=1;
=n;
p=（NODEPTR）malloc（LEN）;
*为当前插入链表的结点分配存储空间*
p->
data=e;
*指向结点的指针变量p指向当前要插入的结点*
q->
next=p;
*指向结点的指针变量q指向当前插入结点的前趋结点，将p作为其后继赋值，完成当前结点的插入*
q=p;
*当前结点完成插入之后，修改指针变量q，为下一次插入做好准备*
q->
returnH;
voidsearch（NODEPTRH,DataTypee）*在单链表中查找指定数据元素e*
NODEPTRp;
inti=1;
p=H->
next;
*指针变量p赋值为头结点的后继，从该位置开始查找整个单链表*
while（p）*当p不为空时，执行循环*
if（p->
data!
=e）*指针变量p当前指向结点的数据域不等于查找元素e*
p=p->
*指针后移，继续向下查找*
i++;
continue;
else*否则，查找成功，输出该结点的位置*
Searchingissuccessful!
Theplaceofthesearchkeyinthememoryis:
p）;
*输出该结点在内存中的存储地址，
（2）*
Theplaceofthesearchkeyinthelistis:
i）;
*输出该结点在线性表中的位置，（3）*
next==NULL）
Thelinklist"
NODEPTRdelposi（NODEPTRH,inti）*按照指定位置i删除链表中的某个元素*
NODEPTRp,pre;
intm;
p=H;
for（m=1;
m++）*按照指定位置i寻找需要删除的结点*
pre=p;
p=p->
pre->
next=p->
*删除指定位置的结点*
free（p）;
*结点删除后，释放存储空间*
NODEPTRinsafter（NODEPTRH,inti,DataTypee）*在指定位置i之后插入元素e*
NODEPTRp,s;
s=（NODEPTR）malloc（LEN）;
*为插入结点分配存储空间*
s->
*指针变量s指向当前的插入结点*
i;
m++）*按照指定位置i确定插入点*
p->
next=s;
*完成指针的修改，实现结点插入*
main（）
{
NODEPTRH,p;
\nFuntion:
createback\n"
H=createback（H）;
*调用createback函数从链尾建立单链表*
\nOutputthelinklist:
*单链表建立成功后，输出单链表的所有结点*
while（p）
%d,%d"
p->
data,p->
next）;
}*
（1）*
search（H,e）;
*调用search函数在单链表中查找关键字e*
delposi\n"
\nOutputthelinklistbeforedeleting:
*删除之前输出单链表的结点*
升级会员 