数据结构上机实验

1、数据结构上机实验报告数据结构上机实验姓名：学号：院系： 指导教师：数据结构上机实验报告实验一 线性表一、 实验目的1、 熟悉线性表的顺序和链式存储结构2、 掌握线性表的基本运算3、 能够利用线性表的基本运算完成线性表应用的运算二、实验内容1、 设有一个线性表E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E= en , en-1 , , e2 , e1 ，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。2、 已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），

2、试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。三、代码1、（1）顺序表逆置void invert(sequenlist*L)int iLen=L-last-1;datatype str;for (int i=0;idatai;L-datai=L-dataiLen-i;L-dataiLen-i=str;（2）单链表逆置void invert(linklist*head)linklist *p,*q,*l;q=head-next;p=q-next;while (p!=NULL)l=p-next;p-next=q;q=p;p=l;h

3、ead-next-next=NULL;head-next=q;2、void resolve(linklist *head,linklist *letter,linklist *digit,linklist *other)linklist *l,*p;l=head-next;char str;while (l)p=l;str=p-data;l=l-next;if (str=a&str=A&str=0&strquelen=0；队满的条件：sq-quelen=m。（文件夹：习题4）三、代码1. int symmetry(linklist *head,stack *s)linklist *r=head

4、;int iLen=length(r);int i=0;while(i+next;push(s,r-data);char str;while(i+next;str=pop(s);if(str!=r-data)return 0;return 1;2./入队 void enqueue(qu *sq,datatype x) if(sq-quelenquelen+;sq-rear=(sq-rear+1)%m;sq-sequsq-rear=x;cout入队成功!n;elsecoutquelen=0)coutrear=(sq-rear-1+m)%m;sq-quelen-;coutsequ(sq-rear-

5、sq-quelen+m)%m;三、 运行结果1.2.实验三 数组一、实验目的1 熟悉数组的结构2 掌握矩阵的压缩存储3 能够对数组和矩阵的压缩存储进行运算二、实验内容1. 若在矩阵Amn中存在一个元素Ai-1j-1，其满足Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。（文件夹：习题5）2. A和B是两个nn阶的对称矩阵，输入时，以行为主序输入对称矩阵的下三角元素，存入一维数组，编写一个算法计算对称矩阵A和B的乘积。（文件夹：对称矩阵相乘）三、代码1、/找马鞍点.hvoid minmax(a

6、rray*pa)int i,j,t,num=0;for (i=0;im;i+)for (j=0;jn;j+)coutAij ;if (j=n-1)coutendl;for (i=0;im;i+)for (j=0;jAijAit&tAij=pa-Atj&tm)t+;if(t=m)coutAij ;num+;coutendl总共有num个马鞍点endl;2、/对称矩阵相乘.hvoid mult(array *pa)for (int i=0;in;i+)for (int j=0;jn;j+)for (int t=0,num=0,num1=0,num2=0;t=t)num1=pa-A(1+i)*i/2+t;elsenum1=pa-A(1+t)*t/2