计算机软件基础实验_实验一.doc

《计算机软件基础实验_实验一.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.实验目的：掌握线性链表的存储、运算及应用。利用链表实现一元多项式计算。2.实验内容:1)编写函数，实现用链表结构建立多项式；2)编写函数，实现多项式的加法运算；3)编写函数，实现多项式的显示；4)测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检杳程序的执行结果。选做内容：修改程序，选择实现以下功能:5)多项式输入：修改主函数，从终端输入多项式的系数和指数，并构建出多项式链表。6)多项式求值：编写一个函数，根据给定的x值计算并返冋多项式f(x)的值。测试该函数(从终端

2、输入一个x的值，调用该函数并显示返冋结果)。7)多项式相减：编写一个函数，求两个多项式相减的多项式。8)多项式相乘：编写一个函数，求两个多项式的乘积多项式。3.算法说明：1)多项式的建立、输岀和相加算法见教材和讲义。2)多项式减法：同次项的系数相减(缺项的系数是0)。例如a(x)=3+2x-5x2,b(x)=3x~4x‘，贝I」a(x)-b(x)=3-x-5x2+4x提示：a(x)-b(x)=a(x)+(-b(x))o3)多项式乘法：两个多项式的相乘是"系数和乘，指数相加”。算法思想是用一个多项式中的各项分别与另一个多项式和

3、乘，形成多个多项式，再将它们累加在—起。例如,a(x)=3+2x-5x2,b(x)=3x-4x',则a(x)*b(x)=(3x)*(3+2x-5x2)+(-4x3)*(3+2x-5x2)=(9x+6x2-15x3)+(-12x3-8x4+20x5)=9x+6x2-27x3-8x4+20x5o4・实验过程线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能止确反映元素的逻辑顺序，就必须在存储每个元素ai的同时

4、，存储其直接后继元素的存储位置。这时，存放数据元素的结点至少包括两个域，一个域存放该元索的数抑，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指针域或链域(next)。这种链式分配的存储结构称为链表。数据元素的结点结构如下：datanext此结构的C语言描述为structnode{intdata;structnode*next;typedefstructnodeNODE;耍对单链表进行操作，首先耍掌握怎样建立单链表。链表是一种动态存储结构，所需的存储空间只有在程序执行mallocZ后，才可能申请到一个可用结

5、点空间;free(p)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即吋生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。动态建立线性表的链式存储结构有两种基本方法，分别适用于不同的场合。可根据所建链表结点的顺序耍求选择采用一种方法。单链表建立方法一：反向建立链表。思想：若线性表的元素已顺序存放在一维数组A[N]中，建表方法是从线性表的最后

6、一个元素开始，从后向前依次插入到当前链表的第一个结点Z前。^defineNm/*m为链表中数据元索的个数*/intA[N];NODE*creatlinkl(){NODE*head,*s;inti;head=(NODE*)malloc(sizeof(NODE));head->next二NULL;for(i=N?l;i>二0;i-?){s=(NODE*)malloc(sizeof(NODE));s->data=A[i];s->next二head->next;head->next二s;returnhead;单链表建立方法二：正向建立

7、单链表。思想：依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点Z后。NODE*creatlink2()NODE*head,*p,*s;intnum;head=(NODE*)malloc(sizeof(NODE));seanf(''%d，',&num);p二head;while(num!=0)s二(NODE*)malloc(sizeof(NODE));s->data二num;p->next二s;P=s;scanf(〃%d〃，&num);}p->next二NULL;returnhead;}具休实例的题面：设有多

8、项式：A(x)=7+3x+9x8+3x15B(x)=5x+6x7-9x8(1)用单链表给出A(x)的存储表示；(2)用单链表给出B(x)的存储表示；(3)以上述两个单链表为基础，通过插入和删除等运算给出A(x)+B(x)的存储农示,其存餡空间覆盖A(x)和B(x)的存储空间解