数据结构实验指导书

1、1数据结构实验指导书信息科学与技术学院刖百数据结构是软件开发的基础。数据结构课程是软件工程、计算机科学与技术、网络工程、 信息安全等专业的必修技术基础课程。该课程是在学生学习高级语言程序设计课程基础上， 使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用 数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法 设计与分析的能力。通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结 构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。既为学生 学习后继课程打好基础，也为将来软件开发提供理论指导。数据结构具有很强

2、的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内 涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。本数据结构实验选择了具有一定难度的实验项目10个，涉及到线性表、栈、队列、字符串、数据、二叉树、图、数据查找、数据排序等全部教学内容。学生不一定完成全部实验内容，根据课程的学分不同， 可以选择不同数目的实验。 一般而言，数据结根 a可以选择其中3个实验，数据结根b可以选择其中两个实验。鼓励学 生多做实验，如果学生所做实验数目超过规定数据，可以加分。本实验是以标准 c语言为背景，以微型计算机为主要机型，实验用编程语言采用 turboc 2.0, borland c 3.0 等以上

3、版本。为了使学生不仅掌握数据结构的一般原理，而且掌握具有一定实用性的程序的一般结构，实验指导书中给出了程序的总体框架和部分源程序代码，以及程序运行控制和交互式操作的 基本方式。通过程序总体框架，让学生学会如何组织程序。通过对程序要解决的问题按功能 进行分解，使学生逐步适应和学会运用抽象思维方式和模块化程序设计技术编写有一定规模、 具有一定实用性的程序的能力。编写数据结构实验指导书是对软件类课程的一个尝试。我们将通过学生在实验过程中的 反馈意见不断完善。15实验元稀疏多项式的计算一、实验目的通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性 链表表示线性表的存储结构和操

4、作的实现。二、实验内容实现一元稀疏多项式的如下运算：(1)两个一元稀疏多项式相加运算(2)两个一元稀疏多项式相减运算(3)两个一元稀疏多项式相乘运算三、实验原理1、一元多项式的逻辑表示一元多项式pn(x)可表示成：pn(x)=po+pix+p2x2+ , +pnxnn+1个系数可用线性表来表示：po, pi, p2,，pn)其中每一项的指数i隐含在其系数pi的序号中。一个一元多项式，如果其系数不为0的项相对于其多项式的次数(最大指数)而言要少得多，则称该一元多项式为一元稀疏多项式。对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪

5、费运算时间。如：s(x)=1+3x 10000+2x20000采用顺序存储分配需 20001个元素空间，但只有 3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1-1所示。图1-1 : 一元稀疏多项式的链表表示示意图2、一元稀疏多项式的链式存储表示结点结构定义如下：typedef struct itemdouble coef;int expn;struct item *next; item,*polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式 a和b,其运算原理如下：(1)两个多项式相加(c=a + b

6、)的运算原则：指数相同，系数相加，若不为 0,则在结果多项式中构成一新项。指数不同，则两项分别抄入结果多项式中。(2)两个多项式相减(c=a b)的运算原则：指数相同，系数相减，若不为 0,则构成一新项。指数不同，对 a多项式的项，直接抄入结果多项式中。对b多项式的项，系数符号变换后，再将放入结果多项式中(3)两个多项式相乘(c=axb)的运算原则用b多项式的每一项分别去乘 a多项式的每一项，并将乘得得结果放入结果 多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。四、实现1、约定使用带头结点的链表表示一元稀疏多项式。(2)用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。

