数据结构上机实验

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

2、只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。三、代码1、( 1)顺序表逆置void in vert(seque nlist*L)int iLe n=L-last-1;datatype str;for (int i=0;idatai;L-datai=L-dataiLe n-i;L-dataiLe n-i=str;(2)单链表逆置void in vert(l in klist*head)lin klist *p,*q,*l;q=head-n ext;p=q _n ext;while (p!=NULL)l=p-n ext;p_n ext=q;q=p;p=l；head-n ext-n

3、 ext=NULL;head-n ext=q;2、void resolve(li nklist *head,li nklist *letter,li nklist *digit,li nklist *other)lin klist *l,*p;l=head-n ext;char str;while (l)p=l;str=p-data;l=l-n ext;if (str=a&str=A&str=0&stre5ktop|ffi2Debugsjj9exeestdtdy,.:J/#$& estdtdv，- , ； * kistdtdy=J /4tPress any key to cont inue实验

4、二栈和队列实验目的1、熟悉栈和队列的顺序和链式存储结构2、掌握栈和队列的基本运算3、能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验内容1、设单链表中存放有 n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：习题3）2、 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq-quelen=0 ;队满的条件：sq-que

5、len=m 。（文件夹：习题 4）三、代码1. int symmetry in klist *head,stack *s) lin klist *r=head;int iLe n=len gth(r);int i=0;while(i+n ext;push(s,r-data);char str;while(i+n ext;str=pop(s);if(str!=r-data)return 0;return 1;2./入队void enq ueue(qu *sq,datatype x)if(sq-quele nquele n+;sq-rear=(sq-rear+1)%m;sq_sequsq_rear

6、=x;cout入队成功!n;elsen;coutquele n=0)coutrear=(sq-rear-1+m)%m;sq-quele n_;coutsequ(sq-rear-sq-quele n+m)%m;三、运行结果1. C:Usersnj lDeskto 卩、习5Debu g3 .exehyttylihyttyh字符串-hytt州冲心对称 Press any 2* to continueJ： 12,烂 II 卩 I LJUS 區 LU JJ胡人匕 UU 9 %二JQfcdf sjfucdf ssiu字符串Mcds9vH不是中心对称 Press anyto cant in tie1.Ent

7、er Queue 2_Delete Queue Enter the Data：23入队成功号1.Enter Queue 2 - Delete Queue Enter the Dta：56入队成功号1.Enter Queue 2.Delets Queue岀队成功*231.Enter Queue 2.Delate Queue岀队成功！5&1.Enter Queue 2.Delete Queue-l.Quit：1 -l.Quit：1 -l.Qwit：2 -1.Quit:21.Quit:实验三数组、实验目的1 .熟悉数组的结构2. 掌握矩阵的压缩存储3. 能够对数组和矩阵的压缩存储进行运算、实验内容1

8、. 若在矩阵Amn中存在一个元素 Ai-1j-1，其满足Ai-1j-1是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amxn ,设计算法求出矩阵中所有马鞍点。（文件夹：习题 5）2. A和B是两个nn阶的对称矩阵，输入时，以行为主序输入对称矩阵的下三角元素，存入一维数组，编写一个算法计算对称矩阵A和B的乘积。（文件夹：对称矩阵相乘）三、代码1、/找马鞍点.hvoid min max(array*pa)int i,j,t ,num=0;for (i=0;im;i+)for (j=0;j n;j+)coutAij;if (j=n-1)coute

9、ndl;for (i=0;im;i+)for (j=0;jAijAit &tAij=pa-Atj&tm)t+；if(t=m)coutAij;nu m+;coutendl总共有num个马鞍点endl;2、对称矩阵相乘.hvoid mult(array *pa)for (i nt i=0;i n ;i+)for (int j=0;j n;j+)for (in t t=0,num=0,nu m1= 0,nu m2=0;t =t)num仁 pa-A(1+i)*i/2+t; elsenum仁 pa-A(1+t)*t/2+i; if (j=t)nu m2=pa-B(1+j)*j/2+t; elsenu m2=pa-B(1+t)*t/2+j;num+=nu ml* nu m2;pa-Cij=num;四、运行结果1、L J32 14