数据结构上机实验报告.doc

《数据结构上机实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构上机实验报告.doc（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、!-数据结构上机实验报告 学 院：电子工程学院 专 业：信息对抗技术 姓 名： 学 号： 教 师：饶 鲜 日 期：目 录实验一 线性表- 2 -一、实验目的- 2 -二、实验代码- 2 -三、实验结果- 8 -四、个人思路- 9 -实验二 栈和队列- 9 -一、实验目的- 9 -二、实验代码- 10 -三、实验结果- 15 -四、个人思路- 16 -实验三 数组- 16 -一、实验目的- 16 -二、实验代码- 16 -三、实验结果- 18 -四、个人思路- 18 -实验四 树- 18 -一、实验目的- 18 -二、实验代码- 19 -三、实验结果- 24 -四、个人思路- 25 -!-实验一

2、 线性表一、实验目的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#inc

3、lude单链表逆置.hvoid main()linklist*head;creat(head);print(head);invert(head);/调用单链表逆置的函数print(head);/单链表结构类型定义.htypedef char datatype;typedef struct nodedatatype data;struct node *next;linklist;/建立单链表.hvoid creat(linklist*&head)/采用尾插法建立具有结点的单链表char ch;linklist *s,*r;head=new linklist;r=head;while(ch=get

4、char()!=*)s=new linklist;s-data=ch;r-next=s;r=s;r-next=NULL;/输出单链表.hvoid print(linklist *head)linklist*p=head-next;while(p!=NULL)coutdatanext;coutnext; 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顺

5、序表结构类型定义.h#include建立顺序表.h#include输出顺序表.h#include顺序表逆置.hvoid main()sequenlist*L;creat(L);print(L);invert(L);/调用顺序表逆值的函数print(L);/顺序表的结构类型定义.htypedef char datatype;const int maxsize=1024;typedef struct datatype datamaxsize; int last;sequenlist;/建立顺序表.hvoid creat(sequenlist*&L)L=new sequenlist;L-last=0

6、;char ch;while(ch=getchar()!=*)L-dataL-last=ch;L-last+;/输出顺序表.hvoid print(sequenlist*L)for(int i=0;ilast;i+)coutdatai ;coutlast-1; while(idatai; L-datai=L-dataj; L-dataj=mid; i+;j-; 顺序表实验截图见下方实验结果。2 已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间

7、。（文件夹：习题2）代码：/分解单链表主程序文件.cpp#include#include#include单链表结构类型定义.h#include建立单链表.h#include输出单链表.h#include输出循环链表.h#include在循环链表中插入.h#include分解单链表.hvoid main() linklist *head,*letter,*digit,*other; creat(head); print1(head); letter=new linklist; letter-next=letter; digit=new linklist; digit-next=digit; ot

8、her=new linklist; other-next=other; resolve(head,letter,digit,other);/调用分解单链表的函数 print2(letter); print2(digit); print2(other);/单链表结构类型定义typedef char datatype;typedef struct node datatype data; struct node *next;linklist;void creat(linklist*&head)/建立单链表 datatype x; linklist *s,*r; head=new linklist;

9、r=head; cinx; while(x!=$) s=new linklist; s-data=x; r-next=s; r=s; cinx; r-next=NULL;void print1(linklist*head)/输出单链表 linklist *p=head-next; while(p!=NULL) coutdata; p=p-next; coutnext; while(p!=head) coutdata; p=p-next; coutnext!=h) q=q-next; q-next=p; p-next=h;/分解单链表.hvoid resolve(linklist* head,l

10、inklist* 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 data =a & t-data data =A & t-data quelen=0；队满的条件：sq-quelen=m。（文件夹：习题3）/循环队列入队出队的主程序文件.cpp#include#include#include#include循环队列的结构类型定义.h#include置空队.h#include

11、入队.h#include出队.hvoid main() qu *sq;datatype x, *p;int key;sq=new qu;setnull(sq);do coutkey;switch(key) case 1: coutx;enqueue(sq,x);break;case 2: p=dequeue(sq);if(p!=NULL) cout*pquelen=0) printf(队列为空，请先进行入队操作n);return 0; else temp=(datatype*)malloc(sizeof(datatype); sq-quelen-; *temp=sq-sequ(sq-rear-

12、sq-quelen+m)%m; coutquelen=m) printf(队列已满，请先进行出队操作n); else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x; coutrear=m-1;sq-quelen=0;实验截图见下方实验结果。2. 设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：习题4）/判字符串中心对称的主程序文件.cpp#include#include单链表顺序栈结