7、(3)每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏， 加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行 表不。(4)每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入a多项式，而a多项式已经存在，这时通过“确认”后再确定是否真正需要输入。2、基本功能(1)多项式的输入(2)两个一元稀疏多项式相加运算：p(x)+q(x(3)两个一元稀疏多项式相减运算：p(x) q(x)(4)两个一元稀疏多项式相乘运算：p(x) x q(x)(5)多项式打印3、辅助功能(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互

8、式控 制程序运行。(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否 进行。(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。(6)判多项式非空：判断某个多项式是否存在。(7)判断两个多项式的当前运算项的关系(指数大于，等于，小于)4、程序结构本程序可以由13个函数组成，其中主函数 1个，基本功能函数 5个，辅助功能函数个。函数间的调用关系图1-2所示。5、程序函数(1)主函数：main功能：

9、通过菜单选择控制对系统功能的操作(2)菜单选择函数：menu函数格式：int menu(void)函数功能：构造功能菜单，并选择下一步要操作的功能。函数参数：无参数。函数返回值：111中的一个序号。可供选择的功能如下:1-create p(x) 2-create q(x) 3-p(x)+q(x) 4-p(x)-q(x) 5-p(x)*q(x) 6-print p(x) 7-print q(x) 8-print p(x)+q(x) 9-print p(x)-q(x) 10-print p(x)*q(x) 11-quit表不生成p多项式表示生成q多项式表小两多项式相加表示两多项式相减表小两多项式相

10、乘表示才t印p多项式表示打印q多项式表示打印两多项式相加的结果表示打印两多项式相减的结果表示打印两多项式相乘的结果表示退出系统，结束程序的运行3,在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。如输入 表不执行p(x)+(x)额运算。输入多项式函数：input函数格式：polyn input(void)函数参数：无参数函数功能：输入多项式各项的系数和指数，生成一个多项式链表。函数返回值：指向一个多项式链表的头指针两多项式相加函数：addpolyn函数格式 polyn addpolyn(polyn h1,polyn h2)函数功能：实现两个多项式h1和h2相加。函数参数：polyn

11、h1 一指向第一个多项式链表的头指针polyn h2一指向第二个多项式链表的头指针函数返回值：指向相加后的结果链表的头指针(5)两多项式相减函数：subtractpolyn函数格式 polyn subtractpolyn(polyn h1,polyn h2)函数功能：实现两个多项式h1和h2相减。函数参数：polyn h1 一指向第一个多项式链表的头指针polyn h2一指向第二个多项式链表的头指针函数返回值：指向相减后的结果链表的头指针(6)两多项式相乘函数：multpolyn函数格式 polyn multpolyn(polyn h1,polyn h2)函数功能：实现两个多项式h1和h2相乘

12、。函数参数：polyn h1 一指向第一个多项式链表的头指针polyn h2一指向第二个多项式链表的头指针函数返回值：指向相乘后的结果链表的头指针(7)显示多项式函数：output函数格式：void output(polyn h,char *title)函数功能：输出多项式的完整表示。如：p(x)=1.00+2.50xa3-3.5xa9函数参数：polyn h 要输出的多项式链表的头指针char *title 字符串，提示要输出一个什么样的多项式，如“p(x)”。函数返回值：无返回值。(8)判断选择函数：select函数格式：int select(char *str)函数功能：根据str提示的

13、内容判断是执行指定的操作，还是不执行。输入“y”则表示执行，若输入“ n”表示不执行。如当p(x)多项式已经产生后，若 再选择产生p(x),这是提示：p(x) is not empty,create p(x) again?input y or n:若输入“ y”则表示重新产生多项式p(x),若输入“ n”表示维持原多项式不变。函数参数：char *str 将要确定的内容。函数返回值：1 表示执行指定的操作0-表示不执行指定的操作(9)插入位置定位函数：insertlocate函数格式：int insertlocate(polyn h,int expn,item *p)函数功能：确定新结点的插入

14、位置。其插入位置的确定是保证多项式链表按指 数递增排列的关键。函数参数：polyn h要查找的多项式链表的头指针 int expn 一新插入项的指数值。item *p 插入位置的前驱结点指针，由该函数的调用而被确定的内 容。新结点一定插入到该结点的后面。函数返回值：-1若指数expn值在某两个结点之间，则返回一1,参数p带回的值为指数值小于expn的结点指针。0若指数expn值等于某结点的指数值，则返回 0,参数p带回 的值为指数值等于expn的结点指针。1-若指数expn值大于最后一个结点的指数值，则返回1,参数p带回最后一个结点的指针(10)结点插入函数：insert函数格式： void

15、insert(item *pre,item *p)函数功能：在指定结点pre后插入一个新结点 p。函数参数：item *pre 被插入结点的前驱结点item *p 一要插入的新结点函数返回值：无(11)撤消链表函数：destroy函数格式：void destroy(polyn h)函数功能：释放链表所占用的存储空间函数参数：polyn h -被撤消的链表的头指针 函数返回值：无(12)判链表非空函数：polynnotempty函数格式：int polynnotempty(polyn h,char *p)函数功能：判断链表是否非空，即代表了一个真正的多项式。函数参数：polyn h 一多项式链表

16、的头指针char *p 多项式名函数返回值：0链表为空1一链表不为空(13)比较多项式两项关系函数：itemcomp函数格式：int itemcomp(item x item y)函数功能：根据两个多项式项的指数判断它们的关系。函数参数：item x表示多项式项的变量item y 表示多项式项的变量函数返回值：-1 -x项的指数小于y项的指数0x项的指数等于y项的指数1x项的指数大于y项的指数五、部分算法描述两个多项式相加运算的算法参见教科书的描述。两个多项式相减运算算法与多项式相加运算的算法结构一致，只是把q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。这里只对两个多项式相乘运

17、算的算法加以描述。两个多项式相乘运算的基本原理是：用q(x)多项式的每一项分别去乘p(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘 法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。【算法1】基本思想：把 q(x)多项式的每一项分别去乘p(x)多项式的每一项所得到的每一个结果(一个结点)插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如图1-3所示。图1-3两个多项式相乘算法 1描述【算法2】基本思想：把q(x)多项式的每一项

18、分别去乘 p(x)多项式得到一个新的多项式,然后把新多项式与结果多项式相加。算法如图3所示。图1-4两个多项式相乘算法2描述七、思考题修改一元多项式相加运算的函数，实现：1、两个有序表合并为一个有序表。2、假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求 结果集合中不能有两个值相同的元素。八、部分函数代码【说明】：为了使学生掌握复杂程序设计的基本方法和程序的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设 计一个程序的基本方法。#in

19、clude #include #include inttypedef struct item double coef;expn;struct item *next;item,*polyn;#define createitem(p) p=(item *)malloc(sizeof(item);#define deleteitem(p) free(void *)p);/*/*判断选择函数*/*/ int select(char *str) char ch;printf(%sn,str);printf(input y or n:);do ch=getch();while(ch!=y&ch!=y&ch

20、!=n&ch!=n);printf(n);if(ch=y|ch=y) return(1);else return(0);/*/*插入位置定位函数*/*/int insertlocate(polyn h,int expn,item *p) item *pre,*q;pre=h;q=h-next;while(q&q-expnnext;if(!q) *p=pre； return(1);else if(q-expn=expn)*p=q;return(0);else *p=pre;return(-1);/*/*插入结点函数*/*/ void insert(item *pre,item *p)p-next

21、=pre-next;pre-next=p;/*/*输入多项式*/*/polyn input(void) double coef;intexpn,flag;item *h,*p,*q,*pp;createitem(h);/ 产生头结点h-next=null;printf(input coef and expn(if end ,expn=-1)n);while(1)scanf(%lf%d,&coef,&expn); / 输入多项式的系数和指数if(expn=-1) break;若指数为1,表示输入结束if(insertlocate(h,expn,&pp)/返回值非0表示插入新结点 createit

22、em(p);p-coef=coef;p-expn=expn;insert(pp,p);else if(select(has the same expn,replace older value?) pp-coef=coef;指数相同，替换系数return h;/*/*撤消多项式*/*/ void destroy(polyn h) item *p=h,*q;while(p!=null)q=p;p=p-next;deleteltem(q);/*/*输出多项式*/*/void output(polyn h,char *title)int flag=1;item *p=h-next;printf(%s=

23、,title);while(p) if(flag)表示是否是多项式的第一项 flag=0;if(p-expn=0) printf(%.2lf,p-coef);else printf(%.2lfxa%d,p-coef,p-expn);else if(p-coef0) printf(+);if(p-expn=0) printf(%.2lf,p-coef);else printf(%.2lfxa%d,p-coef,p-expn);p=p-next;printf(n);/*/*判断两个多项式项的关系*/*/int itemcomp(item x,item y) if(x.expnnext,*pb=h2

24、-next,*s,*s0;double coef;createltem(head);last=head;实现两个多项式相加运算的代码(由学生独立完成)last-next=null;return head;/*/*两多项式多项式相减*/*/polyn subtractpolyn(polyn h1,polyn h2) int flag;item *head,*last,*pa=h1-next,*pb=h2-next,*s,*s0;double coef;createitem(head);last=head;实现两个多项式相减运算的代码(由学生独立完成)last-next=null;return h

25、ead;/*/*两多项式多项式相乘*/*/polyn multpolyn(polyn h1,polyn h2)两个多项式相乘 int item,expn;item *head,*pa,*pb=h2-next,*s,*pp;double coef;createitem(head);head-next=null;实现两个多项式相乘运算的代码（由学生独立完成）return head;/*/*菜单选择*/*/ int menu(void) int num;clrscr();printf(%20c1-create p(x)n,);printf(%20c2-create q(x)n,);printf(%2

26、0c3-p(x)+q(x)n,);printf(%20c4-p(x)-q(x)n,);printf(%20c5-p(x)*q(x)n,);printf(%20c6-print p(x)n,);printf(%20c7-print q(x)n,);printf(%20c8-print p(x)+q(x)n,);printf(%20c9-print p(x)-q(x)n,);printf(%20c10-print p(x)*q(x)n,);printf(%20c11-quitn,);printf(doplease select 1,2,3,4,5,6,7,8,9,10,11:);scanf(%d,

27、&num);while(num11);return(num);/*/*判断多项式是否存在*/*/ int polynnotempty(polyn h,char *p) if(h=null) printf(%s is not exist!n,p);getchar();return(0);else return(1);/*/*主函数*/*/ void main() int num;polyn h1=null;/p(x)polyn h2=null; /q(x)49polyn h3=null; p(x)+q(x)polyn h4=null; p(x)-q(x)polyn h5=null; p(x)*q

28、(x)while(1) num=menu();getchar();switch(num)case 1: 输入第一个多项式，若多项式存在，首先撤消然后再输入 if(h1!=null) if(select(p(x) is not empty,create p(x) again?) destroy(h1);h1=input();else h1=input();break;case 2: 输入第二个多项式，若多项式存在，首先撤消然后再输入 if(h2!=null) if(select(q(x) is not empty,create q(x) again?) destroy(h2);h2=input(

29、);else h2=input();break;case 3: 两多项式相加if(polynnotempty(h1,p(x)&polynnotempty(h2,q(x)”)h3=addpolyn(h1,h2);output(h3,p(x)+q(x);printf(p(x)+q(x) has finished!n);getchar();break;case 4: 两多项式相减if(polynnotempty(h1,p(x)&polynnotempty(h2,q(x)”) h4=subtractpolyn(h1,h2);output(h4,px)-q(x);printf(p(x)-q(x) has

30、 finished!n);getchar();break;case 5: 两多项式相乘if(polynnotempty(h1,p(x)&polynnotempty(h2,q(x)”) h5=multpolyn(h1,h2);output(h5,p(x)*q(x);printf(p(x)*q(x) has finished!n);getchar();break;case 6: 显示第一个多项式if(polynnotempty(h1,p(x) output(h1,p(x);getchar();break;case 7: 显示第二个多项式if(polynnotempty(h2,q(x)”) outp

31、ut(h2,q(x);getchar();break;case 8: 显示相加结果多项式if(polynnotempty(h3,p(x)+q(x)”) output(h3,p(x)+q(x);getchar();break;case 9: 显示相减结果多项式if(polynnotempty(h4,p(x)-q(x) output(h4,p(x)-q(x);getchar();break;case 10: /显示相乘结果多项式if(polynnotempty(h5,p(x)*q(x) output(h5,p(x)*q(x);getchar();break;case 11: /2吉束程序运行。结束

32、前应先撤消已存在的多项式if(h1!=null) destroy(h1);if(h2!=null) destroy(h2);if(h3!=null) destroy(h3);if(h4!=null) destroy(h4);if(h4!=null) destroy(h4);if(h4!=null) destroy(h5);if(num=11) break;getch()；实验三算术表达式求值一、实验目的帮助学生熟练掌握栈的基本操作，并通过用算符优先法对表达式求值的过程深刻领会用 栈解决实际问题的基本方法。二、实验内容编写程序实现从键盘终端输入语法正确的算术表达式，计算出表达式的值。为了避免算符

33、的二义性，可以假设表达式中只包含实型正常数运算符包括加、减、乘、除四种基本运算，可以包含圆括号。三、实验原理1、算术四则运算法则先乘除后加减从左至右先括号内后括号外2、方法对运算符建立优先关系矩阵，按优先关系对表达式进行处理。算符：运算符和界符。根据法则1：对于两个相邻运算符，乘除优先于加减。根据法则2:乘除优先级相同，加减优先级相同。相邻两个同级运算符左优先。根据法则3: “(”前面的运算符优先级低于“(”的优先级。“(”的优先级低于右 边相邻算符。“)”左边的算符高于“)”的优先级。由于“(”和“)”必须成对出现，令它们的优先性相同。为了处理的方便，假设表达式以开始和结束，输入表达式的一般

34、形式为：#表达式#如：#5.3+4.2*(7.6+4.5)#规定开始的“犷的优先性低于所有其它算符，所有其它算符的优先性高于结束的根据假设，表达式开始的“#”和结束的“ #”必须成对出现，所以也令它们的优先性相同。对于一个正确的表达式，“)”不可能与“(”相邻，“(”不可能与结束的“ #相邻，开 始的“ #不可能与“)”相邻，它们之间没有优先性，程序应具有这种判断能力。根据上面的讨论，可用表4-1所示的算符优先关系矩阵来描述算符之间的优先关系，其中，用“”表示表达式中前一个算符的优先性高于后一个算符的优先性，用“-*/(#=0 & strpp=0 & strpp=0 & strpp=0 & strpp=9) /处理实数的小数部分 number=number+(strpp-48)/temp;temp=temp*10;pp+; 六、思考题1、若表达式中的数据带有正负号的实数字符串该怎样进行转换