《软件技术基础》实验指导.docx
《《软件技术基础》实验指导.docx》由会员分享，可在线阅读，更多相关《《软件技术基础》实验指导.docx（52页珍藏版）》请在冰点文库上搜索。
《软件技术基础》实验指导
说明
每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。
对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。
实验一线性表
一、实验目的
1．熟悉线性表的顺序和链式存储结构
2．掌握线性表的基本运算
3．能够利用线性表的基本运算完成线性表应用的运算
二、实验内容
1．设有一个线性表E={e1,e2,…,en-1,en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={en,en-1,…,e2,e1}，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。
（文件夹：
顺序表逆置、单链表逆置）
2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。
（文件夹：
分解单链表）
实验二栈和队列
一、实验目的
1．熟悉栈和队列的顺序和链式存储结构
2．掌握栈和队列的基本运算
3．能够利用栈和队列的基本运算完成栈和队列应用的运算
二、实验内容
1．设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。
（提示：
将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。
）（文件夹：
判字符串中心对称）
2．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。
编写实现该循环队列的入队和出队操作的算法。
提示：
队空的条件：
sq->quelen==0；队满的条件：
sq->quelen==m。
（文件夹：
循环队列）
实验三串
一、实验目的
1．熟悉串的顺序存储结构
2．掌握串的基本运算及应用
二、实验内容
1．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。
（文件夹：
模式匹配）
2．若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法voidSteDelete（char*S,intI,intm），要求从S中删除从第i个字符开始的连续m个字符。
若i≥strlen（S），则没有字符被删除；若i+m≥strlen（S），则将S中从位置i开始直至末尾的字符均删除。
（文件夹：
删除子串）
实验四数组
一、实验目的
1．熟悉数组的结构
2．掌握矩阵的压缩存储
3．能够对数组和矩阵的压缩存储进行运算
二、实验内容
1.若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。
用二维数组存储矩阵Am×n，设计算法求出矩阵中所有马鞍点。
（文件夹：
找马鞍点）
2.A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。
（文件夹：
对称矩阵相乘）
实验五树
一、实验目的
1．熟悉二叉树的链式存储结构
2．掌握二叉树的建立、深度优先递归遍历等算法
3．能够利用遍历算法实现一些应用
二、实验内容
1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。
（文件夹：
交换左右子树）
2．采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。
（文件夹：
统计二叉树结点）
实验六图
一、实验目的
1．熟悉图的邻接矩阵和邻接表的存储结构
2．熟悉图的邻接矩阵和邻接表的建立算法
3．掌握图的遍历算法
二、实验内容
1．无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。
（文件夹：
无向图邻接矩阵）
实验七排序
一、实验目的
1．熟悉各种内部排序算法
2．能够编写程序显示排序过程中各趟排序的结果
3．能够编写一些排序的算法
二、实验内容
1．采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。
（文件夹：
希尔排序）
2．编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序的结果。
（文件夹：
双向起泡排序）
实验八查找
一、实验目的
1．熟悉线性表、二叉排序树和散列表的查找
2．能够编写一些查找的算法
二、实验内容
1．18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53，编写分块查找的算法进行查找。
（文件夹：
分块查找）
2．编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，结点的数据域只存放正整数。
（文件夹：
判断二叉排序树）
附录：
原代码
实验一：
第1题
（1）
//顺序表逆置的程序代码
#include
#include
//顺序表结构类型定义
typedefchardatatype;
constintmaxsize=1024;
typedefstruct
{datatypedata[maxsize];
intlast;
}sequenlist;
voidcreate（sequenlist*&）;
voidprint（sequenlist*）;
voidinvert（sequenlist*）;
voidmain（）
{
sequenlist*L;
create（L）;//建立顺序表
print（L）;//输出顺序表
invert（L）;//调用顺序表逆值的函数
print（L）;//输出顺序表
}
//建立顺序表
voidcreate（sequenlist*&L）
{
L=（sequenlist*）malloc（sizeof（sequenlist））;
L->last=0;
charch;
while（（ch=getchar（））!
='*'）
{
L->last++;
L->data[L->last]=ch;
}
}
//输出顺序表
voidprint（sequenlist*L）
{
for（inti=1;i<=L->last;i++）
printf（"%2c",L->data[i]）;
printf（"\n"）;
}
//顺序表逆置
voidinvert（sequenlist*L）
{
inti;
chara[maxsize];
for（i=1;ilast+1-i;i++）
{
a[i]=L->data[i];
L->data[i]=L->data[L->last+1-i];
L->data[L->last+1-i]=a[i];
}
}
实验一：
第1题
（2）
//单链表逆置的程序代码
#include
#include
//单链表结构类型定义
typedefchardatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
voidcreate（linklist*&）;
voidprint（linklist*）;
voidinvert（linklist*）;
voidmain（）
{
linklist*head;
create（head）;
print（head）;
invert（head）;//调用单链表逆置的函数
print（head）;
}
//采用尾插法建立具有头结点的单链表
voidcreate（linklist*&head）
{
charch;
linklist*s,*r;
head=（linklist*）malloc（sizeof（linklist））;
r=head;
while（（ch=getchar（））!
='*'）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
}
//输出单链表
voidprint（linklist*head）
{
linklist*p=head->next;
while（p!
=NULL）
{
printf（"%2c",p->data）;
p=p->next;
}
printf（"\n"）;
}
//单链表逆置
voidinvert（linklist*head）
{
linklist*p,*q;//定义结构体指针p,q
p=head->next;
head->next=NULL;
while（p!
=NULL）
{
q=p->next;//q指向p的后继结点
p->next=head->next;
head->next=p;
p=q;
}
}
实验一：
第2题
//分解单链表的程序代码
#include
#include
//链表结构类型定义
typedefchardatatype;
typedefstructnode
{datatypedata;
structnode*next;
}linklist;
voidcreate（linklist*&）;
voidresolve（linklist*,linklist*,linklist*,linklist*）;
voidinsert（linklist*,linklist*）;
voidprint1（linklist*）;
voidprint2（linklist*）;
voidmain（）
{linklist*head,*letter,*digit,*other;
create（head）;
print1（head）;
letter=（linklist*）malloc（sizeof（linklist））;//建立3个空循环链表
letter->next=letter;
digit=（linklist*）malloc（sizeof（linklist））;
digit->next=digit;
other=（linklist*）malloc（sizeof（linklist））;
other->next=other;
resolve（head,letter,digit,other）;//调用分解单链表的函数
print2（letter）;//输出循环链表
print2（digit）;
print2（other）;
}
//建立单链表
voidcreate（linklist*&head）
{datatypex;
linklist*s,*r;
head=newlinklist;
r=head;
while（（x=getchar（））!
='$'）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=x;
r->next=s;
r=s;
}
r->next=NULL;
}
//在循环链表中插入
voidinsert（linklist*h,linklist*p）
{linklist*q=h;
while（q->next!
=h）q=q->next;
q->next=p;
p->next=h;
}
//输出单链表
voidprint1（linklist*head）
{linklist*p=head->next;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
//输出循环链表
voidprint2（linklist*head）
{linklist*p=head->next;
while（p!
=head）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
//按字母、数字、其它字符分解单链表
voidresolve（linklist*head,linklist*letter,linklist*digit,linklist*other）
{
linklist*p=head->next;
linklist*q=letter;
linklist*r=digit;
linklist*v=other;
linklist*s;
while（p!
=NULL）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=p->data;
if（s->data>=65&&s->data<=122）//如果为字母
{
s->next=letter;
q->next=s;
q=q->next;
}
elseif（s->data>=48&&s->data<=57）//如果为数字
{
s->next=digit;
r->next=s;
r=r->next;
}
else//其他
{
s->next=other;
v->next=s;
v=v->next;
}
//free（s）;为什么不能释放呢？
？
p=p->next;
}
}
实验二：
第1题
//判字符串中心对称的程序代码
#include
#include
#include
//定义单链表结构类型
typedefchardatatype;
typedefstructnode
{datatypedata;
structnode*next;
}linklist;
//定义顺序栈结构类型
constintmaxsize=40;
typedefstruct
{datatypeelements[maxsize];
inttop;
}stack;
voidsetnull（stack*&）;
intlength（linklist*）;
voidprintlink（linklist*）;
voidcreate（linklist*&,datatype*）;
voidpush（stack*,datatype）;
datatypepop（stack*）;
intsymmetry（linklist*,stack*）;//判字符串是否中心对称的函数声明
voidmain（）
{
linklist*head;stack*s;
datatypestr[80];
gets（str）;
create（head,str）;
printlink（head）;
setnull（s）;
if（symmetry（head,s））printf（"字符串\"%s\"中心对称\n",str）;
elseprintf（"字符串\"%s\"不是中心对称\n",str）;
}
//栈初始化
voidsetnull（stack*&s）
{
s=（stack*）malloc（sizeof（stack））;
s->top=-1;
}
//求单链表长度
intlength（linklist*head）
{linklist*p=head->next;
intn=0;
while（p!
=NULL）{n++;p=p->next;}
returnn;
}
//输出单链表
voidprintlink（linklist*head）
{linklist*p=head->next;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
//建立具有头结点的单链表
voidcreate（linklist*&head,datatype*str）
{datatype*p=str;
linklist*s,*r;
head=（linklist*）malloc（sizeof（linklist））;
r=head;
while（*p!
='\0'）
{
s=（linklist*）malloc（sizeof（linklist））;
s->data=*p;
r->next=s;
r=s;
p++;
}
r->next=NULL;
}
//顺序栈入栈
voidpush（stack*s,datatypee）
{
s->top++;
s->elements[s->top]=e;
}
//顺序栈出栈
datatypepop（stack*s）
{
datatypetemp;
s->top--;
temp=s->elements[s->top+1];
returntemp;
}
//判字符串是否中心对称
intsymmetry（linklist*head,stack*s）
{
inti=1,j=1;
intn=length（head）;
//printf（"n=%d\n",n）;
linklist*p=head->next;
//先把前一半字符依次进栈
//datatypem;
for（i=1;i<=n/2;i++）
{push（s,p->data）;
p=p->next;
}
//依次出栈与另一半字符进行比较
if（n%2!
=0）//判断n的奇偶
p=p->next;
else
p=p;
while（s->elements[s->top]==p->data&&p!
=NULL&&s->top>0）//循环至不等或其中一个为空
{
j++;
pop（s）;
p=p->next;
}
//printf（"j=%2d;n/2=%2d\n",j,n/2）;
if（j==n/2）
return1;
else
return0;
}
实验二：
第2题
//循环队列入队出队的程序代码
#include
#include
#include
//循环队列的结构类型定义
constintm=5;
typedefintdatatype;
typedefstruct
{datatypesequ[m];
intrear,quelen;
}qu;
voidsetnull（qu*）;
voidenqueue（qu*,datatype）;
datatype*dequeue（qu*）;
voidmain（）
{qu*sq;
datatypex,*p;
intkey;
sq=（qu*）malloc（sizeof（qu））;
setnull（sq）;
do
{printf（"1.EnterQueue2.DeleteQueue-1.Quit:
"）;
scanf（"%d",&key）;
switch（key）
{case1:
printf（"EntertheData:
"）;scanf（"%d",&x）;
enqueue（sq,x）;break;
case2:
p=dequeue（sq）;
if（p!
=NULL）printf（"%d\n",*p）;
break;
case-1:
exit（0）;
}
}while
（1）;
}
//置空队
voidsetnull（qu*sq）
{sq->rear=m-1;
sq->quelen=0;
}
//添加入队算法
voidenqueue（qu*sq,datatypex）
{
if（sq->quelen==m）//判队满
{printf（"队列上溢"）;}
else
{
sq->rear=（sq->rear+1）%m;//尾指针加1
sq->sequ[sq->rear]=x;
sq->quelen++;
}
}
//添加出队算法
datatype*dequeue（qu*sq）//出队
{
//datatypetmp;
if（sq->quelen==0）//判队空
{printf（"队列下溢"）;}
else
{
//tmp=sq->sequ[（sq->rear-sq->quelen+m）%m];
sq->quelen--;
return（&sq->sequ[（sq->rear-sq->quelen+m）%m]）;
}
}
实验三：
第1题
//模式匹配的程序代码
#include
#include
#include
//顺序串的结构类型定义
#definemaxsize100
typedefstruct
{
charstr[maxsize];
intlen;
}seqstring;
intIndex（seqstring*,seqstring*）;
voidmain（）
{
seqstring*S,*subS;
S=（seqstring*）malloc（sizeof（seqstring））;
subS=（seqstring*）malloc（sizeof（seqstring））;
printf（"输入串：
"）;gets（S->str）;
S->len=strlen（S->str）;
printf（"输入子串：
"）;gets（subS->str）;
subS->len=strlen（subS->str）;
if（Index（S,subS）>0）printf（"匹配成功！
\n"）;
elseprintf（"匹配失败！
\n"）;
}
//顺序串的朴素模式匹配
intIndex（seqstring*S,seqstring*subS）
{
inti=1,j=1;//目标串从第一个字符开始与模式串的第一个字符开始进行比较
while（i<=S->len&
升级会员 