数据结构上机实验讲解.docx
- 文档编号:15685664
- 上传时间:2023-07-06
- 格式:DOCX
- 页数:11
- 大小:134.57KB
数据结构上机实验讲解.docx
《数据结构上机实验讲解.docx》由会员分享,可在线阅读,更多相关《数据结构上机实验讲解.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构上机实验讲解
数据结构上机实验
姓名:
学号:
院系:
指导教师:
数据结构上机实验报告
实验一线性表
一、实验目的
1、熟悉线性表的顺序和链式存储结构
2、掌握线性表的基本运算
3、能够利用线性表的基本运算完成线性表应用的运算
二、实验内容
1、设有一个线性表E={e1,e2,…,en-1,en},设计一个算法,将线性表逆置,即使元素排列次序颠倒过来,成为逆线性表E’={en,en-1,…,e2,e1},要求逆线性表占用原线性表空间,并且用顺序表和单链表两种方法表示,分别用两个程序来完成。
2、已知由不具有头结点的单链表表示的线性表中,含有三类字符的数据元素(字母、数字和其他字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含有同一类的字符,且利用原表中的结点空间,头结点可另辟空间。
三、代码
1、
(1)顺序表逆置
voidinvert(sequenlist*L)
{
intiLen=L->last-1;
datatypestr;
for(inti=0;i { str=L->data[i]; L->data[i]=L->data[iLen-i]; L->data[iLen-i]=str; } } (2)单链表逆置 voidinvert(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; } head->next->next=NULL; head->next=q; } 2、 voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist*l,*p; l=head->next; charstr; while(l) { p=l; str=p->data; l=l->next; if((str>='a'&&str<='z')||(str>='A'&&str<='Z')) { insert(letter,p); } elseif(str>='0'&&str<='9') { insert(digit,p); } else{ insert(other,p); } } } 四、运行结果 1、 (1) (2) 2、 实验二栈和队列 一、实验目的 1、熟悉栈和队列的顺序和链式存储结构 2、掌握栈和队列的基本运算 3、能够利用栈和队列的基本运算完成栈和队列应用的运算 二、实验内容 1、设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。 (提示: 将单链表中的一半字符先依次进栈,然后依次出栈与单链表中的另一半字符进行比较。 )(文件夹: 习题3) 2、假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。 编写实现该循环队列的入队和出队操作的算法。 提示: 队空的条件: sq->quelen==0;队满的条件: sq->quelen==m。 (文件夹: 习题4) 三、代码 1.intsymmetry(linklist*head,stack*s) { linklist*r=head; intiLen=length(r); inti=0; while(i++ { r=r->next; push(s,r->data); } charstr; while(i++ { r=r->next; str=pop(s); if(str! =r->data) return0; } return1; } 2. //入队 voidenqueue(qu*sq,datatypex) { if(sq->quelen<=m) { sq->quelen++; sq->rear=(sq->rear+1)%m; sq->sequ[sq->rear]=x; cout<<"入队成功! \n"; } else { cout<<"队列已满,请先进行出队操作\n"; } } //出队 int*dequeue(qu*sq) { if(sq->quelen<=0) { cout<<"队列为空,请先进行入队操作\n"; returnNULL; } else { //sq->rear=(sq->rear-1+m)%m; sq->quelen--; cout<<"出队成功! \n"; return&sq->sequ[(sq->rear-sq->quelen+m)%m]; } } 三、运行结果 1. 2. 实验三数组 一、实验目的 1.熟悉数组的结构 2.掌握矩阵的压缩存储 3.能够对数组和矩阵的压缩存储进行运算 二、实验内容 1.若在矩阵Am×n中存在一个元素A[i-1[j-1],其满足A[i-1[j-1]是第i行元素中最小值,且又是第j列元素中最大值,则称此元素为该矩阵的一个马鞍点。 用二维数组存储矩阵Am×n,设计算法求出矩阵中所有马鞍点。 (文件夹: 习题5) 2.A和B是两个n×n阶的对称矩阵,输入时,以行为主序输入对称矩阵的下三角元素,存入一维数组,编写一个算法计算对称矩阵A和B的乘积。 (文件夹: 对称矩阵相乘) 三、代码 1、//找马鞍点.h voidminmax(array*pa) { inti,j,t,num=0; for(i=0;i for(j=0;j { cout< if(j==n-1) cout< } for(i=0;i for(j=0;j { t=0; while(pa->A[i][j]<=pa->A[i][t]&&t { t++; } if(t==n) { t=0; while(pa->A[i][j]>=pa->A[t][j]&&t { t++; } if(t==m) { cout< num++; } } } cout< } 2、//对称矩阵相乘.h voidmult(array*pa) { for(inti=0;i for(intj=0;j { for(intt=0,num=0,num1=0,num2=0;t { if(i>=t) num1=pa->A[(1+i)*i/2+t]; else num1=pa->A[(1+t)*t/2+i]; if(j>=t) num2=pa->B[(1+j)*j/2+t]; else num2=pa->B[(1+t)*t/2+j]; num+=num1*num2; } pa->C[i][j]=num; } } 四、运行结果 1、 2、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 上机 实验 讲解