数据结构实验指导书.docx
- 文档编号:8873583
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:73
- 大小:202.26KB
数据结构实验指导书.docx
《数据结构实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构实验指导书.docx(73页珍藏版)》请在冰点文库上搜索。
数据结构实验指导书
数据结构
实验指导书
信息科学与技术学院
前言
数据结构是软件开发的基础。
数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全等专业的必修技术基础课程。
该课程是在学生学习高级语言程序设计课程基础上,使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计,学会常用数据分类和数据查找的技术,对所设计的算法会做定量或定性的分析比较,培养学生的算法设计与分析的能力。
通过该课程的学习,使学生学会分析数据对象特性,选择合适的数据结构、存贮结构及相应的基本处理算法;初步掌握算法的时间空间复杂度分析技巧。
既为学生学习后继课程打好基础,也为将来软件开发提供理论指导。
数据结构具有很强的实践性,只有通过编程上机实验,才能真正领会数据结构的真正内涵,并灵活运用数据结构的基本知识提高自己的软件开发能力。
本数据结构实验选择了具有一定难度的实验项目10个,涉及到线性表、栈、队列、字符串、数据、二叉树、图、数据查找、数据排序等全部教学内容。
学生不一定完成全部实验内容,根据课程的学分不同,可以选择不同数目的实验。
一般而言,《数据结根A》可以选择其中3个实验,《数据结根B》可以选择其中两个实验。
鼓励学生多做实验,如果学生所做实验数目超过规定数据,可以加分。
本实验是以标准C语言为背景,以微型计算机为主要机型,实验用编程语言采用TurboC2.0,BorlandC3.0等以上版本。
为了使学生不仅掌握数据结构的一般原理,而且掌握具有一定实用性的程序的一般结构,实验指导书中给出了程序的总体框架和部分源程序代码,以及程序运行控制和交互式操作的基本方式。
通过程序总体框架,让学生学会如何组织程序。
通过对程序要解决的问题按功能进行分解,使学生逐步适应和学会运用抽象思维方式和模块化程序设计技术编写有一定规模、具有一定实用性的程序的能力。
编写数据结构实验指导书是对软件类课程的一个尝试。
我们将通过学生在实验过程中的反馈意见不断完善。
实验一一元稀疏多项式的计算
一、实验目的
通过一元稀疏多项式的表示和计算,帮助学生熟练掌握线性表的基本操作,以及用线性链表表示线性表的存储结构和操作的实现。
二、实验内容
实现一元稀疏多项式的如下运算:
(1)两个一元稀疏多项式相加运算
(2)两个一元稀疏多项式相减运算
(3)两个一元稀疏多项式相乘运算
三、实验原理
1、一元多项式的逻辑表示
一元多项式pn(x)可表示成:
pn(x)=p0+p1x+p2x2+…+pnxn
n+1个系数可用线性表来表示:
p0,p1,p2,…,pn)
其中每一项的指数i隐含在其系数pi的序号中。
一个一元多项式,如果其系数不为0的项相对于其多项式的次数(最大指数)而言要少得多,则称该一元多项式为一元稀疏多项式。
对一元稀疏多项式,若采用顺序存储结构,需n+1个元素单元存放系数。
当n很大且为零的系数较多时,既浪费存储空间,又浪费运算时间。
如:
s(x)=1+3x10000+2x20000
采用顺序存储分配需20001个元素空间,但只有3个元素有意义。
若参与同数量级的加法运算,要运行2000次以上。
因此,对一元多项式采用链式存储结构是必然的选择。
上例的链表表示形式如图1-1所示。
p
2、一元稀疏多项式的链式存储表示
结点结构定义如下:
typedefstructItem{
doublecoef;
intexpn;
structItem*next;
}Item,*Polyn;
3、一元稀疏多项式运算原理
设有两个稀疏多项式A和B,其运算原理如下:
(1)两个多项式相加(C=A+B)的运算原则:
指数相同,系数相加,若不为0,则在结果多项式中构成一新项。
指数不同,则两项分别抄入结果多项式中。
(2)两个多项式相减(C=A-B)的运算原则:
指数相同,系数相减,若不为0,则构成一新项。
指数不同,对A多项式的项,直接抄入结果多项式中。
对B多项式的项,系数符号变换后,再将放入结果多项式中
(3)两个多项式相乘(C=A×B)的运算原则
用B多项式的每一项分别去乘A多项式的每一项,并将乘得得结果放入结果多项式中。
若结果多项式中有指数相同的项,则应把它们合并为一项。
四、实现
1、约定
(1)使用带头结点的链表表示一元稀疏多项式。
(2)用线性链表表示的一元稀疏多项式中,各结点按指数的升序排列。
(3)每个多项式都独立存在,即参与运算的两个多项式的数据不能因运算而受到破坏,加、减、乘运算的结果应相互不受影响。
因此,对于每种情况都必须单独建立一个链表进行表示。
(4)每一种重复性的操作都要进行确认,以免破坏原有操作的结果。
如需要输入A多项式,而A多项式已经存在,这时通过“确认”后再确定是否真正需要输入。
2、基本功能
(1)多项式的输入
(2)两个一元稀疏多项式相加运算:
P(x)+Q(x
(3)两个一元稀疏多项式相减运算:
P(x)-Q(x)
(4)两个一元稀疏多项式相乘运算:
P(x)×Q(x)
(5)多项式打印
3、辅助功能
(1)菜单选择:
将上述功能通过“菜单”形式罗列出来,通过菜单选择进行交互式控制程序运行。
(2)插入结点位置查找:
确定将一个新结点插入到多项式链表结构中的位置,以保证链表中结点按指数升序排列。
(3)交互选择:
当出现重复性操作时,提供交互式选择方式,以确定其重复操作是否进行。
(4)撤消多项式:
释放表示多项式链表中所有结点的存储空间。
(5)多项式项插入:
将表示多项式中一项的结点插入到链表中给定的位置。
(6)判多项式非空:
判断某个多项式是否存在。
(7)判断两个多项式的当前运算项的关系(指数大于,等于,小于)
4、程序结构
本程序可以由13个函数组成,其中主函数1个,基本功能函数5个,辅助功能函数7个。
函数间的调用关系图1-2所示。
5、程序函数
(1)主函数:
main
功能:
通过菜单选择控制对系统功能的操作
(2)菜单选择函数:
menu
函数格式:
intmenu(void)
函数功能:
构造功能菜单,并选择下一步要操作的功能。
函数参数:
无参数。
函数返回值:
1~11中的一个序号。
可供选择的功能如下:
1--createP(x)表示生成P多项式
2--createQ(x)表示生成Q多项式
3--p(x)+Q(x)表示两多项式相加
4--P(x)-Q(x)表示两多项式相减
5--p(x)*Q(x)表示两多项式相乘
6--printP(x)表示打印P多项式
7--printQ(x)表示打印Q多项式
8--printP(x)+Q(x)表示打印两多项式相加的结果
9--printP(x)-Q(x)表示打印两多项式相减的结果
10--printP(x)*Q(x)表示打印两多项式相乘的结果
11—Quit表示退出系统,结束程序的运行
在运行过程中,输入其中一个序号,即表示下一步执行后面的功能。
如输入3,表示执行P(x)+(x)额运算。
(3)输入多项式函数:
input
函数格式:
PolynInput(void)
函数参数:
无参数
函数功能:
输入多项式各项的系数和指数,生成一个多项式链表。
函数返回值:
指向一个多项式链表的头指针
(4)两多项式相加函数:
AddPolyn
函数格式PolynAddPolyn(Polynh1,Polynh2)
函数功能:
实现两个多项式h1和h2相加。
函数参数:
Polynh1—指向第一个多项式链表的头指针
Polynh2—指向第二个多项式链表的头指针
函数返回值:
指向相加后的结果链表的头指针
(5)两多项式相减函数:
SubtractPolyn
函数格式PolynSubtractPolyn(Polynh1,Polynh2)
函数功能:
实现两个多项式h1和h2相减。
函数参数:
Polynh1—指向第一个多项式链表的头指针
Polynh2—指向第二个多项式链表的头指针
函数返回值:
指向相减后的结果链表的头指针
(6)两多项式相乘函数:
MultPolyn
函数格式PolynMultPolyn(Polynh1,Polynh2)
函数功能:
实现两个多项式h1和h2相乘。
函数参数:
Polynh1—指向第一个多项式链表的头指针
Polynh2—指向第二个多项式链表的头指针
函数返回值:
指向相乘后的结果链表的头指针
(7)显示多项式函数:
Output
函数格式:
voidOutput(Polynh,char*title)
函数功能:
输出多项式的完整表示。
如:
P(x)=1.00+2.50x^3-3.5x^9
函数参数:
Polynh-要输出的多项式链表的头指针
char*title-字符串,提示要输出一个什么样的多项式,如“P(x)”。
函数返回值:
无返回值。
(8)判断选择函数:
Select
函数格式:
intSelect(char*str)
函数功能:
根据str提示的内容判断是执行指定的操作,还是不执行。
输入“Y”则表示执行,若输入“N”表示不执行。
如当P(x)多项式已经产生后,若再选择产生P(x),这是提示:
P(x)isnotEmpty,CreateP(x)again?
InputYorN:
若输入“Y”则表示重新产生多项式P(x),若输入“N”表示维持原多项式不变。
函数参数:
char*str-将要确定的内容。
函数返回值:
1-表示执行指定的操作
0-表示不执行指定的操作
(9)插入位置定位函数:
InsertLocate
函数格式:
intInsertLocate(Polynh,intexpn,Item**p)
函数功能:
确定新结点的插入位置。
其插入位置的确定是保证多项式链表按指数递增排列的关键。
函数参数:
Polynh-要查找的多项式链表的头指针
intexpn-新插入项的指数值。
Item**p-插入位置的前驱结点指针,由该函数的调用而被确定的内容。
新结点一定插入到该结点的后面。
函数返回值:
-1-若指数expn值在某两个结点之间,则返回-1,参数p带回的值为指数值小于expn的结点指针。
0-若指数expn值等于某结点的指数值,则返回0,参数p带回的值为指数值等于expn的结点指针。
1-若指数expn值大于最后一个结点的指数值,则返回1,参数p带回最后一个结点的指针
(10)结点插入函数:
insert
函数格式:
voidinsert(Item*pre,Item*p)
函数功能:
在指定结点pre后插入一个新结点p。
函数参数:
Item*pre-被插入结点的前驱结点
Item*p-要插入的新结点
函数返回值:
无
(11)撤消链表函数:
Destroy
函数格式:
voidDestroy(Polynh)
函数功能:
释放链表所占用的存储空间
函数参数:
Polynh-被撤消的链表的头指针
函数返回值:
无
(12)判链表非空函数:
PolynNotEmpty
函数格式:
intPolynNotEmpty(Polynh,char*p)
函数功能:
判断链表是否非空,即代表了一个真正的多项式。
函数参数:
Polynh-多项式链表的头指针
char*p-多项式名
函数返回值:
0—链表为空
1—链表不为空
(13)比较多项式两项关系函数:
ItemComp
函数格式:
intItemComp(ItemxItemy)
函数功能:
根据两个多项式项的指数判断它们的关系。
函数参数:
Itemx-表示多项式项的变量
Itemy-表示多项式项的变量
函数返回值:
-1—x项的指数小于y项的指数
0—x项的指数等于y项的指数
1—x项的指数大于y项的指数
五、部分算法描述
两个多项式相加运算的算法参见教科书的描述。
两个多项式相减运算算法与多项式相加运算的算法结构一致,只是把Q(x)多项式的结点作为独立的一项时,其系数应改变其正/负号。
这里只对两个多项式相乘运算的算法加以描述。
两个多项式相乘运算的基本原理是:
用Q(x)多项式的每一项分别去乘P(x)多项式的每一项,并将乘得得结果放入结果多项式中。
若结果多项式中有指数相同的项,则应把它们合并为一项。
这实际上是运用加法运算来实现乘法运算,实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。
【算法1】基本思想:
把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果(一个结点)插入到结果多项式中,若结果多项式中无相同指数的项,则生成一个新结点插入;若有相同指数的项,则系数相加。
算法如图1-3所示。
【算法2】基本思想:
把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式,然后把新多项式与结果多项式相加。
算法如图3所示。
七、思考题
修改一元多项式相加运算的函数,实现:
1、两个有序表合并为一个有序表。
2、假设具有整数值的集合用有序的线性链表表示,实现求两个集合的联合运算,要求结果集合中不能有两个值相同的元素。
八、部分函数代码
【说明】:
为了使学生掌握复杂程序设计的基本方法和程序的结构,下面给出了几乎所有的辅助函数的程序代码,学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。
希望学生通过下面程序代码的阅读、编码、测试和运算,掌握一个完整程序的基本结构和设计一个程序的基本方法。
#include
#include
#include
typedefstructItem{
doublecoef;
intexpn;
structItem*next;
}Item,*Polyn;
#defineCreateItem(p)p=(Item*)malloc(sizeof(Item));
#defineDeleteItem(p)free((void*)p);
/************************************************************/
/*判断选择函数*/
/************************************************************/
intSelect(char*str)
{charch;
printf("%s\n",str);
printf("InputYorN:
");
do{ch=getch();
}while(ch!
='Y'&&ch!
='y'&&ch!
='N'&&ch!
='n');
printf("\n");
if(ch=='Y'||ch=='y')return
(1);
elsereturn(0);
}
/************************************************************/
/*插入位置定位函数*/
/**************************************************************/
intInsertLocate(Polynh,intexpn,Item**p)
{Item*pre,*q;
pre=h;
q=h->next;
while(q&&q->expn {pre=q; q=q->next; } if(! q) {*p=pre; return (1); } elseif(q->expn==expn) {*p=q; return(0); } else {*p=pre; return(-1); } } /************************************************************/ /*插入结点函数*/ /************************************************************/ voidinsert(Item*pre,Item*p) { p->next=pre->next; pre->next=p; } /************************************************************/ /*输入多项式*/ /************************************************************/ PolynInput(void) { doublecoef; intexpn,flag; Item*h,*p,*q,*pp; CreateItem(h);//产生头结点 h->next=NULL; printf("inputcoefandexpn(ifend,expn=-1)\n"); while (1) { scanf("%lf%d",&coef,&expn);//输入多项式的系数和指数 if(expn==-1)break;//若指数为-1,表示输入结束 if(InsertLocate(h,expn,&pp))//返回值非0表示插入新结点 {CreateItem(p); p->coef=coef; p->expn=expn; insert(pp,p); } elseif(Select("hasthesameexpn,Replaceoldervalue? ")) pp->coef=coef;//指数相同,替换系数 } returnh; } /************************************************************/ /*撤消多项式*/ /************************************************************/ voidDestroy(Polynh) { Item*p=h,*q; while(p! =NULL) { q=p; p=p->next; DeleteItem(q); } } /************************************************************/ /*输出多项式*/ /************************************************************/ voidOutput(Polynh,char*title) { intflag=1; Item*p=h->next; printf("%s=",title); while(p) {if(flag)//表示是否是多项式的第一项 {flag=0; if(p->expn==0)printf("%.2lf",p->coef); elseprintf("%.2lfx^%d",p->coef,p->expn); } else {if(p->coef>0)printf("+"); if(p->expn==0)printf("%.2lf",p->coef); elseprintf("%.2lfx^%d",p->coef,p->expn); } p=p->next; } printf("\n"); } /************************************************************/ /*判断两个多项式项的关系*/ /************************************************************/ intItemComp(Itemx,Itemy) {if(x.expn return(-1); elseif(x.expn==y.expn) return(0); elsereturn (1); } /************************************************************/ /*两多项式多项式相加*/ /************************************************************/ PolynAddPolyn(Polynh1,Polynh2) { Item*head,*last,*pa=h1->next,*pb=h2->next,*s,*s0; doublecoef; CreateItem(head); last=head; last->next=NULL; returnhead; } /************************************************************/ /*两多项式多项式相减*/ /************************************************************/ PolynSubtractPolyn(Polynh1,Polynh2) {intflag; Item*head,*last,*pa=h1->next,*pb=h2->next,*s,*s0; doublecoef; CreateItem(head); last=head; last->next=NULL; returnhead; } /************************************************************/ /*两多项式多项式相乘*/ /************************************************************/ PolynMultPolyn(Polynh1,Polynh2)//两个多项式相乘 {intitem,expn; Item*head,*pa,*pb=h2->next,*s,*pp; doublecoef; CreateItem(head); head->next=NULL; returnhead; } /************************************************************/ /*菜单选择*/ /************************************************************/ intmenu(void) {intnum; clrscr(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 指导书