数据结构上机实验报告

数据结构上机实验报告数据结构上机实验报告学院：电子工程学院专业：信息对抗技术姓名：学号：教师：饶 鲜日期：目 录实验一线性表........................................................................................................-4-一、实验目的.............................................................................................-4-二、实验代码.............................................................................................-4-三、实验结果...........................................................................................-19-四、个人思路...........................................................................................-20-实验二栈和队列..................................................................................................-21-一、实验目的...........................................................................................-21-二、实验代码...........................................................................................-21-三、实验结果...........................................................................................-34-四、个人思路...........................................................................................-35-实验三数组..........................................................................................................-36-一、实验目的...........................................................................................-36-二、实验代码...........................................................................................-36-三、实验结果...........................................................................................-40-四、个人思路...........................................................................................-40-实验四树..............................................................................................................-41-一、实验目的...........................................................................................-41--2-二、实验代码...........................................................................................-41-三、实验结果...........................................................................................-57-四、个人思路...........................................................................................-57--3-实验一 线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验代码1．设有一个线性表E={e1,e2,⋯,en-1,en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={en,en-1,⋯,e2,e1}，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：习题1）代码：单链表代码：单链表逆置主文件.cpp#include<iostream.h>#include<stdio.h>-4-#include" 单链表结构类型定义.h"#include" 建立单链表.h"#include" 输出单链表.h"#include" 单链表逆置.h"voidmain(){linklist*head;creat(head);print(head);invert(head);// 调用单链表逆置的函数print(head);}单链表结构类型定义.htypedefchardatatype;typedefstructnode{-5-datatypedata;structnode*next;}linklist;建立单链表.hvoidcreat(linklist*&head)采用尾插法建立具有结点的单链表{charch;linklist*s,*r;head=newlinklist;r=head;while((ch=getchar())!='*'){s=newlinklist;s->data=ch;r->next=s;-6-r=s;}r->next=NULL;}输出单链表.hvoidprint(linklist*head){linklist*p=head->next;while(p!=NULL){cout<<p->data<<"";p=p->next;}cout<<endl;}-7-单链表逆置.hvoidinvert(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;}单链表结果截图见下方实验结果。-8-顺序表代码：顺序表逆置主文件.cpp#include<iostream.h>#include<stdio.h>#include" 顺序表结构类型定义.h"#include" 建立顺序表.h"#include" 输出顺序表.h"#include" 顺序表逆置.h"voidmain(){sequenlist*L;creat(L);print(L);invert(L);// 调用顺序表逆值的函数print(L);}-9-顺序表的结构类型定义.htypedefchardatatype;constintmaxsize=1024;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;建立顺序表.hvoidcreat(sequenlist*&L){L=newsequenlist;L->last=0;charch;while((ch=getchar())!='*'){-10-L->data[L->last]=ch;L->last++;}}输出顺序表.hvoidprint(sequenlist*L){for(inti=0;i<L->last;i++)cout<<L->data[i]<<"";cout<<endl;}顺序表逆置.hvoidinvert(sequenlist*L){charmid;inti,j;-11-i=0;j=L->last-1;while(i<j){mid=L->data[i];L->data[i]=L->data[j];L->data[j]=mid;i++;j--;}}顺序表实验截图见下方实验结果。2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：习题2）-12-代码：分解单链表主程序文件.cpp#include<iostream.h>#include<stdio.h>#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;-13-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;-14-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;}-15-voidprint1(linklist*head)输出单链表{linklist*p=head->next;while(p!=NULL){cout<<p->data;p=p->next;}cout<<endl;}voidprint2(linklist*head)输出循环链表{linklist*p=head->next;while(p!=head){cout<<p->data;p=p->next;-16-}cout<<endl;}在循环链表中插入.hvoidinsert(linklist*h,linklist*p){linklist*q=h;while(q->next!=h)q=q->next;q->next=p;p->next=h;}分解单链表.hvoid resolve(linklist* head,linklist*letter,linklist*digit,linklist*other){linklist*p=head->next,*t;-17-head->next=NULL;while(p!=NULL){t=p;p=p->next;if(t->data>='0'&&t->data<='9')insert(digit,t);else if ((t->data >='a' &&t->data <='z')||(t->data >='A' && t->data<='Z'))insert(letter,t);elseinsert(other,t);}return;}截图见下方实验结果。-18-三、实验结果-19-四、个人思路顺序表做逆置操作时将对应的首尾元素位置交换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容交换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end指针的节点，并将end指针赋值为s指针，就完成了单链表的逆置，可以看出单链表和顺序表都可以完成线性表的逆置。-20-分解单链表的实现思路是首先新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到对应的循环链表中，从而实现分解单链表的功能。实验二 栈和队列一、实验目的1．熟悉栈和队列的顺序和链式存储结构2．掌握栈和队列的基本运算3．能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验代码1．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件： sq->quelen==0；队满的条-21-件：sq->quelen==m。（文件夹：习题 3）循环队列入队出队的主程序文件.cpp#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include" 循环队列的结构类型定义 .h"#include" 置空队.h"#include" 入队.h"#include" 出队.h"voidmain(){qu*sq;datatypex,*p;intkey;sq=newqu;setnull(sq);do{cout<<"1.EnterQueue 2.DeleteQueue-22--1.Quit:";cin>>key;switch(key){case1:cout<<"EntertheData:";cin>>x;enqueue(sq,x);break;case2:p=dequeue(sq);if(p!=NULL)cout<<*p<<endl;break;case-1:exit(0);}}while(1);}出队.hdatatype*dequeue(qu*sq)-23-{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);}-24-}入队.hvoidenqueue(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";}}循环队列的结构类型定义.hconstintm=5;-25-typedefintdatatype;typedefstruct{datatypesequ[m];intrear,quelen;}qu;置空队.hvoidsetnull(qu*sq){sq->rear=m-1;sq->quelen=0;}实验截图见下方实验结果。设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：习题4）-26-判字符串中心对称的主程序文件.cpp#include<iostream.h>#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);-27-printlink(head);setnull(s);if(symmetry(head,s)) cout<<" 字 符串\""<<str<<"\" 中心对称\n";elsecout<<"字符串\""<<str<<"\"不是中心对称\n";}定义单链表结构类型.htypedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;定义顺序栈结构类型constintmaxsize=40;typedefstruct-28-{datatypeelements[maxsize];inttop;}stack;建立具有头结点的单链表.hvoidcreat(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++;-29-}r->next=NULL;}判断字符是否中心对称.hintsymmetry(linklist*head,stack*s){intn=length(head)/2;linklist*p=head->next;datatypex;for(inti=0;i<n;i++){push(s,p->data);p=p->next;}if(length(head)%2==1)p=p->next;-30-while(p!=NULL){x=pop(s);if(x==p->data)p=p->next;elsereturn0;}return1;}求单链表长度.hintlength(linklist*head){linklist*p=head->next;intn=0;while(p!=NULL){n++;p=p->next;}returnn;-31-}输出单链表.hvoidprintlink(linklist*head){linklist*p=head->next;while(p!=NULL){cout<<p->data;p=p->next;}cout<<endl;}顺序栈出栈.hdatatypepop(stack*s){datatypetemp;s->top--;-32-temp=s->elements[s->top+1];returntemp;}顺序栈入栈.hvoidpush(stack*s,datatypee){s->top++;s->elements[s->top]=e;}置栈空.hvoidsetnull(stack*&s){s=newstack;s->top=-1;}-33-截图见下方实验结果。三、实验结果-34-四、个人思路队列是一个先进先出的线性表，入队时，先判断队列是否已满，如果不满将元素插入到队尾，然后判断rear是否指向sequ[m]，如果是，指向队尾指针rear+1，否者rear=sequ[0]，队列内元素个数quelen+1。出队时头指针front后移一位，如果front=sequ[m]，front指向-35-Am×nsequ[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列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵 ，设-36-计算法求出矩阵中所有马鞍点。（文件夹：习题5）找马鞍点的主程序文件.cpp#include<iostream>#include"数组的结构类型定义.h"#include"找马鞍点.h"usingnamespacestd;voidmain(){array*pa=newarray;inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)cin>>pa->A[i][j];minmax(pa);getchar();-37-}数组的结构类型定义.hconstintm=3;constintn=3;typedefstruct{intA[m][n];intmax[m],min[n];}array;找马鞍点.hvoidminmax(array*p){inti,j,have=0;for(i=0;i<m;i++){p->min[i]=p->A[0][i];-38-for(j=1;j<n;j++)if(p->A[i][j]<p->min[i])p->min[i]=p->A[i][j];}for(j=0;j<n;j++){p->max[j]=p->A[0][j];for(i=1;i<m;i++)if(p->A[i][j]>p->max[j])p->max[j]=p->A[i][j];}for(i=0;i<m;i++)for(j=0;j<n;j++)if(p->min[i]==p->max[j]){printf(" 矩阵中存在马鞍点:\n");printf(" 行号:%d,列号:%d,数-39-值:%d\n",i+1,j+1,p->A[i][j]);have=1;}if(!have)printf(" 矩阵中没有马鞍点！\n");}三、实验结果四、个人思路若称元素为该矩阵的一个马鞍点，即说明该元素是第i行元素中最小值，且又是第j列元素中最大值。用两个循环遍历所有元素，第一个循环遍历行，第二个循环遍历列，将A[i-1][j-1]与对应行和列的每一个元素比较， 如果第i行的某元素比A[i-1][j-1] 小或第j列的某元素比-40-A[i-1][j-1]大则跳出内层循环，实现寻找马鞍点的要求。实验四 树一、实验目的1．熟悉二叉树的链式存储结构2．掌握二叉树的建立、深度优先递归遍历等算法3．能够利用遍历算法实现一些应用二、实验代码1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：习题6）交换左右子树的主程序文件.cpp#include<iostream.h>#include<stdio.h>-41-#include"二叉链表的结构类型定义 .h"#include"二叉树的建立.h"#include"二叉树的输出.h"#include"交换左右子树.h"voidmain(){bitree*pb;// 指针pb=creattree();// 创建一棵树,pb 指向这棵树的根节点preorder(pb);// 打印这棵树cout<<endl;swap(pb);//交换这棵树的所有子树preorder(pb);//打印这颗新树cout<<endl;}二叉链表的结构类型定义.h-42-constintmaxsize=1024;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;二叉树的建立.hbitree*creattree(){charch;bitree*Q[maxsize];intfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;-43-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(s&&Q[front])-44-if(rear%2==0)Q[front]->lchild=s;elseQ[front]->rchild=s;if(rear%2==1)front++;}}returnroot;}二叉树的输出.hvoidpreorder(bitree*p){if(p!=NULL){cout<<p->data;if(p->lchild!=NULL||p->rchild!=NULL){-45-cout<<"(";preorder(p->lchild);if(p->rchild!=NULL)cout<<",";preorder(p->rchild);cout<<")";}}}交换左右子树.hvoidswap(bitree*pb){bitree*t;if(pb!=NULL){t=pb->lchild;pb->lchild=pb->rchild;pb->rchild=t;-46-swap(pb->lchild);swap(pb->rchild);}}实验运行结果截图见下方实验结果。2．采用二叉链表结构存储一棵二叉树，编写一个算法删除该二叉树中数据值为x的结点及其子树，并且输出被删除的子树。（文件夹：习题7）删除二叉树结点的主程序文件.cpp#include<iostream.h>#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include" 二叉链表的结构类型定义 .h"#include" 二叉树的建立.h"-47-#include" 二叉树的输出.h"//#include" 删除结点和子树.h"voidmain(){bitree*root;// 创建指针datatypex;// 定义变量xCreateBiTree(root);//创建一颗二叉树，使指针root指向这颗二叉树的根节点preorder(root);// 打印这颗二叉树PrintBiTree(root,2);cout<<endl;cin>>x;// 输入一个字符存储到变量 x中root=delsubtree(root,x);// 从指针root 所指向的根节点开始在这颗二叉树的所有节点中寻找节点内容与变量x内容相同的节点,若没找到则不改变这颗树若找到这样的节点，那么删除一颗以找到节点为根节点的子树-48-preorder(root);// 打印变化之后的二叉树cout<<endl;}二叉链表的结构类型定义.hconstintmaxsize=1024;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;二叉树的建立.hbitree*creattree(){datatypech;-49-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;-50-if(rear==1)root=s;else{if(s&&Q[front])if(rear%2==0)Q[front]->lchild=s;elseQ[front]->rchild=s;if(rear%2==1)front++;}}returnroot;}intCreateBiTree(bitree*&T){charch;scanf("%c",&ch);if(ch=='')T=NULL;else { if(!(T=(bitree*)malloc(sizeof(bitree))))-51-exit(0);T->data=ch;CreateBiTree(T