软件基础实验指导书.docx
《软件基础实验指导书.docx》由会员分享，可在线阅读，更多相关《软件基础实验指导书.docx（37页珍藏版）》请在冰点文库上搜索。
软件基础实验指导书
目录
实验一顺序表的插入、删除……………………………………..1
实验二单链表的插入、删除……………………………..………4
实验三顺序栈的入栈、出栈……………………………..………8
实验四循环队列的入队、出队……………..…………..………10
实验五稀疏矩阵的转置………………………………....………13
实验六二叉排序树的建立、遍历………………………..…..…15
实验七直接插入排序……………………………………..…..…19
实验八直接选择排序……………………………………..…..…20
实验九顺序、二分查找…………………………………..…..…22
实验十二叉排序树查找…………………………………..…..…25
附录实验报告要求……………..…………...…………..………28
实验一顺序表的插入、删除（2学时）
一、实验目的
1、理解线性表的顺序存储结构；
2、能熟练建立一个顺序表，并能对其进行插入、删除等基本操作；
3、能熟练运用宏定义、函数调用。
二、实验内容
从键盘输入10个整数，建立一顺序表（顺序表最大长度为20），用顺序表完成在任意一个位置插入任意整数元素以及删除任意位置数据元素的操作（插入、删除位置及要插入元素数值均从键盘输入），进行完任一操作后将顺序表中的内容及表长输出。
三、参考源程序
#include
#defineMAXLEN20
typedefintelemtype;
typedefstruct
{
elemtypeList[MAXLEN];
intNum;
}Seqlist;
intinsert（Seqlist*la,inti,elemtypex）;
intdel（Seqlist*la,inti）;
voidoutput（Seqlist*la）;
main（）
{
Seqlistla;
intm,i;
elemtypex;
la.Num=-1;
printf（"\nPleaseinputdata:
"）;
for（i=0;i<=9;i++）
{
++la.Num;
scanf（"%d",&la.List[i]）;
}
printf（"Pleaseinputthevalueofm:
m=1---insertm=2---delete\nm="）;
scanf（"%d",&m）;
if（m==1）
{printf（"Pleaseinputinsertlocationandinsertdata:
"）;
scanf（"%d%d",&i,&x）;
insert（&la,i,x）;
output（&la）;
}
elseif（m==2）
{printf（"Pleaseinputdeletelocation:
"）;
scanf（"%d",&i）;
del（&la,i）;
output（&la）;
}
else
printf（"Thevalueofmiswrong!
"）;
}
intinsert（Seqlist*la,inti,elemtypex）
{
intj;
if（i<0||i>la->Num）
{
printf（"\n插入位置不合理！
"）;
return0;}
elseif（la->Num==MAXLEN-1）
{
printf（"\n表满，不能插入！
"）;
return0;}
else
{
for（j=la->Num;j>=i;j--）
la->List[j+1]=la->List[j];
la->List[i]=x;
la->Num++;
return1;
}
}
intdel（Seqlist*la,inti）
{
intj;
if（i<0||i>la->Num）
{
printf（"\nthepositionisinvalid"）;
return0;}
else
{
for（j=i+1;j<=la->Num;j++）
la->List[j-1]=la->List[j];
la->Num--;
return1;
}
}
voidoutput（Seqlist*la）
{intm;
printf（"当前的线性表为"）;
for（m=0;m<=la->Num;m++）
printf（"%d",la->List[m]）;
printf（"\n表长为%d\n",la->Num+1）;
}
四、思考题
1．设顺序表L中的数据元素按递增排列，编写一个算法，将数据元素x插入到顺序表L的适当位置上，以保持顺序表的有序性。
2．设计一算法实现删除顺序表a中第i个元素起的k个元素。
typedefstruct
{intelem[100];
intlength;/*顺序表的长度（即最大下标值）*/
}SqList;
3．设已有线性表la的数据结构定义同上，编写一个算法，删除顺序表la中所有值为x的数据元素。
实验二单链表的插入、删除（2学时）
一、实验目的
1、理解线性表的链式存储结构；
2、能熟练建立一个单链表，并能对其进行插入、删除等基本操作；
3、能理解指针的指针类型的运用。
二、实验内容
首先建立一个数据域为整数的由10个结点组成的单链表，然后用单链表完成在任意一个位置插入任意整数元素以及删除任意位置数据元素的操作（插入、删除位置及要插入元素数值均从键盘输入）,进行完任一操作后将顺序表中的内容及表长输出。
三、参考源程序
#include
#include
#include
typedefintelemtype;
structnode{elemtypedata;
structnode*next;
};
typedefstructnodeslnodetype;
intinitiate1（slnodetype**h）
{
*h=（slnodetype*）malloc（sizeof（slnodetype））;
if（（*h）==NULL）return0;
（*h）->next=NULL;
return1;
}
intCreatL1（slnodetype**h,elemtypea[],intn）
{
slnodetype*p,*s;
intj;
initiate1（h）;
p=*h;
for（j=0;j<=n-1;j++）
{
if（（s=（slnodetype*）malloc（sizeof（slnodetype）））==NULL）
return0;
s->data=a[j];
s->next=NULL;
p->next=s;
p=s;
}
return1;
}
slnodetype*getSL（slnodetype*head,inti）
{
slnodetype*p;
intj;
p=head->next;
while（（p!
=NULL）&&（j{p=p->next;
j++;
}
return（p）;
}
intinsertsl（slnodetype*h,inti,elemtypex）
{
slnodetype*p,*s;
intj;
p=h;
j=0;
while（（p->next!
=NULL）&&（j{
p=p->next;
j++;
}
if（j!
=i-1）
{
printf（"\n插入位置不合理！
"）;
return0;
}
if（（s=（slnodetype*）malloc（sizeof（slnodetype）））==NULL）
return0;
s->data=x;
s->next=p->next;
p->next=s;
return1;
}
intdeletesl（slnodetype*h,inti）
{
slnodetype*p,*s;
intj;
p=h;
j=0;
while（（p->next->next!
=NULL）&&（j{
p=p->next;
j++;
}
if（j!
=i-1）
{
printf（"\n删除位置不合理!
"）;
return0;
}
s=p->next;
p->next=s->next;
free（s）;
return1;
}
out_put（slnodetype*head）
{slnodetype*p;
inti=0;
p=head->next;
printf（"\n当前的线性表数据内容为"）;
while（p!
=NULL）
{printf（"%d",p->data）;
p=p->next;
i++;
}
printf（"\n线性表的表长为%d\n",i）;
}
voidmain（）
{
inti,j,m;
elemtypex,a[10];
slnodetype*head;
for（i=0;i<=9;i++）
{
printf（"\npleaseinputNO.%ddata",i+1）;
scanf（"%d",&a[i]）;
}
CreatL1（&head,a,10）;
out_put（head）;
printf（"\nPleaseinputthevalueofm:
m=1---insertm=2---deletem=3--exit\nm="）;
scanf（"%d",&m）;
if（m==1）
{printf（"Pleaseinputinsertlocationandinsertdata:
"）;
scanf（"%d%d",&i,&x）;
insertsl（head,i,x）;
out_put（head）;
}
elseif（m==2）
{printf（"Pleaseinputdeletelocation:
"）;
scanf（"%d",&j）;
deletesl（head,j）;
out_put（head）;
}
elseif（m==3）
exit
（1）;
else
printf（"Thevalueofmiswrong!
"）;
}
四、思考题
1.编写一个算法，删除单链表l中值相同的多余结点。
2．实现单链表的就地逆序，设其头结点指针为head，编写一个算法将单链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
3．假设现有一个带头结点的单链表head，试写出将单链表中结点数据值为偶数的结点，复制并放入另一个带头结点的单链表head1的头部的算法。
4．设现有一个带头结点的单链表（头指针为head），试写出一算法，删除该单链表中数据为奇数的所有结点。
实验三顺序栈的入栈、出栈（2学时）
一、实验目的
1、理解堆栈是一种先进后出的特殊线性表；
2、能熟练掌握顺序栈的入栈出栈操作；
3、掌握如何判断以及何时该判断堆栈满或空的条件。
二、实验内容
进行顺序栈初始化，实现9个数据的依次入栈及出栈操作。
三、参考源程序
#include
#include
#definemaxlen10
#definem9
typedefintelemtype;
typedefstruct{
elemtypestack[maxlen];
inttop;
}seqstack;
seqstack*inistack（）
{
seqstack*s;
if（（s=（seqstack*）malloc（sizeof（seqstack）））==NULL）
return0;
s->top=-1;
returns;
}
intpush（seqstack*s,elemtypex）
{
if（s->top==maxlen-1）
{
printf（"\nStackisfull"）;
return0;
}
s->top++;
s->stack[s->top]=x;
return1;
}
elemtypepop（seqstack*s）
{
if（s->top==-1）
{
printf（"\nStackisempty!
"）;
return0;
}
elsereturn（s->stack[（s->top）--]）;
}
main（）
{intx,i,j;
seqstack*s;
s=inistack（）;
for（i=1;i<=m;i++）
{printf（"\nPleaseinputadata!
"）;
scanf（"%d",&x）;
push（s,x）;
}
printf（"Theoutputorderis:
"）;
for（j=s->top;j>=0;j--）
printf（"%d",pop（s））;
}
四、思考题
1．如何实现两个顺序栈的共用？
2．设两个栈（stack1，stack2）共享一个一维数组空间s[m]，它们的栈底分别设在数组的两端，试编写一算法，从键盘输入一个整数x，该数大于100时放入stack2，否则放入stack1。
#definem10
typedefstructstack
{ints[m];
inttop1;
inttop2;
}STACK;
STACK*p;
实验四循环队列的入队、出队（2学时）
一、实验目的
1、理解队列是一种先进先出的特殊线性表；
2、能熟练建立循环队列，掌握判断循环队列队满和队空的条件；
3、能熟练掌握循环队列的入队出队操作。
二、实验内容
先建立一个循环队列，然后完成任意队列元素的入队和出队操作。
三、参考源程序
#include
#include
#include
#definemaxlen100
typedefintelemtype;
typedefstruct
{elemtypequeue[maxlen];
intfront,rear;
}sequeue;
voidiniqueue（sequeue*sq）
{
sq->front=0;
sq->rear=0;
}
intaddqueue（sequeue*sq,elemtypex）
{
if（sq->front==（sq->rear+1）%maxlen）
{
printf（"\nQueueisfull"）;
return0;
}
sq->rear=（sq->rear+1）%maxlen;
sq->queue[sq->rear]=x;
return1;
}
elemtypedelqueue（sequeue*sq）
{
if（sq->front==sq->rear）
{
printf（"\nQueueisempty!
"）;
exit
（1）;
}
sq->front=（sq->front+1）%maxlen;
return（sq->queue[sq->front]）;
}
output（sequeue*sq）
{intm;
m=sq->front;
printf（"\nThequeueis:
"）;
while（m!
=sq->rear）
{
m=（m+1）%maxlen;
printf（"%d",sq->queue[m]）;
}
}
voidmain（）
{
inth,a;
sequeue*sq;
if（（sq=（sequeue*）malloc（sizeof（sequeue）））==NULL）
exit（0）;
iniqueue（sq）;
printf（"\nPleaseinputadata!
enter'0'—exit\n"）;
scanf（"%d",&a）;
while（a!
=0）
{addqueue（sq,a）;
printf（"Pleaseinputadata!
\n"）;
scanf（"%d",&a）;
}
output（sq）;
printf（"\nDoyouwanttoaddadataordeleteadata?
1--add2--delete0--exit\n"）;
scanf（"%d",&h）;
while（h!
=0）
{if（h==1）
{printf（"Pleaseinputtheadddata!
"）;
scanf（"%d",&a）;
addqueue（sq,a）;
output（sq）;
printf（"\nGOON?
1--add2--delete0--exit\n"）;
scanf（"%d",&h）;
}
elseif（h==2）
{a=delqueue（sq）;
printf（"Thedeletedatais%d",a）;
output（sq）;
printf（"\nGOON?
1--add2--delete0--exit\n"）;
scanf（"%d",&h）;
}
}
}
四、思考题
除了循环队列，还有哪些方法可以解决顺序队列“假溢出”的问题？
实验五稀疏矩阵的转置
一、实验目的
1、熟悉数组的有关概念；
2、能熟练掌握稀疏矩阵的三元组存储结构的转置方法。
二、实验内容
用三元组顺序表存储结构存储稀疏矩阵，实现稀疏矩阵的转置运算。
三、参考源程序
#include“stdio.h”
#definemaxsize10000
typedefintelemtype;
typedefstruct
{
inti,j;
elemtyped;
}tupletype;
typedefstruct
{
tupletypedata[maxsize];
intmd,nd,td;
}tabletype;
voidtrantup（tabletypesa,tabletype*sb）;
main（）
{
tabletypea={{{1,2,1},{1,4,2},{3,2,3},{8,2,4},{9,3,5},{9,4,6}},29,33,6};
tabletypeb;
intk;
trantup（a,&b）;
printf（“转置前的矩阵”）;
for（k=0;kprintf（“i=%dj=%ddata=%d\n”,a.data[k].i,a.data[k].j,a.data[k].d）;
printf（“转置后的矩阵”）;
for（k=0;kprintf（“i=%dj=%ddata=%d\n”,b.data[k].i,b.data[k].j,b.data[k].d）;
}
voidtrantup（tabletypesa,tabletype*sb）
{intp,q,v;
sb->md=sa.nd;
sb->nd=sa.md;
sb->td=sa.td;
if（sb->td!
=0）
{q=0;
for（v=0;v{for（p=0;p{if（sa.data[p].j==v）
{sb->data[q].i=sa.data[p].j;
sb->data[q].j=sa.data[p].i;
sb->data[q].d=sa.data[p].d;
q++;}
}
}
}
}
四、思考题
采用三元组存储稀疏矩阵的目的是什么？
实验六二叉排序树的建立及遍历（4学时）
一、实验目的
1、掌握二叉排序树的有关概念；
2、能根据所给序列构造（建立）二叉排序树；
3、能熟练掌握二叉树的插入算法；
4、能熟练掌握二叉树的先序、中序和后序遍历算法。
二、实验内容
根据给定序列建立二叉排序树，显示中序、后序、先序的遍历结果。
三、参考源程序
#include
#include
typedefintelemtype;
typedefstructbtreenode
{
elemtypeData;
structbtreenode*lchild;
structbtreenode*rchild;
}TREENODE;
TREENODE*Create（elemtypex,TREENODE*lbt,TREENODE*rbt）;
TREENODE*InsertL（elemtypex,TREENODE*Parent）;
TREENODE*InsertR（elemtypex,TREENODE*Parent）;
voidpreorder（TREENODE*bt）;
voidinorder（TREENODE*bt）;
voidpostorder（TREENODE*bt）;
main（）
{intx;
TREENODE*bt,*p,*q;
printf（"inputroot"）;
scanf（"%d",&x）;
p=Create（x,NULL,NULL）;
bt=p;
printf（"pleaseinputdata,-1--end:
"）;
scanf（"%d",&x）;
while（x!
=-1）
{p=bt;
q=p;
while（q!
=NULL）
{p=q;
if（xData）
q=p->lchild;
else
q=p->rchild;
}
if（xData）
InsertL（x,p）;
else
InsertR（x,p）;
printf（"pleaseinputdata,-1--end:
"）;
scanf（"%d",&x）;
}
printf（"\n先序遍历结果为：
"）;
preorder（bt）;
printf（"\n中序遍历结果为：
"）;
inorder（bt）;
printf（"\n后序遍历结果为：
"）;
postorder（bt）;
}
TREENODE*Create（elem
升级会员 