13、构类型定义.h#include置栈空.h#include求单链表长度.h#include输出单链表.h#include建立单链表.h#include顺序栈入栈.h#include顺序栈出栈.h#include判字符串是否中心对称.h void main()linklist *head;stack *s;datatypestr80;cinstr;creat(head,str);printlink(head);setnull(s);if(symmetry(head,s) cout字符串str中心对称n;else cout字符串strdata=*p;r-next=s; r=s;p+; r-next=

14、NULL;/判断字符是否中心对称.hint symmetry(linklist*head,stack*s) int n=length(head)/2; linklist*p=head-next; datatype x; for(inti=0;idata); p=p-next; if(length(head)%2=1) p=p-next; while(p!=NULL) x=pop(s); if(x=p-data) p=p-next; else return 0; return 1; /求单链表长度.hint length(linklist*head) linklist *p=head-next;

15、int n=0;while(p!=NULL) n+; p=p-next; return n;/输出单链表.hvoidprintlink(linklist*head) linklist *p=head-next;while(p!=NULL) coutdata; p=p-next; couttop-;temp=s-elementss-top+1;return temp;/顺序栈入栈.hvoid push(stack*s,datatype e)s-top+;s-elementss-top=e;/置栈空.hvoidsetnull(stack *&s)s=new stack;s-top=-1;截图见下方

16、实验结果。3、 实验结果四、个人思路队列是一个先进先出的线性表，入队时，先判断队列是否已满，如果不满将元素插入到队尾，然后判断rear是否指向sequm，如果是，指向队尾指针rear+1，否者rear=sequ0，队列内元素个数quelen+1。出队时头指针front后移一位，如果front=sequm，front指向sequ0，否则front+，quelen-1，从而实现入队与出队的操作。 要判断字符串是否中心对称，首先获取栈的长度N，将前N/2个元素（N为偶数）或前(N-1）/2个元素（N为奇数）顺序压入栈中，然后依次出栈（先进后出），与另一半元素依次对应比较，全为真则可判断字符串中心对称

17、。 实验三 数组一、实验目的1 熟悉数组的结构2 掌握矩阵的进行运算二、实验代码 若在矩阵Amn中存在一个元素Ai-1j-1，其满足Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。（文件夹：习题5）/找马鞍点的主程序文件.cpp#include#include数组的结构类型定义.h#include找马鞍点.husing namespace std;void main()array*pa=new array; int i, j; for (i=0;im;i+) for (j=0;jpa-Aij

18、; minmax(pa);getchar();/数组的结构类型定义.hconstint m=3;constint n=3;typedefstructint Amn;int maxm,minn;array;/找马鞍点.hvoidminmax(array*p) inti,j,have=0; for(i=0;imini=p-A0i; for(j=1;jAijmini)p-mini=p-Aij; for (j=0;jmaxj=p-A0j; for(i=1;iAijp-maxj) p-maxj=p-Aij; for(i=0;im;i+)for(j=0;jmini=p-maxj) printf(矩阵中存在

19、马鞍点:n);printf(行号:%d,列号:%d,数值:%dn,i+1,j+1,p-Aij); have=1; if(!have) printf(矩阵中没有马鞍点！n); 三、实验结果4、 个人思路 若称元素为该矩阵的一个马鞍点，即说明该元素是第i行元素中最小值，且又是第j列元素中最大值。用两个循环遍历所有元素，第一个循环遍历行，第二个循环遍历列，将Ai-1j-1与对应行和列的每一个元素比较，如果第i行的某元素比Ai-1j-1小或第j列的某元素比Ai-1j-1大则跳出内层循环，实现寻找马鞍点的要求。实验四 树一、实验目的1 熟悉二叉树的链式存储结构2 掌握二叉树的建立、深度优先递归遍历等算法

20、3 能够利用遍历算法实现一些应用二、实验代码1 已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：习题6）/交换左右子树的主程序文件.cpp#include#include#include二叉链表的结构类型定义.h#include二叉树的建立.h#include二叉树的输出.h#include交换左右子树.hvoid main()bitree * pb;/指针pb=creattree();/创建一棵树,pb指向这棵树的根节点preorder(pb);/打印这棵树coutendl;swap(pb);/交换这棵树

21、的所有子树preorder(pb);/打印这颗新树coutdata=ch;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;/二叉树的输出.hvoid preorder(bitree*p)if(p!=NULL)coutdata;if(p-lchild!=NULL|p-rchild!=NULL)coutlchild);if(p-rchild

22、!=NULL)coutrchild);coutlchild;pb-lchild=pb-rchild;pb-rchild=t;swap(pb-lchild);swap(pb-rchild); 实验运行结果截图见下方实验结果。2 采用二叉链表结构存储一棵二叉树，编写一个算法删除该二叉树中数据值为x的结点及其子树，并且输出被删除的子树。（文件夹：习题7）/删除二叉树结点的主程序文件.cpp#include#include#include#include#include二叉链表的结构类型定义.h#include二叉树的建立.h#include二叉树的输出.h/#include删除结点和子树.hvoid

23、 main()bitree * root;/创建指针datatype x;/定义变量xCreateBiTree(root);/创建一颗二叉树，使指针root指向这颗二叉树的根节点preorder(root);/打印这颗二叉树 PrintBiTree(root,2);coutx;/输入一个字符存储到变量x中root=delsubtree(root,x);/从指针root所指向的根节点开始在这颗二叉树的所有节点中/寻找节点内容与变量x内容相同的节点,若没找到则不改变这颗树/若找到这样的节点，那么删除一颗以找到节点为根节点的子树preorder(root);/打印变化之后的二叉树coutdata=c

24、h;s-lchild=NULL;s-rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&Qfront)if(rear%2=0)Qfront-lchild=s;else Qfront-rchild=s;if(rear%2=1)front+;return root;intCreateBiTree(bitree *&T) charch;scanf(%c,&ch);if (ch= ) T=NULL;else if (!(T=(bitree*)malloc(sizeof(bitree) exit(0); T-data = ch;CreateBiTree

25、(T-lchild);CreateBiTree(T-rchild);return 1;/二叉树的输出.hvoid preorder(bitree*p)if(p!=NULL)coutdata;if(p-lchild!=NULL|p-rchild!=NULL)coutlchild);if(p-rchild!=NULL)coutrchild);coutrchild,n+1);for (i=1;idata);PrintBiTree(T-lchild,n+1);/删除节点及其子树.hbitree*delsubtree(bitree*T,datatype x)if (T!=NULL)/如果根节点不为空 i

