数据结构上机实验报告.docx
- 文档编号:1232661
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:35
- 大小:265.01KB
数据结构上机实验报告.docx
《数据结构上机实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构上机实验报告.docx(35页珍藏版)》请在冰点文库上搜索。
数据结构上机实验报告
数据结构上机实验报告
学院:
电子工程学院
专业:
信息对抗技术
姓名:
学号:
教师:
饶鲜
日期:
实验一线性表
一、实验目的
1.熟悉线性表的顺序和链式存储结构
2.掌握线性表的基本运算
3.能够利用线性表的基本运算完成线性表应用的运算
二、实验代码
1.设有一个线性表E={e1,e2,…,en-1,en},设计一个算法,将线性表逆置,即使元素排列次序颠倒过来,成为逆线性表E’={en,en-1,…,e2,e1},要求逆线性表占用原线性表空间,并且用顺序表和单链表两种方法表示,分别用两个程序来完成。
(文件夹:
习题1)
代码:
单链表代码:
//单链表逆置主文件.cpp
#include
#include
#include"单链表结构类型定义.h"
#include"建立单链表.h"
#include"输出单链表.h"
#include"单链表逆置.h"
voidmain()
{
linklist*head;
creat(head);
print(head);
invert(head);//调用单链表逆置的函数
print(head);
}
//单链表结构类型定义.h
typedefchardatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
//建立单链表.h
voidcreat(linklist*&head)
//采用尾插法建立具有结点的单链表
{
charch;
linklist*s,*r;
head=newlinklist;
r=head;
while((ch=getchar())!
='*')
{
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=p->next;
}
cout< } //单链表逆置.h voidinvert(linklist*head) { linklist*p,*q,*r; p=head->next; q=p->next; while(q! =NULL) { r=q->next; q->next=p; p=q; q=r; } head->next->next=NULL; head->next=p; } 单链表结果截图见下方实验结果。 顺序表代码: //顺序表逆置主文件.cpp #include #include #include"顺序表结构类型定义.h" #include"建立顺序表.h" #include"输出顺序表.h" #include"顺序表逆置.h" voidmain() { sequenlist*L; creat(L); print(L); invert(L);//调用顺序表逆值的函数 print(L); } //顺序表的结构类型定义.h typedefchardatatype; constintmaxsize=1024; typedefstruct {datatypedata[maxsize]; intlast; }sequenlist; //建立顺序表.h voidcreat(sequenlist*&L) { L=newsequenlist; L->last=0; charch; while((ch=getchar())! ='*') { L->data[L->last]=ch; L->last++; } } //输出顺序表.h voidprint(sequenlist*L) { for(inti=0;i cout< cout< } //顺序表逆置.h voidinvert(sequenlist*L) {charmid; inti,j; i=0; j=L->last-1; while(i { mid=L->data[i]; L->data[i]=L->data[j]; L->data[j]=mid; i++;j--; } } 顺序表实验截图见下方实验结果。 2.已知由不具有头结点的单链表表示的线性表中,含有三类字符的数据元素(字母、数字和其他字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含有同一类的字符,且利用原表中的结点空间,头结点可另辟空间。 (文件夹: 习题2) 代码: //分解单链表主程序文件.cpp #include #include #include"单链表结构类型定义.h" #include"建立单链表.h" #include"输出单链表.h" #include"输出循环链表.h" #include"在循环链表中插入.h" #include"分解单链表.h" voidmain() {linklist*head,*letter,*digit,*other; creat(head); 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); } //单链表结构类型定义 typedefchardatatype; typedefstructnode {datatypedata; structnode*next; }linklist; voidcreat(linklist*&head) //建立单链表 {datatypex; linklist*s,*r; head=newlinklist; r=head; cin>>x; while(x! ='$') { s=newlinklist; s->data=x; r->next=s; r=s; cin>>x; } r->next=NULL; } voidprint1(linklist*head) //输出单链表 {linklist*p=head->next; while(p! =NULL) {cout< p=p->next; } cout< } voidprint2(linklist*head) //输出循环链表 {linklist*p=head->next; while(p! =head) {cout< p=p->next; } cout< } //在循环链表中插入.h voidinsert(linklist*h,linklist*p) {linklist*q=h; while(q->next! =h)q=q->next; q->next=p; p->next=h; } //分解单链表.h voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist*p=head->next,*t; head->next=NULL; while(p! =NULL) { t=p;p=p->next; if(t->data>='0'&&t->data<='9') insert(digit,t); elseif((t->data>='a'&&t->data<='z')|| (t->data>='A'&&t->data<='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;队满的条件: sq->quelen==m。 (文件夹: 习题3) //循环队列入队出队的主程序文件.cpp #include #include #include #include"循环队列的结构类型定义.h" #include"置空队.h" #include"入队.h" #include"出队.h" voidmain() {qu*sq; datatypex,*p; intkey; sq=newqu; setnull(sq); do {cout<<"1.EnterQueue2.DeleteQueue-1.Quit: "; cin>>key; switch(key) {case1: cout<<"EntertheData: ";cin>>x; 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) { if(sq->quelen==m) printf("队列已满,请先进行出队操作\n"); else{ sq->quelen++; sq->rear=(sq->rear+1)%m; sq->sequ[sq->rear]=x; cout<<"入队成功! \n"; } } //循环队列的结构类型定义.h constintm=5; typedefintdatatype; typedefstruct {datatypesequ[m]; intrear,quelen; }qu; //置空队.h voidsetnull(qu*sq) {sq->rear=m-1; sq->quelen=0; } 实验截图见下方实验结果。 2.设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。 (提示: 将单链表中的一半字符先依次进栈,然后依次出栈与单链表中的另一半字符进行比较。 )(文件夹: 习题4) //判字符串中心对称的主程序文件.cpp #include #include"单链表顺序栈结构类型定义.h" #include"置栈空.h" #include"求单链表长度.h" #include"输出单链表.h" #include"建立单链表.h" #include"顺序栈入栈.h" #include"顺序栈出栈.h" #include"判字符串是否中心对称.h" voidmain() { linklist*head;stack*s; datatypestr[80]; cin>>str; creat(head,str); printlink(head); setnull(s); if(symmetry(head,s))cout<<"字符串\""< elsecout<<"字符串\""< } //定义单链表结构类型.h typedefchardatatype; typedefstructnode {datatypedata; structnode*next; }linklist; //定义顺序栈结构类型 constintmaxsize=40; typedefstruct {datatypeelements[maxsize]; inttop; }stack; //建立具有头结点的单链表.h voidcreat(linklist*&head,datatype*str) {datatype*p=str; linklist*s,*r; head=newlinklist; r=head; while(*p! ='\0') { s=newlinklist; s->data=*p; r->next=s; r=s; p++; } r->next=NULL; } //判断字符是否中心对称.h intsymmetry(linklist*head,stack*s) { intn=length(head)/2; linklist*p=head->next; datatypex; for(inti=0;i { push(s,p->data); p=p->next; } if(length(head)%2==1) p=p->next; while(p! =NULL) { x=pop(s); if(x==p->data) p=p->next; elsereturn0; } return1; } //求单链表长度.h intlength(linklist*head) {linklist*p=head->next; intn=0; while(p! =NULL){n++;p=p->next;} returnn; } //输出单链表.h voidprintlink(linklist*head) {linklist*p=head->next; while(p! =NULL) {cout< p=p->next; } cout< } //顺序栈出栈.h datatypepop(stack*s) { datatypetemp; s->top--; temp=s->elements[s->top+1]; returntemp; } //顺序栈入栈.h voidpush(stack*s,datatypee) { s->top++; s->elements[s->top]=e; } //置栈空.h voidsetnull(stack*&s) { s=newstack; s->top=-1; } 截图见下方实验结果。 3、实验结果 四、个人思路 队列是一个先进先出的线性表,入队时,先判断队列是否已满,如果不满将元素插入到队尾,然后判断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 #include #include"数组的结构类型定义.h" #include"找马鞍点.h" usingnamespacestd; voidmain() { array*pa=newarray; inti,j; for(i=0;i for(j=0;j cin>>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] p->min[i]=p->A[i][j]; } for(j=0;j { p->max[j]=p->A[0][j]; for(i=1;i if(p->A[i][j]>p->max[j]) p->max[j]=p->A[i][j]; } for(i=0;i for(j=0;j if(p->min[i]==p->max[j]) { printf("矩阵中存在马鞍点: \n"); printf("行号: %d,列号: %d,数值: %d\n",i+1,j+1,p->A[i][j]); have=1; } if(! have) printf("矩阵中没有马鞍点! \n"); } 三、实验结果 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 #include #include #include"二叉链表的结构类型定义.h" #include"二叉树的建立.h" #include"二叉树的输出.h" #include"交换左右子树.h" voidmain() { bitree*pb;//指针 pb=creattree();//创建一棵树,pb指向这棵树的根节点 preorder(pb);//打印这棵树 cout< swap(pb);//交换这棵树的所有子树 preorder(pb);//打印这颗新树 cout< } //二叉链表的结构类型定义.h constintmaxsize=1024; typedefchardatatype; typedefstructnode { datatypedata; structnode*lchild,*rchild; }bitree; //二叉树的建立.h bitree*creattree() { charch; bitree*Q[maxsize]; intfront,rear; bitree*root,*s; root=NULL; front=1;rear=0; while((ch=getchar())! ='#') { s=NULL; if(ch! ='@') { s=newbitree; s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 上机 实验 报告