数据结构上机实验报告文档格式.docx
《数据结构上机实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构上机实验报告文档格式.docx（35页珍藏版）》请在冰点文库上搜索。
='
*'
）
{
s=newlinklist;
s->
data=ch;
r->
next=s;
r=s;
}
r->
next=NULL;
//输出单链表.h
voidprint（linklist*head）
linklist*p=head->
next;
while（p!
=NULL）
cout<
<
p->
data<
"
"
;
p=p->
cout<
endl;
//单链表逆置.h
voidinvert（linklist*head）
linklist*p,*q,*r;
p=head->
q=p->
while（q!
r=q->
q->
next=p;
p=q;
q=r;
head->
next->
单链表结果截图见下方实验结果。
顺序表代码：
//顺序表逆置主文件.cpp
顺序表结构类型定义.h"
建立顺序表.h"
输出顺序表.h"
顺序表逆置.h"
sequenlist*L;
creat（L）;
print（L）;
invert（L）;
//调用顺序表逆值的函数
//顺序表的结构类型定义.h
constintmaxsize=1024;
typedefstruct
{datatypedata[maxsize];
intlast;
}sequenlist;
//建立顺序表.h
voidcreat（sequenlist*&
L）
L=newsequenlist;
L->
last=0;
L->
data[L->
last]=ch;
last++;
//输出顺序表.h
voidprint（sequenlist*L）
for（inti=0;
i<
L->
last;
i++）
data[i]<
//顺序表逆置.h
voidinvert（sequenlist*L）
{charmid;
inti,j;
i=0;
j=L->
last-1;
while（i<
j）
mid=L->
data[i];
data[i]=L->
data[j];
data[j]=mid;
i++;
j--;
顺序表实验截图见下方实验结果。
2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。
习题2）
//分解单链表主程序文件.cpp
输出循环链表.h"
在循环链表中插入.h"
分解单链表.h"
{linklist*head,*letter,*digit,*other;
print1（head）;
letter=newlinklist;
letter->
next=letter;
digit=newlinklist;
digit->
next=digit;
other=newlinklist;
other->
next=other;
resolve（head,letter,digit,other）;
//调用分解单链表的函数
print2（letter）;
print2（digit）;
print2（other）;
//单链表结构类型定义
{datatypedata;
//建立单链表
{datatypex;
cin>
>
x;
while（x!
$'
{
s=newlinklist;
s->
data=x;
r=s;
voidprint1（linklist*head）
//输出单链表
{linklist*p=head->
{cout<
data;
p=p->
voidprint2（linklist*head）
//输出循环链表
=head）
//在循环链表中插入.h
voidinsert（linklist*h,linklist*p）
{linklist*q=h;
while（q->
next!
=h）q=q->
q->
p->
next=h;
//分解单链表.h
voidresolve（linklist*head,linklist*letter,linklist*digit,linklist*other）
linklist*p=head->
next,*t;
next=NULL;
while（p!
t=p;
if（t->
data>
0'
&
&
t->
data<
9'
insert（digit,t）;
elseif（（t->
a'
z'
）||
（t->
A'
Z'
））
insert（letter,t）;
elseinsert（other,t）;
return;
截图见下方实验结果。
3、实验结果
四、个人思路
顺序表做逆置操作时将对应的首尾元素位置交换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容交换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end指针的节点，并将end指针赋值为s指针，就完成了单链表的逆置，可以看出单链表和顺序表都可以完成线性表的逆置。
分解单链表的实现思路是首先新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到对应的循环链表中，从而实现分解单链表的功能。
实验二栈和队列
1．熟悉栈和队列的顺序和链式存储结构
2．掌握栈和队列的基本运算
3．能够利用栈和队列的基本运算完成栈和队列应用的运算
1．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。
编写实现该循环队列的入队和出队操作的算法。
提示：
队空的条件：
sq->
quelen==0；
队满的条件：
quelen==m。
习题3）
//循环队列入队出队的主程序文件.cpp
stdlib.h>
循环队列的结构类型定义.h"
置空队.h"
入队.h"
出队.h"
{qu*sq;
datatypex,*p;
intkey;
sq=newqu;
setnull（sq）;
do
{cout<
1.EnterQueue2.DeleteQueue-1.Quit:
cin>
key;
switch（key）
{case1:
EntertheData:
enqueue（sq,x）;
break;
case2:
p=dequeue（sq）;
if（p!
=NULL）cout<
*p<
break;
case-1:
exit（0）;
}while
（1）;
//出队.h
datatype*dequeue（qu*sq）
{
datatype*temp;
if（sq->
quelen==0）
printf（"
队列为空，请先进行入队操作\n"
）;
return0;
}
else
temp=（datatype*）malloc（sizeof（datatype））;
sq->
quelen--;
*temp=sq->
sequ[（sq->
rear-sq->
quelen+m）%m];
cout<
出队成功!
\n"
return（temp）;
//入队.h
voidenqueue（qu*sq,datatypex）
quelen==m）
printf（"
队列已满，请先进行出队操作\n"
else{
quelen++;
rear=（sq->
rear+1）%m;
sequ[sq->
rear]=x;
入队成功!
//循环队列的结构类型定义.h
constintm=5;
typedefintdatatype;
typedefstruct
{datatypesequ[m];
intrear,quelen;
}qu;
//置空队.h
voidsetnull（qu*sq）
{sq->
rear=m-1;
quelen=0;
实验截图见下方实验结果。
2.设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。
（提示：
将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。
）（文件夹：
习题4）
//判字符串中心对称的主程序文件.cpp
单链表顺序栈结构类型定义.h"
置栈空.h"
求单链表长度.h"
顺序栈入栈.h"
顺序栈出栈.h"
判字符串是否中心对称.h"
linklist*head;
stack*s;
datatypestr[80];
str;
creat（head,str）;
printlink（head）;
setnull（s）;
if（symmetry（head,s））cout<
字符串\"
str<
\"
中心对称\n"
elsecout<
不是中心对称\n"
//定义单链表结构类型.h
typedefstructnode
structnode*next;
//定义顺序栈结构类型
constintmaxsize=40;
{datatypeelements[maxsize];
inttop;
}stack;
//建立具有头结点的单链表.h
voidcreat（linklist*&
head,datatype*str）
{datatype*p=str;
linklist*s,*r;
head=newlinklist;
while（*p!
\0'
s->
data=*p;
p++;
r->
//判断字符是否中心对称.h
intsymmetry（linklist*head,stack*s）
intn=length（head）/2;
datatypex;
for（inti=0;
n;
{
push（s,p->
data）;
}
if（length（head）%2==1）
while（p!
x=pop（s）;
if（x==p->
data）
elsereturn0;
return1;
//求单链表长度.h
intlength（linklist*head）
intn=0;
=NULL）{n++;
returnn;
voidprintlink（linklist*head）
//顺序栈出栈.h
datatypepop（stack*s）
datatypetemp;
top--;
temp=s->
elements[s->
top+1];
returntemp;
//顺序栈入栈.h
voidpush（stack*s,datatypee）
top++;
top]=e;
//置栈空.h
voidsetnull（stack*&
s）
s=newstack;
top=-1;
队列是一个先进先出的线性表，入队时，先判断队列是否已满，如果不满将元素插入到队尾，然后判断rear是否指向sequ[m]，如果是，指向队尾指针rear+1，否者rear=sequ[0]，队列内元素个数quelen+1。
出队时头指针front后移一位，如果front=sequ[m]，front指向sequ[0]，否则front++，quelen-1，从而实现入队与出队的操作。
要判断字符串是否中心对称，首先获取栈的长度N，将前N/2个元素（N为偶数）或前（N-1）/2个元素（N为奇数）顺序压入栈中，然后依次出栈（先进后出），与另一半元素依次对应比较，全为真则可判断字符串中心对称。
实验三数组
1．熟悉数组的结构
2．掌握矩阵的进行运算
若在矩阵Am×
n中存在一个元素A[i-1[j-1]，其满足A[i-1[j-1]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。
用二维数组存储矩阵Am×
n，设计算法求出矩阵中所有马鞍点。
习题5）
//找马鞍点的主程序文件.cpp
iostream>
数组的结构类型定义.h"
找马鞍点.h"
usingnamespacestd;
array*pa=newarray;
inti,j;
for（i=0;
m;
for（j=0;
j<
j++）
pa->
A[i][j];
minmax（pa）;
getchar（）;
//数组的结构类型定义.h
constintm=3;
constintn=3;
typedefstruct{
intA[m][n];
intmax[m],min[n];
}array;
//找马鞍点.h
voidminmax（array*p）
inti,j,have=0;
for（i=0;
i++）
p->
min[i]=p->
A[0][i];
for（j=1;
j++）
if（p->
A[i][j]<
min[i]）
p->
max[j]=p->
A[0][j];
for（i=1;
A[i][j]>
max[j]）
p->
for（i=0;
for（j=0;
min[i]==p->
printf（"
矩阵中存在马鞍点:
行号:
%d,列号:
%d,数值:
%d\n"
i+1,j+1,p->
A[i][j]）;
have=1;
}
if（!
have）
矩阵中没有马鞍点！
三、实验结果
4、个人思路
若称元素为该矩阵的一个马鞍点，即说明该元素是第i行元素中最小值，且又是第j列元素中最大值。
用两个循环遍历所有元素，第一个循环遍历行，第二个循环遍历列，将A[i-1][j-1]与对应行和列的每一个元素比较，如果第i行的某元素比A[i-1][j-1]小或第j列的某元素比A[i-1][j-1]大则跳出内层循环，实现寻找马鞍点的要求。
实验四树
1．熟悉二叉树的链式存储结构
2．掌握二叉树的建立、深度优先递归遍历等算法
3．能够利用遍历算法实现一些应用
1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。
习题6）
//交换左右子树的主程序文件.cpp
二叉链表的结构类型定义.h"
二叉树的建立.h"
二叉树的输出.h"
交换左右子树.h"
bitree*pb;
//指针
pb=creattree（）;
//创建一棵树,pb指向这棵树的根节点
preorder（pb）;
//打印这棵树
swap（pb）;
//交换这棵树的所有子树
//打印这颗新树
//二叉链表的结构类型定义.h
constintmaxsize=1024;
structnode*lchild,*rchild;
}bitree;
//二叉树的建立.h
bitree*creattree（）
charch;
bitree*Q[maxsize];
intfront,rear;
bitree*root,*s;
root=NULL;
front=1;
rear=0;
#'
s=NULL;
if（ch!
@'
{
s=newbitree;
s->
lchild=NULL;
rchild=NULL;
}
rear++;
Q[rear]=s;
if（rear==1）root=s;
else
if
升级会员 