26、f (T-data=x) /如果根节点为要删除的节点 delete T-lchild;/删除左孩子节点 T-lchild=NULL;/左指针指向NULL delete T-rchild;/删除右孩子节点 T-rchild=NULL;/右指针指向NULL delete T;/删除节点T else if (T-lchild!=NULL&T-lchild-data=x) /如果左孩子为要删除的节点 delete T-lchild-lchild;/先删除左孩子的左孩子 delete T-lchild-rchild;/再删除左孩子的右孩子 delete T-lchild;/最后删除左孩子 T-lchil

27、d=NULL;/左指针为空 else if (T-rchild!=NULL&T-rchild-data=x) /如果右孩子为要删除的节点 delete T-rchild-lchild;/先删除右孩子的左孩子 delete T-rchild-rchild;/再删除右孩子的右孩子 delete T-rchild;/最后删除右孩子 T-rchild=NULL;/右指针为空 else if(T-lchild!=NULL) /如果左孩子不为空delsubtree(T-lchild,x);/删除左孩子结点 if(T-rchild!=NULL) /如果右孩子不为空delsubtree(T-rchild,x);/删除右孩子节点 return T;实验运行结果截图见下方实验结果。3、 实验结果四、个人思路交换左右子树的思路是构建一个临时的存储空间t，将左子树存入该空间，再将右子树替换掉左子树，最后从该空间取出左子树替换右子树，则完成了左右子树的交换。删除节点及子树的思路是先查找到要删除的结点然后再删除，首先判断是否是空树，是则直接结束，非空则先查找左子树，再查找右子树，然后将查找到的子树存入临时存储空间T，最后输出T的内容，即是被要求删除的子树。