《软件技术基础》实验指导Word文档下载推荐.docx
《《软件技术基础》实验指导Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《《软件技术基础》实验指导Word文档下载推荐.docx(52页珍藏版)》请在冰点文库上搜索。
![《软件技术基础》实验指导Word文档下载推荐.docx](https://file1.bingdoc.com/fileroot1/2023-5/7/fd7c05c5-034e-4d25-bf00-78d1751c9275/fd7c05c5-034e-4d25-bf00-78d1751c92751.gif)
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<
stdio.h>
malloc.h>
//顺序表结构类型定义
typedefchardatatype;
constintmaxsize=1024;
typedefstruct
{datatypedata[maxsize];
intlast;
}sequenlist;
voidcreate(sequenlist*&
);
voidprint(sequenlist*);
voidinvert(sequenlist*);
voidmain()
{
sequenlist*L;
create(L);
//建立顺序表
print(L);
//输出顺序表
invert(L);
//调用顺序表逆值的函数
}
L)
L=(sequenlist*)malloc(sizeof(sequenlist));
L->
last=0;
charch;
while((ch=getchar())!
='
*'
)
{
L->
last++;
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;
L->
last+1-i;
{
a[i]=L->
data[i];
data[i]=L->
last+1-i];
last+1-i]=a[i];
第1题
(2)
//单链表逆置的程序代码
//单链表结构类型定义
typedefstructnode
datatypedata;
structnode*next;
}linklist;
voidcreate(linklist*&
voidprint(linklist*);
voidinvert(linklist*);
linklist*head;
create(head);
print(head);
invert(head);
//调用单链表逆置的函数
//采用尾插法建立具有头结点的单链表
head)
linklist*s,*r;
head=(linklist*)malloc(sizeof(linklist));
r=head;
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)
p->
data);
p=p->
//单链表逆置
voidinvert(linklist*head)
linklist*p,*q;
//定义结构体指针p,q
p=head->
head->
q=p->
//q指向p的后继结点
p->
next=head->
next=p;
p=q;
第2题
//分解单链表的程序代码
//链表结构类型定义
{datatypedata;
voidresolve(linklist*,linklist*,linklist*,linklist*);
voidinsert(linklist*,linklist*);
voidprint1(linklist*);
voidprint2(linklist*);
{linklist*head,*letter,*digit,*other;
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);
//建立单链表
{datatypex;
head=newlinklist;
while((x=getchar())!
$'
s=(linklist*)malloc(sizeof(linklist));
s->
data=x;
r=s;
//在循环链表中插入
voidinsert(linklist*h,linklist*p)
{linklist*q=h;
while(q->
next!
=h)q=q->
q->
next=h;
voidprint1(linklist*head)
{linklist*p=head->
{printf("
%c"
p=p->
voidprint2(linklist*head)
=head)
//按字母、数字、其它字符分解单链表
voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other)
linklist*q=letter;
linklist*r=digit;
linklist*v=other;
linklist*s;
data=p->
data;
if(s->
data>
=65&
&
s->
data<
=122)//如果为字母
{
s->
q->
q=q->
}
elseif(s->
=48&
=57)//如果为数字
r=r->
else//其他
v->
v=v->
//free(s);
为什么不能释放呢?
?
实验二:
第1题
//判字符串中心对称的程序代码
string.h>
//定义单链表结构类型
//定义顺序栈结构类型
constintmaxsize=40;
{datatypeelements[maxsize];
inttop;
}stack;
voidsetnull(stack*&
intlength(linklist*);
voidprintlink(linklist*);
voidcreate(linklist*&
datatype*);
voidpush(stack*,datatype);
datatypepop(stack*);
intsymmetry(linklist*,stack*);
//判字符串是否中心对称的函数声明
linklist*head;
stack*s;
datatypestr[80];
gets(str);
create(head,str);
printlink(head);
setnull(s);
if(symmetry(head,s))printf("
字符串\"
%s\"
中心对称\n"
str);
elseprintf("
不是中心对称\n"
//栈初始化
s)
s=(stack*)malloc(sizeof(stack));
top=-1;
//求单链表长度
intlength(linklist*head)
intn=0;
=NULL){n++;
returnn;
voidprintlink(linklist*head)
//建立具有头结点的单链表
head,datatype*str)
{datatype*p=str;
while(*p!
\0'
data=*p;
p++;
//顺序栈入栈
voidpush(stack*s,datatypee)
top++;
elements[s->
top]=e;
//顺序栈出栈
datatypepop(stack*s)
datatypetemp;
top--;
temp=s->
top+1];
returntemp;
//判字符串是否中心对称
intsymmetry(linklist*head,stack*s)
{
inti=1,j=1;
intn=length(head);
//printf("
n=%d\n"
n);
//先把前一半字符依次进栈
//datatypem;
=n/2;
{push(s,p->
//依次出栈与另一半字符进行比较
if(n%2!
=0)//判断n的奇偶
else
p=p;
while(s->
top]==p->
data&
p!
=NULL&
top>
0)//循环至不等或其中一个为空
j++;
pop(s);
//printf("
j=%2d;
n/2=%2d\n"
j,n/2);
if(j==n/2)
return1;
else
return0;
//循环队列入队出队的程序代码
stdlib.h>
//循环队列的结构类型定义
constintm=5;
typedefintdatatype;
{datatypesequ[m];
intrear,quelen;
}qu;
voidsetnull(qu*);
voidenqueue(qu*,datatype);
datatype*dequeue(qu*);
{qu*sq;
datatypex,*p;
intkey;
sq=(qu*)malloc(sizeof(qu));
setnull(sq);
do
1.EnterQueue2.DeleteQueue-1.Quit:
"
scanf("
%d"
&
key);
switch(key)
{case1:
EntertheData:
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("
队列上溢"
rear=(sq->
rear+1)%m;
//尾指针加1
sequ[sq->
rear]=x;
quelen++;
//添加出队算法
datatype*dequeue(qu*sq)//出队
//datatypetmp;
quelen==0)//判队空
队列下溢"
//tmp=sq->
sequ[(sq->
rear-sq->
quelen+m)%m];
quelen--;
return(&
quelen+m)%m]);
实验三:
//模式匹配的程序代码
//顺序串的结构类型定义
#definemaxsize100
charstr[maxsize];
intlen;
}seqstring;
intIndex(seqstring*,seqstring*);
seqstring*S,*subS;
S=(seqstring*)malloc(sizeof(seqstring));
subS=(seqstring*)malloc(sizeof(seqstring));
输入串:
gets(S->
str);
S->
len=strlen(S->
输入子串:
gets(subS->
subS->
len=strlen(subS->
if(Index(S,subS)>
0)printf("
匹配成功!
匹配失败!
//顺序串的朴素模式匹配
intIndex(seqstring*S,seqstring*subS)
//目标串从第一个字符开始与模式串的第一个字符开始进行比较
while(i<
=S->
len&